REGISTRO DELLE LEZIONI DI
MATEMATICA COMPUTAZIONALE

CORSO DI LAUREA MAGISTRALE IN INFORMATICA
6
CFU - A.A. 2016/2017
DOCENTE: PROF. GIUSEPPE RODRIGUEZ
ULTIMO AGGIORNAMENTO:
30. maggio 2017

1.          Lunedì 6/03/2017, 9-11.         ore: 2(2)

Introduzione al corso. Riassunto di alcuni argomenti: problemi ben posti, condizionamento, metodi diretti (fattorizzazione $ PA=LU$) e iterativi per sistemi lineari, Matlab. Interpolazione polinomiale e approssimazione di dati affetti da errori.

2.          Martedì 7/03/2017, 9-11.         ore: 2(4)

Riepilogo aritmetica di macchina. Condizionamento delle operazioni aritmetiche, cancellazione. Approssimazione polinomiale di dati affetti da errori sperimentali. Formulazione del problema ai minimi quadrati e del problema algebrico corrispondente. Approssimazione ai minimi quadrati mediante una somma di esponenziali. Esempio: decadimento di un materiale radioattivo. Problemi nonlineari.

3.          Lunedì 13/03/2017, 9-11.         ore: 2(6)

Interpretazioni alternative del prodotto matriciale. BLAS livello 1, 2 e 3. Inner products e outer products: corrispondenti interpretazioni dei prodotti vettore-vettore, matrice-vettore e matrice-matrice. Calcolo dell'inversa. Prodotti matriciali a blocchi. Autovalori e autovettori di matrici Hermitiane: il teorema spettrale. Matrici ortogonali. Matrice di adiacenza associata ad un grafo.

4.          Martedì 14/03/2017, 9-11.         ore: 2(8)

Utilizzazione del subindexing in Matlab. Fattorizzazione spettrale di una matrice Hermitiana e sua interpretazione come outer product. Approssimazione a rango basso di una matrice Hermitiana. Definizione di $ \epsilon$-rango. Applicazione alla principal component analysis e all'analisi di reti complesse. Significato delle potenze della matrice di adiacenza di una rete. Sistemi lineari quadrati, sovradeterminati e sottodeterminati, a rango pieno. Interpretazione mediante il sottospazio generato dalle colonne di $ A$. Conseguenze della presenza di errori nei termini noti. Rumore bianco.

5.          Lunedì 20/03/2017, 9-11.         ore: 2(10)

Sistemi lineari rettangolari: il caso a rango non pieno. Sistemi quadrati singolari. Il range (immagine) e il nucleo (spazio nullo) di una matrice, vista come operatore lineare. Sistemi sovradeterminati a rango pieno: formulazione del problema ai minimi quadrati (LSP). Calcolo del gradiente di alcune funzioni vettoriali. Risoluzione di un LSP mediante il sistema delle equazioni normali. Cenni sull'algoritmo di risoluzione.

6.          Martedì 21/03/2017, 9-11.         ore: 2(12)

Matrice pseudo-inversa. Risoluzione delle equazioni normali con la fattorizzazione di Cholesky. Introduzione alla fattorizzazione QR. Risoluzione di un LSP mediante la fattorizzazione QR. Caratterizzazione delle soluzioni di un LSP. Decomposizione di uno spazio come somma diretta di sottospazi ortogonali. Significato geometrico della condizione di ortogonalità. Consistenza delle equazioni normali. Problema LSP duale per sistemi sottodeterminati. Interpretazione della soluzione di minima norma.

7.          Lunedì 27/03/2017, 9-11.         ore: 2(14)

Formulazione primale e duale di un LSP. Metodo dei moltiplicatori di Lagrange. Equazioni normali del secondo tipo. Matrice pseudoinversa per un sistema sottodeterminato a rango pieno. Sperimentazione numerica in Matlab sulla risoluzione di sistemi sovradeterminati e sottodeterminati.

8.          Martedì 28/03/2017, 9-11.         ore: 2(16)

Riepilogo su autovalori e autovettori: polinomio caratteristico, calcolo di autovalori e autovettori, molteplicità algebrica e geometrica, quoziente di Rayleigh. Matrici simili. Diagonalizzabilità. Fattorizzazione spettrale. Forma canonica di Schur. Introduzione agli algoritmi numerici. Problemi parziali che riguardano gli autovalori. Stabilità: il teorema di Bauer-Fike. Il caso delle matrici Hermitiane. Esempi numerici di instabilità.

