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: 2. 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/2024, 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/2024, 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/2024, 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.

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