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.

1.

2.

3.

4.

5.

1. A course in linear algebra.

2. Computer programming (Matlab is recommended).

homework - 60%

midterm exam - 15%

final exam - 25%