Advanced Methods of Numerical Linear Algebra
Code  Completion  Credits  Range  Language 

01PNLA  ZK  3  2+0  Czech 
 Course guarantor:
 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 QRdecomposition, 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, 01MAA24, 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. QRdecompositions and orthogonal transformations
8. Householder transform
9. GrammSchmidt 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 timetable has been prepared for this course
 The course is a part of the following study plans: