Calcolo Numerico (C.d.S. Informatica (L)) A.A.2017/18
(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 giovedi' 28 settembre 2017 con il seguente orario:
Lunedi' ore 15:30-18:30 Aula Ercolani 1
Giovedi' ore 16:30-18:30 Aula Ercolani 1
Lezioni e Argomenti trattati
- Gi.28/09/17, ore 16.30-18.30: Aula E1
Slide: Introduzione e informazioni sul corso.
(file .pdf)
Numeri Finiti
Richiami sui numeri reali e rappresentazione in base
- Lu.2/10/17, ore 15.30-17.30: Aula E1
Insieme F dei numeri finiti: base, mantissa, range degli esponenti.
Esempio: posizionare sull'asse reale gli elementi di F(2,3,-1,2).
esercizio1:
determinare e posizionare sull'asse reale gli elementi di F(10,2,-4,5);
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.
Esercitati su conversione e rappresentazione in memoria.
- Gi.5/10/17, ore 16.30-18.30: Aula E1
ANSI/IEEE Std 754-1985: arrotondamento ai pari.
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. Rieseguito per arrotondamento.
Definizione di errore assoluto e relativo.
Ripreso l'esercizio e calcolati gli errori relativi sia nel caso di trocamento che di arrotondamento.
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.
Teorema di maggiorazione dell'errore assoluto, definizione di unita' di arrotondamento (U),
teorema di maggiorazione dell'errore relativo.
Ripreso l'esercizio, calcolato U e confrontato con gli errori relativi prima ottenuti;
Calcolo di U nei casi basic/single e basic/double.
Caratterizzazione dell'unita' di arrotondamento.
Come determinare l'unitŕ di arrotondamento utilizzando la sua caratterizzazione.
Caratterizzazione di U nel caso di arrotondamento ai pari in ANSI/IEEE Std 754.
esercizio3:
Implementare un codice (in un qualunque linguaggio) per determinare U basato sulla sua caratterizzazione
e verificarne il valore ottenuto.
- Lu.9/10/17, ore 15.30-17.30: Aula E1
Ancora su caratterizzazione di U.
Aritmetica floating point: precisione di calcolo fra numeri finiti;
in aritmetica finita non valgono le principali proprieta' sulle operazioni aritmetiche;
Problema ben posto. Analisi degli errori in avanti e all'indietro.
Corollario sulla rappresentazione di fl(a);
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.
Teorema su E_TOT, E_IN ed E_ALG.
Condizionamento di un problema e stabilita' di un algoritmo per problemi ben posti.
- Gi.12/10/17, ore 16.30-18.30: Aula E1
Numero di condizione e stima di E_IN nel caso di problemi del tipo f:R->R;
esempi: x1*x2, x1+x2, sqrt(1-x).
Generalizzazione per problemi f:R^n->R;
esempi: x1*x2, x1+x2, sqrt(x_1+x_2) - sqrt(x_1).
Esempio sulla determinazione delle radici di un'eq. di secondo grado.
- Lu.16/10/17, ore 15.30-18.30: Aula E1
Attivita' di LABoratorio (leggere prima della lezione le slide su "MATLAB: ambiente e linguaggio"
e venire con il proprio portatile con Matlab installato)
(vedi testo Esercitazione LAB1_cn1718.pd e archivio script LAB1_cn1718.tgz).
- Gi.19/10/17, ore 16.30-18.30: Aula E1
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. Stima di E_IN nel caso dell'esempio numerico.
- Lu.23/10/17, ore 15.30-17.30: Aula E1
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.
Polinomi e invarianza per traslazione e scala (cambio di variabile).
Cambio di variabile per polinomi di Bernstein nell' intervallo [0,1]. Ripreso esempio numerico.
- Gi.26/10/17, ore 16.30-18.30: Aula E1
Definizione dei polinomi di Bernstein via formula ricorrente, valutazione numerica,
ALG1 basato su valutazione pol. di Bernstein con schema ricorrente; complessita' computazionale.
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.30/10/17, ore 15.30-17.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)
Elementi di grafica vettoriale ed esempi con inkscape.
Slide: Grafica Vettoriale (vedi lucidi)
(file .pdf)
- Gi.2/11/17, ore 16.30-18.30: Aula E1
Rasterizzazione di curve di Bézier.
Slide: Rasterizzazione di curve di Bézier (vedi lucidi)
(file .pdf)
Esempio sullo sviluppo di Taylor con Matlab (script taylor_sin);
Introduzione al problema dell'interpolazione polinomiale di dati e funzioni.
- Lu.6/11/17, ore 15.30-17.30: Aula E1
Ripreso il problema dell'interpolazione polinomiale di dati.
Esistenza e unicita' del polinomio interpolante (sistema lineare e matrice di Vandermonde).
Esempi numerici.
Interpolazione polinomiale nella base di Newton. Esempi numerici. Valutazione nella base di Newton.
Interpolazione adattiva: aggiunta di un punto di interpolazione alla volta.
Interpolazione nella forma di Lagrange; polinomi elementari di Lagrange.
- Gi.9/11/17, ore 16.30-18.30: Aula E1
Costo computazionale. Valutazione nella base di Lagrange: I e II forma di Lagrange e complessita' computazionale.
Esempio numerico.
Interpolazione polinomiale nella base di Bernstein: soluzione via sistema lineare.
Interpolazione di funzione: errore di interpolazione. Espressione dell'errore di interpolazione ed
esempio su e^x. 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).
- Lu.13/11/17, ore 15.30-18.30: Aula E1
Attivita' di LABoratorio. (slide su "Grafica in MATLAB")
(vedi testo Esercitazione LAB2_cn1718.pdf, libreria anmglib_2.0 (archivio anmglib_2.0.tgz) e archivio script LAB2_cn1718.tgz).
- Gi.16/11/17, ore 16.30-18.30: Aula E1
Riprese e completate slide su "Grafica MATLAB" e script in LAB2_cn1718.tgz. Grafica Vettoriale ed SVG (vedi slide svg_1718.pdf).
- Lu.20/11/17, ore 15.30-17.30: Aula E1
Interpolazione polinomiale tratti. Esempio: interpolazione polinomiale a tratti lineare C0 e convergenza.
Interpolazione polinomiale a tratti cubia C1 di Hermite; cenno su 'stima delle derivate'; convergenza e bound.
Curve Spline.
Slide: Curve Spline (vedi lucidi)
(file .pdf)
- Gi.23/11/17, ore 16.30-18.30: Aula E1
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.
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.
- Lu.27/11/17, ore 15.30-18.30: Aula E1
Attivita' di LABoratorio. (Curve a tratti di interpolazione e curve spline)
(vedi testo Esercitazione LAB3_cn1718.pdf e archivio script LAB3_cn1718.tgz).
- Gi.30/11/17, ore 16.30-18.30: Aula E1
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.
Formule dei trapezi e Simpson composte ed errori di integrazione.
Esempio su determinazione del passo h per ottenere un'approssimazione a tolleranza assegnata.
- Lu.4/12/17, ore 15.30-18.30: Aula E1
Lezione annullata
- Gi.7/12/17, ore 16.30-18.30: Aula E1
Estrapolazione di Richardson e metodo adattivo per l'approssimazione numerica
di un integrale definito ad una tolleranza fissata: caso trapezi.
Equazioni non lineari
Metodo di bisezione, ipotesi di applicazione, successione di intervalli, test di arresto.
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.
- Lu.11/12/17, ore 15.30-18.30: Aula E1
Esempi: radice quadrata di un numero, inverso di un numero.
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 e ordine di convergenza, confronto con Newton. Test di arresto.
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.
- Ma.12/12/17, ore 11.30-13.30: Aula E1
Applicazione della fattorizzazione per il calcolo del
determinante e dell'inversa di una matrice.
Fattorizzazione LU con scambio delle righe; 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.
Numero di condizione K(A).
- Gi.14/12/17, ore 16.30-18.30: Aula E1
Soluzione di un sistema lineare mediante fattorizzazione QR.
Matrici elementari di Householder. Metodo di Householder per 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.
Fine delle Lezioni.
Documenti
Download Software e Manuali
Sitografia
Modalita' d'Esame
Torna alla
home page di Giulio Casciola