9.          Lunedì 3/04/2017, 9-11.         ore: 2(18)

Il metodo delle potenze. Ipotesi del metodo e analisi della convergenza. Problemi numerici e normalizzazione. Criterio di stop. Implementazione dell'algoritmo e sua ottimizzazione. Vantaggi dei metodi iterativi. Matrici sparse: memorizzazione e ottimizzazione dei calcoli. Applicazione: eigenvector centrality. Definizione in termini di autovettore principale. Definizione operativa come procedimento iterativo. Esempi numerici.

10.          Martedì 4/04/2017, 9-11.         ore: 2(20)

Decomposizione ai valori singolari (SVD). Forma della fattorizzazione per matrici di diverse dimensioni e a rango non pieno. Forma compatta. Vettori singolari destri e sinistri. Sistema singolare come generalizzazione di autovalori e autovettori. Relazione con la fattorizzazione spettrale di $ A^*A$ e di $ AA^*$. Possibile algoritmo di calcolo. Decomposizione di una matrice come somma di matrici a rango uno. Approssimazioni a rango basso e principal component analysis.

11.          Lunedì 10/04/2017, 9-11.         ore: 2(22)

Riepilogo SVD. Caratterizzazione dei quattro sottospazi fondamentali di una matrice mediante il sistema singolare. Relazione di ortogonalità tra i sottospazi. Soluzione di un sistema singolare. Norma-2 e numero di condizionamento di una matrice. Stabilità di valori singolari. Migliore approssimazione di una matrice in norma-2 e in norma di Frobenius. Soluzione di un sistema quadrato non singolare mediante SVD. Osservazioni sulla propagazione degli errori. Prime considerazioni sulla rappresentazione della pseudoinversa.

12.          Martedì 11/04/2017, 9-11.         ore: 2(24)

Soluzione di un problema ai minimi quadrati mediante la SVD. Rappresentazione generale della matrice pseudoinversa. Confronto con la rappresentazioni particolari ricavate nelle precedenti lezioni. Alcune proprietà della pseudoinversa. Fattorizzazione QR in forma generale e compatta. Relazione tra i sistemi singolari di $ A$ e di $ R$. Soluzione di un LSP primale e duale mediante la fattorizzazione QR.

13.          Martedì 2/05/2017, 9-11.         ore: 2(26)

Applicazione nella computer vision: la tecnica del photometric stereo per ricostruire la forma di un oggetto a partire da fotografie ottenute con diverse illuminazioni. Formulazione matematica. Ruolo della matrice pseudoinversa. Fattorizzazione di Cholesky: calcolo di alcune componenti della matrice fattore.

14.          Lunedì 8/05/2017, 9-11.         ore: 2(28)

Iterazione generale della fattorizzazione di Cholesky. Verifica di alcuni casi particolari e risoluzione di un esercizio. Implementazione dell'algoritmo per colonne e per righe. Cenni sulla influenza dell'ordine di memorizzazione delle matrici. Applicazione alla risoluzione di un sistema e di un problema ai minimi quadrati. Complessità risultante. Matrici elementari di Householder. Proprietà e algoritmo di costruzione.

15.          Lunedì 8/04/2017, 9-11.         ore: 2(30)

Iterazione generale della fattorizzazione di Cholesky. Verifica di alcuni casi particolari e risoluzione di un esercizio. Implementazione dell'algoritmo per colonne e per righe. Cenni sulla influenza dell'ordine di memorizzazione delle matrici. Applicazione alla risoluzione di un sistema e di un problema ai minimi quadrati. Complessità risultante. Matrici elementari di Householder. Proprietà e algoritmo di costruzione.

16.          Martedì 9/05/2017, 9-11.         ore: 2(32)

Riepilogo costruzione delle matrici elementari di Householder. Possibili ottimizzazioni della procedura di calcolo. Algoritmo di fattorizzazione QR di Householder. Descrizione dei primi due passi e del passo generico. Differenze nella fattorizzazione di una matrice quadrata e di una rettangolare. Impostazione di un esercizio.

