Calcolo Numerico (C.d.S. Informatica (L)) A.A.2009/10
(1^ semestre, 2^ anno)
Esame: scritto e/o orale)
Crediti: 6
Docente: Giulio Casciola
Docente Modulo: Carolina Vittoria Beccari
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/Octave.
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)
Orario delle Lezioni
- Le lezioni inizieranno il 28 settembre '09 con il seguente orario:
Lunedi' ore 11:00-13:00 aula Pincherle (Dip.Matematica)
Giovedi' ore 15:00-18:00 aula Pincherle (Dip.Matematica)
Argomenti trattati a Lezione
- Lu.28/09/09, ore 11.00-13.00: Aula Pincherle
Introduzione e informazioni sul corso (proiettati lucidi).
Dispensa:
I Numeri Finiti e l'Aritmetica Floating Point.
(file .pdf)
Numeri Finiti
Richiami sui numeri reali, rappresentazione in base, forma scientifica o normalizzata.
Insieme F dei numeri finiti: base, mantissa, range degli esponenti;
memorizzazione dei numeri finiti (segno, esponente e mantissa); esempi.
esercizio1:
trovare una formula che esprima il numero di elementi di F(beta,t,lambda,omega);
soluzione
esercizio2:
determinare tutti gli elementi di F(2,3,-1,2); quanti sono?
soluzione
esercizio3:
come sono distribuiti sull'asse reale gli elementi di F(2,3,-1,2)?
soluzione
esercizio4:
realizzare un piccolo codice di calcolo per sommare il numero reale 0.1 10 volte;
verificare l'attendibilitā del risultato?
- Gi.01/10/09, ore 15.00-18.00: Aula Pincherle
Correzione di alcuni esercizi assegnati.
Rappresentazione di un numero reale nell'insieme dei numeri finiti.
Approssimazione della mantissa per troncamento e arrotondamento.
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;
Unita' di arrotondamento in IEEE Basic-Single e Basic-Double
esercizio5:
realizzare un piccolo codice di calcolo per determinare l'unitā di
arrotondamento utilizzando la sua caratterizzazione?
esercizio6:
qual č la precisione di rappresentazione in termini di cifre decimali?
- Lu.5/10/09, ore 11.00-13.00: Aula Pincherle
Caratterizzazione di u e arrotondamento ai pari in ANSI/IEEE Std 754.
Aritmetica floating point: precisione di calcolo fra numeri finiti;
esercizio7:
verificare che in aritmetica finita non vale la proprieta' associativa dell'addizione.
Analisi degli errori in avanti e all'indietro.
Analisi in avanti per la moltiplicazione di due numeri reali,
analisi in avanti per l'addizione di due reali, cancellazione numerica.
Esempio numerico sulla cancellazione numerica.
esercizio8:
realizzate un piccolo codice che implementi l'esempio numerico visto sulla cancellazione.
Condizionamento di un problema e stabilita' di un algoritmo:
Errore Inerente, Algoritmico e Totale, teorema su E_TOT, E_IN ed E_ALG.
- Gi.8/10/09, ore 15.00-18.00: Aula Pincherle
Numero di condizione e stima di E_IN nel caso di
problemi del tipo f:R->R, f:R^n->R (ed f:R^n->R^m). Algoritmo stabile e instabile.
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.
Corretti esercizi assegnati nelle lezioni precedenti.
- Lu.12/10/09, ore 11.00-13.00: Aula Pincherle
Dispensa:
Interpolazione con Funzioni Polinomiali.
(file .pdf)
Funzioni Polinomiali e Interpolazione
Introduzione al problema dell'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 per la valutazione di un polinomio: esempio
numerico; stima di E_IN in questo caso.
- Gi.15/10/09, ore 15.00-18.00: Aula Pincherle
Componente di E_IN che dipende dalla rappresentazione e componente
che non dipende dalla rappresentazione.
Polinomi nella base con centro; analisi di E_IN in questa base;
Base dei polinomi di Bernstein su un intervallo;
stesso esempio numerico, ma nella base di Bernstein;
base dei polinomi di Bernstein nell' intervallo [0,1] e loro invarianza
per traslazione e scala; ripreso l'esempio.
Proprieta' dei polinomi base di Bernstein.
Definizione dei polinomi di Bernstein via formula ricorrente, valutazione numerica,
algoritmo che usa formula ricorrente per funzioni base (ALG1), algoritmo di de
Casteljau (ALG2). Curve di Bezier e polinomi di Bernstein;
applicazioni delle curve di Bezier per fonti digitali vettoriali e pacchetti software di disegno.
- Lu.19/10/09, ore 11.00-13.00: Aula Pincherle
Complessita' computazionale per gli algoritmi ALG1 e ALG2.
Formula ricorrente per la derivata dei polinomi base di Bernstein;
valutazione della derivata di un polinomio di Bernstein;
antiderivata e integrale di polinomi nella base di Berstein.
esercizio9:
Calcolare l'integrale definito fra 0 ed 1 dei polinomi base di Berntein di grado n;
e quello definito fra a e b?
soluzione
esercizio10:
Realizzare un codice per il grafico di un polinomio definito nella base di Bernstein.
Curve di Bezier (definizione vettoriale, punti di controllo, poligonale di controllo).
Valutazione di una curva con algoritmo di de Casteljau; suddivisione di una
curva di Bezier; algoritmo di de Casteljau ricorsivo per cubiche;
utilizzo di questo algoritmo per la rasterizzazione di curve.
- Gi.22/10/09, ore 15.00-18.00: Aula Pincherle
Introduzione al problema dell'intepolazione di dati. Intepolazione con funzioni
polinomiali; esistenza e unicita' del polinomio interpolante (matrice di Vandermonde);
interpolazione polinomiale nella base di Newton, Lagrange e Bernstein.
esercizio11:
Determinare il polinomio interpolante nella base di Lagrange dei punti (0,0), (1,1), (2,0)
e poi dei punti (0,0), (1,1), (2,2) e confrontarli con quelli visti a lezione.
Introduzione all'ambiente Matlab/Octave; visionati alcuni programmi Matlab/Octave per
la valutazioni e rappresentazione grafica di polinomi base.
Download programmi Matlab/Octave di esempio:
(matlab_cn0910.tgz)
- Lu.26/10/09, ore 11.00-13.00: Aula Pincherle
Interpolazione nella forma di Newton e aggiunta di punti di interpolazione.
Errore di interpolazione polinomiale.
Sulla convergenza dell'interpolante all'aumentare del numero dei punti; esempio test di Runge;
zeri dei polinomi di Chebyshev di grado n+1 e convergenza.
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);
- Lu.29/10/09, ore 15.00-18.00: Aula Pincherle
Polinomi cubici a tratti di interpolazione di classe C^2 (spline)(interpolazione globale).
Applicazione di interpolante locale (cubiche di Hermite C^1) per il disegno di curve.
Applicazione di interpolante globale (spline cubiche C^2) per il controllo numerico di un robot.
Dimostrazione in aula mediante programmi test in linguaggio Matlab:
dimostrazione sulla convergenza o meno di
interpolanti polinomiali all'aumentare dei punti di interpolazione; esempi sulla funzione
test di Runge; esempi di interpolazione di punti del piano con curve polinomiali a tratti
vettoriali con tensione; esempio di controllo numerico di un robot.
esercizio12:
Realizzare in Octave/Matlab un codice per il disegno di curve di bezier a tratti mediante definizione
e modifica dei Punti di Controllo.
esercizio13:
Modificare il codice Octave/Matlab an_cubic_hermite_curve.m per la modifica di alcuni punti
e ricalcolo dei tratti di Bezier coinvolti.
- Lu.02/11/09, ore 11.00-13.00: Aula Pincherle
Approssimazione ai minimi quadrati; problema
di determinare il minimo di una funzione quadratica in piu` variabili:
sistema della equazioni normali; caso polinomiale nella base delle potenze.
Retta di regressione lineare nella base delle potenze.
esercizio14:
Ripetere l'esempio fatto a lezione sulla retta di regressione lineare usando la base con
contro 1 e x-c con c media aritmetica delle ascisse assegnate.
Cenno all'utilizzo di polinomi ortogonali sui punti x_i assegnati;
variazione del residuo all'aumentare delle dimesioni dello spazio (esempio su P_n);
applicazione dell'approssimazione minimi quadrati a curve nel piano.
- Gi.05/11/09, ore 15.00-18.00: Aula Pincherle
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);
caso n=2 (Simpson); esempio numerico;
errore di integrazione per trapezi e Simpson;
errore di integrazione per n dispari ed n pari.
Formule composte interpolatorie polinomiali a tratti;
formule composte dei trapezi ed errore di integrazione;
Formule composte di Simpson ed errore di integrazione.
esercizio15:
Determinare il passo di integrazione per contenere l'errore
in una tolleranza fissata sia nel caso trapezi che Simpson composti
per il seguente specifico problema: integrazione di 1/(1+x) fra 0 ed 1
con tolleranza 0.5x10^-3
- Lu.09/11/09, ore 11.00-13.00: Aula Pincherle
Estrapolazione di Richardson e formule
adattive per l'approssimazione numerica di un integrale definito ad una
tolleranza fissata: caso trapezi e Simpson.
esercizio16:
Verificare che la formula di estrapolazione di Richardson per Trapezi con
passi h ed h/2 coincide con la formula Simpson composta con h/2.
Applicazione alla lunghezza ed area di una curva piana.
Download programmi Matlab/Octave di esempio:
(matlab_cn0910_2.tgz)
(octave_cn0910_2.tgz)
- Gi.12/11/09, ore 15.00-18.00: Aula Pincherle
Dispensa:
Equazioni non lineari
(file .pdf)
Equazioni non lineari
Metodo di bisezione, ipotesi di applicazione, iterazioni del metodo e test di arresto,
metodo della falsa posizione.
Errore inerente; metodo di Newton: ipotesi di applicazione,
derivazione del metodo, iterazioni del metodo, significato geometrico; teorema di
convergenza per metodi di iterazione funzionale;
Esempio di applicazione della determinazione delle radici di una
equazione polinomiale: l'intersecatore di POV-Ray per superfici implicite.
Sequenza di Sturm per la localizzazione delle radici reali di un'equazione
polinomiale.
Lucidi:
(file .pdf)
- Lu.16/11/09, ore 11.00-13.00: Aula Pincherle
Interpretazione grafica del teorema di convergenza per metodi di iterazione
funzionale. Teorema di convergenza del metodo di Newton;
propagazione degli errori nei metodi iterativi funzionali; test di arresto.
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.
- Gi.19/11/09, ore 15.00-18.00: Aula Pincherle
Esempi numerici di applicazione del metodo di Newton.
Metodo delle secanti, teorema di convergenza, ordine di convergenza.
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.
- Lu.23/11/09, ore 11.00-13.00: Aula Pincherle
Applicazione della fattorizzazione per il calcolo del
determinante e dell'inversa di una matrice.
Fattorizzazione LU con scambio delle righe (o pivoting parziale);
un esempio numerico; soluzione del sistema lineare dopo fattorizzazione con scambio delle righe.
Stabilita` numerica della fattorizzazione LU; fattorizzazione LU
con scambio delle righe e perno massimo; stabilita` numerica di LU in senso debole.
- Gi.26/11/09, ore 15.00-18.00: Aula Pincherle
Richiami su norme vettoriali e norme matriciali; 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.
- Lu.30/11/09, ore 11.00-13.00: Aula Pincherle
Metodo di Householder per fattorizzazione QR di matrici rettangolari;
implementazione del metodo; complessita` computazionale; stabilita`.
Applicazione di QR per sistemi sovradeterminati (vedi problema di
approssimazione ai minimi quadrati).
- Gi.03/12/09, ore 15.00-18.00: Aula Pincherle
Metodi iterativi per la soluzione di sistemi lineari, motivazioni. Richiami
su: autovalori e autovettori di una matrice, raggio spettrale, polinomio
caratteristico, matrice companion;
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; complessita' computazionale.
Metodi di Jacobi e Gauss-Seidel; esempi numerici.
Download programmi Matlab/Octave di esempio:
(matlab_cn0910_3.tgz)
- Lu.07/12/09, ore 11.00-13.00: Aula Pincherle
Oggi non c'e' lezione.
- Gi.10/12/09, ore 15.00-18.00: Aula Pincherle
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.
Esempio numerico su riduzione a matrice di Hessemberg;
Metodo QR per la ricerca degli autovalori.
- Lu.14/12/09, ore 11.00-13.00: Aula Pincherle
Condizionamento del problema di determinare un autovalore.
Applicazione del calcolo degli autovalori per la valutazione di curve e
superfici utilizzate nel grafica computazionale.
Dimostrazione con alcuni programmi.
Download programmi Matlab/Octave di esempio:
(matlab_cn0910_4.tgz)
Lucidi:
(file .pdf)
- Gi.17/12/09, ore 15.00: Aula Pincherle
Compito scritto, simulazione prova d'esame.
Sitografia
Modalita' d'Esame
Torna alla
home page di Giulio Casciola