Registro delle lezioni di
Calcolo Numerico
Corso di laurea in Chimica
A.A. 2000/2001

docente: prof. Giuseppe Rodriguez

ultimo aggiornamento: 10. gennaio 2001

1.          Martedì 3/10/2000, 10.30-12.30.         ore: 2(2)

Introduzione al corso. Argomenti studiati dall'Analisi Numerica. Problemi ben posti. Cenni sulla presenza degli errori di arrotondamento. Complessità computazionale e stabilità di un'algoritmo. Definizione operativa di problema ``risolubile''. Fattori tecnologici che influenzano lo sviluppo dell'Analisi Numerica. Algoritmi. Definizione. Codifica mediante diagrammi di flusso e mappe strutturali. Istruzioni di controllo di flusso. Sottoprogrammi e funzioni. Algoritmi strutturati. Esempi.

2.          Mercoledì 4/10/2000, 8.30-10.30.         ore: 2(4)

Calcolo della complessità computazionale di alcuni semplici algoritmi. Passaggio da un problema applicativo al calcolo dei risultati numerici e la loro interpretazione. Esempio: il calcolo di un integrale mediante la formula dei rettangoli. Analisi del problema, scrittura dell'algoritmo e sperimentazione numerica. Sistemi di numerazione posizionali. Notazione esponenziale. Origine degli errori. Misura degli errori: errore assoluto e relativo. Memorizzazione dei numeri di macchina: virgola fissa e virgola mobile. Definizione dell'insieme dei numeri di macchina e loro rappresentazione in virgola mobile normalizzata. Importanza della normalizzazione.

3.          Martedì 10/10/2000, 10.30-12.30.         ore: 2(6)

Insieme dei numeri di macchina. Memorizzazione di un numero reale non di macchina. Underflow e overflow. Esempio: calcolo della lunghezza di un vettore in modo da evitare underflow e overflow. Troncamento ed arrotondamento: calcolo dell'errore assoluto e relativo, proprietà statistiche dell'errore. Arrotondamento unitario e precisione di macchina. Rappresentazione dei numeri di macchina. Algoritmo per il calcolo della precisione di macchina.

4.          Mercoledì 11/10/2000, 8.30-10.30.         ore: 2(8)

Lo standard IEEE 754: variabili in singola e doppia precisione. Operazioni di macchina: ipotesi fondamentale e sue conseguenze. Analisi in avanti e all'indietro. Stabilità di un algoritmo. Cancellazione e smearing. Analisi di perturbazione per le operazioni di somma algebrica, prodotto e divisione di due numeri. Numero di condizionamento delle operazioni aritmetiche. Amplificazione dell'errore relativo causata dalla cancellazione. Esempi.

5.          Martedì 24/10/2000, 10.30-12.30.         ore: 2(10)

Richiami di Algebra Lineare. Spazi lineri. Esempi: ${\mathbb{R}}^n$, $\Pi_n$ e $C[a,b]$. Combinazioni lineari. Indipendenza lineare. Basi e dimensione. Spazi a dimensione infinita. Spazi normati. Metrica indotta dalla norma. Norme vettoriali: norma con indice 2, 1 e $\infty$. Rappresentazione geometrica in ${\mathbb{R}}^2$ della sfera unitaria corrispondente alle norme 2, 1 e $\infty$. Equivalenza delle norme in ${\mathbb{R}}^n$. Successioni convergenti in spazi normati. Spazi completi. Spazi di Hilbert. Prodotto interno e norma indotta. Ortogonalità. Matrici. Prodotto matriciale: definizione e proprietà. Matrici quadrate: determinante e matrice inversa. Rango di una matrice. Matrici diagonali, triangolari, simmetriche, definite positive e ortogonali.

6.          Mercoledì 25/10/2000, 8.30-10.30.         ore: 2(12)

Autovalori ed autovettori. Sistemi lineari omogenei. Il polinomio caratteristico. Una matrice ha $n$ autovalori complessi, ma non è detto che abbia $n$ autovettori indipendenti. Spettro di una matrice. Raggio spettrale. Matrici simili. Fattorizzazione spettrale. Risoluzione di un sistema lineare mediante la fattorizzazione spettrale. Alcune proprietà degli autovalori. Norme matriciali. Norma di Frobenius. Norme submoltiplicative e consistenti. Norma matriciale indotta da una norma vettoriale (norma naturale). Una norma naturale è consistente e submoltiplicativa. Norma naturale della matrice identità. Calcolo della norma matriciale indotta dalla norma $\infty$. Norme matriciali indotte dalle norme con indice 1 e 2.

