M10CM01 - Learn the most important results and proofs of this course.

M10CM02 - Learn some advanced techniques of numerical computation and its translation into algorithms or constructive problem-solving methods.

M10CM03 - Understand the mathematical concepts needed for the numerical computation of eigenvalues.

M10CM04 - Apply knowledge to solving problems, both theoretical and practical.

M10CM05 - Use an IT tool that handles and applies some of the methods studied, and which serves as a support tool to programs.

M10CM06 - Communicate ideas on the subjects in this module, both in writing and orally.



LEARNING OUTCOMES

- Know some advanced techniques of numerical computation and its translation into algorithms or constructive problem-solving methods.

- Understand the mathematical concepts needed for the numerical computation of eigenvalues.

- Apply knowledge to solving problems, both theoretical and practical.

- Use an IT tool that handles and applies some of the methods studied, and which serves as a support tool to programs.

- Communicate ideas on the subjects in this module, both in writing and orally.

- Know rigorous proofs of some important results on the subjects in this module.

- Acquire new knowledge and techniques in an autonomous manner.

1. VECTORS AND MATRICES: Vectors, matrices and submatrices. Elementary matrices. Kernell and image of a matrix: Rank and nullity. LU factorization: algorithm.

2. NORMS OF VECTORS AND MATRICES: Vector norms. Equivalence of norms. Matrix norms.

3. SINGULAR VALUES: Orthogonality and unitary matrices. Singular values. SVD Theorem. Pseudoinverse. Low rank appproximation.

4. CONDITIONING AND STABILITY: Floating point arithmetic. Relative error and significative digits. Conditioning. Condition numbers. Conditioning of linear systems. Stable algorithms.

5. QR FACTORIZATION AND THE LEAST SQUARES PROBLEMS: Orthogonal projectors. Gram-Schmidt algorithms. Householder reflectors. Givens rotations. Algorithms. Conditioning and stability.

6. EIGENVALUES OF MATRICES: Eigenvalues and eigenvectors. Schur factorization. Defective matrices. Conditioning.

7. ALGORITHMS FOR COMPUTING EIGENVALUES. NONSYMMETRIC EIGENVALUE PROBLEM: Power method. Inverse power method. Rayleigh quotient. QR algorithm. Convergence analysis. Hessenberg reduction. Implementation.

8. ALGORITHMS FOR COMPUTING EIGENVALUES. SYMMETRIC EIGENVALUE PROBLEM: QR algorithm for symmetric matrices. Divide and conquer algorithm. Other algorithms: bisection and Jacobi.

9. ITERATIVE METHODS: Krylov subspaces: Arnoldi and Laczos methods. Conjugate gradient method. Convergence analysis. Preconditioning.



PRACTICAL CONTENT

1. Solving with MATLAB computational problems related with the subject (linear system solving , norms, singular values, rank, QR factorization and eigenvalues).

2. Design of algorithms with MATLAB for solving least squares problems.

3. Design of algorithms for computing eigenvalues and singular values.

The theoretical content is presented in lectures, following basic references that appear in the bibliography and compulsory course material. The lectures are complemented by practical problem-solving classes in which the problems involving the knowledge acquired in class will be discussed. These problems will be notified to students in advance. In the seminars, work will be done on representative questions and examples of the subject, and the students will make presentations on themes related to its content. These presentations will be prepared in advance in small groups. Practical computer exercises will be done to acquire skills in the subject.



Much of the work done by the student is on an individual basis. The professors will provide guidance at all times, encouraging students to do the work enthusiastically and regularly. Students will also be encouraged to use one-to-one tutorials, where they can clarify any doubts or difficulties they may encounter.

The continuous assessment modality consists of the performance of practical work, individual and group projects, a partial exam, and the presentation of projects in the seminars. Moreover, the professors may propose students individual or in groups, previously programmed assessment sessions with them. This continuous assessment modality accounts for 35% of the final grade. The remaining 65% corresponds to a final written exam.



Students who opt to withdraw from the continuous assessment modality must give written notification addressed to their professors within 9 weeks of the start of the term. In this case, the grade for the final written exam accounts for 85% of the final grade while the mark for the computer sessions accounts for 15% of the final grade.



To be given a positive assessment, the grade for the compulsory computer sessions must be higher than 4, which accounts for 15% of the final grade, and the grade for the compulsory final written exam must be at least 4.



A student may withdraw from the call, following the rules in effect: “Artículo 12 del ACUERDO de 15 de diciembre de 2016, del Consejo de Gobierno de la Universidad del País Vasco / Euskal Herriko Unibertsitatea, por el que se aprueba la Normativa reguladora de la Evaluación del alumnado en las titulaciones oficiales de Grado”.

Notes on the course (available at egela)
Guide to MATLAB (available at egela)

Basic bibliography

Ll. N. TREFETHEN Y D. BAU: Numerical Linear Algebra, SIAM, 1997.

J. W. DEMMEL: Applied Numerical Linear Algebra, SIAM, 1997.

G. W. STEWART: Matrix Algorithms. Volume II: Eigensystems, SIAM, 2001.

D. S. WATKINS: The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM, 2008.

R. A. HORN, C. R. JOHNSON: Matrix Analysis, Cambridge University Press, 1989.

C. B. MOLER: Numerical Computing with MATLAB, SIAM, 2004.

In-depth bibliography

G. H. GOLUB Y Ch. F. VAN LOAN: Matrix Computations, SIAM, 1996.
G. W. STEWART, J. SUN: Matrix Perturbation Theory, Academic Press, 1990.
F. CHATELIN: Eigenvalues of Matrices, John Wiley and Sons, 1995. SIAM, 2013.

Journals

SIAM Journal on Matrix Analysis and Applications
Numerical Linear Algebra
Linear Algebra and its Applications