REGISTRO DELLE LEZIONI DI
CALCOLO NUMERICO
CORSO DI LAUREA SPECIALISTICA
IN INGEGNERIA PER L'AMBIENTE E IL TERRITORIO - A.A. 2008/2009
DOCENTE: PROF. GIUSEPPE RODRIGUEZ
TUTOR: FRANCESCO ARRAI
ULTIMO AGGIORNAMENTO: 20. giugno 2009

1.          Martedì 3/3/2009, 8-10.         ore: 2(2/0/0)

Introduzione al corso. Problemi ben posti. Numero di condizionamento. Condizionamento del prodotto tra due numeri reali. Definizione di algoritmo.

2.          Mercoledì 4/3/2009, 10-13.         ore: 3(5/0/0)

Esempi di algoritmi. Caratterizzazione di un algoritmo: stabilità, complessità computazionale ed occupazione di memoria. Complementi di Algebra Lineare. Spazi vettoriali. Sottospazi. Combinazioni lineari.

3.          Martedì 10/3/2009, 8-10.         ore: 2(7/0/0)

Indipendenza lineare. Basi e dimensione. Esempi. Definizione di spazio normato. Norme vettoriali con indice 1, 2 e $\infty$. Norme funzionali con indice 2 e $\infty$. Norme equivalenti. Successioni convergenti. Spazi completi. Spazi di Hilbert. Esempi.

4.          Mercoledì 11/3/2009, 10-13.         ore: 3(10/0/0)

Successioni successioni di Cauchy. Spazi completi. Matrici quadrate e rettangolari. Trasposta e aggiunta. Operazioni su matrici. Matrice identità e potenza di una matrice. Esempi. Inversa, determinante e loro proprietà. Rango. Autovalori e autovettori. Spettro, raggio spettrale, quoziente di Rayleigh. Proprietà degli autovalori.

L1.          Venerdì 13/3/2009, 16-18.         ore: 2(10/2/0)

Laboratorio Introduzione a Matlab. Operatori aritmetici e funzioni elementari. Numeri complessi. Variabili. Controllo del workspace. Programmazione mediante scripts.

5.          Martedì 17/3/2009, 8-10.         ore: 2(12/2/0)

Norme matriciali. Submoltiplicatività e consistenza. Norma di Frobenius. Norme naturali e loro proprietà. Calcolo della norma indotta dalla norma vettoriale-$\infty$. Norma matriciale naturale con indice 1. Fase iniziale del calcolo della norma indotta dalla norma vettoriale euclidea.

6.          Mercoledì 18/3/2009, 10-13.         ore: 3(15/2/0)

Norma indotta dalla norma vettoriale euclidea. Norma-2 per matrici simmetriche. Esempi. Relazione tra raggio spettrale e norme matriciali. Sistemi di numerazione posizionale in base qualsiasi. Errori assoluti e relativi. Rappresentazione in virgola fissa e in virgola mobile. Segno, mantissa ed esponente di un numero. Insieme dei numeri di macchina. Condizione di normalizzazione. Funzione di memorizzazione. Underflow e overflow.

L2.          Venerdì 20/3/2009, 11-13.         ore: 2(15/4/0)

Laboratorio Costruzione di vettori e matrici. Operazioni su vettori e matrici. Subindexing. Funzioni che generano arrays.

E1.          Venerdì 20/3/2009, 15-17.         ore: 2(15/4/2)

Esercitazione Esercizi di algebra lineare: algoritmi di base, calcolo di determinanti e autovalori.

7.          Martedì 24/3/2009, 8-10.         ore: 2(17/4/2)

Troncamento. Errore di troncamento. Arrotondamento. Errore di arrotondamento. Vantaggi rispetto al troncamento. Arrotondamento unitario. Epsilon di macchina. Standard IEEE 754. Variabili in singola e doppia precisione. Operazioni di macchina e aritmetica non aberrante. Esempi. Condizionamento delle operazioni aritmetiche. Cancellazione.

8.          Mercoledì 25/3/2009, 10-13.         ore: 3(20/4/2)

