A systematic presentation is made of some of the most important methods and techniques in Numerical Analysis related to system solving and computing of eigenvalues and eigenvectors. Practical work with computers in MATLAB is an essential requirement.



Conditioning and stability seen in the course Métodos Numéricos I (2nd year) are studied in depth, as well as their application to basic algorithms for the solution of problems of Linear Algebra.



This course and Resolución Numérica de Ecuaciones Diferenciales, both in the 4th year of the Degree in Mathematics, belong to the módulo Ampliación de Métodos Numéricos.

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.

• Continuous Assessment System
• Final Assessment System
• Tools and qualification percentages:
  • See below (%): 100

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”.

To be given a positive assessment in the extraordinary call, the student must certify that he/she has obtained a mark higher than 4 in the compulsory practical work, and take a final written exam, in which his/her mark should be higher than 4. Practical computer work represents 15% of the final grade. Furthermore, students who obtain a mark above 5 in the tasks done throughout the year (either individually or in groups/pairs), their grade will be maintained if they wish. In such case, the weight of this grade will be 35%.

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

Web addresses

https://people.maths.ox.ac.uk/trefethen/
https://www.cs.berkeley.edu/~demmel/
https://www.mathworks.com/moler/
https://ocw.mit.edu/courses/18-335j-introduction-to-numerical-methods-spring-2019/