Analisi Numerica (A-L) (C.d.S. Triennale in Informatica) A.A.2004/05
(1^ semestre, 2^ anno)
Esame: scritto (ed eventualmente orale)
Crediti: 6
Docente: Giulio Casciola
Scopo
Dare i fondamenti del calcolo numerico.
Contenuto
Numeri finiti e aritmetica floating point;
funzioni polinomiali; interpolazione e approssimazione minimi quadrati;
integrazione numerica; equazioni non lineari;
sistemi lineari: metodi diretti e metodi iterativi; calcolo degli
autovalori e autovettori di una matrice;
Il corso prevede un'attività di laboratorio (facoltativa)
in cui si utilizza il sistema MATLAB.
Testi Consigliati
- J.Stoer, R.Bulirisch, Introduction to Numerical Analisysy,
(second edition) Springer Verlag (1997)
- D.Bau, N.Trefethen, Numerical linear algebra, SIAM (1998)
- R.Bevilacqua, D.Bini, M.Capovani, O.Menchi, Metodi numerici,
Zanichelli (1992)
- I.D.Faux, M.J.Pratt, Computational Geometry for Design and
Manufacture, John Wiley & Sons (1979)
Altri testi in italiano
- V.Comincioli, Analisi Numerica Metodi Modelli Applicazioni,
McGraw-Hill Libri Italia, (1995)
- I. Galligani, Elementi di Analisi Numerica, Calderini (1986)
- F.Fontanella, A.Pasquali, Calcolo Numerico, Vol.I e II,
Pitagora Editrice Bologna (1985)
Programma completo (file pdf)
Inizio Lezioni
- Le lezioni del corso A-L sono iniziate il 28 settembre 2004 con il seguente orario:
Ma. 13.20-15.30 Aula Ercolani1
Gi. 15.30-17.30 Aula Ercolani1
Modalita' d'Esame
I Appello d'esame
- verso meta' gennaio 2005. Le date esatte saranno comunicate appena definite.
Argomenti trattati a Lezione
- Mar.28/09/04, ore 13.30-14.30:
Introduzione e informazioni sul corso.
- Gio.30/09/04, ore 15.30-17.30:
Richiami sui numeri reali, loro rappresentazione, notazioni, forma scientifica
o normalizzata.
Numeri finiti: approssimazione della mantissa per troncamento e arrotondamento,
range degli esponenti, insieme F dei numeri finiti, memorizzazione dei numeri
finiti (segno, esponente e mantissa), esercizio sulla
distribuzione dei numeri finiti sull'asse reale per l'insieme
F(2,3,-1,2), cenni su ANSI/IEEE Std 754-1985.
Esercitati su conversione e rappresentazione in memoria
- Mar.05/10/04, ore 13.30-15.30:
Correzione esercizio assegnato; definizione di errore assoluto e relativo,
definizione di unita' di arrotondamento, teorema su maggiorazione dell'errore
relativo, corollario sulla rappresentazione di fl(a), caratterizzazione unita'
di arrotondamento;
unita' di arrotondamento in IEEE Basic-Single e Basic-Double e precisione
in termini di cifre decimali.
Aritmetica floating point, precisione di calcolo fra numeri finiti
e standard IEEE, non validita' delle classiche proprieta' delle operazioni.
Assegnati due esercizi.
- Gio.07/10/04, ore 15.30-17.30:
Analisi degli errori in avanti e all'indietro: esempi; analisi
in avanti per la moltiplicazione di due numeri reali,
analisi in avanti per l'addizione di due reali, cancellazione numerica,
esempio numerico. Errore Inerente, Algoritmico e Totale, teorema che
lega E_TOT, E_IN ed E_ALG, numero di condizione e stima di E_IN nel caso di
problemi del tipo f:R->R.
- Mar.12/10/04, ore 13.30-15.30:
Condizionamento di un problema e stabilita' di un algoritmo;
stima di E_IN nel caso di problemi del tipo f:R^n->R,
esempi sulle operazioni aritmetiche di moltiplicazione e addizione/sottrazione
fra numeri reali; esempio per sqrt(x_1+x_2) - sqrt(x_1);
problema esempio per la determinazione delle radici di un'eq. di secondo grado.
- Gio.14/10/04, ore 15.30-17.30:
Il calcolo di intersezioni in svariati problemi pratici: esemplificazioni.
Un problema semplice: intersezione di due segmenti del piano,
esempio numerico di intersezione di due rette,
varie espressioni per definire rette del piano, condizionamento del
problema dell'intersezione di due rette, indecidibilita' dell'uguaglianza,
tolleranze per misure angolari e tolleranze per distanze.
- Mar.19/10/04, ore 13.30-15.30:
Condizionamento del problema
dell'intersezione di due segmenti definiti a partire dai loro estremi.
algoritmo stabile per distanza punto retta,
algoritmo stabile per l'intersezione di due segmenti, test numerici,
esempi.
- Dispensa:
I Numeri Finiti e l'Aritmetica Floating Point.
(file .ps.gz)
(file .pdf)
- Gio.21/10/04, ore 15.30-17.30:
Richiami sui polinomi, valutazione numerica di
un polinomio: metodo di Horner, metodo di Ruffini; valutazione numerica
della derivata di un polinomio; esempi numerici.
- Mar.26/10/04, ore 13.30-15.30:
E_IN nella valutazione di un polinomio: esempio
numerico per un polinomio lineare; stima di E_IN in questo caso;
componente di E_IN che dipende dalla rappresentazione e componente
che non dipende dalla rappresentazione. Base con centro e
base dei polinomi di Bernstein su un intervallo;
analisi di E_IN in questi caso; esempio numerico per lo stesso polinomio
lineare, ma nella base di Bernstein; base dei polinomi di Bernstein nell'
intervallo [0,1] e loro invarianza per traslazione e scala;
ancora sull'esempio del polinomio lineare nella base di Bernstein.
- Gio.28/10/04, ore 15.30-17.30:
Proprieta' della base di Bernstein, valutazione numerica,
formula ricorrente per la loro definizione in [0,1], algoritmo di de
Casteljau; complessita' computazionale; curve di Bezier e loro applicazioni;
esempio numerico di valutazione con l'algoritmo di de Casteljau,
formula ricorrente per la derivata dei polinomi base di Bernstein,
valutazione della derivata di un polinomio.
- Mar.02/11/04, ore 13.30-15.30:
Intepolazione di dati con funzioni polinomiali;
esistenza e unicita' del polinomio interpolante
via soluzione di un sistema lineare con matrice di Vandermonde;
interpolazione polinomiale nella base di Bernstein;
interpolazione polinomiale nella base di Newton e nella base di Lagrange.
- Gio.04/11/04, ore 15.30-17.30:
Ancora sulla base di Lagrange; errore di interpolazione polinomiale nel caso
di funzioni regolari; l'interpolante polinomiale converge
alla funzione all'aumentare dei punti?; esempio test della
funzione di Runge sulla non convergenza del polinomio interpolante
all'aumentare dei punti di interpolazione;
risultato sulla convergenza nell'intervallo di interpolazione del
polinomio interpolante nel caso di funzione almeno C^1 e punti scelti come zeri
dei polinomi di Chebyshev di grado n+1; funzioni di interpolazione polinomiali
a tratti e funzioni spline; interpolazione di Hermite con un polinomio cubico
nella base di Bernstein.
- Mar.09/11/04, ore 13.30-15.30:
Interpolazione mediante polinomi a tratti cubici C^1 di Hermite
usando polinomi di Bernstein scalati e traslati in [0,1].
Stima delle derivate di Bessel.
Interpolazione mediante spline cubiche usando polinomi nella base di Bernstein
ed imponendo le condizioni di raccordo.
Interpolazione di punti del piano con curve polinomiali a tratti vettoriali
con tensione.
Dimostrazione in aula dei vari metodi di interpolazione visti, mediante programmi
test in linguaggio Matlab: dimostrazione sulla convergenza o meno di tali
interpolanti all'aumentare dei punti di interpolazione; esempi sulla funzione
test di Runge; applicazioni all'interpolazione di punti del piano con curve 2D.
- Dispensa:
Interpolazione con Funzioni Polinomiali.
(file .ps.gz)
(file .pdf)
Codice Matlab:
(archivio1 .tgz)
(archivio2 .tgz)
- Gio.11/11/04, ore 15.30-17.30:
Applicazione di interpolanti regolari, tipo spline cubiche, per il controllo
numerico di un robot. Approssimazione ai minimi quadrati; problema
di determinare il minimo di una funzione quadratica in piu` variabili:
metodo delle equazioni normali; caso polinomiale nella base delle
potenze e nella base di Bernstein.
- Mar.16/11/04, ore 13.30-15.30:
Retta di regressione lineare nella base delle potenze e nella base con centro.
Integrazione Numerica o Quadratura Numerica;
formule interpolatorie polinomiali nella forma di Lagrange su punti equidistanti
(formule di quadratura di Newton-Cotes); caso n=1 (trapezi) .
- Gio.18/11/04, ore 13.30-15.30:
(formule di quadratura di Newton-Cotes); caso n=2 (Simpson);
esempio numerico; errore di integrazione per n dispari ed n pari;
caso errore per trapezi e Simpson; formule composte o interpolatorie
polinomiali a tratti;
formule composte dei trapezi ed errore di integrazione; esempio di determinazione
del passo di integrazione per contenere l'errore in una tolleranza fissata;
formule composte di Simpson ed errore di integrazione.
- Dispensa:
Integrazione Numerica.
(file .ps.gz)
(file .pdf)
- Mar.23/11/04, ore 13.30-15.30:
Estrapolazione di Richardson e formule
adattive per l'approssimazione numerica di un integrale definito ad una
tolleranza fissata: caso trapezi e Simpson.
Equazioni non lineari: metodo di bisezione, ipotesi
di applicazione, iterazioni del metodo e test di arresto;
errore inerente.
- Gio.25/11/04, ore 13.30-15.30:
Ancora sull'errore inierente; metodo di Newton, ipotesi di applicazione,
derivazione del metodo, iterazioni del metodo; teorema di
convergenza per metodi di iterazione funzionale.
Teorema di convergenza del metodo di Newton, propagazione degli errori, test di arresto;
- Dispensa:
Equazioni non Lineari.
(file .ps.gz)
(file .pdf)
- Mar.30/11/04.
La lezione non e' stata tenuta per chiusura aule dovuta a sciopero.
- Gio.02/12/04, ore 13.30-15.30:
Problemi applicativi: radice quadrata di un numero, inverso di un numero.
Definizione di ordine di convergenza di una successione,
ordine di convergenza quadratica del metodo di Newton per
radici semplici e lineare per radici multiple, esempi numerici,
Metodo delle secanti, teorema di convergenza, ordine di convergenza;
zeri di polinomi nella base di Bernstein; metodo geometrico/numerico;
applicazione: data una curva chiusa piana in forma parametrica ed un punto del piano
determinare se questi e' interno/esterno alla curva.
- Mar.07/12/04, ore 13.30-15.30:
Soluzione di un sistema lineare quadrato: motivazione di
metodi a complessita` computazionale accettabile;
fattorizzazione LU di una matrice, soluzione del sistema a partire
dalla fattorizzazione LU (sistemi Ly=b ed Ux=y per sostituzioni in avanti
e all'indietro), metodo di eliminazione di Gauss e matrici elementari di Gauss
per la fattorizzazione LU, complessita' computazionale.
esempio di fattorizzazione e soluzione di
un sistema lineare; applicazione della fattorizzazione per il calcolo del
determinante e dell'inversa di una matrice; fattorizzazione LU con scambio
delle righe.
- Gio.09/12/04, ore 15.30-15.70:
Metodo di Gauss con scambio delle righe (o pivoting parziale);
esempio numerico; stabilita` numerica di LU; fattorizzazione LU
con scambio delle righe e perno massimo; stabilita` di LU in senso debole.
Richiami su norme vettoriali e norme matriciali; condizionamento del
problema Ax=b; numero di condizione.
- Mar.14/12/04, ore 13.30-15.30:
Ancora sul condizionamento del problema Ax=b.
Soluzione di un sistema lineare mediante
fattorizzazione QR della matrice; matrici elementari di Householder;
esempio numerico; metodo di Householder;
complessita` computazionale; stabilita` della fattorizzazione
QR.
Metodi iterativi per la soluzione di sistemi lineari, motivazioni. Richiami
su autovalori e autovettori di una matrice: raggio spettrale, polinomio
caratteristico associato ad una matrice.
- Gio.16/12/04, ore 15.30-15.70:
Convergenza di una successione di vettori e risultati preliminari;
metodi iterativi; decomposizione della
matrice e successione di vettori; teorema di convergenza;
condizioni sufficienti per la convergenza.
Test di arresto di un metodo iterativo; metodi di Jacobi e Gauss-Seidel.
Cenni sulla determinazione degli autovalori di una matrice; matrici simili
e trasformazioni per similitudine, matrice diagonalizzabile, metodo QR per
la ricerca degli autovalori.
- Dispensa:
Algebra Lineare Numerica.
(file .ps.gz)
(file .pdf)
Torna alla
home page di Giulio Casciola