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).
Grading Policy
homework - 60%
midterm exam - 15%
final exam - 25%
Final Exam Date:
as scheduled