Esempi sulla cancellazione. Sistemi lineari. Propagazione degli errori presenti sul termine noto. Numero di condizionamento. Condizionamento nel caso generale. Esempi. Proprietà del numero di condizionamento. Metodi diretti per sistemi lineari. Risoluzione di sistemi con struttura particolare. Sistemi diagonali, ortogonali e triangolari inferiori: proprietà, algoritmi e complessità.

L3.          Venerdì 27/3/2009, 11-13.         ore: 2(20/6/2)

Laboratorio Costruzione di un sistema lineare test. Algoritmo di sostituzione all'indietro per sistemi triangolari superiori. Test dell'algoritmo e analisi dei risultati. Scripts e funzioni.

E2.          Venerdì 27/3/2009, 15-17.         ore: 2(20/6/4)

Esercitazione Esercizi sull'aritmetica di macchina.

9.          Martedì 31/3/2009, 8-10.         ore: 2(22/6/4)

Risoluzione di sistemi triangolari superiori. Algoritmo di triangolarizzazione di Gauss. Analisi di un esempio numerico e dei primi due passi dell'algoritmo. Studio del generico passo dell'algoritmo.

10.          Mercoledì 1/4/2009, 10-13.         ore: 3(25/6/4)

Mappa strutturale dell'algoritmo di Gauss. Ipotesi di applicabilità. Complessità computazionale e ottimizzazione dell'algoritmo rispetto all'occupazione di memoria. Giustificazione del pivoting parziale. Pivoting parziale e totale. Rilevazione della singolarità della matrice. Mappa strutturale dell'algoritmo di Gauss con pivoting parziale. Teorema di Wilkinson. Fattore di crescita e sua influenza sull'errore. Crescita del condizionamento. Fattorizzazione LU.

L4.          Venerdì 3/4/2009, 11-13.         ore: 2(25/8/4)

Laboratorio Implementazione del metodo di Gauss con e senza pivoting.

E3.          Venerdì 3/4/2009, 15-17.         ore: 2(25/8/6)

Esercitazione Esercizi sul numero di condizionamento e sul metodo di Gauss con e senza pivoting.

11.          Martedì 7/4/2009, 8-10.         ore: 2(27/8/6)

Fattorizzazione LU e sua utilizzazione per la risoluzione di $m$ sistemi lineari con la stessa matrice dei coefficienti. Utilizzazione della fattorizzazione LU per il calcolo del determinante e della matrice inversa. Complessità risultante. Matrici di scambio e di permutazione. Fattorizzazione $PA=LU$ e sue applicazioni. Esempi.

12.          Mercoledì 8/4/2009, 10-13.         ore: 3(30/8/6)

Altre fattorizzazioni LU: $LDR$, $LDL^T$ per una matrice simmetrica e $R^TR$ per una matrice definita positiva. Inerzia di una matrice e lemma di Sylvester. Costruzione della fattorizzazione di Cholesky. Algoritmo e complessità. Fattorizzazione QR e suoi vantaggi in termini di stabilità. Matrici elementari di Householder. Calcolo stabile delle matrici elementari di Householder.

E4.          Mercoledì 8/4/2009, 15-17.         ore: 2(30/8/8)

Esercitazione Metodo di Gauss con pivoting, fattorizzazioni LU e di Cholesky.

13.          Mercoledì 15/4/2009, 11-13.         ore: 2(32/8/8)

Riepilogo del calcolo delle matrici elementari di Householder. Definizione alternativa. Applicazione ottimizzata di una matrice di Householder ad un vettore. Fattorizzazione QR di Householder: analisi dei primi tre passi dell'algoritmo. Analisi del generico passo. Cenni sull'applicazione a matrici rettangolari.

L5.          Venerdì 17/4/2009, 11-13.         ore: 2(32/10/8)

Laboratorio Implementazione del metodo di Gauss con e senza pivoting. Sperimentazione numerica. Alcune istruzioni grafiche.

E5.          Venerdì 17/4/2009, 15-17.         ore: 2(32/10/10)

Esercitazione Esercizi sul metodo di Gauss con e senza pivoting, fattorizzazione LU e fattorizzazione QR di Householder.

14.          Martedì 21/4/2009, 8-10.         ore: 2(34/10/10)

