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:

Syllabus of lectures:

Outline:

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 transformations, Schur's theorem, measurement of distances between spectra of two matrices

4. Theorem on sensitivity of 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:

Study materials:

Key references:

[1] J. Liesen, Z. Strakoš, Krylov Subspace Methods, Principles and Analysis, Oxford University Press, 2013

[2] M.A. Olshanskii, E.E. Tyrtyshnikov: Iterative Methods for Linear Systems, Theory and Applications, SIAM 2014.

[3] J. Drkošová, Z. Strakoš: Úvod do teorie citlivosti a stability v numerické lineární algebře, skripta ČVUT Praha,

1997.

Recommended references:

[4] D.S. Watkins: The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM 2007.

[5] H. van der Vorst: Iterative Krylov Methods for Large Linear Systems, Cambridge University Press, 2003.

[6] Y. Saad: Numerical Methods for Large Eigenvalue Problems, SIAM 2011.

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans:

• Aplikovaná algebra a analýza (elective course)
• Aplikace informatiky v přírodních vědách (elective course)
• Matematické inženýrství (compulsory course in the program)
• Matematická informatika (elective course)