66736 - Numerical Methods

Learning outcomes

Knowledge of the fundamental aspects of numerical linear algebra and numerical analysis, that can be used in computer systems. Particular attention will be addressed to the acquisition of basic mathematical and computational tools typical of some applications such as signal and image processing and analysis of structured data.

Course contents

1. Numerical Calculus - Goals and problems in solving practical computer problems.

2. Introduction to Artificial Intelligence - Overview of Artificial Intelligence (AI), Machine Learning (ML) and Deep Learning (DL) applications - Impact of AI in the Economy - Brief history of AI evolution - Definitions and paradigm general of the ML and DL.

3. Introduction to Neural Networks: ML tasks (classification, regression and clustering) - Learning (supervised, unsupervised, self-supervised) -Definition of Artificial Neuron and Multi-Layer Perceptron (MLP) - Definition of Convolutional Neural Network (CNN) - Objective function (Loss Function). Forward Propagation and Backward Propagation.

4. Finite numbers - Representation of real numbers. Finite numbers. Representation errors. Floating point arithmetic. Error analysis in elementary arithmetic operations. Error propagation: conditioning of a problem and stability of an algorithm.

5. Linear Algebra recalls on vectors, matrices and vector spaces. Vector norms and matrix norms.

6. Zeros of Functions - Problem formulation. Resolution Techniques. Iterative methods, convergence and order of methods. Local convergence and global convergence methods. Bisection method and other methods of the first order. A second-order method: the Newton method. Quasi-Newton methods: the secant method. 

7. Numerical solution of Linear Systems - Direct methods - Condition number of a matrix and conditioning of the problem. The Gauss elimination algorithm. LU factorization of a matrix. Stability of LU factorization. Pivoting. Cholesky factorization of symmetric and positive definite matrices. Householder method, QR factorization, SVD factorization  of non-square matrices. Properties.

8. Numerical solution of linear systems: Iterative methods - Iterative methods based on matrix splitting. Necessary and sufficient condition for convergence. Jacobi method, Gauss-Seidel- Relaxation methods (Gauss-Seidel Sor) - Sufficient conditions for convergence. Descent methods for the solution of a linear system with symmetric and positive definite matrix. Condition for admissibility of descent direction. Gradient method and Conjugate gradient method. Influence of matrix conditioning on the convergence speed of descent methods.

9. Least Squares approximation - Normal equations and QRLS method (least squares solution using QR factorization), least squares solution using SVD factorization.

10. Interpolation - Polynomial interpolation. Existence and uniqueness of the interpolating polynomial. Lagrange's form and Newton's form of the interpolating polynomial. Error expression in polynomial interpolation. Convergence problems. Analysis of conditioning of the polynomial interpolation problem.

11. Optimization of the loss function for training a neural network.. Non-convexity of the loss-function - Calculation of the partial derivatives of the loss function with respect to all the weights of the network and consequent updating using the backpropagation algorithm. Gradient descent method, stochastic gradient method, minibatch gradient method. Hyperparameters of a neural network. Learning rate scheduling: step decay, exponential decay, time dependent decay. Adaptive learning rate: Adagrad, RMSProp, Adadelta, Adam.

Readings/Bibliography

It will be fundamental to use the notes taken during the lectures and the computer material made available at https://virtuale.unibo.it/

For further study we recommend:

[1] R. Johansson: Numerical Python - Scientific Computing and Data Science Applications with Numpy, SciPy and Matplotlib (2nd edition), Apress, 2019

[2] J. Kiusalaas: Numerical Methods in Engineering with Python 3, Cambridge University Press, 2013

[3] A. Quarteroni, R. Sacco, F. Saleri, P. Gervasio: Matematica Numerica (4th edition), Springer Verlag, 2014

[4] R. Bevilacqua, D. Bini, M. Capovani, O. Menchi: Metodi Numerici, Zanichelli, Bologna, 1992

[5] D. Bini, M. Capovani, O. Menchi: Metodi numerici per l'algebra lineare, Zanichelli, Bologna, 1996

Teaching methods

The course is structured in lectures and exercises in the computer laboratory. More precisely, the lectures on the basic numerical methods to solve classical mathematical problems through the use of a computer, are followed by laboratory exercises aimed at implementing these methods in Python and developing an adequate sensitivity and awareness of their use.

Assessment methods

The exam aims to verify the achievement of the following educational objectives:

- knowledge of the fundamental elements of numerical calculus, illustrated during the lectures;

- ability to use basic numerical methods to solve real problems using a computer.

The end-of-course exam (the evaluation of which is in thirtieths) will take place in a single test which includes both the development of Python codes for solving numerical problems, and the written answer to theoretical questions on the topics covered in the lessons.

Teaching tools

The course includes a laboratory activity in which the Python programming language is used. The corresponding teaching material will be made available to the student in electronic format and will be downloadable at https://virtuale.unibo.it/

Office hours

See the website of Damiana Lazzaro

See the website of Guido Borghi