METODI DI APPROSSIMAZIONE NUMERICA
Anno accademico e docente
Non hai trovato la Scheda dell'insegnamento riferita a un anno accademico precedente?
Ecco come fare >>
- English course description
- Anno accademico
- 2020/2021
- Docente
- GAETANO ZANGHIRATI
- Crediti formativi
- 9
- Periodo didattico
- Primo Semestre
- SSD
- MAT/08
Obiettivi formativi
- Il corso fornisce ampie conoscenze riguardo la teoria e i metodi dell'approssimazione numerica di dati e funzioni, sia nel caso continuo che nel caso discreto. Il corso prevede una parte di ore dedicata all'attività di laboratorio, nella quale si fa uso dell'Optimization Toolbox di Matlab.
Le principali conoscenze fornite dal corso saranno:
- formulazione generale del problema dell'approssimazione in norma in spazi funzionali, sia nel caso continuo che nel caso discreto ;
- principali algoritmi per la soluzione del problema lineare dell'approssimazione in norma euclidea, sia nel continuo che nel discreto;
- principali algoritmi per la soluzione del problema non lineare dell'approssimazione in norma euclidea nel caso discreto;
- principali algoritmi per la soluzione del problema lineare dell'approssimazione in norma infinito, sia nel caso continuo, che nel caso discreto;
- cenni ai principali algoritmi per la soluzione del problema non lineare dell'approssimazione in norma infinito nel caso discreto.
Le principali abilità che gli studenti dovranno acquisire (ossia le capacità di applicare le conoscenze) saranno:
- saper formulare matematicamente il problema di approssimazione in norma, sia per funzioni che per osservazioni;
- saper valutare quale approccio di soluzione è più conveniente per un dato problema;
- saper risolvere in vari modi un problema lineare di approssimazione in norma euclidea, sia nel continuo, che nel discreto;
- saper formulare matematicamente un problema di approssimazione non lineare nel discreto;
- saper risolvere semplici problemi di approssimazione non lineare nel discreto utilizzando vari metodi;
- saper scrivere il codice Matlab che consente di calcolare la soluzione di un problema di approssimazione in norma, sia lineare che non lineare. Prerequisiti
- Per seguire con profitto il corso, è necessario aver acquisito le seguenti conoscenze e abilità dai corsi di Geometria 1, Analisi Matematica 1 e 2, Analisi Numerica 1 e Programmazione:
- algebra lineare (calcolo matriciale, spazi vettoriali, cambiamenti di base, diagonalizzazione, ecc.);
- trigonometria, successioni numeriche, limiti di successioni e funzioni;
- calcolo differenziale e calcolo integrale in più variabili;
- aritmetica finita e calcolo degli errori;
- metodi numerici (sia diretti che iterativi) per la soluzione di sistemi di equazioni lineari;
- metodi numerici per la soluzione di equazioni non lineari;
- metodi numerici per l'interpolazione polinomiale;
- principi di programmazione strutturata e capacità di scrivere semplici codici in un linguaggio di programmazione;
- conoscenza almeno basilare del linguaggio Matlab.
La conoscenza del linguaggio Matlab è caldamente consigliata e di notevole aiuto in ogni caso, ma risulta indispensabile per essere in grado di utilizzare l'Optimization Toolbox nelle esercitazioni di laboratorio. Contenuti del corso
- Il corso prevede 63 ore di lezione, delle quali circa 50 di lezioni teoriche ed il rimanente di esercitazioni di programmazione con Matlab. La suddivisione oraria (indicata fra parentesi) può variare, anche sensibilmente, a seconda delle difficoltà incontrate dagli studenti nelle varie parti del programma.
Gli argomenti che verranno trattati nelle lezioni saranno i seguenti:
— Introduzione ai concetti fondamentali dell'Approssimazione Numerica, polinomi di Bernstein e di Chebyshev, funzioni razionali, somme di esponenziali; criteri di selezione dell'approssimante. (4)
— Problema lineare dell'approssimazione: formulazione del caso continuo e del caso discreto in spazi Lp. (2)
— Teorema fondamentale dell'approssimazione lineare in spazi Lp. (1)
— Approssimazione ai minimi quadrati ordinari (OLS), caso continuo: polinomio generalizzato di migliore approssimazione; equazioni normali; polinomi algebrici, ortogonali e ortonormali; serie di Fourier generalizzata; disuguaglianza di Bessel, identità di Parseval, procedimento di Gram-Schmidt; convergenza in norma Euclidea; polinomi di Legendre, formula di Clenshaw-Curtis, serie di Fourier e sua convergenza. (9)
— Approssimazione OLS, caso discreto: equazioni normali, esistenza e unicità della soluzione; accettabilità statistica del modello, interpretazione geometrica; inversa generalizzata e pseudoinversa di Moore-Penrose; soluzione del sistema delle equazioni normali e suo condizionamento; caso di rango massimo e di rango incompleto; polinomi ortogonali nel discreto; decomposizione ai valori singolari (SVD), soluzione del problema lineare mediante SVD; interpretazione statistica e Teorema di Gauss-Markoff. (10)
— Minimi quadrati totali (TLS): separazione dei valori singolari, soluzione mediante SVD, unicità; relazione con OLS, condizionamento, sensitività; caratterizzazione minimax dei valori singolari; problema lineare di regressione della distanza ortogonale. (6)
— Introduzione al problema non lineare dei minimi quadrati (NLS): concetti, brevi richiami di ottimizzazione; metodi del prim'ordine: Gauss-Newton (G-N) e G-N rilassato; proprietà di discesa della direzione di G-N; rilevanza del rango numerico dello Jacobiano; cenni al metodo trust region. (2)
— Metodi di tipo Newton per NLS: velocità locale di convergenza; metodo di Newton ibrido: soluzione mediante SVD; cenno ai metodi quasi-Newton per NLS: rank1, DFP e BFGS; regressione non lineare della distanza ortogonale; problema non lineare dell'approssimazione geometrica: fit con elementi geometrici. (2)
— Approssimazione in norma di Chebyshev, caso continuo: polinomio minimax; teorema di De la Vallée-Puossin, teorema di equioscillazione di Chebyshev, unicità della soluzione; secondo algoritmo di Remez; convergenza per funzioni continue, stima di Jackson, resto minimax; polinomio trigonometrico minimax per funzioni periodiche. (7)
— Approssimazione in norma di Chebyshev, caso discreto: generalità; caso m = n+1: esistenza e unicità della soluzione, proprietà dell'alternanza; teorema di de la Vallée-Puossin, caso polinomiale algebrico, determinanti di Vandermonde; caso generale con m > n+1: unicità della soluzione, metodo dello scambio per dati discreti. (8)
— Laboratorio: applicazione dei polinomi trigonometrici e della FFT all'approssimazione; esercizi per TLS e problema lineare della regressione della distanza ortogonale; introduzione all'Optimization toolbox, function handle, m-function con numero variabile di argomenti; regressione geometrica circolare 2D mediantelsqnonlin; immagini ed SVD; algoritmo di Remez per il caso continuo. (12) Metodi didattici
- Il corso prevede lezioni teoriche in aula e/o in streaming su tutti gli argomenti sopra menzionati e lezioni pratiche in laboratorio informatico e/o in streaming per la realizzazione degli algoritmi in ambiente Matlab e la loro prova su alcuni semplici problemi. In caso di necessità, materiale video di guida potrà essere fornito a supporto e/o in sostituzione alle esercitazioni di programmazione (modalità asincrona).
Modalità di verifica dell'apprendimento
- Obiettivo delle prove d'esame è la verifica di un adeguato livello di raggiungimento degli obiettivi formativi del corso, sia rispetto alle conoscenze, che rispetto alle abilità, includendo anche la parte di laboratorio in Matlab.
L'esame è costituito da una prova orale, divisa in due parti:
- nella prima parte sono previste domande aperte su tutti gli argomenti svolti a lezione;
- nella seconda parte è prevista una discussione sugli esercizi di laboratorio in Matlab, sia quelli svolti a lezione che quelli assegnati, e la consegna al docente dei relativi sorgenti.
Il punteggio finale è dato dalla somma della valutazione della prima parte, che in generale non può superare i 28/30, e quella della seconda parte. Il punteggio massimo sulla seconda parte varia tra 2/30 e 10/30, a seconda della quantità di tempo che è stato possibile dedicare al laboratorio durante il corso: pertanto, questo non può essere noto a priori. Tuttavia, se non viene consegnato alcun esercizio di Matlab, l'esame è compromesso. Testi di riferimento
- - Åke Björck, "Numerical Methods for Least Squares Problems", SIAM, 1996. ISBN-13: 978-0-898713-60-2. ISBN-10: 0-89871-360-9.
- Matlab Optimization Toolbox User's Guide
- Appunti del docente
