Numerical linear algebra: direct and iterative methods [SMATM103]

Learning outcomes

This course covers the main numerical tools to solve systems of linear equations and eigenvalue problems.

Objectives

This course aims to familiarize students with the numerical resolution of systems of linear equations and eigenvalue problems by direct or iterative methods, but also to familiarize them with the mathematical approach used to establish algorithms of numerical resolution of systems of linear equations and eigenvalue problems and to develop the critical thinking linked to this approach (structure exploitation, error analysis of an algorithm in finite precision, efficiency criteria of an algorithm, etc.).

Content

For the resolution of systems of linear equations, this course is based on the first five chapters as well as the eleventh chapter of the book ``Matrix Computation'' (fourth edition), written by Gene H. Golub and Charles F. van Loan, Johns Hopkins University Press, Baltimore, 2013. After an introduction to matrix computation, the first part of the course addresses the resolution of general and particular linear systems using direct methods. The second part studies overdetermined linear systems (least squares problems), while the third part concerns the resolution of linear systems by iterative methods.

For the resolution of eigenvalue problems, the course focuses on the so-called "QR iteration" method and is inspired by the fourth chapter of the book ``Scientific Computing - An Introductory Survey'' (second edition), written by Michael T. Heath, McGraw-Hill, International Edition, 2005.

Table of contents

Chapter I: Matrix multiplication

   A. Basic algorithms

   B. Taking advantage of structures

   C. Bloc Matrices and associated algorithms

Chapter II: Matrix analysis

   A. Basic concepts of linear algebra

   B. Vector norms

   C. Matrix norms

   D. Matrix computation and finite precision

   E. Orthogonality and the singular value decomposition

   F. Sensitivity of linear systems

Chapter III: General linear systems

   A. Triangular systems

   B. LU factorization

   C. Gaussian elimination and roundoff error

   D. Pivoting

Chapter IV: Special linear systems

   A. LDM^T and LDL^T factorizations

   B. Positive definite systems

   C. Symmetric indefinite systems

Chapter V: Orthogonalization and least squares

   A. Householder and Givens transformations

   B. QR factorization

   C. Full-rank least squares problems

Chapter VI: Iterative methods for linear systems

   A. Standard methods (Jacobi -- Gauss-Seidel -- SOR)

   B. Conjugate gradient method

   C. Preconditioning

Chapter VII: Eigenvalues and eigenvectors

   A. Generalities

   B. Sensitivity and conditioning

   C. Problem Transformations

   D. Computing eigenvalues and eigenvectors

Exercises description

Exercise sessions are given for 2h00 per week.