Registro delle lezioni di
Analisi Numerica I
Corso di laurea in Matematica
A.A. 2000/2001

docenti: prof. Giuseppe Rodriguez, dott. Carmine Di Fiore

ultimo aggiornamento: 31. gennaio 2001

1.          Lunedì 2/10/2000, 15.30-16.30.         ore: 1(1)

Introduzione al corso. Motivazione dello studio dei problemi ai minimi quadrati e dei metodi per la loro risoluzione. Alcuni esempi.

2.          Lunedì 9/10/2000, 14.30-16.30.         ore: 2(3)

Sistemi lineari sovradeterminati e sottodeterminati a rango pieno e non. Sottospazi fondamentali associati ad una matrice. Teorema dell'alternativa di Fredholm. Formulazione del problema dei minimi quadrati (LSP). Cenni storici. Impostazione statistica. Richiami di alcune definizione di base in notazione vettoriale. Modelli statistici lineari. Stime unbiased di minima varianza. Enunciato del teorema di Gauss-Markov e sue conseguenze. Caratterizzazione delle soluzioni di un LSP: condizione di ortogonalità. Sistema delle equazioni normali. Unicità della soluzione nel senso dei minimi quadrati (LSS) nel caso di rango pieno. Espressione della proiezione ortogonale sullo spazio $\mathcal{R}(A)$.

3.          Martedì 10/10/2000, 9.30-10.30.         ore: 1(4)

LSP con rango non pieno. Norme strettamente convesse. Unicità della soluzione nel senso dei minimi quadrati di minima norma (MNLSS). Riformulazione di un sistema lineare sottodeterminato come problema di minima norma. Problema LS primale e duale. Espressione della soluzione del problema duale: equazioni normali del secondo tipo. Caratterizzazione congiunta dei due problemi mediante il sistema aumentato.

4.          Lunedì 23/10/2000, 14.30-16.30.         ore: 2(6)

Esistenza ed unicità della fattorizzazione di Cholesky. La decomposizione a valori singolari (SVD). Definizione e dimostrazione dell'esistenza. Interpretazione geometrica. SVD compatta. Non unicità della fattorizzazione. Definizione alternativa del sistema singolare. La SVD e i quattro sottospazi fondamentali associati ad una matrice. Problemi di autovalori connessi con la SVD. Somiglianze e differenze tra fattorizzazione spettrale e SVD. Legame tra la norma-2 di una matrice ed i suoi valori singolari.

5.          Martedì 24/10/2000, 9.30-10.30.         ore: 1(7)

Decomposizione polare di una matrice. SVD a rango $\ell$. Teorema di Weyl e sua dimostrazione. Presentazione del teorema di Courant-Fisher sulla caratterizzazione minimax dei valori singolari come corollario del teorema di Weyl.

6.          Lunedì 30/10/2000, 14.30-16.30.         ore: 2(9)

Il teorema di Courant-Fisher. Stabilità dei valori singolari rispetto ad una perturbazione della matrice dei coefficienti. Caratterizzazione minimax e risultati di stabilità per gli autovalori di matrici Hermitiane e non. Il quoziente di Rayleigh. Esempio numerico. Risoluzione mediante la SVD di un sistema lineare non singolare e di un LSP in forma generale. Matrice pseudoinversa e sue proprietà. Condizioni di Penrose. Relazioni tra la pseudoinversa e i proiettori sui sottospazi fondamentali. Esistenza della fattorizzazione QR. Legame con la SVD e la fattorizzazione di Cholesky. Fattorizzazione QR compatta.

7.          Martedì 31/10/2000, 9.30-10.30.         ore: 1(10)

Utilizzazione della fattorizzazione QR per la risoluzione del sistema lineare aumentato associato ad un LSP. Risoluzione del problema primale e del duale ed espressione delle pseudoinverse di $A$ e di $A^T$ in termini dei fattori $Q$ e $R$. Fattorizzazione QR rank revealing per matrici a rango non pieno. Difficoltà nella determinazione del rango numerico. Decomposizione ortogonale completa con fattore centrale triangolare e bidiagonale. Confronto con la SVD.

8.          Lunedì 6/11/2000, 14.30-16.30.         ore: 2(12)

Analisi di perturbazione per un LSP. Alcuni risultati sull'effetto di una perturbazione sulla pseudoinversa di una matrice. Numero di condizionamento per una matrice rettangolare. Studio del condizionamento di un LSP in presenza di errori sulla matrice dei coefficienti e sui termini noti. Algoritmi per la formazione delle equazioni normali. Forme inner product e outer product. Complessità computazionale. Fattorizzazione di Cholesky. Diversi modi di applicare la fattorizzazione per la risoluzione di un LSP. Algoritmi per righe e per colonne. Complessità computazionale.

9.          Lunedì 13/11/2000, 14.30-16.30.         ore: 2(14)

Fattorizzazione di Cholesky a blocchi. Trasformazioni ortogonali elementari. Matrici di Householder: proprietà ed algoritmi di costruzione e di pre- e post-moltiplicazione per una matrice. Matrici di rotazione di Givens: costruzione stabile ed applicazione ad un vettore per annullarne una componente. Fattorizzazione QR di una matrice mediante trasformazioni di Householder e di Givens. Complessità computazionale. Algoritmo ottimizzato per la fattorizzazione QR di Householder.

