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 $A$. 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 $R(A)$ e $N(A^T)$ indotti dalla soluzione dei minimi quadrati nel caso sovradeterminato a rango pieno. Soluzioni di minima norma. La soluzione normale è ortogonale al nucleo di $A$. 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 $A^TA$: 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