|
|
|||||||||||||||||
Course Catalog 2011-2012
MAT-31107 Numerical Analysis, 4 cr |
Additional information
In the tutorial sessions you solve problems, do computer exercises on your own laptop, and write snap quizzes. There are no lectures in English, you are expected to self-study material from the textbook.
Suitable for postgraduate studies
Person responsible
Robert Piche
Lessons
| Study type | P1 | P2 | P3 | P4 | Summer | Implementations | Lecture times and places |
|
|
|
|
|
|
|
|
|
Requirements
Exam and weekly quizzes
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, 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/Octave | decoding IEEE numbers |
| 2. | root-finding algorithms (bisection, Newton-Raphson, secant): derivation, advantages, disadvantages; convergence test for single-variable fixed-point iteration; stopping criteria | multiple roots; Brent's method; cobweb diagram; quadratic convergence of Newton-Raphson; computing square roots; attainable accuracy; solving equations using Matlab/Octave | proof of convergence of fixed-point algorithm; Illinois method; convergence of Newton-Raphson to multiple root; attainable accuracy of multiple root; chaotic iterations |
| 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; truncation error and stability of cubic Hermite polynomial; interpolation of data using Matlab/Octave | 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/Octave | 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/Octave | 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 | uniqueness of IVP solution; proof of local truncation error of Heun's method; solving IVP's with Matlab/Octave |
Evaluation criteria for the course
Exam. Bonus points (up to 20%) can be earned by participating in quizzes during the tutorial sessions.
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 |
|
|
|
More precise information per implementation
| Implementation | Description | Methods of instruction | Implementation |
| Teaching: 32 h lectures (in Finnish (partly in English), slides in English, non-mandatory), 16 h exercises (in English, non-mandatory). The contents and requirements are the same as in the previous implementation of MAT-31107 in Spring 2012. Please, visit the course web page: http://www.math.tut.fi/~piche/numa/index.html |