ITALIANO

-Decomposizione di matrici: Fattorizzazione LDLT, fattorizzazione di cholesky, decomposizione ai valori singolari. Analisi delle componenti principali.
Applicazioni alla compressione e alla riduzione della dimensionalità
- Metodi iterativi non stazionari per sistemi lineari
-Quadratura numerica: formule composite e di Gauss-Seidel. Integratore automatico
-Metodi numerici per ODE: Eulero esplicito ed implicito. Matodi Runge-Kutta
-Interpolazione mediante spline

- A. Quarteroni, F. Saleri, R. Sacco, P. Gervasio, Matematica Numerica, 4a edizione, Springer-Verlag Italia, 2014.
-Appunti delle lezioni

al termine del corso lo studente dovrà aver acquisito conoscenze riguardanti metodi numerici e software di base per la risoluzione di problemi matematici che si presentano in semplici applicazioni scientifiche.

Calcolo numerico 1

48 ore di lezione frontale e 24 ore di attività di laboratorio sotto la guida del docente.

l'accertamento del profitto consiste di norma in una prova di laboratorio, seguita da una prova orale. Per accedere alla prova orale bisogna superare la prova di laboratorio. La prova di laboratorio finale può essere sostituita da prove di laboratorio parziali, eseguite durante lo svolgimento del corso.

Sono previste, come parte integrante del programma, attività di laboratorio volte all'implementazione di metodi trattati durante il corso o all'uso di routine che implementano tali metodi, e all'analisi dei risultati con essi ottenuti. Tali attività sono svolte sia utilizzando il linguaggio Matlab

Algebra Lineare
• Metodi diretti (matrici simmetriche e matrici simmetriche definite positive)
Fattorizzazione LU di matrici a banda: algoritmo con e senza pivoting, complessità computazionale. Fattorizzazione LDLT di matrici simmetriche: esistenza e unicità, algoritmo per il calcolo della fattorizzazione, cenni al pivoting, complessità computazionale. Fattorizzazione di Cholesky di matrici simmetriche definite positive: esistenza e unicità, algoritmo per il calcolo della fattorizzazione, complessità computazionale. Risoluzione di sistemi lineari utilizzando le fattorizzazioni suddette. Fattorizzazione LU di matrici a banda: algoritmo con e senza pivoting, complessità computazionale. Algoritmo per una matrice tridiagonale.
Decomposizione ai valori singolari. Analisi delle componenti principali. Applicazione alla compressione di immagini digitali.

• Metodi iterativi (matrici generiche e matrici simmetriche definite positive)
Matrici sparse, grado di sparsità, memorizzazione di matrici sparse. Metodi lineari stazionari basati sullo splitting della matrice: formulazione generale, metodi di Jacobi, di Gauss-Seidel, consistenza, convergenza, velocità di convergenza, complessità computazionale. Tecniche di rilassamento: JOR e SOR. Metodi non stazionari per la risoluzione di sistemi lineari con matrice simmetrica definita positiva: metodo del gradiente proprietà, convergenza, stima dell’errore, relazioni tra lo spettro della matrice ed il comportamento dei metodi, complessità computazionale. Criteri di arresto. Metodo delle direzioni coniugate: formulazione e terminazione finita. Cenni al metodo del gradiente coniugato.

Interpolazione mediante spline
Funzioni spline: definizione e rappresentazione. Spline naturali. Interpolazione di Lagrange mediante spline naturali. Esistenza e unicità della spline naturale cubica interpolante un insieme di punti; algoritmo per la costruzione di tale spline, risoluzione dei sistemi lineari tridiagonali che si presentano in tale algoritmo, complessità computazionale.

