Italiano

Programma sintetico:
- 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;
- risoluzione numerica di equazioni differenziali ordinarie.

1. Å. Björck, Numerical Methods for Least Squares Problems, SIAM, 1996.
2. Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM, 2003.
3. A. Quarteroni, R. Sacco, F. Saleri, P. Gervasio, Matematica Numerica, 4a edizione, Springer, 2014.

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, algoritmi 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.

L'insegnamento non prevede propedeuticità, ma presuppone la conoscenza degli argomenti generalmente trattati in un corso di laurea triennale in matematica, tra i quali gli argomenti di un corso di base di 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. Per accedere alla prova orale bisogna aver ottenuto una valutazione di almeno 18/30 nella prova di laboratorio. Il voto finale si ottiene facendo la media pesata delle valutazioni conseguite nella prova di laboratorio e nella prova orale e considerando il primo numero intero non inferiore al risultato; le due prove hanno rispettivamente un peso del 40% e del 60%. Ad esempio, il voto risultante da una valutazione della prova di laboratorio pari a 28/30 e da una valutazione della prova orale pari a 30/30 è 30≈29.2=28*0.4+30*0.6. Lo studente che ha una valutazione pari a 30/30 può conseguire anche la lode.

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. Ciascuna prova parziale ha un peso del 20% nel calcolo del voto finale. Il voto finale si ottiene facendo la media pesata delle valutazioni conseguite nelle prove di laboratorio parziali e nella prova orale e considerando il primo numero intero non inferiore al risultato.

Per partecipare a qualsiasi prova è necessario esibire un documento di riconoscimento in corso di validità.

Le tracce di prove di laboratorio già assegnate sono reperibili nella sezione "Materiale didattico" della pagina del docente sul sito web del Dipartimento di Matematica e Fisica (nella pagina web http://www.matfis.unicampania.it/dipartimento/docenti, "cliccare" sul nome del docente e poi su "Materiale didattico", che conduce al portale SharePoint dell'Ateneo).

ARGOMENTI

1. Risoluzione numerica del problema dei minimi quadrati lineare.
Il problema dei minimi quadrati lineare: formulazione, interpretazione geometrica, equazioni normali e loro risoluzione mediante fattorizzazione di Cholesky e fattorizzazione QR (nel caso di matrici con rango massimo). Esistenza della fattorizzazione QR. Relazione tra fattorizzazione QR e fattorizzazione di Cholesky. Trasformazioni ortogonali di Givens e di Householder, calcolo della fattorizzazione QR mediante tali trasformazioni. Calcolo della fattorizzazione QR mediante ortogonalizzazione di Gram-Schmidt. Confronto tra i metodi suddetti per la risoluzione del problema dei minimi quadrati, in termini di accuratezza e costo computazionale.

2. Metodi di Krylov per la risoluzione di sistemi lineari: il metodo del Gradiente Coniugato e il metodo GMRES.
Equivalenza tra la risoluzione di sistemi lineari con matrice simmetrica definita positiva e la minimizzazione di funzioni quadratiche strettamente convesse. Metodo del gradiente: formulazione, proprietà, convergenza, complessità computazionale. Metodi delle direzioni coniugate. Metodo del Gradiente Coniugato: formulazione, proprietà, relazioni tra spettro della matrice ed errore, complessità computazionale. Il metodo del Gradiente Coniugato precondizionato. Precondizionatore diagonale, precondizionatori basati sulla fattorizzazione incompleta di Cholesky. Metodi di proiezione ortogonale e obliqua: formulazione, interpretazione geometrica, proprietà di ottimo (minimizzazione dell’errore e del residuo). Metodi di proiezione su sottospazi di Krylov. Il metodo del Gradiente Coniugato come metodo di proiezione ortogonale su sottospazi di Krylov. Il metodo GMRES: formulazione, breakdown, convergenza, complessità computazionale. Versioni "restarted" e "truncated" del metodo GMRES. Cenni sul precondizionamento del metodo GMRES e sui precondizionatori basati sulla fattorizzazione LU incompleta.

3. Metodi numerici per il calcolo di autovalori e autovettori di matrici.
Richiami su autovalori e autovettori di matrici. Un'applicazione di un problema agli autovalori: l'algoritmo PageRank di Google. Decomposizioni di Schur e di Jordan. Quoziente di Rayleigh e teorema di Courant-Fischer (min-max) per gli autovalori di matrici hermitiane. Localizzazione degli autovalori mediante i teoremi di Gershgorin. Condizionamento del problema agli autovalori nel caso di matrici diagonalizzabili, condizionamento rispetto a un autovalore semplice e a un autovettore corrispondente. Metodo delle potenze, delle potenze inverse e delle potenze con shift. Cenni sul metodo QR per il calcolo degli autovalori: formulazione di base e algoritmo per matrici in forma di Hessenberg.

4. Risoluzione numerica di equazioni differenziali ordinarie.
Richiami sui problemi di Cauchy per le equazioni differenziali ordinarie. Introduzione ai metodi a un passo per la risoluzione di problemi di Cauchy per le equazioni differenziali ordinarie: metodo di Eulero in avanti e metodo di Eulero all’indietro; consistenza, convergenza, zero-stabilità, stabilità assoluta ed errore di roundoff di tali metodi. Teorema di equivalenza di Dahlquist. Metodi di Runge-Kutta espliciti. Relazione tra stadi e ordine di un metodo di Runge-Kutta. Adattatività del passo nei metodi di Runge-Kutta, metodo di Runge-Kutta-Fehlberg. Metodi multistep lineari di Adams-Bashforth e Adams-Moulton. Consistenza, zero-stabilità, convergenza, assoluta stabilità dei metodi di Runge-Kutta e dei metodi di Adams. Risoluzione col metodo di Newton delle equazioni non lineari che si presentano nei metodi impliciti. Cenni ai problemi stiff.

ATTIVITA' DI LABORATORIO

Costituiscono parte integrante del programma del corso le attività di laboratorio di seguito elencate, svolte in ambiente MATLAB.

- Sviluppo di funzioni per la risoluzione del problema dei minimi quadrati lineare mediante fattorizzazione QR, basata su trasformazioni di Householder, su trasformazioni di Givens e sull'ortogonalizzazione di Gram-Schmidt. Applicazione di tali funzioni a un insieme di problemi test che mettano in luce le principali caratteristiche dei metodi implementati. Confronto dei risultati ottenuti risolvendo problemi ai minimi quadrati lineari, con matrici aventi differenti indici di condizionamento, mediante gli algoritmi di fattorizzazione QR suddetti e la fattorizzazione di Cholesky (funzione MATLAB chol) applicata alle equazioni normali.

- Sviluppo di funzioni che implementano il metodo del gradiente e il metodo del gradiente coniugato precondizionato, per la risoluzione di sistemi lineari con matrice simmetrica definita positiva. Costruzione di problemi test con matrice simmetrica definita positiva avente indice di condizionamento o autovalori assegnati, utilizzando la funzione MATLAB sprandsym. Testing delle implementazioni suddette su un insieme di sistemi lineari che metta in luce le proprietà dei metodi considerati, con particolare attenzione alle relazioni tra l'errore nel metodo del gradiente coniugato e le proprietà spettrali della matrice del sistema. Confronto dei risultati ottenuti con quelli forniti dalla funzione pcg di MATLAB. Il metodo del gradiente coniugato deve essere applicato senza precondizionatore, con il precondizionatore diagonale e con un precondizionatore di tipo fattorizzazione di Cholesky incompleta, calcolato con la funzione ichol.

- Sviluppo di una funzione che implementa il metodo GMRES restarted per la risoluzione di sistemi lineari. Costruzione di problemi test che mettano in luce qualche proprietà del metodo, applicazione ad essi della funzione suddetta, analisi dei risultati e confronto con quelli ottenuti con la funzione gmres di MATLAB. Applicazione della funzione gmres di MATLAB con il precondizionatore diagonale e con un precondizionatore di tipo fattorizzazione LU incompleta, calcolato con la funzione ilu di MATLAB.

- Sviluppo di funzioni che implementano i metodi di Eulero in avanti e all'indietro e applicazione a problemi di Cauchy per equazioni e sistemi di equazioni differenziali ordinarie che mettano in luce differenti caratteristiche di base dei due metodi. Confronto dei risultati ottenuti con quelli forniti da altre funzioni della ode suite di MATLAB, tra le quali ode45.

- Sviluppo di una funzione che implementa il metodo delle potenze per il calcolo dell'autovalore dominante di una matrice e di un autovettore corrispondente. Applicazione di tale funzione a problemi test che mettano in luce alcune proprietà del metodo implementato e analisi dei risultati. Applicazione delle funzioni condeig ed eig di MATLAB ad alcuni problemi test e analisi dei risultati.

Italian

Summary of contents:
- solution of linear least squares problems;
- Krylov methods for linear systems;
- numerical methods for computing eigenvalues and eigenvectors of matrices;
- numerical methods for ordinary differential equations.

1. Å. Björck, Numerical Methods for Least Squares Problems, SIAM, 1996.
2. Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM, 2003.
3. A. Quarteroni, R. Sacco, F. Saleri, P. Gervasio, Matematica Numerica, 4a edizione, Springer, 2014.

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 numerical analysis, usually taught in undergraduate programs in mathematics, 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. In order to be admitted to the oral assessment, a student must earn a grade of at least 18 in the lab test. The exam grade is obtained by computing the weighted mean of the grades on the lab test and the oral assessment, and taking the first integer number not less than the mean; the weight of the lab test is 40% and the weight of the oral assessment is 60%. E.g., a student receiving a grade of 28 on the lab test and of 30 on the oral assessment, earns an exam grade of 30 (30≈29.2=28*0.4+30*0.6). Outstanding performance corresponds to a grade of "30 cum laude".

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. Each partial lab test has a weight of 20% in the whole exam grade. This grade is obtained by computing the weighted mean of the grades on the lab tests and the oral assessment, and taking the first integer number not less than the mean.

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

Past exam papers (lab tests) are available in the section "Materiale didattico" of the instructor web page on the website of the Department of Mathematics and Physics (go to http://www.matfis.unicampania.it/dipartimento/docenti, click on the name of the instructor and then on "Materiale didattico", which leads to SharePoint).

TOPICS

1. Numerical solution of linear least squares problems.
Linear least squares: problem formulation, geometrical interpretation, normal equations, solution of normal equations by Cholesky and QR factorization (full-rank matrices). Existence of QR factorization. QR factorization and its relation to Cholesky factorization. Computation of the QR factorization by using Householder transformations, Givens transformations and Gram-Schmidt orthogonalization process. Comparison of the previous algorithms in terms of accuracy and computational cost.

2. Krylov methods for the solution of linear systems: Conjugate Gradient (CG) and Generalized Minimal RESidual (GMRES) methods.
Solution of linear systems with symmetric positive definite matrix and minimization of strictly convex quadratic functions. Steepest descent method: algorithm, basic properties, convergence, computational complexity. Conjugate direction methods. CG method: algorithm, basic properties, relations between error and matrix eigenvalues, computational complexity. Preconditioned CG method. Diagonal and incomplete Cholesky factorization preconditioners. Orthogonal and oblique projection methods: basic definitions, geometrical interpretation, optimality properties. Krylov subspace methods. The CG method as a Krylov subspace method. The GMRES method: algorithm, breakdown, convergence, computational complexity. Restarted and truncated GMRES methods. GMRES with preconditioning, incomplete LU preconditioners: basic issues.

3. Numerical methods for computing eigenvalues and eigenvectors.
Eigenvalues and eigenvectors of matrices: basic definitions. Eigenvalues, eigenvectors and the Google PageRank algorithm. Schur and Jordan decompositions, Rayleigh quotient and Courant-Fischer (min-max) theorem. Geometrical location of the eigenvalues: the Gershgorin theorems.
Conditioning of the eigenvalue problem for nondefective matrices, conditioning of a simple eigenvalue and a corresponding eigenvector. Power method, inverse power method and shifted power method. Introduction to QR method: basic QR iteration and QR method for matrices in Hessenberg form.

4. Numerical solution of Ordinary Differential Equations (ODEs).
Initial value problems for ODEs: basic theory. Introduction to one-step methods: Euler and backward Euler methods, and their consistency, convergence, stability, absolute stability and roundoff error. Dahlquist equivalence theorem. Explicit Runge-Kutta methods. Order and stages of Runge-Kutta methods. Stepsize adaptivity in Runge-Kutta methods, Runge-Kutta-Fehlberg methods. Adams-Bashfort and Adams-Moulton linear multistep methods. Consistency, stability, convergence, absolute stability of Runge-Kutta and Adams methods. Solution by Newton's method of nonlinear equations in implicit ODE methods. Basics on the solution of stiff equations.

COMPUTING LABORATORY EXERCISES

The following computing laboratory exercises will be carried out during the course, using the MATLAB environment. All students are required to do the exercises before taking the exam.

- Development and testing of functions for solving the linear least squares problem via QR factorization, computed by using Householder transformations, Givens transformations, and Gram-Schmidt orthogonalization. The functions must be applied to a set of test problems in order to show the main features of the three QR algorithms. A comparison is required among the results obtained by using the previous functions and the Cholesky factorization (MATLAB function chol) of the normal equations matrix, on least squares problems with matrices having various condition numbers.

- Development and testing of functions implementing the gradient method and the preconditioned CG method, for solving linear systems with symmetric positive definite (spd) matrices. The functions must be applied to a set of test problems in order to show the main features of the two methods; special attention must be put on the relation between the error in the CG method and the spectral properties of the matrix. The CG method has to be applied without any preconditioner, with diagonal preconditioner, and with an incomplete Cholesky preconditioner. The last preconditioner can be computed by using the MATLAB function ichol. A comparison with the results obtained with the MATLAB function pcg is also required.

- Development and testing of a function implementing the GMRES method. The function must be applied to a set of test problems in order to show basic features of GMRES. A comparison with the results obtained by using the MATLAB function gmres, without any preconditioner, with diagonal preconditioner, and with an incomplete LU preconditioner (computed by the MATLAB function ilu), must be also performed.

- Development and testing of functions implementing the forward and backward Euler methods for solving initial value problems for (systems of) ODEs. The functions must be applied to a set of test problems in order to show basic features of the two methods. A comparison with the results obtained by using some MATLAB ODE solvers, including ode45, is also required.

- Development and testing of a function implementing the power method for computing the dominant eigenvalue of a matrix and a corresponding eigenvector. The function must be applied to test problems in order to show basic features of the power method. The application of the MATLAB functions condeig and eig to well-conditioned and ill-conditioned eigenproblems, along with an analysis of the results, is also required.