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