7.          Martedì 31/10/2000, 10.30-12.30.         ore: 2(14)

Riepilogo sugli autovalori e sulle norme matriciali. Esercizi: spettro dell'inversa e della potenza di una matrice, la matrice $A^TA$ è simmetrica e definita positiva, norma-2 di una matrice simmetrica. Problemi diretti, inversi e di identificazione. Problemi ben posti. Esempi. Condizionamento assoluto e relativo di un problema. Condizionamento di un sistema lineare. Amplificazione dell'errore relativo sulla soluzione di un sistema lineare rispetto all'errore relativo sui termini noti. Illustrazione di due esempi che evidenziano l'effetto del cattivo condizionamento. Proprietà del numero di condizionamento di una matrice.

8.          Martedì 7/11/2000, 10.30-12.30.         ore: 2(16)

Stima degli autovalori. Relazione tra il raggio spettrale di una matrice e una sua norma naturale. Richiami sui numeri complessi. Il teorema dei cerchi di Gershgorin. I tre teoremi di Gershgorin sulla localizzazione degli autovalori di una matrice. Esempi di applicazione dei teoremi di Gershgorin. Sistemi lineari non singolari, sovradeterminati e sottodeterminati. Sistemi lineari di forma particolare: sistemi diagonali, ortogonali e triangolari inferiori o superiori. Algoritmi per la risoluzione di queste classi di sistemi e loro complessità computazionale.

9.          Mercoledì 8/11/2000, 8.30-10.30.         ore: 2(18)

Richiami sull'algoritmo di Gauss. Mappa strutturale dell'algoritmo. Fattorizzazione $A=LU$. Complessità computazionale delle varie fasi dell'algoritmo. Calcolo del determinante e dell'inversa di una matrice. Pivoting di colonna nell'algoritmo di Gauss. Matrici di permutazione e fattorizzazione $PA=LU$. Crescita del condizionamento derivante dall'applicazione dell'algoritmo di Gauss con pivoting parziale.

10.          Martedì 14/11/2000, 10.30-12.30.         ore: 2(20)

Fattorizzazione $A=QR$ per la risoluzione di un sistema lineare. Complessità. Vantaggi in termini di condizionamento. Fattorizzazione $QR$ di una matrice rettangolare. Sistemi lineari sovradeterminati, sottodeterminati e singolari. Motivazioni applicative. Problema ai minimi quadrati per un sistema sovradeterminato. Risoluzione mediante la fattorizzazione $QR$.

11.          Mercoledì 15/11/2000, 8.30-10.30.         ore: 2(22)

Scrittura dell'algoritmo per la risoluzione di un sistema lineare sovradeterminato mediante la fattorizzazione QR. Motivazioni che conducono all'utilizzazione di metodi iterativi per la risoluzione di sistemi lineari. Convergenza e consistenza di un metodo iterativo. Metodi iterativi stazionari del primo ordine. Calcolo dell'errore al passo $k$. Condizione sufficiente per la convergenza. Condizione necessaria e sufficiente per la convergenza. Costruzione di metodi iterativi mediante splitting additivo della matrice del sistema. Splitting della matrice $A$ che conduce ai metodi di Jacobi e Gauss-Seidel.

12.          Martedì 21/11/2000, 10.30-12.30.         ore: 2(24)

I metodi iterativi di Jacobi e Gauss-Seidel per la risoluzione di un sistema lineare. Formulazione matriciale e calcolo della generica iterazione componente per componente. Espressione della matrice di iterazione. Confronto dei due metodi. Matrici a predominanza diagonale stretta e convergenza dei metodi di Jacobi (con dimostrazione) e Gauss-Seidel. Criteri di arresto per un generico metodo iterativo.

13.          Mercoledì 22/11/2000, 8.30-10.30.         ore: 2(26)

Criterio di arresto per i metodi iterativi basato sull'esame del residuo. Descrizione algoritmica del metodo di Jacobi. Introduzione al calcolo delle radici di equazioni non lineari. Radici singole e multiple. Condizione necessaria e sufficiente perché una radice abbia molteplicità $n$. Condizionamento del problema nel caso di radici singole. Il metodo di bisezione.

14.          Martedì 28/11/2000, 10.30-12.30.         ore: 2(28)

