Calcolo Numerico (C.d.S. Informatica (L)) A.A.2015/16
(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 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 21 settembre 2015 con il seguente orario:
Lunedi' ore 8:30-11:30 Aula Ercolani 1
Martedi' ore 8:30-10:30 Aula Ercolani 1
Lezioni e Argomenti trattati
- Lu.21/09/15, ore 8.30-11.30: Aula E1
Slide: Introduzione e informazioni sul corso (vedi lucidi).
(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 per troncamento e arrotondamento.
esercizio1:
determinare e posizionare sull'asse reale gli elementi di F(2,3,-1,2);
- Ma.22/09/15, ore 8.30-10.30: Aula E1
Svolto esercizio1; considerazioni sulla distribuzione dei numeri finiti sull'asse reale;
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.
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 usando l'arrotondamento.
esercizio3:
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.
- Lu.28/09/15, ore 9.00-11.30: Aula E1
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);
Aritmetica floating point: precisione di calcolo fra numeri finiti;
in aritmetica finita non valgono le principali proprieta' sulle operazioni aritmetiche;
caratterizzazione dell'unita' di arrotondamento.
Caratterizzazione di u nel caso di arrotondamento ai pari in ANSI/IEEE Std 754.
Come determinare l'unità di arrotondamento utilizzando la sua caratterizzazione.
esercizio4:
Implementare in un qualunque linguaggio un codice basato sulla caratterizzazioen di u
e verificarne il valore ottenuto.
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.
- Ma.29/09/15, ore 8.30-10.30: Aula E1
Esempio numerico sulla cancellazione numerica.
Problema ben posto. Condizionamento di un problema e stabilita' di un algoritmo:
Errore Inerente, Algoritmico e Totale, teorema su E_TOT, E_IN ed E_ALG.
Problema ben/mal condizionato. Algoritmo stabile/instabile.
Numero di condizione e stima di E_IN nel caso di problemi del tipo f:R->R,
f:R^n->R. Esempio sqrt(1-x).
Esempi sulle operazioni aritmetiche di moltiplicazione e addizione fra numeri reali.
- Lu.5/10/15, ore 9.00-11.30: Aula E1
Esempio sqrt(x_1+x_2) - sqrt(x_1).
Esempio sulla determinazione delle radici di un'eq. di secondo grado.
Esempio sulla somma di n numeri reali.
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.
E_IN nella valutazione polinomiale: esempio numerico; stima di E_IN in questo caso.
- Ma.6/10/15, ore 8.30-10.30: Aula E1
Polinomi nella base con centro ed esempio numerico.
Analisi di E_IN per polinomi nella base con centro;
Componente di E_IN che dipende dalla rappresentazione e componente
che non dipende dalla rappresentazione.
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.
- Lu.12/10/15, ore 9.00-11.30: Aula E1
Stima di E_IN nel caso generale di valutazione di un polinomio di grado n in una base assegnata.
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.
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.
- Ma.13/10/15, ore 8.30-10.30: Aula E1
Applicazione dei polinomi nella base di Bernstein al disegno al calcolatore.
Slide: Le Curve di Bezier nel disegno al calcolatore (vedi lucidi)
(file .pdf)
- Lu.19/10/15, ore 9.00-11.30: Aula E1
Slide: Grafica Vettoriale (vedi lucidi)
(file .pdf)
Slide: Presentazione del pacchetto software Mini-System (vedi lucidi).
(file .pdf)
- Ma.20/10/15, ore 8.30-10.30: Aula E1
Introduzione al problema dell'interpolazione polinomiale di funzioni e dati.
Esistenza e unicita' del polinomio interpolante (sistema lineare e matrice di Vandermonde); esempi numerici.
Interpolazione polinomiale nella base di Newton.
Interpolazione nella forma di Lagrange; polinomi elementari di Lagrange.
- Lu.26/10/15, ore 9.00-11.30: Aula E1
Interpolazione di Lagrange: costo computazionale; prima forma di Lagrange e seconda forma di Lagrange e complessita' computazionale.
Interpolazione nella base di Bernstein: soluzione via sistema lineare e metodo PIA.
Applicazione per l'interpolazione con curve di Bezier.
Errore di interpolazione.
Sulla convergenza dell'interpolante all'aumentare del numero dei punti;
esempio su e^x; esempio test di Runge; distribuzione secondo gli zeri di Chebyshev
di grado n+1 e convergenza.
- Ma.27/10/15, ore 8.30-10.30: Aula E1
Errore inerente per il problema dell'interpolazione polinomiale.
Interpolazione alla Hermite in contrapposizione alla Lagrange; esempio di intepolazione
alla Hermite di due punti e derivate nella base di Bernstein.
Funzioni polinomiali a tratti vs a funzioni polinomiali (meno regolari ma piu' flessibili).
- Lu.2/11/15, ore 9.00-11.30: Aula E1
Interpolazione polinomiale di funzioni vettoriali 2D (curve piane) e funzioni scalari con
il Mini-System; esempio di Runge su punti equispaziati e secondo la distribuzione di Chebyshev
con verifica sperimentale dei risultati di convergenza polinomiale (demo con il Mini-System).
Utilizzo del Mini-System come ambiente di sperimentazione di calcolo numerico.
Esaminati alcuni punti da sviluppare come possibili esercitazioni anche ai fini esame.
- Ma.3/11/15, ore 8.30-10.30: Aula E1
Polinomi a tratti lineari e cubici di interpolazione; errore di interpolazione;
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 "derivare agli estremi", "naturali", "periodiche" e "not a knot" ed unicita' della soluzione.
- Lu.9/11/15, ore 9.00-11.30: Aula E1
Ancora su interpolazione a tratti cubica C2 di interpolazione (spline) con derivate agli estremi (interpolazione globale). Errore di interpolazione e proprieta' di minimo.
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.
- Ma.10/11/15, ore 8.30-10.30: Aula E1
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.
Integrazione Numerica
Formule di Quadratura Interpolatorie: formule di quadratura di Newton-Cotes
(interpolazione polinomiale nella forma di Lagrange su punti equispaziati in [a,b]).
- Lu.16/11/15, ore 9.00-11.30: Aula E1
Riprese le formuledi quadratura di Newton-Cotes. 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.
Formule composte interpolatorie;
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.
- Ma.17/11/15, ore 8.30-10.30: Aula E1
Estrapolazione di Richardson e metodo adattivo per l'approssimazione numerica
di un integrale definito ad una tolleranza fissata: caso trapezi e Simpson.
Integrazione numerica nel MiniSystem: lunghezza ed area di una curva polinomiale a tratti.
Function trapezi_adapt e simpson_adapt in ambiente Octave/Matlab: demo.
- Lu.23/11/15, ore 9.00-11.30: Aula E1
Equazioni non lineari
Metodo di bisezione, ipotesi di applicazione, iterazioni del metodo, test di arresto.
Metodo della falsa posizione. 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.
- Ma.24/11/15, ore 8.30-10.30: Aula E1
Definizione di ordine di convergenza di una successione; ordine di convergenza di un metodo
iterativo funzionale.
Teorema di convergenza del metodo di Newton. Ordine di convergenza del metodo di Newton.
Test di arresto.
Esempi: radice quadrata di un numero, inverso di un numero.
Metodo delle secanti, teorema di convergenza, ordine di convergenza, confronto con Newton.
Errore inerente del problema senza dim..
- Lu.30/11/15, ore 9.00-11.30: Aula E1
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)
Intersezione di curve nel Mini-System e metodi in zerip.c per zeri di funzioni.
Applicazioni di zeri di funzioni per intersezioni curva/retta, punti estremi di una
curva, distanza minima punto/curva.
- Ma.1/12/15, ore 8.30-10.30: Aula E1
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).
- Lu.7/12/15, ore 9.00-11.30: Aula E1
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. Esempio numerico.
Richiami su norme vettoriali e matriciali. Condizionamento del problema Ax=b.
Perturbazione di b, poi di A, quindi risultato generale perturbando contemporaneamente A e b.
- Lu.14/12/15, ore 9.00-11.30: Aula E1
Soluzione di un sistema lineare mediante fattorizzazione QR.
Matrici elementari di Householder. Esempio.
Metodo di Householder per fattorizzazione QR.
Complessita` computazionale. Stabilita`. Esempio numerico.
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