Analisi Numerica (A-L) (C.d.S. Triennale in Informatica) A.A.2006/07
(1^ semestre, 2^ anno)
Esame: scritto e/o 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.
Programma completo (file pdf)
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)
Inizio Lezioni
- Le lezioni del corso A-L inizieranno il 27 settembre 2006 con il seguente orario:
Lunedi' ore 8:30-11:30
Mercoledi' ore 10:30-12:30
Argomenti trattati a Lezione
- Me.27/09/06, ore 10.30-12.30: Aula E2
Introduzione e informazioni sul corso.
Dispensa: I Numeri Finiti e l'Aritmetica Floating Point.
(file .pdf)
Numeri Finiti
Richiami sui numeri reali, loro rappresentazione, notazioni,
forma scientifica o normalizzata.
Approssimazione della mantissa per troncamento e arrotondamento,
range degli esponenti, insieme F dei numeri finiti,
esercizio1: definito un insieme F quanti sono i suoi elementi?
esercizio2: determinare tutti gli elementi di F(2,3,-1,2);
esercizio3: come sono distribuiti sull'asse reale gli elementi di F(2,3,-1,2);
- Lu.02/10/06, ore 8.30-12.30: Aula E2
Correzione esercizi assegnati; casi di Overflow e Underflow,
memorizzazione dei numeri finiti (segno, esponente e mantissa),
cenni su ANSI/IEEE Std 754-1985.
Esercitati su conversione e rappresentazione in memoria
definizione di errore assoluto e relativo,
definizione di unita' di arrotondamento, teoremi su maggiorazioni dell'errore
assoluto e dell'errore relativo, corollario sulla rappresentazione di fl(a),
caratterizzazione unita' di arrotondamento, esempi numerici per troncamento
e arrotondamento.
- Me.04/10/06
Non c'e' lezione per festivita' del Patrono.
- Lu.09/10/06, ore 8.30-11.30: Aula E2
Caratterizzazione di u e arrotondamento ai pari in ANSI/IEEE Std 754.
Unita' di arrotondamento in IEEE Basic-Single e Basic-Double e precisione
in termini di cifre decimali.
(assegnato da provare codice per determinare u).
Aritmetica floating point: precisione di calcolo fra numeri finiti
e standard IEEE, non validita' delle classiche proprieta' delle operazioni
(assegnato esercizio sulla proprieta' associativa dell'addizione).
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.
Condizionamento di un problema e stabilita' di un algoritmo:
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.
- Me.11/10/06, ore 10.30-12.30: Aula E2.
Stima di E_ALG; 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;
problema esempio per l'intersezione di due rette del piano (sistema lineare 2x2).
- Lu.16/10/06, ore 8.30-11.30: Aula E2.
Dispensa: Interpolazione con Funzioni Polinomiali.
(file .pdf)
Funzioni Polinomiali e Interpolazione
Richiami sui polinomi, valutazione numerica di
un polinomio: metodo di Horner, metodo di Ruffini; valutazione numerica
della derivata di un polinomio; esempi numerici.
E_IN nella valutazione di un polinomio: esempio
numerico per un polinomio lineare; stima di E_IN in questo caso;
Cambio di base polinomiale: base con centro; esempio;
componente di E_IN che dipende dalla rappresentazione e componente
che non dipende dalla rappresentazione.
- Me.18/10/06
Non c'e' lezione per Lauree.
- Lu.23/10/06, ore 8.30-11.30: Aula E2.
Base dei polinomi di Bernstein su un intervallo;
analisi di E_IN in questi casi; esempio numerico per lo stesso polinomio
lineare visto la lezione scorsa, ma nella base di Bernstein;
base dei polinomi di Bernstein nell' intervallo [0,1] e loro invarianza
per traslazione e scala; ripreso l'esempio del polinomio lineare nella
base di Bernstein, ma in [0,1]. Proprieta' dei polinomi base di Bernstein,
definizione via formula ricorrente, valutazione numerica,
algoritmo via funzioni base (ALG1), algoritmo di de
Casteljau (ALG2); complessita' computazionale; curve di Bezier
(definizione vettoriale, punti di controllo, poligonale di controllo)
- Me.25/10/06, ore 10.30-12.30: Aula E2
Valutazione di una curva con algoritmo di de Casteljau; suddivisione di una
curva di Bezier; algoritmo di de Casteljau ricorsivo per cubiche;
Interpretazione geometrica dei coefficienti di un pol. di Bernstein; esempio numerico di
valutazione; formula ricorrente per la derivata dei polinomi base di Bernstein;
valutazione delle derivata di un pol. di Bernstein e di una curva di Bezier;
antiderivata e integrale.
Introduzione al problema dell'intepolazione di dati.
- Lu.30/10/06, ore 8.30-11.30: Aula E2
Dimostrazione in aula di applicazioni delle curve di Bezier.
Intepolazione di dati con funzioni polinomiali;
esistenza e unicita' del polinomio interpolante;
interpolazione polinomiale nella base di Newton,
di Bernstein e di Lagrange.
- Lu.6/11/06, ore 8.30-11.30: Aula E2
Errore di interpolazione polinomiale; convergenza dell'interpolante
all'aumentare dei punti; esempio test della funzione di Runge;
zeri dei polinomi di Chebyshev di grado n+1 e convergenza dell'interpolante;
funzioni di interpolazione polinomiali a tratti;
interpolazione di Hermite; esempio polinomio cubico nella base di Bernstein;
polinomi cubici a tratti di interpolazione di Hermite di classe C^1 (interpolazione locale);
polinomi cubici a tratti di interpolazione di classe C^2 (spline)(interpolazione globale).
Introduzione all'ambiente Matlab e dimostrazione con programmi Matlab
(archivio1 .tgz)
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;
- Me.8/11/06, ore 10.30-12.30: Aula E2
Interpolazione di punti del piano con curve polinomiali a tratti vettoriali
con tensione.
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:
sistema della equazioni normali.
- Lu.13/11/06, ore 8.30-11.30: Aula E2
Approssimazione ai minimi quadrati: caso polinomiale nella base delle
potenze e nella base di Bernstein. Retta di regressione lineare nella base
delle potenze e nella base con centro.
Dispensa: Integrazione Numerica.
(file .pdf)
Integrazione Numerica
Formule di Quadratura;
formule interpolatorie polinomiali nella forma di Lagrange su punti equidistanti
(formule di quadratura di Newton-Cotes); caso n=1 (trapezi);
(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.
- Me.15/11/06, ore 10.30-12.30: Aula E2
Formule composte interpolatorie polinomiali a tratti;
formule composte dei trapezi ed errore di integrazione;
formule composte di Simpson ed errore di integrazione.
Esempio di determinazione del passo di integrazione per contenere l'errore
in una tolleranza fissata (caso trapezi e Simpson composti);
Estrapolazione di Richardson e formule
adattive per l'approssimazione numerica di un integrale definito ad una
tolleranza fissata: caso trapezi e Simpson.
Applicazione alla lunghezza e all'area di una curva piana.
- Lu.20/11/06, ore 8.30-11.30: Aula E2
Dispensa: Equazioni non lineari
(file .pdf)
Equazioni non lineari
Metodo di bisezione, ipotesi di applicazione, iterazioni del metodo e test di arresto;
errore inerente; 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;
Problemi applicativi: radice quadrata di un numero, inverso di un numero.
- Me.22/11/06, ore 10.30-12.30: Aula E2
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;
Un esempio di applicazione della determinazione delle radici di una
equazione polinomiale: l'intersecatore di POV-Ray per superfici implicite.
teorema di Sturm per la localizzazione delle radici reali di un'equazione
polinomiale.
- Lu.27/11/06, ore 8.30-11.30: Aula E2
Dispensa:
Algebra Lineare Numerica.
(file .pdf)
Algebra Lineare Numerica
Soluzione di un sistema lineare quadrato: motivazione di
metodi con 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 (o pivoting parziale), esempio numerico.
- Me.29/11/06, ore 10.30-12.30: Aula E2
Stabilita` numerica della fattorizzazione 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.
- Lu.04/12/06, ore 8.30-11.30: Aula E2
Ancora su condizionamento del problema Ax=b; soluzione di un sistema lineare mediante
fattorizzazione QR; matrici elementari di Householder.
Verifica analitica e numerica (su un esempio) dell'effetto di una
trasformazione di Householder; metodo di Householder per fattorizzazione QR.
- Me.06/12/06, ore 10.30-12.30: Aula E2
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;
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;
complessita' computazionale; test di arresto.
- Lu.11/12/06, ore 8.30-11.30: Aula E2
Metodi di Jacobi e Gauss-Seidel; esempi numerici.
Proprieta' degli autovalori di una matrice; risultati su autovalori e
autovettori; matrici simili e trasformazioni per similitudine, matrice diagonalizzabile;
teorema di Schur; matrici di Hessemberg.
Metodi per la determinazione degli autovalori di una matrice: fase di riduzione a
matrici in forma di Hessemberg, fase di convergenza.
- Me.13/12/06, ore 10.30-12.30: Aula E2
Metodo QR per la ricerca degli autovalori.
Applicazione del calcolo degli autovalori per la valutazione di curve e
superfici utilizzate nel grafica computazionale.
Dimostrazione con alcuni programmi.
Modalita' d'Esame
Torna alla
home page di Giulio Casciola