70224 - Numerical Algorithms

Learning outcomes

At the end of the course the student knows the fundamental concepts for solving a real problem by computer, with particular attention to the numerical linear algebra , interpolation and integration tools.

Course contents

Floating-point Arithmetic - Computer representation of numbers. Overflow and underflow. Rounding errors. Floating-point arithmetic. Propagation of errors. Cancellation. Errors in summation. Stability in Numerical Analysis. Backward error analysis.

Nonlinear Equations - The bisection method and other first order methods. Local and global convergence methods. Rates of convergence. Fixed point iterative methods. Convergence theorems. A second order method: the Newton method. Quasi-Newton methods: the secant method.

Recalls of Linear Algebra - Vector spaces, matrices and linear systems. Vector and matrix norms.

Numerical Solution of Systems of Linear Equations - The Gaussian elimination method. LR factorization of a matrix: existence and uniqueness. Condition number of a matrix and the condition of a linear system. Cholesky factorization of positive definte matrix. Variants of Gaussian elimination for banded matrices: the tridiagonal case. Iterative methods for the solution of linear systems: Method of Jacobi. Method of Gauss-Seidel. Descent methods. Conjugate Gradient Methods.

Interpolation - Polynomial interpolation. Existence and uniqueness of the interpolating polynomial. Evaluation of the interpolant: the Lagrange form and the Newton form. Error in the interpolation. Convergence. The Chebyshev points. Outline on the interpolation with spline functions.

Approximation: least squares method. Normal equations, LSQR method. Singular Value Decomposition

Numerical Integration - The Newton-Cotes formulas: the trapezoidal rule and the Simpson's rule. Errors in the Newton-Cotes formulas. The composite integration rules. Choice of the integration step. Self-adaptive integration rules.

Readings/Bibliography

A. Quarteroni, F. Saleri, Introduzione al Calcolo Scientifico -Esercizi e problemi risolti con MATLAB, Springer, 2004

A. Quarteroni, R. Sacco, F. Saleri, Matematica Numerica, Springer, 1998

R. Bevilacqua, D. Bini, M. Capovani, O. Menchi, Metodi Numerici, Zanichelli, 1992

Teaching methods

Lectures and laboratory exercises.

Assessment methods

Lab exercises and written examination.

Teaching tools

The course includes an activity in laboratory that forms an integral part; software MATLAB will be used.

Office hours

See the website of Serena Morigi