REGISTRO DELLE LEZIONI DI
OTTIMIZZAZIONE
CORSO DI LAUREA MAGISTRALE IN MATEMATICA
8 CFU - A.A. 2017/2018
DOCENTE: PROF. GIUSEPPE RODRIGUEZ
ULTIMO AGGIORNAMENTO: 16. marzo 2021
1.
Martedì 6/03/2018, 9-11. ore:
2(2)
Introduzione al corso. Problemi di migliore approssimazione. Riassunto di
alcuni argomenti: problemi ben posti, prodotti scalari, norme vettoriali e
matriciali, condizionamento, aritmetica di macchina, cancellazione, metodi
diretti (fattorizzazione ) per sistemi lineari, Matlab.
2.
Giovedì 8/03/2018, 9-11. ore:
2(4)
Metodi iterativi per sistemi lineari. Vantaggi e svantaggi rispetto ai metodi
diretti. Interpolazione polinomiale e approssimazione 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.
Cenni sui problemi nonlineari. Interpretazioni alternative del prodotto
matriciale. BLAS livello 1, 2 e 3. Inner e outer products.
3.
Martedì 13/03/2018, 9-11. ore:
2(6)
Inner products e outer products: corrispondenti interpretazioni dei prodotti
vettore-vettore, matrice-vettore e matrice-matrice. Esempi. Calcolo
dell'inversa. Prodotti matriciali a blocchi. I prodotti di Hadamard e di
Kronecker. Autovalori e autovettori. Diagonalizzabilità. Il caso particolare
delle matrici Hermitiane: il teorema spettrale. Matrici ortogonali. Matrice di
adiacenza associata ad un grafo.
4.
Mercoledì 14/03/2018, 9-11. ore:
2(8)
Laboratorio Matlab. Creazione e manipolazione di matrici. Calcolo matriciale e
vettoriale. Estrazione di sottoarray. Indicizzazione con vettori di indici e
con vettori logici. Grafici 2D, 3D e visualizzazione di immagini. Esempi.
5.
Giovedì 15/03/2018, 9-11. ore:
2(10)
Fattorizzazione spettrale di una matrice Hermitiana e sua interpretazione come
outer product. Approssimazione a rango basso di una matrice Hermitiana.
Definizione di -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 . Conseguenze della presenza di errori nei termini
noti. Rumore bianco. 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.
6.
Martedì 20/03/2018, 9-11. ore:
2(12)
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. Matrice pseudo-inversa. Consistenza delle
equazioni normali. 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à.
7.
Mercoledì 21/03/2018, 9-11. ore:
2(14)
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. Il metodo di Newton per la risoluzione di un
sistema di equazioni nonlineari. Il metodo di Gauss-Newton per la risoluzione
di un problema ai minimi quadrati nonlineare. Dimostrazioni del teorema di
caratterizzazione della soluzione di un LSP.
8.
Giovedì 22/03/2018, 9-11. ore:
2(16)
Sottoinsiemi convessi di uno spazio vettoriale. Norme strettamente convesse.
Unicità della soluzione di un LSP di minima norma. Riformulazione ben-posta
di un sistema sottodeterminato a rango pieno. La soluzione normale è
ortogonale al nucleo di . 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.
9.
Martedì 27/03/2018, 9-11. ore:
2(18)
Considerazioni numeriche sul calcolo della matrice : vantaggi, svantaggi,
algoritmi. Inerzia di una matrice, legge di Sylvester. Fattorizzazione di
Cholesky: esistenza della fattorizzazione, verifica di alcuni casi particolari
e formulazione generale. Implementazione dell'algoritmo per colonne e per
righe. Complessità. Cenni sulla influenza dell'ordine di memorizzazione delle
matrici. Applicazione alla risoluzione di un problema ai minimi quadrati.
Esempi.
10.
Mercoledì 28/03/2018, 9-11. ore:
2(20)
Introduzione alla fattorizzazione QR. Principali proprietà e applicazione
alla risoluzione di un sistema lineare e di un LSP sovradeterminato.
Interpretazione come algoritmo di ortogonalizzazione. Matrici elementari di
Householder. Proprietà e algoritmo di costruzione. Possibili ottimizzazioni
della procedura di calcolo. Algoritmo di fattorizzazione QR di Householder.
Descrizione dei primi tre passi e del passo generico. Complessità. Differenze
nella fattorizzazione di una matrice quadrata e di una rettangolare.
Impostazione di un esercizio.
11.
Mercoledì 4/04/2018, 9-11. ore:
2(22)
Fattorizzazione QR di una matrice mediante il metodo di ortogonalizzazione di
Gram-Schmidt classico (CGS, presentazione di Marcello Cabboi). Ortogonalità e
indipendenza lineare. Breakdown dell'algoritmo: rilevazione di vettori
dipendenti e del rango della matrice. Fattorizzazione QR mediante il metodo di
Gram-Schmidt modificato (MGS). Cenni sull'algoritmo privo di radici quadrate e
sull'equivalenza di MGS con l'algoritmo di Householder applicato ad una matrice
aumentata. Fattorizzazione QR completa e compatta. Connessione tra MGS e
fattorizzazione di Cholesky. Cenni sulla stabilità dei metodi analizzati.
12.
Giovedì 5/04/2018, 9-11. ore:
2(24)
Riepilogo fattorizzazione QR di Householder. Rotazioni piane. Matrici
elementari di Givens. Algoritmo di fattorizzazione QR di Givens. Ottimizzazione
dell'algoritmo. Indicatori numerici di performance per la fattorizzazione QR.
Esempi numerici sul calcolo degli autovalori e su fenomeni di instabilità.
13.
Martedì 10/04/2018, 9-11. ore:
2(26)
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. Teorema spettrale come corollario al Teorema di Schur.
Matrici normali. Introduzione agli algoritmi numerici. Sottoproblemi legati al
calcolo degli autovalori. Teorema di Bauer-Fike. Il caso di una matrice
Hermitiana. Il metodo delle potenze. Ipotesi del metodo e analisi della
convergenza. Problemi numerici e normalizzazione. Criteri di stop. Mappa
strutturale dell'algoritmo. Applicazione: eigenvalue centrality di una rete non
orientata.
14.
Mercoledì 11/04/2018, 9-11. ore:
2(28)
Proiezioni ortogonali su un sottospazio: definizione, unicità. Proiezioni
ortogonali derivanti dal partizionamento per colonne di una matrice ortogonale.
Proiettori sul range di e sul nucleo di espressi mediante la matrice
pseudo-inversa e mediante la fattorizzazione QR di . Riepilogo algoritmo
MGS. Proiezioni ortogonali effettuate a ogni passo. Versione dell'algoritmo che
aggiorna il termine noto
del sistema lineare.
15.
Giovedì 12/04/2018, 9-11. ore:
2(30)
Discussione sul processo di pubblicazione degli articoli scientifici e la
valutazione bibliometrica della qualità della ricerca, delle riviste
scientifiche e degli articoli stessi. Riepilogo metodo delle potenze. Il metodo
delle potenze inverse per l'approssimazione dell'autovalore di minimo modulo.
Potenze inverse con shift dello spettro per il calcolo di altri autovalori, il
miglioramento di una stima, la determinazione dell'autovettore associato ad un
autovalore assegnato. Matrici sparse: memorizzazione ottimizzata e vantaggi
computazionali. Cenni su altre strutture algebriche che consentono un calcolo
veloce del prodotto matrice-vettore.
16.
Martedì 17/04/2018, 9-11. ore:
2(32)
Laboratorio. Sperimentazione numerica sulla risoluzione di sistemi lineari al
variare della dimensione. Grafici in scala semilogaritmica. Minimi quadrati:
risoluzione con Cholesky e QR. Sistemi sovradeterminati compatibili e
incompatibili. Costruzione di un termine noto con una componente ortogonale
all'immagine della matrice e con residuo assegnato. Introduzione del noise nel
termine noto. Ottimizzazione del codice relativamente all'uso della memoria.
17.
Mercoledì 18/04/2018, 9-11. ore:
2(34)
Dimostrazione del Teorema di Bauer-Fike. Forma normale di Jordan. Blocchi e
catene di Jordan. Autovettori generalizzati. Molteplicità algebrica e
geometrica di un autovettore. Esempi. Formulazione del problema di migliore
approssimazione in uno spazio di Hilbert. Teorema di caratterizzazione della
migliore approssimazione. Sua interpretazione in
e in
.
18.
Giovedì 19/04/2018, 9-11. ore:
2(36)
Matrice compagna associata ad un polinomio monico. Calcolo delle radici del
polinomio come autovalori della matrice compagna. Algoritmo QR per il calcolo
degli autovalori. Invarianti per trasformazioni QR: similitudine, simmetria.
Costruzione della forma di Schur e, per una matrice simmetrica, della
fattorizzazione spettrale. Matrici di fase. Teorema di convergenza e
rilassamento delle ipotesi. Riduzione del costo computazionale: passaggio in
forma di Hessenberg e uso di trasformazioni di Givens. Accelerazione della
convergenza mediante shift dello spettro.
19.
Martedì 24/04/2018, 9-11. ore:
2(38)
Riepilogo algoritmo QR. Algoritmo per portare una matrice quadrata in forma di
Hessenberg attraverso trasformazioni di similitudine. 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.
Decomposizione di una matrice come somma di matrici a rango uno.
Approssimazioni a rango basso e principal component analysis.
20.
Giovedì 26/04/2018, 9-11. ore:
2(40)
Riepilogo SVD. Esempi numerici sul calcolo della SVD. Legame tra la SVD e la
fattorizzazione spettrale di e . Possibile algoritmo di calcolo e
sue condtroindicazioni numeriche. Identificazione mediante i vettori singolari
dei quattro sottospazi fondamentali di una matrice. Proprietà di
ortogonalità che li lega. Soluzione generale di un sistema omogeneo. Il caso
particolare di rango e cenni sull'applicazione alla camera
calibration.
21.
Mercoledì 2/05/2018, 9-11. ore:
2(42)
Dimostrazione dell'esistenza della SVD (presentazione di Vincenzo Solinas).
Migliore approssimazione in uno spazio di Hilbert. Sistema delle equazioni
normali. Matrice di Gram. Momenti e coefficienti di Fourier. Polinomio di
migliore approssimazione in . La matrice di Hilbert. Serie di
Fourier. Importanza dell'ortogonalità delle funzioni di base.
22.
Giovedì 3/05/2018, 9-11. ore:
2(44)
Soluzione di un sistema quadrato non singolare mediante SVD. Osservazioni sulla
propagazione degli errori. Cenni sulla soluzione regolarizzata di un sistema
malcondizionato mediante la TSVD. 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. Introduzione al problema dello
shape from shading della computer vision.
23.
Martedì 8/05/2018, 9-11. ore:
2(46)
Applicazione nella computer vision: la tecnica del photometric stereo.
Ricostruzione di modelli 3D a partire da immagini. La legge di Lambert:
formulazione scalare e matriciale. che consente di determinare il campo
normale. Discussione sul numero minimo di immagini necessarie per la
risoluzione del problema. Ruolo della matrice pseudoinversa, sotto l'ipotesi
che sia nota la posizione delle fonti di illuminazione. Cenni sui modelli
differenziali associati al problema e sulla loro risoluzione numerica.
Costruzione di fattorizzazioni a rango fissato mediante la SVD. Illustrazione
di risultati sperimentali.
24.
Mercoledì 9/05/2018, 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à. Esempio: costruzione di una formula a due punti per un peso
particolare. Formule a precisione ottimale. Polinomi ortogonali. Costruzione di
una base di polinomi ortogonali monici mediante il metodo di Gram-Schmidt.
25.
Giovedì 10/05/2018, 9-11. ore:
2(50)
Laboratorio. Sperimentazione sulla fattorizzazione QR. Costruzione ottimizzata
di una matrice elementare di Householder. Implementazione dell'algoritmo di
fattorizzazione in forma standard. Ottimizzazione successiva del programma.
Verifica dell'accuratezza della fattorizzazione e osservazione del
miglioramento nella complessità computazionale.
26.
Martedì 15/05/2018, 9-11. ore:
2(52)
Relazione tra la norma-2 e la norma di Frobenius di una matrice e i suoi valori
singolari. Approssimazione di una matrice mediante ls SVD troncata e
espressione dell'errore di approssimazione. Teorema di Weyl e sua
dimostrazione. Teorema di Courant-Fisher. Dimostrazione della stabilità dei
valori singolari. Migliore approssimazione di una matrice con una matrice a
rango fissato, nella norma 2 e nella norma di Frobenius. Risultati di
stabilità per la pseudoinversa. Espressione del numero di condizionamento di
una matrice mediante i valori singolari. Condizionamento di un problema ai
minimi quadrati.
27.
Mercoledì 16/05/2018, 9-11. ore:
2(54)
Riepilogo formule di ricorrenza per polinomi ortogonali. Proprietà dei
polinomi ortogonali: radici, matrice di interpolazione. Formule di quadratura
Gaussiane: calcolo di nodi e pesi. Matrice di Jacobi associata ai polinomi.
Famiglie di polinomi ortogonali classici. Dimostrazione del teorema sulla
precisione algebrica e l'ottimalità delle formule Gaussiane.
28.
Giovedì 17/05/2018, 9-11. ore:
2(56)
Schema dell'algoritmo di Golub-Reinsch per il calcolo della SVD: passaggio in
forma bidiagonale e applicazione implicita dell'algoritmo QR. Riepilogo sui
metodi iterativi per sistemi lineari. Vantaggi rispetto ai metodi diretti.
Criteri di stop. Precondizionamento e proprietà connesse. Metodi di
Richardson. Fattorizzazione LU incompleta. Cenni su un'applicazione: problema
ai minimi quadrati nonlineare derivante dall'inversione di dati
elettromagnetici in geofisica applicata.
29.
Martedì 22/05/2018, 9-11. ore:
2(58)
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. Implementazione del
precondizionamento. Ottimalità di un punto rispetto ad una direzione.
Condizione necessaria e sufficiente per l'ottimalità. Direzioni coniugate.
30.
Giovedì 24/05/2018, 9-11. ore:
2(60)
Riepilogo metodo del gradiente, ottimalità di un punto rispetto ad una
direzione, direzioni coniugate. Determinazione di direzioni coniugate 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.
31.
Martedì 29/05/2018, 9-11. ore:
2(62)
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.
32.
Giovedì 31/05/2018, 9-11. ore:
2(64)
Applicazione implicita del gradiente coniugato alle equazioni normali: il
metodo CGLS. Riepilogo metodi di Krylov. 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 non simmetriche e l'iterazione di Golub-Kahan per matrici
rettangolari.
Totale ore: 64
Giuseppe Rodriguez
rodriguez@unica.it