Math 571 - Numerical Methods for Scientific Computing I - Fall 1998

Numerical Linear Algebra

Instructor: Robert Krasny, 2842 East Hall, 763-3505, krasny@math.lsa.umich.edu

Time and Location: MWF, 9-10am, 2866 East Hall

This course is an introduction to numerical methods for linear algebra. Three types of problems are considered: solving a linear system of equations (Ax=b), computing the eigenvalues and eigenvectors of a matrix (Ax=\lambda x), and least squares problems (min_x ||Ax-b||_2). These problems arise in many scientific applications and much effort has gone into developing effective solution algorithms. Standard mathematical expressions for the solution (e.g. x=A^{-1}b) and naive implementations (e.g. Gaussian elimination) may fail in practice either because the operation count is prohibitive or because computer roundoff error ruins the answer. The challenge for the numerical analyst lies in deriving alternative expressions which lead to practical algorithms. This may involve exploiting a special property of the matrix (e.g. positive definite) or a radical approach (e.g. QR algorithm for computing eigenvalues).

In this class, we shall study some of the main algorithms in use today for linear algebra. For example, we shall see how the singular value decomposition of a matrix leads to an algorithm for image compression. Two important issues we shall discuss are the efficiency and stability of an algorithm. In addition, for the case of approximate iterative methods, we shall also discuss the rate of convergence. We shall study the rigorous derivation of each algorithm, as well as practical implementation issues. Applications and examples will be provided throughout.

Syllabus
1. Background: vector and matrix norms, reduction to normal form, condition number, finite precision arithmetic, backward error analysis, projectors, reflectors
2. Linear systems: Gaussian elimination, LU factorization, pivoting, Cholesky factorization, Krylov methods, Arnoldi iteration, GMRES, conjugate gradient method, preconditioning, finite-difference schemes for a two-point boundary value problem, Dirichlet problem for the Laplace equation
3. Eigenvalues and eigenvectors: perturbation theory (Bauer-Fike theorem), Schur factorization, reduction to Hessenberg and tridiagonal form, power method, inverse iteration, shifts, Rayleigh quotient iteration, QR algorithm
4. Least squares problems: normal equations, Gram-Schmidt orthogonalization, QR factorization, singular value decomposition
5. Time permitting: FFT, multigrid

Text: Applied Numerical Linear Algebra, J. Demmel, SIAM

Prerequisites
1. A course in linear algebra.
2. Computer programming (Matlab is recommended).