|
|
|||||||||||||||||
Course Catalog 2010-2011
MAT-31107 Numerical Analysis, 4 cr |
Person responsible
Robert Piche
Lessons
| Study type | P1 | P2 | P3 | P4 | Summer | Implementations | Lecture times and places |
|
|
|
|
|
|
|
|
Requirements
Exam
Completion parts must belong to the same implementation
Learning outcomes
Numerical analysis is the design and study of algorithms (usually implemented as computer programs) to solve mathematical problems that involve real and complex numbers: solving equations, approximating functions, calculating integrals, solving differential equations, etc. The theory deals with questions such as the accuracy of approximation, the rate of convergence, and the computational complexity of algorithms. A solid understanding of this theory is essential for the effective use of existing computer codes and for the development of new ones. After studying this course, the student is able to describe the derivation of standard algorithms and can use them to solve simple mathematical problems with a non-programmable calculator. He/she can demonstrate his/her understanding of theory by estimating the error of a given approximation formula, deriving new variants of algorithms, explaining results that are produced by computer programs, determining the convergence or accuracy of a given algorithm, and comparing the strengths and weaknesses of different algorithms for a certain kind of problem.
Content
| Content | Core content | Complementary knowledge | Specialist knowledge |
| 1. | sources of error; descriptions of approximation: absolute error, relative error, bounding error, correct decimals, significant digits; error propagation in arithmetic, in univariate functions, and in multivariate functions; cancellation and its mitigation via algebraic reformulation or series approximation; floating point concepts: base, mantissa, exponent, IEEE single and double, spacing, machine epsilon, unit roundoff, arithmetic model; forward error analysis of simple expressions | round to nearest even; additional error caused by rounding; derivation of error propagation formulas; roots of quadratic polynomial; special floating point numbers (0, inf, NaN, subnormal); forward and backward error of summation; roundoff in Matlab | decoding IEEE numbers |
| 2. | root-finding algorithms (bisection, Newton-Raphson, secant): derivation, advantages, disadvantages; convergence test for single-variable fixed-point iteration; stopping criteria; Horner's algorithm for p and p'; sensitivity of polynomial roots; Newton-Raphson method for multivariate problem | multiple roots; Brent's method; cobweb diagram; quadratic convergence of Newton-Raphson; computing square roots; attainable accuracy; root deflation; convergence test for multivariate fixed-point iteration; solving equations using Matlab | proof of convergence of fixed-point algorithm; convergence of Newton-Raphson to multiple root; attainable accuracy of multiple root; chaotic iterations; companion matrix; 3 iterations suffice to compute square root |
| 3. | polynomial interpolation: definition, uniqueness, existence; Newton polynomial using divided difference tables; stability of linear interpolation; Runge's example; derivation of cubic Hermite interpolation | proof of uniqueness and existence; proof of error formula; Neville's method; interpolation with Matlab; truncation error and stability of cubic Hermite polynomial; interpolation of data using Matlab | uniform convergence of sine function interpolation; derivation of Newton polynomial; divided difference properties; derivation of Hermite error formula |
| 4. | numerical integration: Newton-Cotes formula derivations using interpolation and using undetermined coefficients; truncation error of trapezoid rule and Simpson's rule; composite rules: trapezoid, Simpson's; Romberg formula; adaptive quadrature; dealing with singularities and infinite intervals: change of variables, series approximation | proof of accuracy of Simpson's rule; error estimate for "cutting off the tail"; recursive composite trapezoid rule; equivalence of first 3 columns of Romberg to Newton-Cotes; calculation of integrals with Matlab | Euler-Maclaurin summation formula |
| 5. | least squares approximation theory: weighted euclidean norm and scalar product for vectors and continuous functions, orthogonality theorem, normal equations; orthogonal polynomial construction using undetermined coefficients, best-approximation, and 3-term recurrence | uniqueness of least squares approximation; repeated abscissas; least-squares approximation of data using Matlab | Clenshaw's algorithm |
| 6. | ordinary differential equation initial value problems (IVP): conversion to standard form; Euler method derivation, use, local truncation error; Heun and Runge-Kutta methods formula and accuracy; adaptive solution; stability test; stiff problems; trapezoidal method | uniqueness of IVP solution; proof of local truncation error of Heun's method; solving IVP's with Matlab |
Evaluation criteria for the course
Exam. Bonus points (up to 20%) can be earned by active participation in PC labs and in weekly exercises.
Assessment scale:
Numerical evaluation scale (1-5) will be used on the course
Partial passing:
Study material
| Type | Name | Author | ISBN | URL | Edition, availability, ... | Examination material | Language |
| Book | Introduction to Numerical Computation | Lars Eldén et al. | English |
Prerequisite relations (Requires logging in to POP)
Correspondence of content
| Course | Corresponds course | Description |
|
|
|
Additional information
Suitable for postgraduate studies
More precise information per implementation
| Implementation | Description | Methods of instruction | Implementation |