17.          Venerdì 12/05/2017, 15-17.         ore: 2(34)

Laboratorio. Costruzione di una sperimentazione numerica per il metodo di Cholesky: matrice definita positiva di dimensione assegnata, sistema lineare con soluzione fissata. Implementazione del metodo di Cholesky. Differenze tra uno script e una function. Confronto dei risultati e del tempo di esecuzione con l'algoritmo di Matlab. Ottimizzazione dell'algoritmo. Subindexing e operazioni matriciali. Soluzione di un sistema malcondizionato: la matrice di Hilbert.

18.          Lunedì 15/04/2017, 9-11.         ore: 2(36)

Esercizio sulla fattorizzazione QR di Householder. Rotazioni piane. Matrici elementari di Givens. Algoritmo di fattorizzazione QR di Givens. Ottimizzazione dell'algoritmo. Esercizio sulla fattorizzazione QR di Givens. Cenni sull'algoritmo QR per il calcolo degli autovalori.

19.          Martedì 16/05/2017, 9-11.         ore: 2(38)

Algoritmo QR per il calcolo degli autovalori. Invarianti: similitudine, simmetria, forma di Hessenberg. Ipotesi di convergenza. Comportamento dell'algoritmo in caso di non convergenza. Calcolo della forma di Schur. Il caso particolare delle matrici simmetriche: fattorizzazione spettrale. Passaggio in forma di Schur. Cenni sull'algoritmo di Golub-Reinsch per il calcolo della SVD. Generalità sui metodi iterativi. Vantaggi rispetto ai metodi diretti. Criteri di stop.

20.          Venerdì 19/05/2017, 15-17.         ore: 2(40)

Laboratorio. Costruzione di una matrice elementare di Householder. Implementazione dell'algoritmo di fattorizzazione QR di Householder. Verifica del funzionamento dell'algoritmo su problemi modello: sistema lineare quadrato e problema ai minimi quadrati sovradeterminato.

21.          Lunedì 22/05/2017, 9-11.         ore: 2(42)

Introduzione ai metodi iterativi di massima discesa per sistemi con matrice simmetrica definita positiva. Determinazione del passo ottimale. Il metodo del gradiente. Ottimizzazione del calcolo del residuo. Test di convergenza. Algoritmo. Convergenza lenta del metodo. Significato del precondizionamento. Fattorizzazione di Cholesky incompleta. Implementazione del precondizionamento.

22.          Martedì 23/05/2017, 9-11.         ore: 2(44)

Riepilogo metodo del gradiente precondizionato. Ottimalità di un punto rispetto ad una direzione. Direzioni coniugate e loro determinazione a partire dal residuo. Il metodo del gradiente coniugato. Aggiornamento del residuo. Schema dell'algoritmo e ottimizzazione dei calcoli. Precondizionamento. Metodi di proiezione in spazi di Krylov. Conseguenze del breakdown del metodo. Il metodo del gradiente coniugato come metodo di Krylov. Condizione di ottimalità verificata dalla generica iterazione.

23.          Venerdì 26/05/2017, 15-17.         ore: 2(46)

Laboratorio. Memorizzazione, uso e visualizzazione delle matrici sparse in Matlab. Creazione di un sistema lineare test con matrice sparsa simmetrica definita positiva. Sintassi di chiamata della funzione pcg, che implementa il metodo del gradiente coniugato. Costruzione di un precondizionatore mediante fattorizzazione di Cholesky incompleta e suo uso nella funzione pcg. Sperimentazione numerica al variare di alcuni parametri. Implementazione del metodo del gradiente coniugato.

24.          Lunedì 29/05/2017, 9-11.         ore: 2(48)

Decomposizione parziale di Lanczos per una matrice simmetrica. Costruzione dell'algoritmo. Possibile breakdown dell'algoritmo e cenni sulla riortogonalizzazione. Risoluzione di un sistema lineare col metodo di Lanczos. Approssimazione degli autovalori estremali di una matrice simmetrica. Idea alla base dei metodi di proiezione. Cenni su alcune generalizzazioni del metodo di Lanczos: l'iterazione di Arnoldi per matrici quadrate nonsimmetriche e l'iterazione di Golub-Kahan per matrici rettangolari.

Totale ore: 48



Giuseppe Rodriguez
rodriguez@unica.it