ITALIANO

Risoluzione numerica del problema dei minimi quadrati lineare.
- Metodi di Krylov per la risoluzione di sistemi lineari.
- Metodi numerici per il calcolo di autovalori e autovettori di matrici.
-Trasformata discreta di Fourier e algorutmi FFT. Applicazioni all'elaborazioni di immagini
- cenni ai metodi numerici per PDE

Alfio Quarteroni, Riccardo Sacco, Fausto Saleri, Paola Gervasio, Matematica Numerica, Springer Milano,
2014
• Valeriano Comincioli, Metodi Numerici e Statistici per le Scienze, Applicate
•E.O. Brigham, The Fast Fourier Transform and Its Applications, Prentice Hall Signal Processing Series, 1988 [Cap. 8].
• note delle lezioni

Conoscenze e capacità di comprensione: al termine del corso lo studente dovrà aver acquisito una solida conoscenza di metodologie e strumenti per lo sviluppo e l’analisi di metodi e software numerici per la risoluzione di
problemi matematici che sono alla base della modellazione e simulazione numerica di applicazioni scientifiche.

Applicazione delle conoscenze e della capacità di comprensione: al termine del corso lo studente dovrà essere in grado di scegliere ed applicare, tra le metodologie e gli strumenti acquisiti, quelli più adatti a una (semplice) applicazione scientifica.

Abilità comunicative: al termine del corso lo studente dovrà essere in grado di comunicare idee e strumenti per la risoluzione numerica di problemi del calcolo scientifico, e di esporre in maniera chiara eventuali risultati ottenuti con tali strumenti.

Si presume la conoscenza dei metodi e degli strumenti fondamentali della matematica normalmente insegnati nei corsi di laurea triennale in matematica, e in particolare dell'analisi numerica.

Il corso si articola in 48 ore di lezioni frontali, corrispondenti a 6 CFU, e 24 ore di attività in laboratorio, corrispondenti a 2 CFU.

La frequenza non è obbligatoria, ma è fortemente consigliata.

La verifica dell'apprendimento consiste di norma in una prova di laboratorio, della durata di due ore, e in una prova orale. Durante la prova di laboratorio può essere richiesto l'uso di programmi MATLAB sviluppati durante il corso.

La prova di laboratorio e la prova orale sono valutate in trentesimi. Il minimo per superare ciascuna prova è 18/30; prove particolarmente brillanti sono valutate con 30/30 e lode. Per accedere alla prova orale bisogna aver superato la prova di laboratorio. Quest'ultima ha un peso del 40% sulla valutazione complessiva.

La prova di laboratorio ha validità per una intera sessione d'esame. Lo studente può ripetere la prova di laboratorio nella medesima sessione; in tal caso, si assume come valutazione quella corrispondente alla prova più recente.

La prova di laboratorio può essere sostituita da due prove di laboratorio parziali, eseguite durante lo svolgimento del corso. Una valutazione non inferiore a 18/30 in entrambe le prove parziali dà diritto all'esonero dalla prova di laboratorio per l'intera durata dell'anno accademico.

email del docente: valentina.desimoneunicampania.it

RISOLUZIONE DI SISTEMI LINEARI CON METODI ITERATIVI
Convergenza di metodi iterativi: generalità. Ordine di convergenza, consistenza e convergenza (teorema) per i metodi
stazionari. Metodi basati sullo splitting della matrice. Jacobi, Gauss-Seidel e relative versioni rilassate.
Il caso di Matrici simmetriche definite positive: equivalenza fra risoluzione del sistema lineare e minimizzazione di una
funzione quadratica. Metodi di discesa. Il metodo dello steepest descent (SD). Convergenza del metodo dello SD.
Il metodo delle direzioni coniugate. Il metodo dei gradienti coniugati (CG): derivazione e formulazione del metodo.
Risultati di convergenza. Metodi basati su iterazioni in sottospazi di Krylov . Il metodo di Arnoldi per sistemi lineari
Il metodo GMRES. Criteri di arresto per metodi iterativi.
da Quarteroni: (4.2, 4.2.1, 4.2.2, 4.2.3, 4.2.6, 4.3, 4.3.3, 4.3.4, 4.3.5, 4.4 , 4.4.1, 4.4.2, 4.5, 4.5.1, 4.5.2) integrati con
appunti dalle lezioni.
Codici Matlab: Implementazione di SD, CG, GMRES. Costruzione di problemi test che illustrino il comportamento dei
metodi al variare dello spettro e del condizionamento della matrice. Analisi di errori e residui.

