Analisi Numerica (sia A-L che M-Z) (C.d.S. Triennale in Informatica) A.A.2007/08
(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.
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 inizieranno il 24 settembre 2007 con il seguente orario:
Lunedi' ore 11:30-13:30 aula E2
Venerdi' ore 10:30-13:30 aula E2
il 24/9 e' prevista la presentazione dei corsi del CdS.
Argomenti trattati a Lezione
- Ve.28/09/07, ore 10.30-13.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: trovare una formula che esprima il numero di elementi di F(beta,t,lambda,omega);
esercizio4: come sono distribuiti sull'asse reale gli elementi di F(2,3,-1,2);
- Lu.01/10/07, ore 11.30-13.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.03/10/07, ore 16.30-18.30: Aula E1
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,
non validita' delle classiche proprieta' delle operazioni.
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.
- Ve.05/10/07, ore 10.30-13.30: Aula E2
Esempio numerico sulla cancellazione.
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, f:R^n->R e 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;
- Lu.08/10/07, ore 11.30-13.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.
- Ve.12/10/07, ore 10.30-13.30: Aula E2
Cambio di base polinomiale: base con centro; esempio;
componente di E_IN che dipende dalla rappresentazione e componente
che non dipende dalla rappresentazione.
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,
- Lu.15/10/07, ore 11.30-13.30: Aula E2.
Def. Pol. di Bernstein 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).
Valutazione di una curva con algoritmo di de Casteljau; suddivisione di una
curva di Bezier; algoritmo di de Casteljau ricorsivo per cubiche;
Dimostrazione in aula di applicazioni delle curve di Bezier.
- Ve.19/10/07, ore 10.30-13.30: Aula E2
Pol. di Bernstein di approssimazione uniforme e interpretazione geometrica
dei suoi coefficienti; formula ricorrente per la derivata dei polinomi base di Bernstein;
valutazione delle derivata di un pol. di Bernstein; antiderivata e integrale.
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 Bernstein, Newton e Lagrange.
- Lu.22/10/07, ore 11.30-13.30: Aula E2.
Ancora sull'interpolazione polinomiale nella base di Lagrange.
Valutazione di polinomi nella base di Newton e di Lagrange.
Interpolazione polinomiale iterativa per aggiunta di punti.
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.
- Ve.26/10/07, ore 10.30-13.30: Aula E2
Non si è fatta lezione per indisponibilità del docente.
- Lu.29/10/07, ore 11.30-13.30: Aula E2.
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).
Applicazione di interpolanti regolari, tipo spline cubiche, per il controllo
numerico di un robot.
- Ve.02/11/07, ore 10.30-13.30: Aula E2
NON si è fatta lezione.
- Lu.05/11/07, ore 11.30-13.30: Aula E2.
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 e nella base con centro.
Introduzione all'ambiente Matlab e dimostrazione con programmi Matlab
(matlab_an0708.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; esempi di interpolazione di punti del piano con curve polinomiali a tratti
vettoriali con tensione.
- Ve.09/11/07, ore 10.30-13.30: Aula E2
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.
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);
- Lu.12/11/07, ore 11.30-13.30: Aula E2.
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 una curva piana.
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.
- Ve.16/11/07, ore 10.30-13.30: Aula E2
Errore inerente; metodo di Newton: ipotesi di applicazione,
derivazione del metodo, iterazioni del metodo, significato geometrico; teorema di
convergenza per metodi di iterazione funzionale;
teorema di convergenza del metodo di Newton; test di arresto per Newton;
propagazione degli errori nei metodi iterativi funzionali.
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.
- Lu.18/11/07, ore 11.30-13.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.23/11/07, ore 10.30-13.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).
- Lu.26/11/07, ore 11.30-13.30: Aula E2.
Fattorizzazione LU con scambio delle righe: formalizzazione ed 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` di LU in senso debole.
Richiami su norme vettoriali.
- Ve.30/11/07, ore 10.30-13.30: Aula E2
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; metodo di Householder per fattorizzazione QR.
- Lu.03/12/07, ore 11.30-13.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, matrice companion.
- Ve.07/12/07, ore 10.30-13.30: Aula E2
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.
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.
- Lu.10/12/07, ore 11.30-13.30: Aula E2.
Esempio numerico su riduzione a matrice di Hessemberg;
Metodo QR per la ricerca degli autovalori.
Applicazione del calcolo degli autovettori per determinare il Page-Rank
di Google.
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