Quadratura
Formule di quadratura esatte per polinomi algebrici. Formule di Newton-Cotes e formule di Gauss. Analisi dell’errore mediante il teorema di Peano. Convergenza delle formule di Newton-Cotes e di Gauss. Formule composite di Newton-Cotes. Convergenza delle formule composite e ordine di convergenza. Stime calcolabili dell’errore e criteri di arresto. Integratori automatici. Complessità computazionale degli algoritmi di quadratura. Algoritmi adattativi di tipo locale e globale. Introduzione ai polinomi ortogonali. Caratterizzazione delle formule di quadratura con massimo grado di precisione algebrico. Formule di Gauss e relativi esempi. Convergenza delle formule di Gauss. Condizionamento delle formule di Quadratura di Gauss. Formule di Gauss con nodi preassegnati.

Introduzione alla risoluzione numerica di equazioni differenziali ordinarie
Richiami sui problemi di Cauchy per le equazioni differenziali ordinarie. Metodi di Eulero in avanti e all’indietro: consistenza, zero-stabilità, convergenza e teorema di Dahlquist; stabilità assoluta, equazione test e regioni di assoluta stabilità; errore di roundoff. Metodi Runge-Kutta (RK). Matrice di Butcher. Metodi a 2 stati: formula generale, metodo di Heun e metodo di Eulero modificato. Interpretazione geometrica del metodo di Eulero modificato. Metodi RK e formule di quadratura. Consistenza, convergenze e stabilità dei metodi RK.

Attività di laboratorio
Costituiscono parte integrante del programma le attività di laboratorio di seguito specificate. Si noti che per ciascuno dei programmi elencati è richiesta l’esecuzione su un insieme di problemi test, che mettano in luce le caratteristiche del metodo implementato e gli aspetti salienti del corrispondente programma, e l’analisi dei risultati ottenuti.

1. Costruzione di funzioni Matlab che implementano i metodi di Jacobi, Gauss-Seidel, JOR e SOR per sistemi sparsi.
2. Sviluppo di una funzione Matlab che implementa il metodo del gradiente e confronto con la funzione pcg di Matlab (senza pecondizionatore) per sistemi con matrice dei coefficienti SPD. Costruzione a analisi di problemi test che mettano in luce le relazioni tra il comportamento del metodo e le proprietà spettrali della matrice del sistema
3. Sviluppo di un integratore automatico, per il calcolo dell'integrale definito di una funzione f su un intervallo [a; b], basato sulla formula trapezoidale composita (strategia non adattativa). Applicazione delle funzioni quad, quadl e integral di Matlab a un insieme di problemi test che metta in luce le caratteristiche dell'algoritmo adattativo in essa implementato.
4. Uso delle funzioni ode23, ode45 della ODE suite di Matlab per la risoluzione di problemi di Cauchy per equazioni e sistemi di equazioni differenziali ordinarie del primo ordine.

Italian

Matrix Decompositions: LDLT Factorization, Cholesky Factorization, Singular Value Decomposition. Principal Component Analysis.
Applications in Compression and Dimensionality Reduction.
Non-Stationary Iterative Methods for Linear Systems.
Numerical Quadrature: Composite Formulas and Gauss-Seidel Quadrature. Automatic Integrator.
Numerical Methods for ODEs: Explicit and Implicit Euler, Runge-Kutta Methods.
Interpolation using Splines.

A. Quarteroni, F. Saleri, R. Sacco, P. Gervasio, Matematica Numerica, 4a edizione, Springer-Verlag Italia, 2014.
-Class notes

At the end of the course, the student should have acquired knowledge concerning numerical methods and basic software for solving mathematical problems that arise in simple scientific applications.

Calcolo numerico 1

48 hours of frontal lectures and 24 hours of laboratory activities under the guidance of the instructor

The final valutation consists of a laboratory test followed by an oral exam. To access the oral exam, one must pass the laboratory test. The final laboratory test can be replaced by partial laboratory tests conducted during the course.

As an integral part of the program, laboratory activities aimed at implementing methods covered during the course or using routines that implement such methods, and at analyzing the results obtained with them, are planned. These activities are carried out using the Matlab language

