Advanced Methods of Numerical Linear Algebra

Garant předmětu:

Lecturer:

Tutor:

Supervisor:

Department of Mathematics

Synopsis:

Representation of real numbers in computers, behaviour of rounding errors during numerical computations, sensitivity of a problem, numerical stability of an algorithm. We will analyse sensitivity of the eigenvalues of a given matrix and sensitivity of roots of systems of linear algebraic equations. Then, the backward analysis of these problems will be performed. The second part of the course is devoted to the methods of QR-decomposition, least squares problem, and to several modern Krylov subspace methods for the solution of systems of linear algebraic equations and the Lanczos method for approximation of the eigenvalues of a symmetric square matrix.

Requirements:

Basic course of Calculus, Linear Algebra and Ordinary Differential Equations (in the extent of the courses 01MA1, 01MAA2-4, 01LA1, 01LAA2, 01NM held at the FNSPE CTU in Prague).

Syllabus of lectures:

1. Introduction, basic terminology, representation of numbers in computers

2. Standard arithmetics IEEE, behaviour of rounding errors in computations in finite precision arithmetics, forward and backward analysis

3. Similarity transforms, Schur's theorem, measurement of the distances between spectra of two matrices

4. Theorem on sensitivity of the spectra of general matrices

5. Sensitivity of eigenvalues of diagonalizable and normal matrices, backward analysis of the eigenvalue problem

6. Sensitivity of roots of systems of linear algebraic equations, backward analysis of the solutions to the systems of algebraic equations

7. QR-decompositions and orthogonal transformations

8. Householder transform

9. Gramm-Schmidt orthogonalization process

10. Krylov space methods - introduction, Arnoldi's algorithm, method of generalized minimal residual (GMRES) for solution of systems of linear algebraic equations

11. Lanczos algorithm, approximation of eigenvalues of a symmetric matrix

12. Overview of the Krylov space methods for solution of systems of linear algebraic equations

13. Preconditioning of the iterative methods, examples of simple preconditioners

Syllabus of tutorials:

Study Objective:

Floating point arithmetics, rounding errors in the finite precision arithmetics, backward analysis and its application to estimation of the approximation error, sensitivity and backward analysis of matrix spectra and solution of systems of the linear algebraic equations, methods for QR decomposition, Arnoldi algorithm, basic Krylov subspace methods for solution of systems of linear algebraic equations (GMRES, CG, MinRes, BiCG, QMR), and the Lanczos method for approximation of eigenvalues of a symmetric matrix.

Skills: To choose a suitable method for solution of a system of linear algebraic equations or evaluation of a spectrum of a given matrix and to estimate error of the obtained approximation.

Study materials:

Key references:

[1] D. S. Watkins: Fundamentals of Matrix Computations, J. Willey, New York, 1991

Recommended references:

[2] B. N. Parlett: Symmetric Eigenvalue Problem, Prentice Hall, Engl. Cliffs, 1988

[3] G. H. Golub, C. F. van Loan: Matrix Computations, John Hopkins, 1997.

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans:

• Matematické inženýrství (compulsory course of the specialization)
• Aplikace softwarového inženýrství (elective course)