Calcolo Numerico (C.d.S. Informatica (L)) A.A.2011/12
(1^ semestre, 2^ anno)
Esame: 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/Octave.
Testi Consigliati
- R.Bevilacqua, D.Bini, M.Capovani, O.Menchi, Metodi numerici,
Zanichelli (1992)
- J.Stoer, R.Bulirisch, Introduction to Numerical Analisysy,
(second edition) Springer Verlag (1997)
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 26 settembre 2011 con il seguente orario:
Mercoledi' ore 08:30-11:30 Aula Ercolani 2
Venerdi' ore 08:30-10:30 Aula Ercolani 2
Lezioni e Argomenti trattati
- Me.28/09/11, ore 08.30-11.30: Aula Ercolani 2
Introduzione e informazioni sul corso (vedi lucidi).
(file .pdf)
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;
Approssimazione della mantissa per troncamento e arrotondamento.
Rappresentazione di un numero reale nell'insieme dei numeri finiti.
esercizio1:
trovare una formula che esprima il numero di elementi di F(beta,t,lambda,omega);
esercizio2:
determinare tutti gli elementi di F(2,3,-1,2); quanti sono?
esercizio3:
come sono distribuiti sull'asse reale gli elementi di F(2,3,-1,2) e quindi in generale i numeri finiti?
- Ve.28/09/11, ore 08.30-09.30: Aula Ercolani 2
Memorizzazione dei numeri finiti (segno, esponente e mantissa); esempi.
Definizione di errore assoluto e relativo. Cenni su ANSI/IEEE Std 754-1985.
Esercitati su conversione e rappresentazione in memoria.
- Me.05/10/11, ore 08.30-11.30: Aula Ercolani 2
ANSI/IEEE Std 754-1985: formati Basic-Single e Basic-Double, NaN, infinity, gradual underflow.
Teorema di maggiorazione dell'errore assoluto, unita' di arrotondamento, teorema di maggiorazione
dell'errore relativo, corollario sulla rappresentazione di fl(a);
unita' di arrotondamento in IEEE Basic-Single e Basic-Double,
precisione di rappresentazione in termini di cifre decimali.
Aritmetica floating point: precisione di calcolo fra numeri finiti;
Caratterizzazione dell'unita' di arrotondamento;
caratterizzazione di u nel caso di arrotondamento ai pari in ANSI/IEEE Std 754.
esercizio4:
realizzare un piccolo codice per verificare che in aritmetica finita non vale la proprieta' associativa dell'addizione.
esercizio5:
realizzare un piccolo codice di calcolo per sommare il numero reale 0.1 10 volte;
verificare l'attendibilita' del risultato.
esercizio6:
realizzare un piccolo codice di calcolo per determinare l'unità di
arrotondamento utilizzando la sua caratterizzazione.
Analisi degli errori in avanti e all'indietro.
- Ve.07/10/11, ore 08.30-10.30: Aula Ercolani 2
Correzione degli esercizi 1,2 e 3 assegnati.
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.
esercizio7:
realizzare 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.
- Me.12/10/11, ore 08.30-11.30: Aula Ercolani 2
Numero di condizione e stima di E_IN nel caso di problemi del tipo f:R->R.
Stima di E_IN nel caso di problemi 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.
Dispensa:
Funzioni Polinomiali e Interpolazione.
(file .pdf)
Funzioni Polinomiali e Interpolazione
- Ve.14/10/11, ore 08.30-10.30: Aula Ercolani 2
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.
- Me.19/10/11, ore 08.30-11.30: Aula Ercolani 2
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;
esercizio8:
Applicare la definizione data per ricavare i poinomi di Bernstein di grado 3.
Esempio numerico di valutazione 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). Complessita' computazionale per gli algoritmi ALG1 e ALG2.
esercizio9:
Realizzare un codice che implementi uno degli algoritmi visti per la valutazione di
un polinomio definito nella base di Bernstein. Si proceda poi ad un suo grafico.
- Ve.21/10/11, ore 08.30-10.30: Aula Ercolani 2
Slide: Le Curve di Bezier.
(file .pdf)
Curve di Bezier (definizione vettoriale, punti di controllo, poligonale di controllo).
Curva di de Casteljau; suddivisione di una
curva di Bezier/de Casteljau; algoritmo di de Casteljau ricorsivo per cubiche;
utilizzo di questo algoritmo per la rasterizzazione di curve.
Applicazioni delle curve di Bezier per fonti
digitali vettoriali e pacchetti software di disegno.
- Me.26/10/11, ore 08.30-11.30: Aula Ercolani 2
Formula ricorrente per derivata polinomi base di Bernstein;
valutazione della derivata di un polinomio nella base di Bernstein (de Casteljau);
antiderivata e integrale di polinomi nella base di Berstein.
esercizio10:
Calcolare l'integrale definito fra 0 ed 1 dei polinomi base di Berntein di grado n;
e quello definito fra a e b?
Introduzione all'ambiente Matlab/Octave;
Slide: Octave e Matlab.
(file .pdf)
Demo su Octave; visionati alcuni programmi Matlab/Octave
Download:
programmi Matlab/Octave di esempio:
(matlab_cn1112_1.tgz)
esercizio11:
Realizzare uno script Matlab/Octave per disegnare una curva di Bezier.
- Ve.28/10/11, ore 08.30-10.30: Aula Ercolani 2
Introduzione al problema dell'interpolazione polinomiale di dati.
Esistenza e unicita' del polinomio interpolante (sisteme lineare e matrice di Vandermonde);
interpolazione polinomiale nella base di Newton, Bernstein e Lagrange; polinomi elementari di Lagrange.
esercizio12:
Determinare (carta e penna) il polinomio interpolante nella forma di Lagrange e poi di Newton 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.
Riformulazione polinomio di Lagrange, esempio.
- Me.02/11/11, ore 08.30-11.30: Aula Ercolani 2
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;
polinomi a tratti cubici di Hermite di classe C^1 (interpolazione locale);
polinomi a tratti cubici di classe C^2 (spline) (interpolazione globale);
Demo, mediante programmi test in linguaggio Matlab/Octave, sulla convergenza o meno di
interpolanti polinomiali all'aumentare dei punti di interpolazione.
- Ve.04/11/11, ore 08.30-10.30: Aula Ercolani 2
Applicazione di interpolante globale (spline cubiche C^2) per il controllo numerico di un robot.
Approssimazione ai minimi quadrati con polinomi; problema
di determinare il minimo di una funzione quadratica in piu` variabili:
sistema della equazioni normali; caso polinomiale in una base generica.
- Me.09/11/11, ore 08.30-11.30: Aula Ercolani 2
Retta di regressione lineare nella base delle potenze; esempio numerico.
esercizio13:
Ripetere l'esempio fatto a lezione sulla retta di regressione lineare usando la base con
centro 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 Pn.
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.
- Ve.11/11/11, ore 08.30-10.30: Aula Ercolani 2
Formule composte interpolatorie;
formule composte dei trapezi ed errore di integrazione; esempio;
formule composte di Simpson ed errore di integrazione; esempio.
Estrapolazione di Richardson e formule
adattive per l'approssimazione numerica di un integrale definito ad una
tolleranza fissata: caso trapezi e Simpson.
- Me.16/11/11, ore 08.30-11.30: Aula Ercolani 2
Dispensa:
Equazioni non lineari
(file .pdf)
Equazioni non lineari
Errore inerente del problema.
Metodo di bisezione, ipotesi di applicazione, iterazioni del metodo e test di arresto;
metodo della falsa posizione.
Metodo di Newton: ipotesi di applicazione,
derivazione del metodo, iterazioni del metodo, significato geometrico; teorema di
convergenza al punto fisso di una funzione; interpretazione grafica del teorema di convergenza.
Teorema di convergenza del metodo di Newton.
Propagazione degli errori nei metodi iterativi funzionali.
- Ve.18/11/11, ore 08.30-10.30: Aula Ercolani 2
Ancora su propagazione degli errori; test di arresto.
Esempi: radice quadrata di un numero, inverso di un numero.
Definizione di ordine di convergenza di una successione,
ordine di convergenza del metodo di Newton.
Esempi numerici di applicazione del metodo di Newton.
Metodo delle secanti, teorema di convergenza, ordine di convergenza.
- Ve.25/11/11, ore 08.30-10.30: Aula Ercolani 2
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.
Demo: visionati alcuni programmi Matlab/Octave
Download:
programmi Matlab/Octave di esempio:
(matlab_cn1112_2.tgz)
(matlab_cn1112_3.tgz)
- Me.30/11/11, ore 08.30-11.30: Aula Ercolani 2
Dispensa:
Algebra Lineare Numerica.
(file .pdf)
Algebra Lineare Numerica
Soluzione di un sistema lineare:
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).
Fattorizzazione LU di Gauss e matrici elementari, 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);
un esempio numerico.
Stabilita` numerica della fattorizzazione LU; fattorizzazione LU
con scambio delle righe e perno massimo.
- Ve.02/12/11, ore 08.30-10.30: Aula Ercolani 2
Richiami su norme vettoriali e matriciali; condizionamento del problema Ax=b.
Soluzione di un sistema lineare mediante fattorizzazione QR.
Matrici elementari di Householder.
- Me.07/12/11, ore 08.30-11.30: Aula Ercolani 2
Metodo di Householder per fattorizzazione QR;
implementazione del metodo; complessita` computazionale; stabilita`.
Convergenza di una successione di vettori e risultati preliminari.
Metodi iterativi per la soluzione di sistemi lineari: motivazioni;
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.
- Ve.09/12/11, ore 08.30-10.30: Aula Ercolani 2
Richiami su: autovalori e autovettori di una matrice;
matrici simili e trasformazioni per similitudine, matrice diagonalizzabile,
teorema di Schur, riduzione a matrici di Hessemberg superiore, metodo QR.
Applicazione: Page Rank di Google.
Fine delle Lezioni.
Sitografia
Modalita' d'Esame
Torna alla
home page di Giulio Casciola