Fattorizzazione QR di matrici quadrate e rettangolari. Sistemi lineari rettangolari sovradeterminati e sottodeterminati. Risoluzione di sistemi lineari sovradeterminati nel senso dei minimi quadrati. Calcolo del gradiente di alcune funzioni espresse in forma matriciale. Sistema delle equazioni normali e soluzione mediante la fattorizzazione di Cholesky. Matrice pseudo-inversa e sue proprietà.

15.          Mercoledì 22/4/2009, 10-13.         ore: 3(37/10/10)

Calcolo della soluzione nel senso dei minimi quadrati tramite la fattorizzazione QR. Confronto tra i due metodi. Introduzione ai metodi iterativi per la risoluzione dei sistemi lineari. Convergenza e consistenza. Metodi lineari, stazionari, del prim'ordine. Valore del vettore di iterazione che garantisce la consistenza di un metodo iterativo. Condizione sufficiente e condizione necessaria e sufficiente per la convergenza. Costruzione di metodi mediante splitting additivo. Il metodo di Jacobi: espressione matriciale e in componenti. Parallelizzabilità. Il metodo di Gauss-Seidel.

L6.          Venerdì 24/4/2009, 11-13.         ore: 2(37/12/10)

Laboratorio Costruzione di matrici elementari di Householder. Fattorizzazione QR di Householder. Risoluzione di sistemi lineari.

E6.          Venerdì 24/4/2009, 15-18.         ore: 3(37/12/13)

Esercitazione Risoluzione di sistemi nel senso dei minimi quadrati. Fattorizzazione QR. Esercizi di riepilogo.

16.          Martedì 28/4/2009, 8-10.         ore: 2(39/12/13)

Riepilogo metodi iterativi. Espressione in componenti del metodo di Gauss-Seidel. Classi di matrici per cui i metodi di Jacobi e Gauss-Seidel convergono. Criteri di arresto. Fattori che influenzano la scelta della matrice di precondizionamento. Espressione di un metodo iterativo in termini del vettore residuo.

17.          Mercoledì 22/4/2009, 10-13.         ore: 3(42/12/13)

Fattorizzazione LU incompleta. Metodi di rilassamento. Metodi di Richardson stazionari e non stazionari. Problema di minimo associato ad un sistema lineare simmetrico definito positivo. Metodi di discesa. Calcolo del passo ottimale in un metodo di discesa. Il metodo del gradiente. Aggiornamento del residuo. Mappa strutturale. Precondizionamento. Ottimalità di un punto rispetto ad una direzione. Direzioni $A$-coniugate e loro costruzione. Il metodo del gradiente coniugato.

18.          Martedì 5/5/2009, 8-10.         ore: 2(44/12/13)

Commenti sull'applicabilità del metodo del gradiente coniugato. Autovalori e autovettori. Matrici simili e loro proprietà. Matrici diagonalizzabili e unitariamente diagonalizzabili. Condizione per la diagonalizzabilità. Teorema di Schur. Matrici Hermitiane. Introduzione agli algoritmi numerici. Teorema di Bauer-Fike sul condizionamento del problema agli autovalori.

19.          Mercoledì 6/5/2009, 10-13.         ore: 3(47/12/13)

Il metodo delle potenze. Normalizzazione. Rilassamento delle ipotesi di convergenza. Il metodo delle potenze inverse. Miglioramento di una stima di un autovalore e determinazione dell'autovettore corrispondente ad un autovalore assegnato. Algoritmo QR. Ipotesi di convergenza. Conservazione dello spettro e dell'Hermitianità attraverso trasformazioni QR. Costruzione della forma di Schur mediante l'algoritmo QR. Cenni sul passaggio in forma di Hessenberg e sui conseguenti vantaggi per l'algoritmo QR. Introduzione alla soluzione numerica di equazioni non lineari. Convergenza e ordine di un metodo iterativo. Richiami sulla formula di Taylor.

L7.          Venerdì 8/5/2009, 11-13.         ore: 2(47/14/13)

Laboratorio Matrici sparse e metodo del gradiente coniugato.

E7.          Venerdì 8/5/2009, 15-17.         ore: 2(47/14/15)

Esercitazione Esercizi di riepilogo.

E8.          Mercoledì 13/5/2009, 10-13.         ore: 3(47/14/18)

