Programma Preliminare Calcolo Numerico (Corso B) a.a.2002/2003 Docente: Di Lena Giovanni 1) ANALISI DEGLI ERRORI Definizione di Aritmetica Finita: i numeri macchina, l'operatore di discretizzazione, la precisione di una AF, gli errori di underflow e di overflow. I numeri floating-point e costruzione di una AF; discretizzazione mediante troncamento e mediante arrotondamento. Descrizione della aritmetica IEEE: i numeri normalizzati e non normalizzati, i simboli +Inf, -Inf, NaN, e loro comportamento operativo. Definizione di errore assoluto ed errore relativo, loro significato empirico in temini di cifre decimali corrette e cifre significative corrette. Introduzione alla nozione di Algoritmo Numerico ed alla sua stabilità. Definizione di Problema Ben-posto e numero di condizione, numero di condizione assoluto e numero di condizione relativo. Numero di condizione delle quattro operazioni aritmetiche. Analisi del numero di condizione del prodotto scalare di due vettori, numero di condizione di una funzione differenziabile. Analisi della stabilità di un algoritmo: analisi in avanti ed analisi all'indietro. Numero di condizione di un algoritmo e sua dipendenza dai dati. 2) SISTEMI DI EQUAZIONI LINEARI 2a) Metodi diretti Algoritmo di risoluzione di un sistema con matrice triangolare inferiore o superiore, o con matrice ortogonale; costo computazionale di tali metodi. Fattorizzazione LU di una matrice quadrata e condizioni di esistenza. Metodo di risoluzione basato sulla fattorizzazione LU. Fattorizzazione LLT di una matrice simmetrica definita positiva, e metodo di risoluzione del sistema lineare. Fattorizzazione QR di una matrice quadrata e rettangolare, e metodo di risoluzione dei sistema lineare. Algoritmo di Gauss, senza pivot e con pivot, per la risoluzione di un sistema lineare con matrice non singolare. Matrici di permutazione e fattorizzazione LU di una matrice non singolare e suo legame con il metodo di Gauss. Calcolo della inversa di una matrice tramite le matrici elementari di Gauss-Jordan. Numero di condizione di una matrice, legame del numero di condizione con la norma utilizzata, i valori singolari, il determinante, gli autovalori della matrice. Il caso particolare delle matrici simmetriche, legame tra errore e residuo sia per i sistemi lineari che per l'inversa di una matrice. 2b) Metodi iterativi Teoria generale: dei metodi iterativi: funzioni contrattive, esistenza ed unicità del punto fisso, convergenza del metodo iterativo basato su una contrazione. Maggiorazione dell'errore assoluto e dell'errore relativo delle iterate. Definizione di ordine di convergenza di un metodo iterativo, maggiorazione asintotica dell'errore per metodi di ordine maggiore di uno. Analisi dell'errore in AF; criteri di stop nei metodi iterativi. Metodi iterativi lineari e matrice d'iterazione; condizioni di convergenza, maggiorazione dell'errore. Analisi in Aritmetica Reale e in Aritmetica Finita. Algoritmo di Jacobi, convergenza del metodo per matrice del sistema a predominanza diagonale per righe o per colonne sia in senso forte che in senso debole. Algoritmo di Gauss-Seidel, convergenza per matrici a predominanza diagonale per matrici simmetriche definite positive. Algoritmo del rilassamento, convergenza per matrici a predominanza diagonale e per matrici simmetriche definite positive. 2c) Problema ai minimi quadrati Fattorizzazione SVD di una matrice rettangolare, valori singolari e rango della matrice, legame tra autovalori di una matrice simmetrica ed i valori singolari. Definizione di pseudo-inversa di una matrice rettangolare, range e spazio nullo di una matrice, della trasposta e della pseudo- inversa: proprietà caratteristiche della pseudo-inversa. Impostazione del problema dei minimi quadrati e designazione dell'unica soluzione. Rappresentazione dell'unica soluzione mediante la pseudo- inversa. Equivalenza tra il problema dei minimi quadrati e la equazione normale. Uso della fattorizzazione SVD per la risoluzione del problema ai minimi quadrati, uso della fattorizzazione QR per matrici rettangolari di rango massimo. 3) EQUAZIONI NON LINEARI Metodi iterativi per il calcolo degli zeri di una funzione: metodo di bisezione dell'intervallo, metodo della direzione costante, metodo della secante, metodo di Newton. Ordine e convergenza di un metodo. Numero di condizione di una radice. Sistemi di equazioni non lineari: metodo di Newton e metodi quasi-newtoniani. 4) SPAZI LINEARI FUNZIONALI 4a) Spazi lineari di funzione di dimensione finita, lineare indipendenza e base dello spazio, una condizione sufficiente per la lineare indipendenza di funzioni tramite la matrice generalizzata di Vandermonde, analisi della stabilità di una base e funzione di Lebesgue. Insieme di punti di unicità, condizioni equivalenti. Base nodale, partizione dell'unità, base ortogonale nel continuo e coefficienti di Fourier, base ortogonale nel discreto, e calcolo dei relativi coefficienti di Fourier. Interpretazione dei coefficienti di una funzione rispetto alla base rappresentata. Tecniche di approssimazione mediante: interpolazione, migliore approssimazione in norma infinito, migliore approssimazione nel senso dei minimi quadrati nel continuo; approssimazione ai minimi quadrati nel discreto. Confronto tra le varie approssimazioni con quella di migliore approssimazione in norma infinito. 4b) Spazi di polinomi La base delle potenze, la base nodale di Lagrange, polinomi di Bernstein; polinomi di Chebychev, proprietà di minimax dei polinomi di Chebychev. 4c) Spazi di funzioni polinomiali a tratti Definizione degli spazi Msk ([a,b], D ); dimensione e base delle potenze troncate. Definizione delle funzioni spline; costruzione della base delle B-spline lineari e cubiche su nodi equidistanti; costruzione delle funzioni B-spline su una sequenza generica di nodi mediante formule ricorsive, e loro proprietà. 4d) Polinomi trigonometrici Definizione di polinomio trigonometrico, rappresentazione mediante funzioni esponenziali. ortogonalità nel continuo e nel discreto della base delle funzioni esponenziali. 5) INTERPOLAZIONE ED APPROSSIMAZIONE Interpolazione polinomi e polinomi di Langage, algoritmo di Neville. Polinomio ai minimi quadrati e sua determinazione tramite la fattorizzazione QR. Approssimazione di una funzione mediante un polinomio interpolante: rappresentazione dell'errore. il fenomeno di Runge, il problema della scelta dei nodi ottimali ed uso degli zeri dei polinomi di Chebychev. Analisi del comportamento del polinomio interpolante rispetto al tipo di funzione da cui proviene il campione utilizzato per l'interpretazione. Interpretazione con spline lineari e cubiche. Determinazione della spline cubica naturale, completa, periodica. Indice di Sard delle spline cubiche interpolanti, cenni sull'errore di approssimazione Una applicazione delle funzioni B-spline alla modellazione di una curva di forma libera. Interpolazione trigonometrica, e suo legame con la trasformata di Fourier, l'algoritmo FFT. Legame tra minimi quadrati e interpolazione per i polinomi trigonometrici. Una applicazione al filtraggio dei dati. 6) QUADRATURA NUMERICA Formula dei trapezi, rappresentatone dell'errore sia su nodi equidistanti che generici. algoritmi di calcolo. Stima empirica e stima attendibile di Richardson dell'errore. L'algoritmo di Romberg. Un algoritmo basato su una tecnica adattativa. Analisi delle formule di quadratura: ordine di una formula di quadratura, stabilità delle formule di quadratura. 7) ESERCITAZIONI Verifica sperimentale di algoritmi stabili ed instabili per la risoluzione di semplici problemi. Utilizzando opportune matrici test risolvere il sistema di equazioni lineari con i vari metodi, evidenziando il numero di condizione del problema, il valore del residuo normalizzato, il costo di calcolo di ciascun metodo, l'errore di calcolo effettivamente commesso ed il suo legame con il residuo normalizzato. Verificare la stabilità numerica degli algoritmi studiati. Per i metodi iterativi confrontare i diversi criteri di stop, il costo computazionale e la convergenza degli stessi. Applicare le conoscenze acquisite alla risoluzione di problemi tipo: problemi ai valori ai limiti; problema di Poisson. Valutare l'importanza della gestione sparsa delle matrici che sorgono nel risolvere tali problemi. Per le radici di una equazione verificare le proprietà di convergenza dei vari metodi iterativi studiati, e l'ordine di convergenza in termini di cifre decimali corrette avute ad ogni passo. Valutare il costo di calcolo di ciascun metodo ed il metodo di lavorare dei vari criteri di stop. Osservare il comportamento delle iterate in dipendenza della costante asintotica e del numero di condizione. Per lo studio delle funzioni visualizzare i grafici della base nodale di polinomi sia con nodi equidistanti che di Chebychev, delle funzioni spine cubiche e dei polinomi trigonometrici: confrontare anche la funzione di Lebesgue di dette basi. Eseguire l'interpolazione con polinomi, con spline cubiche, trigonometria su funzioni semplici che presentano una particolare proprietà di regolarità della funzione o delle derivate. In modo analogo considerare il problema ai minimi quadrati con dati ridondanti o perturbati, al fine di valutare la distinzione tra interpolazione e approssimazione con i minimi quadrati. Nel contesto della modellazione geometrica di una curva di forma libera, realizzare un programma che permette in modo interattivo di definire dei punti nel piano ( punti di controllo), e disegnare la curva utilizzando o la base di Lagrange o di Bernstein o delle B-spline. Successivamente mediante la selezione di un punto di controllo modificare dinamicamente la posizione del punto modificare la curva di conseguenza, verificare quale base è più idonea alla modellazione libera della curva. Per le formule di quadratura numerica, considerare il comportamento asintotico delle formule al decrescere del passo, confrontare il costo computazionale tra l'analisi a-priori dell'errore e la stima a posteriori dell'errore con la tecnica di Richardson. Realizzare ed utilizzare la routine adattativa per il calcolo di un integrale di una funzione complessa e confrontare il costo di calcolo rispetto al passo costante. Testi di riferimento: - V. Comincioli ''Analisi Numerica, metodi modelli applicazioni'', McGraw- Hili Libri Italia - D. Bini, M. Capovani, O. Menchi, '' Metodi Numerici per l'algebra lineare'', Zanichelli Editore - R. Bevilaqua, D. Bini, M. Capovani, O. Menchi '' Metodi Numerici'' Zanichelli Editore - A. Cavallo R. Setola, F. Vasca, '' Guida operativa a Matlab, simulink e control toolbox.'' Liguori editore. - Dispense distribuite dal docente.