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. Finite numbers - Representation of real numbers. Finite numbers. Representation errors. Floating point arithmetic. Error analysis in elementary arithmetic operations. Error propagation: stability and conditioning.

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

4. 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 with global convergence. The Fixed Point iteration method. Convergence theorem. A second-order method: the Newton method. Quasi-Newton methods: the secant method.

5. Numerical solution of Linear Systems - Condition number of a matrix and well-conditioned problems. The Gauss elimination algorithm. LU factorization of a matrix. Stability of LU factorization. Pivoting. Cholesky factorization of symmetric and positive definite matrices. Householder method and QR factorization of non-square matrices. Properties.

6. Least Squares approximation - Normal equations and QRLS method.

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

8. Numerical Integration - Newton-Cotes quadrature formulas. Simple and composite quadrature formulas. Error of simple and composite formulas. Adaptive quadrature formulas.

9. Fourier analysis - Fourier series. Continuous and Discrete Fourier transform. Properties. Convolution and correlation theorems. Fast Fourier Transform (FFT). Signal filtering techniques in the Fourier domain: lowpass and highpass filters.

Readings/Bibliography

It will be fundamental to use the notes taken during the lectures and the computer material made available on the web. For further study we recommend:

[1] A. Quarteroni, F. Saleri: Introduzione al Calcolo Scientifico - Esercizi e problemi risolti con MATLAB, Springer Verlag, 2006

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

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

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

[5] E. O. Brigham, The Fast Fourier Transform and its applications, Prentice-Hall, New Jersey, USA, 1988

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 MATLAB 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 the 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 MATLAB codes for solving numerical problems, and the written answer to theoretical questions on the topics covered in the lessons.

During the test, the use of support material such as textbooks, notes, computer supports is not allowed.

******

PLEASE NOTE: DUE TO THE covid-19 PANDEMIC, THE EXAMINATIONS WILL BE CARRIED OUT ONLINE, WITH THE STUDENTS AT HOME AT WORK ON THEIR PC. IN THIS SITUATION, THE EXAMINATION TEST WILL LAST ONLY 90 MINUTES. TO BE ABLE TO TAKE PART TO THE ONLINE EXAM, STUDENTS WILL HAVE TO INSTALL ON THEIR PC:

1) ZOOM CLIENT FOR MEETINGS (please follow the instructions at https://www.unibo.it/en/services-and-opportunities/online-services/online-services-for-students-1/lessons-and-exams-online
and select “How to take a written exam online via Zoom”)

2) MATLAB

3) A FILE ARCHIVER TO CREATE EITHER .ZIP OR .RAR FILES.

Finally, since during the exam the webcam should be able to capture not only the student's face, but also the table and hands, it would be advisable to use an external webcam (or even an external keyboard) to improve the visibility of the workplace.
The external keyboard could be used in the absence of an external webcam, to move sufficiently far away from the PC and allow the integrated webcam to provide a wider view. In order to use a mobile phone or tablet as an external webcam, it is necessary to install appropriate applications as neither mobile phone nor tablet can be logged in to Zoom. Students must be logged in to Zoom only from the PC where they give the exam.

STUDENTS WHO CANNOT ARRANGE WHAT INDICATED ABOVE ARE INVITED TO CONTACT ME AS SOON AS POSSIBLE.

******

Teaching tools

The course includes a laboratory activity in which the MATLAB software is used. The corresponding teaching material will be made available to the student in electronic format and will be available on the IOL platform.

Office hours

See the website of Lucia Romani

See the website of Damiana Lazzaro