RISOLUZIONE DI SISTEMI DI EQUAZIONI NON LINEARI.
Il Metodo di Newton: derivazione e risultati di convergenza.
Metodi di Newton inesatti: derivazione e risultati di convergenza. Generalità sulle tecniche di globalizzazione della
convergenza. Metodi Quasi Newton. La condizione secante. Metodi di Broyden. Condizioni di convergenza (senza
dimostrazione). Broyden per sistemi lineari.
Codici Matlab: Implementazione del metodo di Newton. Costruzione di problemi test che illustrino il comportamento
del metodo (Jacobiano quasi singolare, singolare, etc.). Implementazione metodi di Broyden (per F(x)=0 e per sistemi
lineari). Implementazione metodi Newton inesatti e con tecniche di globalizzazione (facoltativi).

AUTOVALORI E AUTOVETTORI (come su Quarteroni)
5. Approssimazione di autovalori e autovettori
5.1 Localizzazione geometrica degli autovalori
5.2 Analisi di stabilità e condizionamento
5.2.1 Stime a priori
5.2.2 Stime a posteriori
5.3 Il metodo delle potenze
5.3.1 Calcolo dell’autovalore di modulo massimo
5.3.2 Calcolo dell’autovalore di modulo minimo
(*) Deflazione.
5.3.3 Aspetti computazionali e di implementazione
5.4 Metodi basati sulle iterazioni QR
5.5 L’iterazione QR nella sua forma di base
5.6 Il metodo QR per matrici in forma di Hessenberg
5.6.1 Matrici di trasformazione di Householder e di Givens
5.6.2 Riduzione di una matrice in forma di Hessenberg
5.6.3 Fattorizzazione QR di una matrice in forma di Hessenberg
Matlab: Implementazione: Metodo delle Potenze (MdP), MdP inverse, MdP con deflazione per il calcolo dei primi m
autovettori/autovalori di una matrice nxn.
Implementazione fattorizzazione QR per matrici generiche e matrici in forma di Hessemberg.
Implementazione del metodo QR per autovalori/autovettori: per matrici generiche e matrici in forma di Hessemberg.
Costruzione problemi test: in particolare analizzare: velocità del MdP in relazione alle proprietà spettrali della matrice,
costruire esempi che illustrino i Teoremi di Bauer Fike (stime a priori), stabilità singoli autovalori, le stime a posteriori
(ad esempio nell’implementazione di condizioni di arresto del MdP) .

La trasformata discreta di Fourier.
Trasformata discreta di Fourier (DFT): definizione e proprietà. Trasformata inversa di Fourier. Relazione tra la Trasformata continua e la trasformata discreta di Fourier. Formulazione matriciale e proprietà della matrice di Fourier. L’algoritmo FFT radix-2 per il calcolo della DFT: versioni “decimation in time” e “decimation in frequency”. Cenni su algoritmi FFT radix-r.
Applicazioni della DFT all’Elaborazione di Immagini: Introduzione all’Elaborazione di immagini. Immagini analogiche e digitali e relativi modelli di degradazione. Filtri digitali:definizione e classificazione. Alcuni esempi di filtri digitali (filtro soglia, filtro media, filtro mediano). Filtri digitali per il problema della ricostruzione di immagini nel dominio di Fourier. Filtro inverso, filtro inverso generalizzato, filtro di Wiener.

-Risoluzione numerica di equazioni differenziali alle derivate parziali. Problemi ai valori iniziali. Differenze divise. consistenza, convergenza e stabilità. Teorema di Lax

Italian

solution of linear least squares problems;
- Krylov methods for linear systems;

- numerical methods for computing eigenvalues and eigenvectors of matrices;
- DFT e FFT

- Numerical solution of nonlinear systems, minimization of multivariate finctions

- numerical methods for PDE

Alfio Quarteroni, Riccardo Sacco, Fausto Saleri, Paola Gervasio, Matematica Numerica, Springer Milano,
2014
• Valeriano Comincioli, Metodi Numerici e Statistici per le Scienze, Applicate
• lecture notes

Knowledge and understanding: students are expected to acquire a sound knowledge of methods and tools for the development and analysis of numerical algorithms and software that are the basis for numerical modeling and simulation of scientific applications.

Applying knowledge and understanding: at the end of the course students should be able to select and apply suitable methods and tools for the solution of a (simple) scientific application.

Communication skills: students should be able to communicate ideas, methods and techniques for the numerical solution of scientific computing problems, and to present results obtained with these tools.

Knowledge of basic methods and tools of mathematics usually taught in undergraduate programs in mathematics, and in particular of numerical analysis, is assumed.

The course consists of 48 hours of lectures (6 ECTS credits) and 24 hours (2 ECTS credits) of computing laboratory.

Attendance is not mandatory, but it is strongly recommended

The exam consists of two parts: a two-hour test using a PC in the computing laboratory and an oral assessment. Students are admitted to the oral assessment if they pass the lab test. The use of MATLAB programs developed in the Scientific Computing course can be required in the lab test.

