Numerical Linear Algebra

All the topics of this exam are covered in the undergraduate course MATE 4061, Introduction to Numerical Analysis and the graduate course MATE 6025, Numerical Linear Algebra. Elementary topics of Linear Algebra are covered in the advanced undergraduate course MATE 5150, Linear Algebra.

Topics:

• Floating point numbers: representation of real numbers in finite precision, finite precision arithmetic, error bounds, backward and forward error analysis.
• Linear algebra: real and complex vector spaces, families of linear independent vectors, basis, dimension of a vector space. Emphasis will be given to finite dimensional vector spaces.
• Linear operators: definition, matrix representation, definition of the kernel and rank of a linear operator, Fundamental Theorem of Linear Algebra.
• Eigenvalues and eigenvectors: spectrum of a linear operator, spectral radius, invariant spaces, diagonalizable matrices, Jordan decomposition Theorem (a proof of the Jordan Theorem is not required however the student should know how to apply it).
• Normed spaces: vector and matrix norms, matrix norms induced by vector norms, equivalent norms in finite dimensional vector spaces. Convergence of sequences and series in normed spaces, Cauchy sequences, complete normed spaces.
• Inner products: norm induced by inner products, Cauchy-Schwarz inequality, orthogonality, adjoint operator, orthogonal projection, norms induced by inner products, Gram-Schmidt orthogonalization process, Givens rotations, Househölder orthogonalization, QR factorization, least squares problem.
• Direct methods for solving dense linear systems: Gaussian elimination and its variants, LU and LUP factorization. Cholesky factorization.
• Iterative methods for solving sparse linear systems: analysis of convergence of Richardson, Jacobi, Gauss-Seidel, SOR, SSOR, Steepest descent, Conjugate Gradient, GMRES, QMR, BICG, BICG-Stab methods; Preconditioning techniques, computational aspects.
• Singular values: definition and decomposition of a matrix in singular values (SVD).
• Approximation of eigenvalues and eigenvectors: power method, Givens-Householder and QR, computational aspects.

Bibliography:

• Matrix Analysis, R. A. Horn and C.R. Johnson, Cambridge University Press, 1992.
• Applied Numerical Linear Algebra, J.W. Demmel, SIAM, 1997
• Introduction to matrix computations, G.W. Stewart, Academic Press, 1973.
• Matrix Computations, G.H. Golub and C.F. Van Loan, third edition, John Hopkins University Press.
• The symmetric eigenvalue problem, B.N. Parlett, Prentice Hall, Englewood Cliffs, 1980.
• Iterative solution methods, O. Axelsson, Cambridge University Press.
• Iterative methods for large sparse linear systems, Y. Saad, PWS Publishing Company, 1996.
Previous exams:

Spring-2007