Linear Algebra
Direct Methods (Symmetric Matrices and Positive Definite Symmetric Matrices)
LU Factorization of Banded Matrices: Algorithm with and without Pivoting, Computational Complexity.
LDLT Factorization of Symmetric Matrices: Existence and Uniqueness, Algorithm for Computing the Factorization, Pivoting Overview, Computational Complexity.
Cholesky Factorization of Positive Definite Symmetric Matrices: Existence and Uniqueness, Algorithm for Computing the Factorization, Computational Complexity.
Solving Linear Systems using the above Factorizations.
LU Factorization of Banded Matrices: Algorithm with and without Pivoting, Computational Complexity. Algorithm for Tridiagonal Matrices.
Singular Value Decomposition. Principal Component Analysis. Application to Digital Image Compression.
Iterative Methods (Generic Matrices and Positive Definite Symmetric Matrices)
Sparse Matrices, Sparsity Degree, Sparse Matrix Storage. Stationary Linear Methods based on Matrix Splitting: General Formulation, Jacobi, Gauss-Seidel Methods, Consistency, Convergence, Convergence Rate, Computational Complexity. Relaxation Techniques: JOR and SOR. Non-Stationary Methods for Solving Linear Systems with Positive Definite Symmetric Matrices: Gradient Method Properties, Convergence, Error Estimation, Relationship between Matrix Spectrum and Method Behavior, Computational Complexity. Stopping Criteria. Conjugate Gradient Method: Formulation and Finite Termination. Brief Overview of the Conjugate Gradient Method.
Spline Interpolation

Spline Functions: Definition and Representation. Natural Splines. Lagrange Interpolation using Natural Splines. Existence and Uniqueness of the Natural Cubic Spline Interpolating a Set of Points; Algorithm for Constructing such a Spline, Solving Tridiagonal Linear Systems Arising in the Algorithm, Computational Complexity.
Quadrature

Exact Quadrature Formulas for Algebraic Polynomials. Newton-Cotes Formulas and Gauss Formulas. Error Analysis using Peano's Theorem. Convergence of Newton-Cotes and Gauss Formulas. Composite Newton-Cotes Formulas. Convergence of Composite Formulas and Convergence Order. Computable Error Estimates and Stopping Criteria. Automatic Integrators. Computational Complexity of Quadrature Algorithms. Local and Global Adaptive Algorithms. Introduction to Orthogonal Polynomials. Characterization of Quadrature Formulas with Maximum Algebraic Precision. Gauss Formulas and Related Examples. Convergence of Gauss Formulas. Conditioning of Gauss Quadrature Formulas. Gauss Formulas with Preassigned Nodes.
Introduction to Numerical Solution of Ordinary Differential Equations

Review of Initial Value Problems for Ordinary Differential Equations. Forward and Backward Euler Methods: Consistency, Zero-Stability, Convergence and Dahlquist's Theorem; Absolute Stability, Test Equation and Absolute Stability Regions; Roundoff Error. Runge-Kutta Methods (RK). Butcher Matrix. Two-Stage Methods: General Formulation, Heun's Method and Modified Euler's Method. Geometric Interpretation of Modified Euler's Method. RK Methods and Quadrature Formulas. Consistency, Convergence, and Stability of RK Methods.
Laboratory Activities
The following laboratory activities are an integral part of the program. Note that for each of the listed programs, execution on a set of test problems is required to highlight the characteristics of the implemented method and the key aspects of the corresponding program, along with the analysis of the obtained results.

Construction of Matlab functions implementing Jacobi, Gauss-Seidel, JOR, and SOR methods for sparse systems.
Development of a Matlab function implementing the gradient method and comparison with Matlab's pcg function (without preconditioner) for systems with SPD coefficient matrices. Construction and analysis of test problems highlighting the relationships between method behavior and spectral properties of the system matrix.
Development of an automatic integrator for computing the definite integral of a function f over an interval [a, b], based on composite trapezoidal rule (non-adaptive strategy). Application of Matlab's quad, quadl, and integral functions to a set of test problems highlighting the features of the adaptive algorithm implemented.
Use of Matlab's ode23 and ode45 functions from the ODE suite for solving Cauchy problems for first-order ordinary differential equations and systems of ordinary differential equations.