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: 23. aprile 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ì 26/03/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.

Totale ore: 40 (lezione), 4 (laboratorio)