REGISTRO DELLE LEZIONI DI
ALGORITMI NUMERICI E APPLICAZIONI - COMPUTATIONAL MATHEMATICS
CORSO DI LAUREA MAGISTRALE IN MATEMATICA E IN INFORMATICA
9 CFU - A.A. 2024/2025
DOCENTE: PROF. GIUSEPPE RODRIGUEZ
ULTIMO AGGIORNAMENTO: 14. maggio 2025

1.         Lunedì 3/03/2025, 9–11.         ore: 2(2)

Introduzione al corso. Il gruppo di Analisi Numerica, corsi attivi del settore, opportunità di tesi e tirocinio. Problemi ben posti. Numero di condizionamento assoluto e relativo di un problema. Problemi diretti, inversi e di identificazione. Esempi. Equazioni integrali di Fredoholm e Volterra, di primo e secondo tipo. Antitrasformata di Fourier come equazione integrale. Equazioni integrali convolutorie. Esempi.

2.         Mercoledì 5/03/2025, 9–11.         ore: 2(4)

Discussione sulla valutazione dei corsi universitari da parte degli studenti. Esempi di equazioni integrali del primo tipo mal poste. Legami tra esistenza ed unicità della soluzione e struttura dell'immagine e del nucleo dell'operatore. Richiami sui sistemi di numerazione e sull'aritmetica di macchina. 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.

3.         Giovedì 6/03/2025, 9–11.         ore: 2(6)

Approssimazione ai minimi quadrati mediante una somma di esponenziali. Esempio: decadimento di un materiale radioattivo. Cenni sui problemi nonlineari. 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. Prodotto matriciale e sua formulazione alternativa: 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ì 10/03/2025, 9–11.         ore: 2(8)

Riepilogo BLAS. 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. 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: costruzione di una fotografia sintetica di una superficie.

5.         Mercoledì 12/03/2025, 9–11.         ore: 2(10)

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

6.         Giovedì 13/03/2025, 9–11.         ore: 2(12)

Risoluzione di un LSP mediante il sistema delle equazioni normali. Matrice pseudo-inversa. La matrice del sistema è simmetrica 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).

7.         Lunedì 17/03/2025, 9–11.         ore: 2(14)

Teorema di Gauss-Markov. Media e varianza della soluzione dei minimi quadrati. Fattorizzazione spettrale della matrice varianza-covarianza e analisi delle componenti principali (PCA). 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. Proiettori ortogonali prodotti dal partizionamento di una matrice ortogonale.

8.         Mercoledì 19/03/2025, 9–11.         ore: 2(16)

Discussione sulla struttura di tre libri di Algebra Lineare. Il database scientifico Scopus e il suo uso nella valutazione della ricerca. Espressione dei proiettori indotti dalla soluzione dei minimi quadrati mediante la fattorizzazione QR. Soluzioni di minima norma. La soluzione normale è ortogonale al nucleo di $A$. 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 Hilbert è sempre strettamente convessa. Riformulazione ben-posta di un sistema sottodeterminato a rango pieno. Il metodo dei moltiplicatori di Lagrange. Esercizio.

9.         Giovedì 20/03/2025, 9–11.         ore: 2(18)

Riformulazione ben-posta di un sistema sottodeterminato a rango pieno. Equazioni normali del secondo tipo. Matrice pseudoinversa per un sistema sottodeterminato a rango pieno. Formulazione primale e duale di un LSP. Riepilogo risoluzione di sistemi sovradeterminati e sottodeterminati a rango pieno. Considerazioni numeriche sul calcolo della matrice $A^TA$: vantaggi, svantaggi, algoritmi, complessità. Implementazione come inner product e come outer product. Riepilogo fattorizzazione di Gauss con pivoting parziale o totale. 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.

L1.         Lunedì 24/03/2025, 9–11.         ore: 2(2)

Laboratorio Esperimenti numerici sui minimi quadrati in Matlab: risoluzione di un sistema sovradeterminato con vari metodi. Confronto tra le soluzioni ottenute. Costruzione di un problema test con soluzione assegnata. Rappresentazione grafica dei risultati. Creazione di un sistema sovradeterminato incompatibile con soluzione assegnata. Esperimento su un problema sottodeterminato. Differenze tra la soluzione di minima norma e quella calcolata dall-operatore backslash di Matlab. Creazione di un problema test con soluzione di minima norma assegnata.

10.         Mercoledì 26/03/2025, 9–11.         ore: 2(20)

Riepilogo fattorizzazione di Cholesky. Matrici definite positive: verifica pratica della proprietà. Implementazione dell'algoritmo per colonne. Complessità. Cenni sull'implementazione dell'algoritmo per righe o a blocchi. Esercizio sulla fattorizzazione di Cholesky. 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à. Algoritmo per la loro costruzione ottimizzata. Possibili ulteriori ottimizzazioni della procedura di calcolo. Introduzione all'algoritmo di fattorizzazione QR di Householder.

11.         Giovedì 27/03/2025, 9–11.         ore: 2(22)

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à. Casi in cui l'algoritmo di Givens è preferibile ad Householder. Matrici di Hessenberg.

12.         Lunedì 31/03/2025, 9–11.         ore: 2(24)

Esercizio: fattorizzazione QR di una matrice $5\times 2$ con in metodi di Householder e Givens. Algoritmo di ortonormalizzazione di Gram–Schmidt classico (CGS). Metodo di Gram–Schmidt modificato (MGS). Fattorizzazioni QR risultanti da CGS e MGS. Risultati numerici sull'uso della fattorizzazione QR. Possibili miglioramenti del metodo MGS: aggiornamento del vettore dei termini noti e algoritmo senza normalizzazione.

13.         Martedì 1/04/2025, 9–11.         ore: 2(26)

Legame tra MGS e l'algoritmo di Householder. 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. 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.

L2.         Mercoledì 2/04/2025, 9–11.         ore: 2(4)

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. Verifica dell'accuratezza della fattorizzazione. Ottimizzazioni successive del programma e loro effetto sulla complessità computazionale. Uso avanzato della funzione fprintf.

14.         Lunedì 7/04/2025, 9–11.         ore: 2(28)

Localizzazione di autovalori. Cerchi riga e cerchi colonna. Primo teorema di Gershgorin. 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. Teorema di Bauer–Fike. Il caso di una matrice Hermitiana.

15.         Mercoledì 9/04/2025, 9–11.         ore: 2(30)

Creazione di un problema test. Matrice compagna associata ad un polinomio monico. 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. Cenni sul metodo delle potenze inverse. Matrici sparse: vantaggi computazionali. Cenni su altre matrici strutturate.

16.         Giovedì 10/04/2025, 9–11.         ore: 2(32)

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. Applicazione: eigenvalue centrality di una rete non orientata. Matrice compagna associata ad un polinomio monico e calcolo delle radici di un polinomio come autovalori della matrice compagna. Algoritmo QR per il calcolo degli autovalori. Invarianti per trasformazioni QR: similitudine, simmetria. Teorema di convergenza e rilassamento delle ipotesi. Costruzione della forma di Schur e, per una matrice simmetrica, della fattorizzazione spettrale. Riduzione del costo computazionale: passaggio in forma di Hessenberg e uso di trasformazioni di Givens.

17.         Lunedì 14/04/2025, 9–11.         ore: 2(34)

Accelerazione della convergenza dell'algoritmo QR mediante shift dello spettro. Database utilizzati nella classificazione degli articoli scientifici. Metriche di valutazione. Il processo di pubblicazione di un articolo. Decomposizione ai valori singolari (SVD). Esercitazione: dimostrazione per induzione dell'esistenza della SVD.

18.         Mercoledì 16/04/2025, 9–11.         ore: 2(36)

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. Cenni sull'algoritmo di calcolo effettivamente utilizzato. Rappresentazione dei quattro sottospazi fondamentali di una matrice mediante i vettori singolari. Relazioni tra i sottospazi. Soluzione di un sistema quadrato non singolare mediante SVD. Osservazioni sulla propagazione degli errori.