Both the lab test and the oral assessment are graded on a scale of 0 to 30. The minimum passing grade is 18/30; outstanding performance is marked 30/30 cum laude. In order to be admitted to the oral assessment, a student must pass the lab test. The lab test has a weight of 40% on the overall exam.

The grade earned on the lab test lasts for the whole exam session. Students are allowed to repeat the lab test in the same session; in this case, the grade corresponding to the last test is considered for computing the exam grade.

The final lab test can be replaced by two partial lab tests, performed during the course. Students earning a grade of at least 18 out of 30 in both partial lab tests are admitted to the oral assessment in any exam session of the current academic year.

In order to be admitted to the evaluation, students must show a valid id card.

email: Questo indirizzo email è protetto dagli spambots. È necessario abilitare JavaScript per vederlo.

SOLUTION OF LINEAR SYSTEMS WITH ITERATIVE METHODS
Convergence of iterative methods: generalities. Order of convergence, consistency and convergence (theorem) for stationary methods.
Methods based on matrix splitting. Jacobi, Gauss-Seidel and related relaxed versions.
The case of positive definite symmetric matrices: equivalence between solving the linear system and minimising a
quadratic function. Descent methods. The steepest descent (SD) method. Convergence of the SD method.
The conjugate gradient method. The conjugate gradient (CG) method: derivation and formulation of the method.
Convergence results. Methods based on iterations in Krylov subspaces. Arnoldi's method for linear systems.
The GMRES method. Stopping criteria for iterative methods.
From Quarteroni: (4.2, 4.2.1, 4.2.2, 4.2.3, 4.2.6, 4.3, 4.3.3, 4.3.4, 4.3.5, 4.4 , 4.4.1, 4.4.2, 4.5, 4.5.1, 4.5.2) supplemented with
lecture notes.
Matlab codes: Implementation of SD, CG, GMRES. Construction of test problems illustrating the behaviour of the
methods as the spectrum and conditioning of the matrix vary. Analysis of errors and residuals.

SOLUTION OF NON-LINEAR SYSTEMS OF EQUATIONS.
Newton's method: derivation and convergence results.
Inexact Newton's methods: derivation and convergence results. Generalities on convergence globalisation techniques.
Quasi-Newton methods. The secant condition. Broyden's methods. Convergence conditions (without
proof). Broyden for linear systems.
Matlab codes: Implementation of Newton's method. Construction of test problems illustrating the behaviour
of the method (quasi-singular Jacobian, singular Jacobian, etc.). Implementation of Broyden methods (for F(x)=0 and for linear systems ).
Implementation of inexact Newton methods and globalisation techniques (optional).

EIGENVALUES AND EIGENVECTORS (as in Quarteroni)
5. Approximation of eigenvalues and eigenvectors
5.1 Geometric localisation of eigenvalues
5.2 Stability and conditioning analysis
5.2.1 A priori estimates
5.2.2 A posteriori estimates
5.3 The power method
5.3.1 Calculation of the maximum modulus eigenvalue
5.3.2 Calculation of the smallest eigenvalue
(*) Deflation.
5.3.3 Computational and implementation aspects
5.4 Methods based on QR iterations
5.5 QR iteration in its basic form
5.6 The QR method for Hessenberg matrices
5.6.1 Householder and Givens transformation matrices
5.6.2 Reduction of a Hessenberg matrix
5.6.3 QR factorisation of a Hessenberg matrix.
Matlab: Implementation: Powers method (MdP), inverse MdP, MdP with deflation for calculating the first m
eigenvectors/eigenvalues of an nxn matrix.
Implementation of QR factorisation for generic matrices and matrices in Hessenberg form.
Implementation of the QR method for eigenvalues/eigenvectors: for generic matrices and matrices in Hessenberg form.
Construction of test problems: in particular, analyse: speed of the POM in relation to the spectral properties of the matrix,
construct examples that illustrate Bauer Fike's Theorems (a priori estimates), stability of individual eigenvalues, a posteriori estimates
(e.g. in the implementation of POM stopping conditions) .
THE DISCRETE FOURIER TRANSFORM

Discrete Fourier Transform (DFT): definition and properties. Inverse Fourier Transform. Relationship between the continuous Fourier Transform and the Discrete Fourier Transform. Matrix formulation and properties of the Fourier matrix.

The radix-2 FFT algorithm for computing the DFT: decimation-in-time and decimation-in-frequency versions. Brief overview of radix-r FFT algorithms.

Applications of the DFT to Image Processing

Introduction to image processing. Analog and digital images and their degradation models. Digital filters: definition and classification.

Examples of digital filters:

threshold filter,
mean filter,
median filter.

Digital filters for image restoration in the Fourier domain:

inverse filter,
generalized inverse filter,
Wiener filter.
NUMERICAL SOLUTION OF PARTIAL DIFFERENTIAL EQUATIONS

Initial value problems. Finite differences. Consistency, convergence, and stability. The Lax Equivalence Theorem.