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: 18. aprile 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ì 5/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 . 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 e indotti dalla
soluzione dei minimi quadrati nel caso sovradeterminato a rango pieno.
Soluzioni di minima norma. La soluzione normale è ortogonale al nucleo di
. 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 : 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 . 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.
Totale ore: 35 (lezione),
3 (laboratorio)
Giuseppe Rodriguez
rodriguez@unica.it