Calcolo Numerico (C.d.S. Informatica (L)) A.A.2016/17
(1^ semestre, 2^ anno)
Esame: orale
Crediti: 6
Docente: Giulio Casciola
Avviso
Sono disponibili il pacchetto Mini-System (nuova versione)
e gli archivi con codici MATLAB (vedi Download Software e Manuali)
Avviso
E' disponibile la dispensa del corso (vedi Documenti)
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 Analisys,
(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 19 settembre 2016 con il seguente orario:
Lunedi' ore 15:30-18:30 Aula Ercolani 2
Giovedi' ore 13:30-15:30 Aula Ercolani 2
Lezioni e Argomenti trattati
- Lu.19/09/16, ore 15.30-17.30: Aula E2
Slide: Introduzione e informazioni sul corso (vedi lucidi).
(file .pdf)
- Gi.22/09/16, ore 13.30-15.30: Aula E2
Numeri Finiti
Richiami sui numeri reali, rappresentazione in base, forma scientifica o normalizzata.
Insieme F dei numeri finiti: base, mantissa, range degli esponenti.
esercizio1:
determinare e posizionare sull'asse reale gli elementi di F(2,3,-1,2);
Approssimazione di un numero reale nell'insieme dei numeri finiti:
esponente ed approssimazione della mantissa per troncamento o arrotondamento.
Memorizzazione dei numeri finiti (segno, esponente e mantissa); esempi.
ANSI/IEEE Std 754-1985: formati Basic-Single e Basic-Double, NaN, infinity, gradual underflow,
arrotondamento ai pari.
Esercitati su conversione e rappresentazione in memoria.
- Lu.26/09/16, ore 15.30-17.30: Aula E2
Svolto l'esercizio1; considerazioni sulla distribuzione dei numeri finiti sull'asse reale;
Esempio: dato F(2,5,-3,4) con troncamento (8 bit: 1 segno, 3 esponente, 4 mantissa),
rappresentare in memoria il numero reale in base 10, -13.9; fare poi il procedimento
opposto per produrre in output quanto memorizzato.
esercizio2:
Ripetere l'esercizio con F(2,4,-7,8) sia per troncamento che arrotondamento
(8 bit: 1 segno, 4 esponente, 3 mantissa) per +13.9.
Definizione di errore assoluto e relativo.
Teorema di maggiorazione dell'errore assoluto, definizione di unita' di arrotondamento,
teorema di maggiorazione dell'errore relativo, corollario sulla rappresentazione di fl(a);
Caratterizzazione dell'unita' di arrotondamento.
Come determinare l'unità di arrotondamento utilizzando la sua caratterizzazione.
esercizio3:
Implementare in un qualunque linguaggio un codice basato sulla caratterizzazione di u
e verificarne il valore ottenuto.
- Gi.29/09/16, ore 13.30-15.30: Aula E2
Aritmetica floating point: precisione di calcolo fra numeri finiti;
in aritmetica finita non valgono le principali proprieta' sulle operazioni aritmetiche;
Caratterizzazione di u nel caso di arrotondamento ai pari in ANSI/IEEE Std 754.
Problema ben posto. 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.
Errore Inerente, Algoritmico e Totale.
- Lu.03/10/16, ore 15.30-17.30: Aula E2
Teorema su E_TOT, E_IN ed E_ALG.
Condizionamento di un problema e stabilita' di un algoritmo:
Numero di condizione e stima di E_IN nel caso di problemi del tipo f:R->R;
esempio sqrt(1-x).
Generalizzazione per problemi f:R^n->R;
esempi sulle operazioni aritmetiche di moltiplicazione e addizione fra numeri reali.
Esempio sqrt(x_1+x_2) - sqrt(x_1).
Esempio sulla determinazione delle radici di un'eq. di secondo grado.
- Gi.6/10/16, ore 13.30-15.30: Aula E2
Funzioni Polinomiali
Richiami sulle funzioni polinomiali.
Valutazione numerica di un polinomio: metodo della definizione, metodo di Horner, metodo di Ruffini
e loro complessita' computazionale. Valutazione numerica della derivata di un polinomio; esempi numerici. Cenno alla stabilita' dell'algoritmo di Ruffini/Horner.
E_IN nella valutazione polinomiale: esempio numerico.
- Lu.10/10/16, ore 15.30-17.30: Aula E2
Stima di E_IN nel caso dell'esempio numerico.
Generalizzazione della stima di E_IN per valutazione di polinomi di grado n nella base canonica.
Componente di E_IN che dipende dalla rappresentazione e componente
che non dipende dalla rappresentazione.
Polinomi nella base con centro ed esempio numerico.
Analisi di E_IN per polinomi nella base con centro.
Base dei polinomi di Bernstein su un intervallo;
proprieta' dei polinomi base di Bernstein.
Ripreso esempio numerico nella base di Bernstein;
base dei polinomi di Bernstein nell' intervallo [0,1] e loro invarianza
per traslazione e scala.
Definizione dei polinomi di Bernstein via formula ricorrente, valutazione numerica,
ALG1 basato su valutazione pol. di Bernstein con schema ricorrente; complessita' computazionale.
- Gi.13/10/16, ore 13.30-15.30: Aula E2
ALG2 di de Casteljau; complessita' computazionale.
Suddivisione di polinomi su un intervallo via alg. di de Casteljau.
Formula ricorrente per la derivata dei polinomi base di Bernstein.
Valutazione della derivata di un polinomio nella base di Bernstein (via de Casteljau);
primitiva e integrale di un polinomio nella base di Bernstein.
- Lu.17/10/16, ore 15.30-18.30: Aula E2
Introduzione al problema dell'interpolazione polinomiale di funzioni e dati.
Esistenza e unicita' del polinomio interpolante (sistema lineare e matrice di Vandermonde).
Esempi numerici.
Slide: Grafica Vettoriale (vedi lucidi)
(file .pdf)
Applicazione dei polinomi nella base di Bernstein al disegno al calcolatore.
Slide: Le Curve di Bezier nel disegno al calcolatore (vedi lucidi)
(file .pdf)
- Gi.20/10/16, ore 13.30-15.30: Aula E2
Slide: Presentazione del pacchetto software Mini-System (vedi lucidi).
(file .pdf)
Demo con il pacchetto software Mini-System (archivio Mini_System_sdl2.tgz).
Slide: MATLAB: ambiente e linguaggio (vedi lucidi).
(file .pdf)
- Lu.24/10/16, ore 15.30-18.30: Aula E2
Ancora su linguaggio Matlab; demo con script Matlab su gradual underflow e unita' di arrotondamento (archivio
matlab_cn1617.tgz);
Slide: MATLAB: grafici e polinomi (vedi lucidi).
(file .pdf)
Demo in MATLAB su basi polinoniali e curve di Bezier (archivio matlab_bezier_curve.tgz).
Interpolazione polinomiale nella base di Bernstein: soluzione via sistema lineare.
Applicazione per l'interpolazione con curve di Bezier.
Interpolazione polinomiale nella base di Newton.
- Gi.27/10/16, ore 13.30-15.30: Aula E2
Ancora su interpolazione nella base di Newton: aggiunta di un punto di interpolazione; valutazione nella base di
Newton. Esempio numerico. Interpolazione nella forma di Lagrange; polinomi elementari di Lagrange.
Costo computazionale. Valutazione nella base di Lagrange: I e II forma di Lagrange e complessita' computazionale.
Esempio numerico. Errore Inerente per l'interpolazione polinomiale.
Errore di interpolazione. Espressione dell'errore di interpolazione ed
esempio su e^x.
- Lu.31/10/16, ore 15.30-17.30: Aula E2
Esempio test di Runge; distribuzione secondo gli zeri di Chebyshev
di grado n+1 e convergenza.
Funzioni polinomiali a tratti vs funzioni polinomiali (meno regolari ma piu' flessibili).
Interpolazione alla Hermite in contrapposizione alla Lagrange; esempio di intepolazione
alla Hermite di due punti e derivate nella base di Bernstein.
Polinomi a tratti cubici di interpolazione di Hermite di classe C^1 (interpolazione locale); errore di interpolazione; cenno su 'stima delle derivate' da usare nell'interpolazione a tratti cubici di Hermite C^1.
Polinomi a tratti cubici di classe C^2 di interpolazione (spline); condizioni "derivate agli estremi", "naturali", "periodiche" e "not a knot" ed unicita' della soluzione.
- Gi.3/11/16, ore 13.30-15.30: Aula E2
Ancora su interpolazione a tratti cubica C2 di interpolazione (spline) con derivate agli estremi (interpolazione globale). Errore di interpolazione.
Approssimazione ai minimi quadrati con polinomi; problema
di determinare il minimo di una funzione quadratica in piu` variabili:
sistema della equazioni normali in una generica base polinomiale.
- Lu.7/11/16, ore 15.30-17.30: Aula E2
Retta di regressione lineare nella base monomiale; esempio numerico;
stesso esempio usando la base con centro 1 e x-c con c media aritmetica
delle ascisse assegnate. Cenno all'utilizzo di polinomi ortogonali:
applicazione ricerca della soluzione in una sequenza di spazi polinomiali annidati
per soddisfare una assegnata tolleranza.
Demo con Matlab: visionati alcuni script degli archivi matlab_interp_fun.tgz e matlab_approx_fun.tgz
e sperimentata la convergenza polinomiale e polinomiale a tratti sulla funzione test di Runge sia con
punti equispaziati che di Chebyshev.
Demo con Matlab: esempio "controllo di un robot".
- Gi.10/11/16, ore 13.30-15.30: Aula E2
Integrazione Numerica
Formule di Quadratura Interpolatorie: formule di quadratura di Newton-Cotes
(interpolazione polinomiale nella forma di Lagrange su punti equispaziati in [a,b]).
Caso n=1 (trapezi); caso n=2 (Simpson).
Grado di precisione. Errore di integrazione per trapezi e Simpson;
errore di integrazione per n dispari ed n pari; esempi numerici.
Interpolazione polinomiale a tratti e formule di quadratura composte.
- Lu.14/11/16, ore 15.30-17.30: Aula E2
Formule composte dei trapezi ed errore di integrazione.
Formule composte di Simpson ed errore di integrazione.
Esempio su determinazione del passo h per ottenere un'approssimazione a tolleranza assegnata.
Estrapolazione di Richardson e metodo adattivo per l'approssimazione numerica
di un integrale definito ad una tolleranza fissata: caso trapezi e Simpson.
Function trapezi_adapt e simpson_adapt per Matlab/Octave.
- Gi.17/11/16, ore 13.30-15.30: Aula E2
Demo con il Mini-System: Interpolazione polinomiale e polinomiale a tratti di curve piane;
lunghezza ed area di curve piane (integrazione).
Equazioni non lineari
Metodo di bisezione, ipotesi di applicazione, successione di intervalli, test di arresto.
Metodo della falsa posizione, successione di valori, test di arresto.
- Lu.21/11/16, ore 15.30-17.30: Aula E2
Metodo di Newton: ipotesi di applicazione,
derivazione del metodo, iterazioni del metodo, interpretazione geometrica.
Metodi di iterazione funzionale per trovare il punto fisso di una funzione.
Teorema di convergenza al punto fisso di una funzione.
Teorema di convergenza del metodo di Newton. Test di arresto.
Esempi: radice quadrata di un numero, inverso di un numero.
- Gi.24/11/16, ore 13.30-15.30: Aula E2
Definizione di ordine di convergenza di una successione; ordine di convergenza di un metodo
iterativo funzionale. Ordine di convergenza del metodo di Newton.
Metodo delle secanti, teorema di convergenza, ordine di convergenza, confronto con Newton.
Errore inerente.
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.
Slide: POVRay (Persistent Of Vision RayTracer)
(file .pdf)
- Lu.28/11/16, ore 15.30-17.30: Aula E2
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.
Pseudocodice per Fattorizzazione LU e complessita' computazionale.
Esempio di fattorizzazione. 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.
- Gi.1/12/16, ore 13.30-15.30: Aula E2
Ripreso e completato l'esempio numerico. Stabilita` numerica della fattorizzazione LU; fattorizzazione LU
con scambio delle righe e perno massimo. Esempi numerici.
Richiami su norme vettoriali e matriciali. Condizionamento del problema Ax=b.
Caso di perturbazione solo di b. Numero di condizione K(A).
- Lu.12/12/16, ore 15.30-17.30: Aula E2
Ancora sul condizionamento di Ax=b; perturbazione di A, quindi risultato generale perturbando sia A che b.
Soluzione di un sistema lineare mediante fattorizzazione QR.
Matrici elementari di Householder. Esempio. Metodo di Householder per fattorizzazione QR. Esempio numerico.
- Gi.15/12/16, ore 13.30-15.30: Aula E2
Ancora su fattorizzazione QR: complessita` computazionale e stabilita`.
Metodi iterativi per la soluzione di sistemi lineari: motivazioni;
decomposizione della matrice e successione di vettori;
convergenza di una successione di vettori. Teorema di convergenza.
Condizioni sufficienti per la convergenza. Metodi di Jacobi e Gauss-Seidel.
Fine delle Lezioni.
Documenti
Download Software e Manuali
Sitografia
Modalita' d'Esame
Torna alla
home page di Giulio Casciola