This course covers the main numerical tools to solve systems of linear equations and eigenvalue problems.
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.).
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.
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
Exercise sessions are given for 2h00 per week.
A single exam, in the form of individual work with oral presentation.
Matrix computations (Golub and Van Loan)
Scientific Computing - An Introductory Survey (Michael T. Heath)