Analisi Numerica (A-L) (C.d.S. Triennale in Informatica) A.A.2005/06
(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 30 settembre 2005 con il seguente orario:
Lu. 16:30-18.30 Aula Ercolani2
Ve. 9:00-12:00 Aula Magna di Chimica
Argomenti trattati a Lezione
- Ve.30/09/05, ore 9.00-12.00: Aula Magna Chimica
Introduzione e informazioni sul corso.
Dispensa: I Numeri Finiti e l'Aritmetica Floating Point.
(file .ps.gz)
(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, 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
- Lu.03/10/05, ore 16.30-18.30: Aula E2
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, esempi numerici per troncamento e arrotondamento; arrotondamento
ai pari (ANSI/IEEE Std 754).
- Ve.07/10/05, ore 9.00-12.00: Aula Magna Chimica
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
(assegnato un esercizio).
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.
- Lu.10/10/05, ore 16.30-18.30: Aula E2
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.
- Ve.14/10/05, ore 9.00-12.00: Aula Magna Chimica
Dispensa: Interpolazione con Funzioni Polinomiali.
(file .ps.gz)
(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.
- Lu.17/10/05, ore 16.30-18.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].
- Ve.21/10/05, ore 9.00-12.00: Aula Magna Chimica
Proprieta' dei polinomi base di Bernstein,
definizione via formula ricorrente, valutazione numerica,
algoritmo via valutazione funzioni base (ALG1), algoritmo di de
Casteljau (ALG2); complessita' computazionale; curve di Bezier
(definizione vettoriale, punti di controllo, poligonale di controllo);
dimostrazione in aula di applicazioni di curve di Bezier.
- Lu.24/10/05, ore 16.30-18.30: Aula E2
Formula ricorrente per la derivata dei polinomi base di Bernstein,
valutazione della derivata di un polinomio.
primitiva di un polinomio di Bernstein; integrale definito di un
polinomio di Bernstein.
Intepolazione di dati con funzioni polinomiali;
esistenza e unicita' del polinomio interpolante
mediante soluzione di un sistema lineare con matrice di Vandermonde;
interpolazione polinomiale nella base di Newton.
- Ve.28/10/05, ore 9.00-12.00: Aula Magna Chimica
Interpolazione polinomiale nella base e di Bernstein e di Lagrange;
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 e funzioni spline;
interpolazione di Hermite; esempio polinomio cubico nella base di Bernstein;
Interpolazione mediante polinomi a tratti cubici C^1 di Hermite
usando polinomi di Bernstein scalati e traslati in [0,1].
- Lu.31/10/05, ore 16.30-18.30: Aula E2
Non si e' fatta lezione.
- Ve.04/11/05, ore 9.00-12.00: Aula Magna Chimica
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.
Applicazione di interpolanti regolari, tipo spline cubiche, per il controllo
numerico di un robot.
Codice Matlab:
(archivio1 .tgz)
- Lu.07/11/05, ore 16.30-18.30: Aula E2
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.
Retta di regressione lineare nella base delle potenze e nella base con centro.
- Ve.11/11/05, ore 9.00-12.00: Aula Magna Chimica
Dispensa: Integrazione Numerica.
(file .ps.gz)
(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; formule composte o interpolatorie
polinomiali a tratti;
formule composte dei trapezi ed errore di integrazione;
formule composte di Simpson ed errore di integrazione.
- Lu.14/11/05, ore 16.30-18.30: Aula E2
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.
- Ve.18/11/05, ore 9.00-12.00: Aula Magna Chimica
Dispensa: Equazioni non lineari.
(file .ps.gz)
(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;
- Lu.21/11/05, ore 16.30-18.30: Aula E2
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;
- Ve.25/11/05, ore 9.00-12.00: Aula Magna Chimica
Un esempio di applicazione della determinazione delle radici di una
equazione polinomiale: l'intersecatore di POV-Ray per superfici implicite.
Dispensa:
Algebra Lineare Numerica.
(file .ps.gz)
(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.
- Lu.28/11/05, ore 16.30-18.30: Aula E2
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).
- Ve.02/12/05, ore 9.00-12.00: Aula Magna Chimica
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; soluzione di un sistema lineare mediante
fattorizzazione QR della matrice; matrici elementari di Householder.
- Lu.05/12/05, ore 16.30-18.30: Aula E2
Verifica analitica e numerica (su un esempio) dell'effetto di una
trasformazione di Householder; metodo di Householder per fattorizzazione QR;
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.
- Ve.08/12/05, ore 9.00-12.00: Aula Magna Chimica
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; velocita' di convergenza;
test di arresto di un metodo iterativo; metodi di Jacobi e Gauss-Seidel;
esempi numerici.
Modalita' d'Esame
I e II Appello d'esame
Torna alla
home page di Giulio Casciola