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 $A$. 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 $R(A)$ e $N(A^T)$ indotti dalla soluzione dei minimi quadrati nel caso sovradeterminato a rango pieno. Soluzioni di minima norma. La soluzione normale è ortogonale al nucleo di $A$. 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 $A^TA$: 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 $5\times 3$. 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 $A^*A$ e $AA^*$. 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)