SM/0077 - NUMERICAL ALGORITHMS AND APPLICATIONS
Academic Year 2019/2020
Free text for the University
GIUSEPPE RODRIGUEZ (Tit.)
- Teaching style
- Lingua Insegnamento
|[60/65] MATHEMATICS||[65/10 - Ord. 2012] Generale||6||48|
|[60/65] MATHEMATICS||[65/20 - Ord. 2012] Applicativo||6||48|
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. Least squares problems: theory and properties (4 hours)
Motivation and historical background. Description of a least squares problem and characterization of its solution. Normal equations. Minimal norm solution.
2. Basic analytical methods (14 hours)
Cholesky factorization. Singular value decomposition (SVD). Singular system of a linear operator. Fundamental subspaces associated to a matrix. Polar decomposition. Pseudo-inverse matrix. QR factorization. Rank revealing factorization. Ill-conditioned and rank-deficient problems. Truncated singular value decomposition (TSVD). Tikhonov regularization.
3. Numerical algorithms (14 hours)
Implementation of Cholesky decomposition. Elementary orthogonal transformations. QR factorization by Householder and Givens transformations. Classic and modified Gram-Schmidt process. SVD computation. Regularization techniques. Regularization parameter estimation. Iterative methods: the gradient method and the conjugate gradient method. Preconditioning. Other projection methods in Krylov spaces. Arnoldi, Lanczos, and Golub-Kahan iterations. Applications to the solution of linear systems, to the computation of eigenvalues, and to regularization.
4. Approximation of functions and quadrature rules (10 hours)
The best approximation problem. Approximation in Hilbert spaces. Characterization of the solution. Trigonometric approximation by truncated Fourier series. Orthogonal polynomials. Gaussian quadrature rules.
5. Laboratory (6 hours)
Advanced Matlab programming techniques. Optimized implementation of the algorithms studied.
The course consists of 48 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.
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.
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.