Math 571 - Numerical Methods for Scientific Computing I - Fall 1998
Numerical Linear Algebra
2842 East Hall,
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),
least squares problems
These problems arise in many scientific applications
much effort has gone into developing effective solution algorithms.
Standard mathematical expressions for the solution
(e.g. Gaussian elimination)
may fail in practice
because the operation count is prohibitive
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.
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.
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.
vector and matrix norms,
reduction to normal form,
finite precision arithmetic,
backward error analysis,
2. Linear systems:
conjugate gradient method,
finite-difference schemes for a two-point boundary value problem,
Dirichlet problem for the Laplace equation
3. Eigenvalues and eigenvectors:
reduction to Hessenberg and tridiagonal form,
Rayleigh quotient iteration,
4. Least squares problems:
singular value decomposition
5. Time permitting:
Applied Numerical Linear Algebra,
J. Demmel, SIAM
1. A course in linear algebra.
2. Computer programming (Matlab is recommended).
homework - 60%
midterm exam - 15%
final exam - 25%
Final Exam Date: