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.
- Decomposizione a valori singolari
- Risoluzione di sistemi non lineari e minimizzazione di funzioni
- Risoluzione numerica di equazioni differenziali ordinarie (cenni).

• Kelley - C.T. Kelley, Iterative Methods for Linear and Nonlinear Equations - SIAM,www:siam:org=books=textbooks=fr16 book:pdf
• Quarteroni et al. - A. Quarteroni, R. Sacco, F. Saleri, Matematica numerica. Springer-Verlag, Italia, Milano, 1998.
• Epelman - Continuous Optimization Methods https://www.cse.iitd.ac.in/~naveen/courses/CSL866/511notes.pdf
• Lambert - D.Lambert, Numerical methods for ordinary diferential systems. The initial value problem. John Wiley and Sons, Ltd., Chichester, 1991
• Dispense fornite dal docente

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.

L'insegnamento non prevede propedeuticità, ma presuppone la conoscenza di 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. 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.

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

Eventuale materiale didattico aggiuntivo rispetto ai testi di riferimento e prove di laboratorio d'esame precedentemente assegnate saranno disponibili sulla piattaforma e-learning di Ateneo (https://elearning.unicampania.it/), dove sarà attivato il corso "Calcolo Scientifico", a cui gli studenti avranno accesso con le credenziali di Ateneo.

Sistemi lineari Ax=b: analisi degli errori. La Forward Error Analysis. Effetto di perturbazioni su A e b (dim). Teorema di Gastinel. Errori di arrotondamento. Matrici triangolari. Analisi a Posteriori. Stima dell’errore per il metodo di Gauss (facoltativo).
(Appunti, Quarteroni et al)

Metodi iterativi per la risoluzione di Ax = b: generalit`a e definizioni, consistenza e convergeza. teorema sulla convergenza di un metodo consistente (dim) e maggiorazione dell’errore. Velocit`a di convergenza (media e asintotica). Metodi basati sullo splitting di A. Metodi di Jacobi e Gauss Seidel. Condizioni sufficienti per la convergenza; diagonale dominanza(dim). Teorema di Stein-Rosemberg. Il caso delle matrici tridiagonali. Convergenza per matrici simmetriche definite positive (dim). Tecniche di rilassamento, Metodi JOR e SOR. Convergenza per matrici simmetriche. Teorema di Ostrowski. Criteri di arresto per i metodi iterativi, relazione fra residuo e errore. Metodi di Richardson: generalit`a. Convergenza di Richardson stazionario (dim).
Implementazioni matlab: Jacobi e Gauss Seidel, JOR, SOR. Problemi test che illustrino i risultati teorici studiati.

Metodi diretti: fattorizzazione LU (richiami) e fattorizzazione di Cholesky: formulazione e aspetti implementativi.
Implementazioni matlab: Cholesky: caso generale e matrici a banda. Problemi test.
(Appunti, Quarteroni et al., Kelley)

Minimizzazione di una funzione quadratica convessa. Presupposti teorici; proprieta` di discesa del gradiente. Il metodo della discesa più ripida (SD). Il caso di funzioni quadratiche. Disuguaglianza di Kantorvich. Velocita` di convergenza. Metodi di discesa per funzioni C1. Metodo del gradiente, condizioni di sufficiente decrescita, condizioni di Armijio. Convergenza (parte facoltativa). (Epelman. Section 1, ch. 3-7).
CG Mininimizzazione di una funzione quadratica convessa in sot- tospazi. Direzioni coniugate (DC) e loro propriet`a metodo delle DC. Metodo del Gradiente coniugato (CG). Propriet`a di con- vergenza e formula dei ricorrenza. Convergenza e spettro di
A (dim). Caratterizzazione dell’errore assoluto e stima dell’errore relativo in funzione del condizionamento. CG precondizionato (Ja- cobi, Cholesky incompleto). Polinomi di Cebicev. Metodi di Krilov (parte facoltativa). GMRES: formulazione, maggiorazione del residuo. Il caso di matrici diagonalizzabili. Algoritmo di Arnoldi. Il teorema dell’happy breakdown. (appunti dalle lezioni + Kelley).
Implementazione matlab: Implementazione di CG. Problemi test che illustrino le proprietà teoriche studiate (in particolare convergenza del metodo, dipendenza dal condizionamento della matrice, esempi relative a differenti distribuzioni/clusterizzazione degli autovalori) . Implementzaione
di GMRES. Problemi test che illustrino le proprietà teoriche studiate.

Risoluzione di sistemi on lineari: Metodo del punto fisso e risultati base di convergenza. Metodo di Newton per sistemi di equazioni. Proprietà di convergenza. Derivazione dei metodi Newton inesatti e relativi risultati di convergenza (dim). Metodi Quasi Newton: derivazione. (appunti dalle lezioni
+ Kelley).

Autovettori ed autovalori. Presupposti teorici. Condizionamento. Metodo delle potenze, convergenza (dim). Iterazione inversa e deflazione. Trasformazioni ortogonali (Givens e Householder), fattorizzazione QR di una matrice.
Trasformazioni per similitudini. Algoritmo QR per il calcolo dello spettro di una matrice. Il metodo QR per matrici in forma di Hessenberg (appunti dalle lezioni+ Kelley) (appunti dalle lezioni + Quarteroni et al.). Implementazione in matlab: metodo delle potenze e potenze inverse,
con problemi test che illustrino le proprietà di convergenza. Trasformazioni di Householder e Givens. Fattorizzazione QR di una matrice. Problemi test.

Il problema di Cauchy. Introduzione ai metodi numerici per problemi ai valori iniziali. Convergenza, consistenza, zero-stabilità. Metodi numerici ad un passo. Analisi dei metodi ad un passo. L'assoluta stabilità. Metodi di tipo Runge-Kutta. Analisi deimetodi RK. Derivazione di un metodo RK esplicito. Regioni di assoluta stabilità per i metodi RK. Metodi lineari multistep Analisi dei metodi multistep. I metodi di Adams. (parte facoltativa) (Lambert, Quarteroni et al.).
Implementazione matlab: implementazione dei metodi studiati, utilizzo delle corrispondenti routine matlab. Problemi test che illustrino le proprietà teoriche studiate.

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

- Sviluppo di funzioni che implementano il metodo di Eulero in avanti e il metodo di Runge-Kutta-Fehlberg e applicazione a problemi di Cauchy per equazioni e sistemi di equazioni differenziali ordinarie che mettano in luce le differenti caratteristiche dei metodi. Confronto dei risultati ottenuti con quelli forniti da altre funzioni della ode suite di MATLAB, tra le quali ode45.

Italian

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

- numerical methods for computing eigenvalues and eigenvectors of matrices;
- Singular value decomposition
- Numerical solution of nonlinear systems, minimization of multivariate finctions

- numerical methods for ordinary differential equations.

• Kelley - C.T. Kelley, Iterative Methods for Linear and Nonlinear Equations - SIAM,www:siam:org=books=textbooks=fr16 book:pdf
• Quarteroni et al. - A. Quarteroni, R. Sacco, F. Saleri, Matematica numerica. Springer-Verlag, Italia, Milano, 1998.
• Epelman - Continuous Optimization Methods https://www.cse.iitd.ac.in/~naveen/courses/CSL866/511notes.pdf
• Lambert - D.Lambert, Numerical methods for ordinary diferential systems. The initial value problem. John Wiley and Sons, Ltd., Chichester, 1991
• Notes from the lessons

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.

Additional course material and past exam papers (lab tests) will be made available on the university e-learning platform (https://elearning.unicampania.it/), under the course "Calcolo Scientifico", which can be accessed by the students using their credentials for University online services.

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. QR method: basic QR iteration, QR method for matrices in Hessenberg form, similarity transformations to upper Hessenberg form, QR method with shifting techniques, convergence.

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

- Development and testing of functions implementing the Euler method and the Runge-Kutta-Fehlberg method 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.
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