REGISTRO DELLE LEZIONI DI
OTTIMIZZAZIONE

CORSO DI LAUREA MAGISTRALE IN MATEMATICA
8
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.          Giovedì 9/03/2017, 9-11.         ore: 2(6)

Laboratorio Matlab. Creazione e manipolazione di matrici. Calcolo matriciale e vettoriale. Estrazione di sottoarray. Grafici 2D. Cenni sul sistema handle graphics.

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

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.

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

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.

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

Presentazione di Gabriele Stocchino sulla ricostruzione di oggetti 3D mediante photometric stereo. Descrizione dei modelli differenziali associati al problema. Relazione matriciale che consente di determinare il campo normale. Illustrazione di risultati sperimentali. Applicazioni della tecnica del photometric stereo.

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

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.

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

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.

9.          Giovedì 23/03/2017, 9-11.         ore: 2(18)

Media e varianza di vettori di variabili aleatorie. Trasformazioni lineari tra vettori aleatori. Modello statistico lineare standard. Stimatori unbiased di minima varianza (BLUE). Teorema di Gauss-Markov. Media e varianza della soluzione dei minimi quadrati. Dimostrazioni del teorema di caratterizzazione della soluzione di un LSP.

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

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.

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

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à.

12.          Giovedì 30/03/2017, 9-11.         ore: 2(24)

Proiezioni ortogonali su un sottospazio. Proiettori sul range di $ A$ e sul nucleo di $ A^T$. Norme strettamente convesse. Unicità della soluzione di minima norma. Sistema aumentato che caratterizza sia il problema primale che il duale. Forma canonica di Jordan. Blocchi e catene di Jordan. Rilevamento della presenza di autovettori difettivi e della loro molteplicità geometrica.

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

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.

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

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.

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

Matrici normali e matrici unitariamente diagonalizzabili. Dimostrazione del Teorema di Bauer-Fike. Errori assoluti e relativi. La matrice di Hilbert. Il metodo delle potenze inverse. Potenze inverse con traslazione dello spettro. Problemi parziali che possono essere risolti col metodo delle potenze. Creazione di problemi agli autovalori test, da utilizzare in una sperimentazione numerica. Matrice compagna associata ad un polinomio. Calcolo delle radici di un polinomio.

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

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.

17.          Martedì 11/04/2017, 9-11.         ore: 2(34)

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.

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

Dimostrazione dell'esistenza della SVD (presentazione di Federica Pes). Decomposizione polare di una matrice. SVD troncata e espressione dell'errore di approssimazione. Enunciato del Teorema di Weyl. Teorema di Courant-Fisher. Dimostrazione della stabilità dei valori singolari.

19.          Giovedì 27/04/2017, 9-11.         ore: 2(38)

Dimostrazione del teorema di Weyl (presentazione di Tatiana Selloni). Migliore approssimazione di una matrice con una matrice a rango fissato, nella norma 2 e nella norma di Frobenius. Espressione della pseudoinversa mediante la SVD. Le condizioni di Penrose. Introduzione alla migliore approssimazione di un elemento di uno spazio di Hilbert mediante un elemento di un sottospazio. Prodotti scalari standard e pesati. Significato applicativo del prodotto scalare di $ L^2[a,b]$.

20.          Martedì 2/05/2017, 9-11.         ore: 2(40)

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.

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

Fattorizzazione QR di una matrice mediante il metodo di ortogonalizzazione di Gram Schmidt classico, e mediante quello modificato (presentazione di Chiara Leo). Migliore approssimazione in uno spazio di Hilbert. Teorema di caratterizzazione della soluzione. Interpretazione in $ {\mathbb{R}}^n$. Sistema delle equazioni normali. Matrice di Gram. Momenti e coefficienti di Fourier. Polinomio di migliore approssimazione in $ L^2[0,1]$. La matrice di Hilbert. Importanza dell'ortogonalità delle funzioni di base.

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

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.

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

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.

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

Momenti e coefficienti di Fourier. Importanza dell'ortogonalità delle funzioni di base. Generalità sulle formule di quadratura. Precisione algebrica, formule interpolatorie. Funzioni peso ed integrali con singolarità. Formule a precisione ottimale. Polinomi ortogonali. Costruzione di una base di polinomi ortogonali monici mediante il metodo di Gram-Schmidt.

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

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.

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

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.

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

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.

28.          Giovedì 18/05/2017, 9-11.         ore: 2(56)

Riepilogo formule di ricorrenza per polinomi ortogonali. Proprietà dei polinomi ortogonali: radici, matrice di interpolazione. Formule di quadratura Gaussiane. Dimostrazione del teorema sulla precisione algebrica e l'ottimalità delle formule Gaussiane (presentazione di Maria Lucia Pilo). Calcolo dei pesi e dei nodi delle formule. Matrice di Jacobi associata ai polinomi. Famiglie di polinomi ortogonali classici.

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

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.

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

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.

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

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.

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

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.

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

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: 66



Giuseppe Rodriguez
rodriguez@unica.it