REGISTRO DELLE LEZIONI DI
ALGORITMI NUMERICI E APPLICAZIONI - COMPUTATIONAL MATHEMATICS
CORSO DI LAUREA MAGISTRALE IN MATEMATICA E IN INFORMATICA
9 CFU - A.A. 2023/2024
DOCENTE: PROF. GIUSEPPE RODRIGUEZ
ULTIMO AGGIORNAMENTO: 25. giugno 2024
1.
Lunedì 4/03/2024, 9–11. ore:
2(2)
Il gruppo di Analisi Numerica e i corsi attivi del settore MAT/08. Problemi ben
posti. Numero di condizionamento assoluto e relativo di un problema. Riepilogo
aritmetica di macchina.
2.
Martedì 5/03/2024, 11–13. ore:
2(4)
Modelli matematici e modelli numerici. Problemi diretti, inversi e di
identificazione. Propagazione degli errori nei calcoli. Condizionamento delle
operazioni aritmetiche, cancellazione. 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.
3.
Giovedì 7/03/2024, 9–11. ore:
2(6)
Opportunità di tesi e tirocinio presso il gruppo CaNA. Calcolo matriciale e
BLAS livello 1, 2 e 3. Inner products e outer products: definizioni e
corrispondenti interpretazioni dei prodotti vettore-vettore e matrice-vettore.
Prodotti matrice-vettore a blocchi. Esempi: proiezione di un vettore su una
base, combinazione lineare. Prodotti matriciali: inner e outer product, per
righe e per colonne a blocchi. Varie interpretazioni. Matrici di Gram. Calcolo
della matrice inversa: vari approcci e confronto della complessità
computazionale.
4.
Lunedì 11/03/2024, 9–11. ore:
2(8)
Riepilogo BLAS. Calcolo della matrice inversa. Esempi: basi ortonormali e
matrici ortogonali. Rappresentazione di un vettore in una base ortogonale e
non. I prodotti di Hadamard e di Kronecker. Autovalori e autovettori.
Diagonalizzabilità. Il caso particolare delle matrici Hermitiane: il teorema
spettrale. Fattorizzazione spettrale di una matrice Hermitiana e sua
interpretazione come outer product. Approssimazione a rango basso di una
matrice Hermitiana. Matrice di adiacenza associata ad un grafo. Applicazione
alla principal component analysis.
5.
Martedì 12/03/2024, 11–13. ore:
2(10)
Calcolo delle potenze di una matrice mediante la sua fattorizzazione spettrale
e corrispondente approssimazione spettrale a rango basso. Calcolo di funzioni
di matrice. Cenni sull'applicazione all'analisi di reti complesse. Applicazione
nella computer vision: la tecnica del photometric stereo. Ricostruzione di
immagini a partire da modelli 3D (problema diretto). La legge di Lambert:
formulazione scalare e matriciale per determinare il campo normale.
Implementazione mediante ordinamento lessicografico dei vettori normali.
Illustrazione di un programma Matlab che effettua il calcolo. Sistemi lineari
quadrati, sovradeterminati e sottodeterminati a rango pieno.
6.
Giovedì 14/03/2024, 9–11. ore:
2(12)
Interpretazione dei sistemi sovradeterminati e sottodeterminati, a rango pieno.
mediante il sottospazio generato dalle colonne di . Conseguenze della
presenza di errori nei termini noti. Condizionamento di un sistema lineare
quadrato non singolare. Sistemi lineari rettangolari: il caso a rango non
pieno. Sistemi quadrati singolari. Cenni storici. Sistemi sovradeterminati a
rango pieno: formulazione del problema ai minimi quadrati (LSP). Sottospazi
fondamentali: il range (immagine) e il nucleo (spazio nullo) di una matrice,
vista come operatore lineare. Interpretazione del teorema dell'alternativa di
Fredholm. Calcolo del gradiente di alcune funzioni vettoriali. Risoluzione di
un LSP mediante il sistema delle equazioni normali.
7.
Lunedì 18/03/2024, 9–11. ore:
2(14)
Risoluzione di un LSP mediante il sistema delle equazioni normali. Matrice
pseudo-inversa. La matrice del sistema è definita positiva. Risoluzione delle
equazioni normali con la fattorizzazione di Cholesky. Riepilogo proprietà
matrici ortogonali e numero di condizionamento. Introduzione alla
fattorizzazione QR. Risoluzione di un LSP mediante la fattorizzazione QR.
Complessità e confronto con le equazioni normali. Media e varianza di vettori
di variabili aleatorie. Trasformazioni lineari tra vettori aleatori. Modello
statistico lineare standard. Rumore bianco. Stimatori unbiased di minima
varianza (BLUE).
8.
Martedì 19/03/2024, 11–13. ore:
2(16)
Teorema di Gauss-Markov. Media e varianza della soluzione dei minimi quadrati.
Caratterizzazione delle soluzioni di un LSP. Consistenza delle equazioni
normali. Decomposizione di uno spazio come somma diretta di sottospazi
ortogonali e relative proprietà per la soluzione dei minimi quadrati.
Significato geometrico della condizione di ortogonalità. Proiettori
ortogonali e proprietà. Proiettori su e indotti dalla
soluzione dei minimi quadrati nel caso sovradeterminato a rango pieno.
Soluzioni di minima norma. La soluzione normale è ortogonale al nucleo di
. Sottoinsiemi convessi di uno spazio vettoriale. Norme strettamente
convesse.
9.
Venerdì 22/03/2024, 11–13. ore:
2(18)
Riepilogo caratterizzazione delle soluzioni dei minimi quadrati. Sottoinsiemi
convessi di uno spazio vettoriale. Norme strettamente convesse. Unicità della
soluzione di un LSP di minima norma. Dimostrazione che la norma indotta in uno
spazio di Hilberti è sempre strettamente convessa. Riformulazione ben-posta
di un sistema sottodeterminato a rango pieno. Formulazione primale e duale di
un LSP. Equazioni normali del secondo tipo. Matrice pseudoinversa per un
sistema sottodeterminato a rango pieno. Riepilogo risoluzione di sistemi
sovradeterminati e sottodeterminati a rango pieno.
10.
Lunedì 25/03/2024, 9–11. ore:
2(20)
Riepilogo problema primale e duale ai minimi quadrati. Considerazioni numeriche
sul calcolo della matrice : vantaggi, svantaggi, algoritmi,
complessità. Implementazione come inner product e come outer product. Cenni
sulla stabilità all'indietro: il Teorema di Wilkinson. Inerzia di una
matrice, legge di Sylvester. Fattorizzazione di Cholesky: esistenza della
fattorizzazione, calcolo di alcuni elementi del fattore. Verifica di alcuni
casi particolari e formulazione generale. Implementazione dell'algoritmo per
colonne. Complessità. Cenni sull'implementazione dell'algoritmo per righe.
Applicazione alla risoluzione di un problema ai minimi quadrati.
L1.
Martedì 26/03/2024, 11–12. ore:
1(1)
Laboratorio Esperimenti numerici sui minimi quadrati in Matlab: risoluzione del problema
primale e duale con vari metodi. Confronto tra le soluzioni ottenute.
Costruzione di un problema test con soluzione assegnata.
11.
Martedì 26/03/2024, 12–13. ore:
1(21)
Introduzione alla fattorizzazione QR. Principali proprietà: conservazione del
della norma-2 e del numero di condizionamento. Uso della fattorizzazione QR
nella risoluzione di un sistema quadrato. Confronto con l'algoritmo di Gauss.
Matrici elementari di Householder e principali proprietà.
12.
Giovedì 4/04/2024, 9–11. ore:
2(23)
Esercizio sulla fattorizzazione di Cholesky. Riepilogo fattorizzazione QR.
Fattorizzazione QR completa e compatta. Proiettori ortogonali indotti dalla
fattorizzazione QR. Matrici elementari di Householder. Proprietà e algoritmo
di costruzione. Possibili ottimizzazioni della procedura di calcolo. Algoritmo
di fattorizzazione QR di Householder. Descrizione del primo passo.
13.
Lunedì 8/04/2024, 9–11. ore:
2(25)
Riepilogo matrici elementari di Householder. Algoritmo di fattorizzazione QR di
Householder. Descrizione dei primi tre passi. Descrizione del passo generico.
Differenze nella fattorizzazione di una matrice quadrata e di una rettangolare.
Complessità. Ottimizzazione dell'algoritmo. Rotazioni piane. Matrici
elementari di Givens e loro costruzione e applicazione ottimizzata. Algoritmo
di fattorizzazione QR di Givens. Complessità.
14.
Martedì 9/04/2024, 11–13. ore:
2(27)
Riepilogo fattorizzazioni QR di Householder e Givens. Esempio: applicazione dei
due metodi di ad una matrice . Ottimizzazione dell'algoritmo di
costruzione delle matrici elementari di Givens. Algoritmo di
ortonormalizzazione di Gram–Schmidt classico (CGS). Metodo di Gram–Schmidt
modificato (MGS). Fattorizzazioni QR risultanti da CGS e MGS.
L2.
Giovedì 11/04/2024, 11–13. ore:
2(3)
Laboratorio Sperimentazione sulla fattorizzazione QR. Costruzione ottimizzata di una
matrice elementare di Householder. Programmazione Matlab mediante
scripts e functions. Implementazione dell'algoritmo di
fattorizzazione in forma standard. Cenni sull'ottimizzazione del programma e
sul conseguente miglioramento nella complessità computazionale. Verifica
dell'accuratezza della fattorizzazione. Sperimentazione numerica al variare
della dimensione.
15.
Lunedì 15/04/2024, 9–11. ore:
2(29)
Riepilogo MGS e fattorizzazione QR risultante. Riepilogo fattorizzazioni QR e
loro utilizzazione. Risultati numerici sull'uso della fattorizzazione QR.
Riepilogo su
autovalori e autovettori. Polinomio caratteristico, calcolo teorico di
autovalori e autovettori. Matrici simili e unitariamente simili.
Diagonalizzabilità. Fattorizzazione spettrale. Matrici difettive. Forma
canonica di Schur. Teorema spettrale come corollario al Teorema di Schur.
Matrici normali. Forma canonica di Jordan. Blocchi e catene di Jordan.
16.
Martedì 16/04/2024, 11–13. ore:
2(31)
Forma canonica di Jordan. Autovettori generalizzati, generatori e catene di
Jordan. Molteplicità algebrica e geometrica. Matrici riducibili. Vantaggi
della riducibilità per la risoluzione di sistemi lineari e il calcolo di
autovalori. Caratterizzazione delle matrici irriducibili. Grafo orientato
associato ad una matrice. Grafi fortemente connessi. Legame con
l'irriducibilità. Esempi. Localizzazione di autovalori. Cerchi riga e cerchi
colonna. Primo teorema di Gershgorin.
17.
Mercoledì 17/04/2024, 11–13. ore:
2(33)
Corollari al primo teorema di Gershgorin. Secondo teorema. Terzo teorema.
Esempi e applicazioni. Matrici diagonalmente dominanti. Introduzione agli
algoritmi numerici. Sottoproblemi legati al calcolo degli autovalori. Esempi
numerici di instabilità.
18.
Giovedì 18/04/2024, 9–11. ore:
2(35)
Teorema di Bauer–Fike. Il caso di una matrice Hermitiana. Spiegazione
dell'instabilità osservata in alcuni esempi numerici. Il metodo delle
potenze. Ipotesi del metodo e analisi della convergenza. Problemi numerici e
normalizzazione. Rilassamento delle ipotesi di convergenza. Criteri di stop.
Implementazione dell'algoritmo e sua ottimizzazione.
19.
Lunedì 29/04/2024, 9–11. ore:
2(37)
Riepilogo del 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: vantaggi computazionali. Cenni su altre matrici strutturate.
Matrice compagna associata ad un polinomio monico e calcolo delle radici di un
polinomio come autovalori della matrice compagna. Database utilizzati nella
classificazione degli articoli scientifici. Metriche di valutazione. Il
processo di pubblicazione di un articolo. Applicazione: eigenvalue centrality
di una rete non orientata. Algoritmo QR per il calcolo degli autovalori.
Invarianti per trasformazioni QR: similitudine, simmetria.
20.
Martedì 30/04/2024, 11–13. ore:
2(39)
Riepilogo algoritmo QR per il calcolo degli autovalori. Costruzione della forma
di Schur e, per una matrice simmetrica, della fattorizzazione spettrale.
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.
Decomposizione ai valori singolari (SVD). Esistenza della fattorizzazione.
L3.
Giovedì 2/05/2024, 11–13. ore:
2(5)
Laboratorio Costruzione di vari problemi agli autovalori con soluzione assegnata.
Implememntazione del metodo delle potenze per determinare l'autovalore di
massimo modulo di una matrice e l'autovettore corrispondente. Sperimentazione
numerica al variare della molteplicità dell'autovalore principale e della
dimensione della matrice. Costruzione di un esempio con matrice sparsa e
sperimentazione sull'influenza della sparsità sul tempo di calcolo e
l'occupazione di memoria.
21.
Lunedì 6/05/2024, 9–11. ore:
2(41)
Riepilogo SVD. Decomposizione ai valori singolari (SVD) completa e compatta.
Valori singolari e vettori singolari destri e sinistri. Decomposizione di una
matrice come somma di matrici a rango uno. Approssimazioni a rango basso e
principal component analysis. Sistema singolare come generalizzazione di
autovalori e autovettori. SVD di una matrice Hermitiana. Forma della
fattorizzazione per matrici di diverse dimensioni e a rango non pieno. Legame
tra la SVD e la fattorizzazione spettrale di e . Possibile
algoritmo di calcolo e sue controindicazioni numeriche. Rappresentazione dei
quattro sottospazi fondamentali di una matrice mediante i vettori singolari.
Relazioni tra i sottospazi.
22.
Martedì 7/05/2024, 11–13. ore:
2(43)
Riepilogo SVD e sottospazi fondamentali. Soluzione di un sistema quadrato non
singolare mediante SVD. Osservazioni sulla propagazione degli errori. Problemi
fisici che generano modelli malposti e sistemi malcondizionati. Corrispondente
comportamento dei valori singolari e dei vettori singolari. 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. Pseudo inversa e condizioni di
Penrose. Inverse generalizzate. Proprietà della pseudoinversa.
Fine corso Computational Mathematics.
23.
Giovedì 9/05/2024, 11–13. ore:
2(45)
Rappresentazione dei proiettori ortogonali sui sottospazi fondamentali mediante
pseudoinversa e SVD. Dimostrazione di alcune proprietà per esercizio.
Shape from shading e photometric stereo nella computer vision.
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.
Soluzione del problema del photometric stereo. Approssimazione a rango 3 della
matrice dei dati.
24.
Lunedì 13/05/2024, 9–11. ore:
2(47)
Relazione tra la norma-2 e la norma di Frobenius di una matrice e i suoi valori
singolari. Costruzione di fattorizzazioni a rango fissato mediante la SVD.
Approssimazione di una matrice mediante la SVD troncata e espressione
dell'errore di approssimazione. Teorema di Weyl e sua dimostrazione. Teorema di
Courant-Fisher. Dimostrazione della stabilità dei valori singolari. Teorema
di Fisher sugli autovalori. Confronto numerico della stabilità degli
autovalori e dei valori singolari.
25.
Martedì 14/05/2024, 11–13. ore:
2(49)
Riepilogo Teoremi di Courant-Fisher e Weyl. Migliore approssimazione di una
matrice rispetto alla norma 2 e alla norma di Frobenius mediante una matrice a
rango fissato. Espressione del numero di condizionamento di una matrice
mediante i valori singolari. Condizionamento di un problema ai minimi quadrati
in presenza di una perturbazione sul vettore dei termini noti e della matrice
del sistema. Ruolo della compatibilità del sistema. Riepilogo sui metodi
iterativi lineari, stazionari, del prim'ordine per sistemi lineari. Vantaggi
rispetto ai metodi diretti. Condizioni che assicurano la convergenza. Cenni
sulle strutture algebriche che consentono un calcolo veloce del prodotto
matrice-vettore. Vantaggi dei metodi iterativi.
26.
Lunedì 20/05/2024, 9–11. ore:
2(51)
Criteri di stop: residuo relativo, limitazione sul numero di iterazioni,
criterio di Cauchy. Relazione tra criteri di stop e errore sulla soluzione.
Precondizionamento e proprietà connesse. Metodi di Richardson.
Fattorizzazioni LU e Cholesky incomplete. Metodi iterativi di massima discesa
per sistemi con matrice simmetrica definita positiva. Determinazione del passo
ottimale. Il metodo del gradiente.
27.
Martedì 21/05/2024, 11–13. ore:
2(53)
Riepilogo metodo del gradiente. Ottimizzazione del calcolo del residuo.
Algoritmo. Implementazione del metodo. Convergenza lenta del metodo e
conseguente necessità di introdurre il precondizionamento. Ottimalità di un
punto rispetto ad una direzione. Condizione necessaria e sufficiente per
l'ottimalità di un punto rispetto ad una direzione. Determinazione di
direzioni coniugate a partire dal residuo. Il metodo del gradiente coniugato.
Aggiornamento del residuo.
28.
Giovedì 23/05/2024, 11–13. ore:
2(55)
Schema dell'algoritmo del gradiente coniugato e ottimizzazione dei calcoli.
Precondizionamento. Introduzione ai metodi di proiezione in spazi di Krylov.
Conseguenze del breakdown del metodo. Il metodo del gradiente coniugato come
metodo di Krylov. Idea alla base dei metodi di proiezione. Condizione di
ottimalità verificata dalla generica iterazione. Il processo di Lanczos per
una matrice simmetrica. Costruzione dell'algoritmo.
L4.
Lunedì 27/05/2024, 9–11. ore:
2(7)
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. Creazione di un
sistema test basato sulla discretizzazione del Laplaciano.
29.
Martedì 28/05/2024, 11–13. ore:
2(57)
Riepilogo processo di Lanczos. Schema dell'algoritmo. Situazione alla
convergenza. Proiezione di una matrice nello spazio di Krylov. Approssimazione
di una matrice prodotta dal processo di Lanczos. Soluzione di un sistema
lineare. Applicazione al calcolo degli autovalori estremali di una matrice di
grandi dimensioni e dei relativi autovettori. Calcolo di funzioni di matrice.
Conseguenze del breakdown e suo trattamento.
30.
Giovedì 30/05/2024, 11–13. ore:
2(59)
Discussione di breakdown, restart e riortogonalizzazione nel metodo di Lanczos.
Altr su altri metodi di Krylov: Arnoldi e Golub-Kahan. Il metodo GMRES.
Migliore approssimazione in uno spazio di Hilbert. Esempi. Caratterizzazione
della migliore approssimazione in uno spazio di Hilbert. Il sistema delle
equazioni normali e il calcolo della migliore approssimazione. Applicazione ai
polinomi algebrici e ai polinomi trigonometrici. Influenza della scelta della
base sulla matrice di Gram ad essa associata. Importanza della presenza di una
base ortogonale.
31.
Lunedì 3/06/2024, 9–11. ore:
2(61)
Riepilogo migliore approssimazione in uno spazio di Hilbert.
Formule di quadratura. Precisione algebrica. Costruzione di formule
interpolatorie. Funzioni peso e integrali pesati. Esempi.
Polinomi ortogonali. Processo di Stiltjes. Formula ricorsiva a tre termini.
32.
Martedì 4/06/2024, 11–13. ore:
2(63)
Riepilogo polinomi ortogonali. Processo di Stiltjes. Formula ricorsiva a tre
termini. Principali proprietà: ortogonalità, radici, matrice di
collocazione. Esempi. Formule di quadratura Gaussiane. Calcolo dei pesi che
rendono la formula interpolatoria. Teorema di caratterizzazione. Calcolo di
nodi e pesi di una formula Gaussiana mediante gli autovalori e autovettori
della matrice di Jacobi associata ai polinomi ortogonali. Principali famiglie
di polinomi ortogonali classici su intervalli finiti e infiniti.
L5.
Giovedì 6/06/2024, 9–11. ore:
2(9)
Laboratorio Uso di LaTeX per la stesura della tesina del corso. Costruzione di polinomi
ortogonali di Legendre e di Chebychev, monici e normalizzati. Valutazione
mediante la formula ricorsiva a tre termini. Grafico dei polinomi. Costruzione
della matrice di Jacobi associata ai polinomi e calcolo dei pesi e dei nodi
della corrispondente formula di quadratura Gaussiana. Calcolo di integrali con
la formula trovata.
Totale ore: 63 (lezione),
9 (laboratorio)
Giuseppe Rodriguez
rodriguez@unica.it