Esercitazione Prova scritta.

L8.          Venerdì 15/5/2009, 11-13.         ore: 2(47/16/18)

Laboratorio Correzione del compito. Metodi iterativi per sistemi lineari. Visualizzazione di immagini in Matlab.

E9.          Venerdì 15/5/2009, 15-17.         ore: 2(47/16/20)

Esercitazione Metodi iterativi per sistemi lineari.

20.          Martedì 19/5/2009, 8-10.         ore: 2(49/16/20)

Caratterizzazione algebrica ed analitica delle radici singole e multiple di un'equazione non lineare. Condizionamento del problema. Zeri di polinomi come autovalori della matrice compagna. Il metodo di bisezione: algoritmo e studio della convergenza.

21.          Mercoledì 20/5/2009, 10-13.         ore: 3(52/16/20)

Metodo di Newton: costruzione, studio della convergenza e dell'ordine. Metodi quasi-Newton: corde e secanti. Risultati numerici e confronto tra i metodi. Funzioni di iterazione e punti fissi. Visualizzazione grafica della convergenza. Contrattività. Funzioni di iterazione contrattive. Teorema sulla convergenza e sull'ordine di un metodo iterativo. Esempi.

L9.          Venerdì 22/5/2009, 11-13.         ore: 2(52/18/20)

Laboratorio Metodi di Jacobi e Gauss-Seidel. Algoritmo QR per gli autovalori. Dichiarazione inline di funzioni. Il metodo di Newton per le equazioni non lineari.

E10.          Venerdì 22/5/2009, 15-17.         ore: 2(52/18/22)

Esercitazione Autovalori. Equazioni non lineari.

22.          Martedì 26/5/2009, 8-10.         ore: 2(54/18/22)

Interpolazione ed approssimazione. Costruzione di una funzione interpolante e condizione che ne assicura l'esistenza ed unicità. I teoremi di Taylor e di Weierstrass. Interpolazione polinomiale mediante la base canonica. Matrici di Vandermonde. Instabilità di una rappresentazione. Polinomi caratteristici di Lagrange. Forma di Lagrange per il polinomio interpolante.

23.          Mercoledì 27/5/2009, 10-13.         ore: 3(57/18/22)

Errore di interpolazione. Influenza sull'errore della regolarità della funzione da interpolare e della distribuzione dei nodi. Errore di interpolazione e nodi di Chebychev. Alcuni risultati sulla convergenza. Polinomio di migliore approssimazione. Approssimazione nel senso dei minimi quadrati rispetto ad una norma discreta. Introduzione alla risoluzione numerica dei problemi di Cauchy. Funzioni globalmente e localmente Lipschitziane. Teorema sull'esistenza ed unicità della soluzione del problema di Cauchy. Esempi.

L10.          Venerdì 29/5/2009, 11-13.         ore: 2(57/20/22)

Laboratorio Polinomi cardinali di Lagrange. Interpolazione.

E11.          Venerdì 29/5/2009, 15-17.         ore: 2(57/20/24)

Esercitazione Equazioni non lineari. Esercizi di riepilogo.

24.          Mercoledì 3/6/2009, 10-13.         ore: 3(60/20/24)

Formule alle differenze finite. La formula di Eulero-Cauchy esplicita ed implicita, del punto medio, di Crank-Nicolson e di Heun. Formule esplicite ed implicite, monostep e multistep. La formula di Eulero modificata. Numero degli stadi di una formula. Espressione generale delle formule di Runge-Kutta. Errore globale di discretizzazione. Convergenza, consistenza e stabilità. Errore locale di discretizzazione. Ordine di una formula alle differenze finite. Verifica della consistenza e dell'ordine per le formule di Eulero e di Heun.

25.          Giovedì 4/6/2009, 9-10.         ore: 1(61/20/24)

Verifica della consistenza e dell'ordine per la formula di Eulero modificata. Influenza degli errori di arrotondamento. Implementazione dei metodi impliciti. Schemi predictor-corrector. Esempi.

E12.          Giovedì 4/6/2008, 15-17.         ore: 2(61/20/26)

Esercitazione Esercizi di riepilogo.

Totale ore: 61 (lezione), 20 (laboratorio), 26 (esercitazione)