Il metodo di bisezione. Descrizione algoritmica del metodo. Analisi della convergenza. Stima del numero di iterazioni necessarie per il raggiungimento di una prefissata precisione. Illustrazione di alcuni risultati numerici. Metodo di Newton per la risoluzione di equazioni non lineari. Significato geometrico ed analitico del metodo. Ordine di convergenza di un metodo iterativo. Il metodo di Newton è del second'ordine in presenza di una radice non multipla, mentre il metodo di bisezione ha ordine uno. Analisi della convergenza del metodo di Newton. Criteri di stop.

15.          Mercoledì 29/11/2000, 8.30-10.30.         ore: 2(30)

Esempio sul comportamento del metodo di Newton in presenza di una radice doppia. Metodi quasi-Newton: il metodi delle corde e delle secanti. Cenni sull'applicazione del metodo di Newton ad un sistema di due equazioni non lineari. Metodo delle corde multidimensionale. Motivazioni che portano al problema dell'interpolazione. Formulazione generale. Unisolvenza e determinante di Haar. Interpolazione polinomiale. Enunciati dei teoremi di Weierstrass e di Taylor. Dimostrazione di esistenza e unicità del polinomio interpolante. Matrici di Vandermonde.

16.          Martedì 5/12/2000, 10.30-12.30.         ore: 2(32)

Polinomio interpolante nella forma di Lagrange. Polinomi caratteristici di Lagrange. Errore di interpolazione. Calcolo dell'espressione dell'errore. Influenza del posizionamento dei nodi sull'errore di interpolazione. Nodi di Chebychev. Polinomi di Chebychev e calcolo dei loro zeri. Esempio di Runge.

17.          Mercoledì 6/12/2000, 8.30-10.30.         ore: 2(34)

Formula di Neville per il calcolo del polinomio interpolante in un punto. Differenze divise: formula ricorsiva e schema per il loro calcolo. Polinomio interpolante nella forma di Newton. Vantaggi rispetto agli altri algoritmi. Introduzione al problema della migliore approssimazione polinomiale nel senso dei minimi quadrati.

18.          Mercoledì 13/12/2000, 8.30-10.30.         ore: 2(36)

Approssimazione polinomiale nel senso dei minimi quadrati. Formulazione matriciale del problema. Risoluzione del risultante sistema lineare sovradeterminato mediante la fattorizzazione $QR$. Integrazione numerica. Formule di quadratura, pesi e nodi. Precisione algebrica. Cambio di variabili per ricondurre un integrale ad un intervallo di riferimento. Determinazione dei pesi, una volta fissati i nodi, col metodo dei coefficienti indeterminati. Formule di quadratura interpolatorie. Espressione dei pesi. Formule di Newton-Cotes chiuse.

19.          Martedì 19/12/2000, 10.30-12.30.         ore: 2(38)

Formule di Newton-Cotes aperte. Calcolo dei pesi. Formule elementari del punto medio, dei trapezi e di Simpson. Formule composte. Formule composte dei rettangoli, dei trapezi e di Simpson. Precisione algebrica delle formule di Newton-Cotes con $n$ pari. Cenni sulla precisione algebrica ottimale. Maggiorazione dell'errore di integrazione mediante l'errore di interpolazione.

20.          Mercoledì 20/12/2000, 8.30-10.30.         ore: 2(40)

Calcolo dell'errore per la formula dei trapezi elementare e composta. Espressione dell'errore per le formule del punto medio e di Simpson elementari e composte. Equazioni differenziali ordinarie. Problema di Cauchy. Funzioni lipschitziane. Esistenza ed unicità di una soluzione locale. Problema di Cauchy come determinazione di una curva integrale in un campo vettoriale. Cenni sui sistemi di equazioni differenziali del prim'ordine.

21.          Martedì 9/1/2001, 10.30-12.30.         ore: 2(42)

Riepilogo sulle equazioni differenziali ordinarie. Esempi. Trasformazione di una equazione differenziale del second'ordine in un sistema di equazioni del prim'ordine. Formule alle differenze finite. Metodo di Eulero esplicito ed implicito. Metodo del punto medio. Formule esplicite ed implicite, monostep e multistep. Applicazione di alcune formule di quadratura: la formula di Crank-Nicholson. La formula di Heun.

22.          Mercoledì 10/1/2001, 8.30-10.30.         ore: 2(44)

La formula di Eulero modificata. Errore globale di discretizzazione. Errore locale di discretizzazione. Consistenza e ordine di un metodo. Errore di propagazione e stabilità. Metodi di Runge-Kutta. Verifica dell'ordine per i metodi di Eulero, Heun ed Eulero modificato mediante lo sviluppo in serie dell'errore locale di discretizzazione.

Totale ore: 44