SM/0077 - NUMERICAL ALGORITHMS AND APPLICATIONS
Academic Year 2021/2022
Free text for the University
GIUSEPPE RODRIGUEZ (Tit.)
- Teaching style
- Lingua Insegnamento
|[60/65] MATHEMATICS||[65/50 - Ord. 2020] MATEMATICA PER LA DIDATTICA E LA DIVULGAZIONE||9||72|
|[60/65] MATHEMATICS||[65/60 - Ord. 2020] MATEMATICA APPLICATA||9||72|
1. Acquiring knowledge and understanding.
The course is devoted to students in the first year of the Master's degree in Mathematics. It aims to provide a working knowledge of advanced methodologies in numerical analysis. These topics are presented by providing both a rigorous theoretical justification, and clear indications on some of the possible applications.
2. Applying knowledge and understanding.
The employment of the methods treated during the course in relevant applications in sciences and technology will be discussed. The student will have to implement the algorithms in a programming language and verify their performance by effective numerical experiments.
3. Making informed judgements and choices.
This course provides the students with knowledge and understanding sufficient to apply the methodologies described in the course to the solution of real-world problems.
4. Communicating knowledge and understanding.
The evaluation of the written test keeps into account the ability of the student to give a systematic and consistent exposition of the program of the course. The student's communicating knowledge will be analyzed during an oral interview and by a written report, which must contain a complete description of the assigned theme and a suitable numerical experimentation.
5. Capacities to continue learning.
This course allows students to acquire a wide expertise, sufficient to understand advanced mathematical texts and scientific papers, for widening their knowledge autonomously.
1. Knowledge. The course requires a good knowledge of the fundamentals of linear algebra and of real and complex mathematical analysis. The students should have followed a first course in Numerical Analysis, treating the basic direct and iterative methods for linear systems. An essential knowledge of the Matlab programming language is required.
2. Skills. Students must be able to apply the mathematical procedures learned during the Bachelor degree and the first year of the Master degree. In detail: computation of derivatives and integrals, advanced matrix and vector computation, implementation of algorithms in Matlab or in another programming language.
3. Competence. To fully understand the course it is necessary to understand the formulation of a mathematical model, and to describe effectively an algorithm for its solution.
Preparatory courses. No preparatory courses are required.
1. Introduction (6 hours)
Summary of basic notions. Polynomial approximation in the least-squares sense. Various interpretations of the matrix product: inner and outer product. BLAS. Computation of the inverse matrix. Block matrix products. The spectral theorem. Spectral factorization. Low-rank approximation. Epsilon-rank.
2. Least-squares problems (7 hours).
Overdetermined and underdetermined linear systems. Range and null space of a matrix. Statement of an overdetermined least squares problem (LSP) and resolution by the normal equations. Characterization of solutions. Pseudo inverse matrix. Orthogonal decomposition of a space. Dual LSP for underdetermined linear systems. Minimal norm solution. Normal equations of the second kind.
3. Direct numerical methods (6 hours).
The Cholesky factorization, its implementation, and its use for the solution of normal equations. QR factorization and application to an LSP. Householder and Givens elementary matrices. Corresponding QR factorization algorithms. Compact QR factorization.
4. Eigenvalues and eigenvectors computation (7 hours).
Basic definitions. Matrix similarity, diagonalizability, spectral factorization. Schur canonical form. Defective matrices. Normal matrices. Bauer-Fike theorem. The power method and the inverse power method. Spectrum translation. The companion matrix for computing a polynomial roots. Iterative methods and sparse matrices. The QR algorithm for computing eigenvalues. Convergence acceleration. Reduction to Hessenberg form.
5. Singular value decomposition (SVD) (8 hours).
Definition of singular values and singular vectors. General form of the factorization. Analogy with eigenvalue decomposition. Low-rank approximation. The four principal spaces associated to a matrix. General expression of the solution of a homogeneous linear system. Best matrix approximation. Application of SVD to the solution of linear systems and LSPs. Pseudo-inverse representation and properties. Truncated SVD and approximation errors. Weyl and Courant-Fisher theorems. Stability of the singular values. General definition of condition number. Penrose conditions. Hints on the Golub-Reinsch method for computing the SVD.
6. Iterative numerical methods (12 hours).
Introduction to iterative methods. Richardson methods. Preconditioning. LU and Cholesky incomplete factorizations. The gradient method and the conjugate gradient method. The CGLS method. Projection methods in Krylov spaces. The Lanczos algorithm. Breakdown and reorthogonalization. Solution of a linear system by the Lanczos method. Arnoldi and Golub-Kahan processes. The GMRES and LSQR methods.
7. Approximation of functions and numerical quadrature (10 ore).
The best approximation problem. Approximation in Hilbert spaces. Characterization of best approximation. Trigonometric approximation by truncated Fourier series. Orthogonal polynomials. Gauss quadrature rules and their optimality.
8. Laboratory (6 hours)
Advanced Matlab programming techniques. Optimized implementation of the algorithms studied.
The course consists of 72 lecture hours, which also include practical lessons regarding the solution to problems and exercises. The instructor gives constant assistance to students, during the whole year, both by personal interviews and by means of e-mail messages and teleconferencing systems.
In accordance to the “Manifesto degli Studi per l'A.A. 2021-22” and compatibly to the pandemic situation, teaching will be delivered mainly in person , integrated and “augmented” by online strategies, with the aim of ensuring it may be enjoyed in an innovative and inclusive fashion.
Verification of learning
Grading normally consists of the evaluation of a written report, on a theme assigned by the teacher, and of a subsequent oral interview. The student must demonstrate to know and have understood the algorithms described during the course and must be able to apply them to the solution of problems. The report must be delivered to the teacher at least one week before the official grading date.
To pass the exam the student must reach a grade of at least 18/30. To reach this goal the student must attest a basic knowledge of all the topics covered in the course. In order to achieve the maximum score 30/30, the student must demonstrate to know all the topics of the course in an excellent way , to be able to discuss them in detail, and to apply them autonomously to the solution of problems.
Students have the opportunity to be aware of their level of preparation during the practical lectures and through personal discussions with the instructor.
Due to the COVID-19 emergency, in the academic year 2021-2022 the exams will be in person or online according to the indications given by the University.
The main textbooks for the course are the following:
Pitagora Editrice, Bologna, 2008.
Numerical Methods for Least Squares Problems.
SIAM, Philadelphia, 1996.
Further references, aiming to deepen the understanding of selected topics, will be given by the instructor during the course, who will distribute, on particular topics, notes and other documentation.
The main tools to support teaching is the instructor’s personal web site. It provides information updated in real time, including: a lectures diary reporting the topics treated in each lecture, information on teaching activities, additional documents to support learning.