19.         Giovedì 17/04/2025, 9–11.         ore: 2(38)

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. Dimostrazione di alcune proprietà per esercizio. Applicazione: Photometric stereo, ricostruzione di modelli 3D a partire da immagini. La legge di Lambert: formulazione scalare e matriciale. 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.

20.         Mercoledì 23/04/2025, 9–11.         ore: 2(40)

Esempi numerici sulla tecnica del photometric stereo. Applicazione: camera calibration. Determinazione del legame tra i sistemi di riferimento ``world'', ``camera'' e ``image''. Parametri intrinseci ed estrinseci. Sistema lineare omogeneo a rango 7 che lega una parte dei parametri ai punti osservati. Soluzione del sistema mediante SVD e determinazione della costante di proporzionalità. Determinazione dei rimanenenti parametri. 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.

21.         Giovedì 24/04/2025, 9–11.         ore: 2(42)

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. Migliore approssimazione di una matrice rispetto alla norma 2 e alla norma di Frobenius mediante una matrice a rango fissato.

L3.         Lunedì 28/04/2025, 9–11.         ore: 2(6)

Laboratorio Esperimenti sulla stabilità del calcolo di autovalori e vettori singolari. Implementazione ottimizzata del metodo delle potenze. Esperimenti al variare del posizionamento degli autovalori della matrice test.

22.         Mercoledì 30/04/2025, 9–11.         ore: 2(44)

Commenti sugli esperimenti fatti nell'ultima lezione in laboratorio. Risultati di stabilità per la matrice pseudoinversa. 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. Cenni sull'algoritmo di calcolo della SVD. Riepilogo sui metodi iterativi lineari, stazionari, del prim'ordine per sistemi lineari. Vantaggi rispetto ai metodi diretti. Condizioni che assicurano la convergenza. Criteri di stop: residuo relativo, limitazione sul numero di iterazioni, criterio di Cauchy. Relazione tra i criteri di stop e l'errore sulla soluzione. Precondizionamento e proprietà connesse. Cenni sulla fattorizzazione LU incompleta.

23.         Lunedì 5/05/2025, 9–11.         ore: 2(46)

Riepilogo metodi iterativi. Vantaggi nella soluzione di sistemi strutturati. Metodi di Richardson. Matrici sparse e matrici di Toeplitz. Cenni sulla discretizzazione di un problema differenziale ai limiti. Precondizionamento mediante fattorizzazioni LU e Cholesky incomplete. Esercizio: il precondizionatore circolante di Chan. Metodi iterativi di massima discesa per sistemi con matrice simmetrica definita positiva. Determinazione del passo ottimale.

24.         Mercoledì 7/05/2025, 9–11.         ore: 2(48)

Riepilogo metodi di discesa. Il 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. Schema dell'algoritmo del gradiente coniugato e ottimizzazione dei calcoli.

25.         Giovedì 8/05/2025, 9–11.         ore: 2(50)

Schema dell'algoritmo del gradiente coniugato precondizionato e ottimizzazione dei calcoli. Formulazione alternativa dell'algoritmo. Esercizio: dimostrazione dell'ortogonalità dei residui e della $A$-ortogonalità delle direzioni coniugate. Introduzione ai metodi di proiezione in spazi di Krylov. Conseguenze del breakdown del metodo sulla risoluzione di un sistema lineare. Idea alla base dei metodi di proiezione. Condizione di ottimalità verificata dalla generica iterazione e scelta della base. Il metodo del gradiente coniugato come metodo di Krylov.

26.         Lunedì 12/05/2025, 9–11.         ore: 2(52)

Riepilogo metodi di Krylov e metodo del gradiente. Il processo di Lanczos per una matrice simmetrica. Costruzione 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.

27.         Mercoledì 14/05/2025, 9–11.         ore: 2(54)

Riepilogo processo di Lanczos. Schema dell'algoritmo per la soluzione di un sistema lineare. Possibili test di convergenza. 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. Discussione di breakdown, restart e riortogonalizzazione nel metodo di Lanczos. Altri metodi di Krylov: il processo di Arnoldi. Il metodo GMRES.

Totale ore: 54 (lezione), 6 (laboratorio)