NUMERICAL ANALYSIS
Programming, Lab. Computational Mathematics, Linear Algebra, Analysis.
The written exam is a barrier for access to the oral exam, i.e. without a minimum level a student cannot access the oral exam:
- the written test lasts three hours, it contains exercises that are never standard, the student can bring any kind of material they consider necessary (except communication tools, as phones, PC etc)
- individual points are hidden among the exercises where imagination is required: such points are aimed at finding students with talent for research
- the exercises can be solved in various ways: those who find a faster and more elegant way (minimising the amount of maths) will be assessed more positively
- the oral test aims to check the level of mathematical rigour acquired by the student
- the final grade starts from that of the written paper by adding at most 8 points depending on the outcome of the oral part.
If the oral part is particularly lacking, the student will be invited to appear later for the oral part only
The present lectures contribute to the broader educational objectives of the CdS in Mathematics, as it aims to provide students with the knowledge of the critical analysis of algorithms and of their complexity and numerical stability.
The course also aims to educate the student in the constructive demonstration and the algorithmic view of mathematics, starting from Linear Algebra and Matrix Theory.
EXPECTED LEARNING OUTCOMES
At the end of the course, the student is expected to be able to:
1. carry out an a priori analysis of linear systems to verify the invertibility or strong nonsingularity or definiteness in sign of the coefficient matrix
2. on the basis of point 1., choose the most efficient numerical resolution technique, i.e. the least expensive in terms of the number of operations and with the best possible stability features
3. carry out rank analysis of large matrices
4. choose the most appropriate technique for calculating eigenvalues and eigenvectors, also in relation to very large problems such as the Google PageRanking computation
Matrix theory. Unitary matrix, Hermitian, definite positive, normals.
Normal forms: Schur and Jordan
Spectral characterisation of unitary, Hermitian, positive definite, normal matrices by Schur
Eigenvalues: localisation (Gerschgorin Theorems I, II, III), vector norms, matrix norms, induced norms (relations between spectral radius and induced norms)
Topological equivalence theorem of norms on finite-dimensional vector spaces
Elementary matrices (spectral, inverse characterisation): Gauss, Householder
Numerical solving of linear systems: linear systems in special form (unitary matrix, triangular etc.)
Problem conditioning and stability
Numerical resolution of linear systems:
Gauss elimination, pivoting, QR factorisation
Choleski algorithm for positive definite matrices
Shermann-Morrison-Woodbury formula (efficient update techniques)
Numerical stability of direct resolution algorithms
Iterative methods: general theory, Jacobi and Gauss-Seidel methods (convergence analysis)
Calculation of eigenvalues using the method of powers and variants. Example of the Google Pageranking case
Evaluation of a polynomial at a point. Interpolation. Vandermonde matrix.
Lectures occupy three-quarters of the teaching hours; a quarter is devoted to exercises.
Lectures are always on the blackboard: an education in flexibility will be favoured (there is never just one way to prove a mathematical assertion)
The exercises often deal with 'complex' problems that can be considered as complements to the theory and an introduction to research
The more complex topics are dealt with by the teacher; the more standard exercises are entrusted to a qualified tutor