10.          Martedì 14/11/2000, 9.30-10.30.         ore: 1(15)

Algoritmo per la fattorizzazione QR con Givens. Fattorizzazione QR con l'algoritmo di ortogonalizzazione di Gram-Schmidt classico (CGS). Formulazione matriciale e parallelizzabilità. Algoritmo di Gram-Schmidt modificato (MGS). Analisi del passo $k$-esimo e fattorizzazione QR da esso generata.

11.          Lunedì 20/11/2000, 14.30-16.30.         ore: 2(17)

Formulazione matriciale dell'algoritmo MGS. Aggiornamento del vettore $b$ nel corso dell'algoritmo: motivazione ed implementazione. Equivalenza con l'applicazione di MGS ad una matrice bordata col vettore dei termini noti. Versione dell'algoritmo priva di radici quadrate. Implementazione e formulazione matriciale. Matrici elementari di Gauss. Illustrazione di alcuni risultati sperimentali ottenuti confrontando i metodi QR studiati. Equivalenza numerica tra MGS e l'applicazione di Householder ad una particolare matrice aumentata. Conseguenze: MGS è stabile all'indietro. Metodi basati sulla fattorizzazione LU: l'algoritmo di Peters-Wilkinson. Cenni sul caso a rango non pieno: la fattorizzazione LU rank-revealing.

12.          Martedì 21/11/2000, 9.30-10.30.         ore: 1(18)

Calcolo della SVD. Riduzione di una matrice $A$ in forma bidiagonale superiore. Algoritmo di Golub-Reinsch, basato su trasformazioni di Householder. Algoritmo di Chan, basato su rotazioni di Givens. Confronto delle complessità computazionali dei due metodi.

13.          Lunedì 27/11/2000, 14.30-16.30.         ore: 2(20)

Algoritmo QR di Francis per il calcolo degli autovalori di una matrice. Descrizione dell'algoritmo di base. Forma di Schur. Enunciato del teorema di convergenza. Riduzione del costo computazionale: forma di Hessenberg. Convergenza in ipotesi più deboli. Condizioni di arresto e riduzione dell'ordine. Deflazione. Accelerazione del metodo mediante traslazione dello spettro. Vantaggi e semplificazioni derivanti dall'applicazione del metodo a matrici simmetriche. Cenni sul calcolo degli autovettori.

14.          Martedì 28/11/2000, 9.30-10.30.         ore: 1(21)

Algortitmo QR implicito con shift per il calcolo dei valori singolari di una matrice bidiagonale $B$ senza il calcolo esplicito di $B^TB$. Matrici irriducibili. Casi in cui si verifica una riduzione dell'ordine. Costruzione finale della decomposizione a valori singolari. Approssimazione dei valori singolari mediante spectrum slicing.

15.          Lunedì 4/12/2000, 14.30-16.30.         ore: 2(23)

(Dott. Di Fiore) Risoluzione di $A\mathbf{x}=\mathbf{c}$, $A\in\mathbb{R}^{m\times n}$, $\mathbf{c}\in\mathbb{R}^m$ ($m>n$) minimizzando una forma quadratica definita positiva $f(\mathbf{x})$. Sistemi lineari con matrice dei coefficienti $H$ definita positiva. Un esempio scaturito dalla discretizzazione di un problema differenziale e possibili tecniche di risoluzione con i metodi iterativi del Gradiente (G) e del Gradiente Coniugato (GC).

16.          Martedì 5/12/2000, 9.30-10.30.         ore: 1(24)

Algoritmo di bisezione con spectrum slicing per l'approssimazione di un singolo valore singolare. Trattamento di LSP molto mal condizionati o a rango non pieno. Rango matematico e $\delta$-rango numerico. Decomposizione a valori singolari troncata (TSVD). Regolarizzazione alla Tikhonov e confronto con la TSVD. Determinazione dei parametri di regolarizzazione $k$ e $\lambda$ mediante la curva-L.

17.          Lunedì 11/12/2000, 14.30-16.30.         ore: 2(26)

(Dott. Di Fiore) Insiemi di livello di $f$. Algoritmo di base per la minimizzazione di $f$.

18.          Giovedì 14/12/2000, 9.30-10.30.         ore: 1(27)

(Dott. Di Fiore) Il metodo G: risultati di convergenza e precondizionamento.

19.          Martedì 19/12/2000, 9.30-10.30.         ore: 1(28)

(Dott. Di Fiore) GC come metodo diretto/iterativo: tre risultati di ``convergenza'' e criteri di arresto.

20.          Lunedì 8/1/2001, 14.30-16.30.         ore: 2(30)

(Dott. Di Fiore) Ruolo dei polinomi di Chebyshev nella stima della rapiditá di convergenza di GC.

21.          Martedì 9/1/2001, 9.30-10.30.         ore: 1(31)

(Dott. Di Fiore) Precondizionamento di GC (GCP): due possibili implementazioni.

22.          Venerdì 19/1/2001, 9.30-10.30.         ore: 1(32)

(Dott. Di Fiore) Applicazione di GC e di GCP al sistema delle equazioni normali ($H=A^TA$). La proiezione di $A^TA$ sullo spazio delle matrici circolanti come possibile precondizionatore.

Totale ore: 32