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: 1. 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
. 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
e
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
. 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
: 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
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.
Totale ore: 26 (lezione),
2 (laboratorio)
Giuseppe Rodriguez
rodriguez@unica.it