Calcolo Numerico (C.d.S. Informatica (L)) A.A.2014/15
(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 (da definire)
- Le lezioni inizieranno il 29 settembre 2014 con il seguente orario:
Mercoledi' ore 11:00-13:30 Aula M1 Minerologia
Giovedi' ore 11:00-13:30 Aula M1 Minerologia
Lezioni e Argomenti trattati
- Gi.2/10/14, ore 11.00-13.30: Aula M1 Mineralogia
Slide: Introduzione e informazioni sul corso (vedi lucidi).
(file .pdf)
Numeri Finiti
Richiami sui numeri reali, rappresentazione in base, forma scientifica o normalizzata.
- Me.8/10/14, ore 11.00-13.30: Aula M1 Mineralogia
Insieme F dei numeri finiti: base, mantissa, range degli esponenti;
Esempio: determinare e posizionare sull'asse reale gli elementi di F(2,3,-1,2);
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, rappresentare in memoria il numero
reale in base 10, -13.9; fare il procedimento opposto per produrre in output quanto memorizzato.
- Gi.9/10/14, ore 11.00-13.30: Aula M1 Mineralogia
esercizio1:
Ripetere l'esercizio fatto insieme con F(2,4,-7,8) sia per troncamento che arrotondamento 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);
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.
Pseudocodice di calcolo per determinare l'unità di arrotondamento utilizzando la sua caratterizzazione.
Caratterizzazione di u nel caso di arrotondamento ai pari in ANSI/IEEE Std 754.
esercizio2:
Implementare il codice dato in un qualunque linguaggio e verificare il valore calcolato di u.
- Me.15/10/14, ore 11.00-13.30: Aula M1 Mineralogia
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.
Condizionamento di un problema e stabilita' di un algoritmo:
Errore Inerente, Algoritmico e Totale, teorema su E_TOT, E_IN ed E_ALG.
- Gi.16/10/14, ore 11.00-13.30: Aula M1 Mineralogia
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. Algoritmo stabile e instabile.
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 e Interpolazione
Richiami sulle funzioni polinomiali.
- Me.22/10/14, ore 11.00-13.30: Aula M1 Mineralogia
Ancora richiami su funzioni polinomiali.
Valutazione numerica di un polinomio: metodo di Horner, metodo di Ruffini
e loro complessita' computazionale.
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. Polinomi nella base con centro
ed esempio numerico.
- Gi.23/10/14, ore 11.00-13.30: Aula M1 Mineralogia
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.
Stima di E_IN nel caso generale di valutazione di un polinomio di grado n in una base assegnata.
Base dei polinomi di Bernstein su un intervallo;
ripreso esempio numerico nella base di Bernstein;
base dei polinomi di Bernstein nell' intervallo [0,1] e loro invarianza
per traslazione e scala.
Proprieta' dei polinomi nella base di Bernstein.
- Me.29/10/14, ore 11.00-13.30: Aula M1 Mineralogia
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 (de Casteljau);
- Gi.30/10/14, ore 11.00-13.30: Aula M1 Mineralogia
Slide: Presentazione del pacchetto software Mini-System
(vedi lucidi).
(file .pdf)
Slide: Presentazione di Hardware e Software per la grafica del Mini-System (vedi lucidi).
(file .pdf)
Slide: Introduzione alle librerie SDL 1.2 (vedi lucidi).
(file .pdf)
- Me.5/11/14, ore 11.00-13.30: Aula M1 Mineralogia
Slide: Libreria Grafica SDL: Esempi (vedi lucidi).
(file .pdf)
Visti esempi di programmi con SDL; esaminate le strutture dati piu'
importanti del Mini-System.
Slide: Le Curve di Bezier nel disegno al calcolatore (vedi lucidi)
(file .pdf)
- Gi.6/11/14, ore 11.00-13.30: Aula M1 Mineralogia
Suddivisione di una curva di Bezier. Primitiva e integrale di un polinomio
nella base di Bernstein.
Introduzione al 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.
- Me.12/11/14, ore 11.00-13.30: Aula M1 Mineralogia
Interpolazione nella base di Bernstein.
Interpolazione nella forma di Lagrange; polinomi elementari di Lagrange;
costo computazionale; prima forma di Lagrange e seconda forma di Lagrange.
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. Funzioni di interpolazione polinomiali a tratti.
- Gi.13/11/14, ore 11.00-13.30: Aula M1 Mineralogia
Interpolazione polinomiale di funzioni vettoriali 2D (curve piane).
Interpolazione alla Lagrange e all'Hermite. Esempio di interpolazione di
Hermite di due punti e derivate nella base di Bernstein.
Polinomi a tratti cubici di Hermite di classe C^1 (interpolazione locale).
Demo, mediante programmi test in linguaggio Matlab/Octave, sulla convergenza o meno di
interpolanti polinomiali all'aumentare dei punti di interpolazione.
- Me.19/11/14, ore 11.00-13.30: Aula M1 Mineralogia
Presentazione della 'Documentazione del mini-System' (vedi Documenti) e presentazione
di possibili esercizi da svolgere.
Cenno su 'stima delle derivate' da usare nell'interpolazione a tratti cubici di Hermite C^1.
Polinomi a tratti cubici di classe C^2 (spline) (interpolazione globale).
- Gi.20/11/14, ore 11.00-13.30: Aula M1 Mineralogia
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.
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.
Applicazioni; ricerca della soluzione in una sequenza di spazi polinomiali annidati;
cenno all'utilizzo di polinomi ortogonali.
- Me.26/11/14, ore 11.00-13.30: Aula M1 Mineralogia
Integrazione Numerica
Formule di Quadratura Interpolatorie; interpolazione polinomiale nella forma di
Lagrange su punti equispaziati in [a,b] (formule di quadratura di Newton-Cotes);
caso n=1 (trapezi); caso n=2 (Simpson). 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 di riduzione dell'errore;
determinazione del passo h per ottenere un'approssimazione a tolleranza assegnata.
- Gi.27/11/14, ore 11.00-13.30: Aula M1 Mineralogia
Estrapolazione di Richardson e formule adattive per l'approssimazione numerica
di un integrale definito ad una tolleranza fissata: caso trapezi e Simpson.
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.
- Me.3/12/14, ore 11.00-13.30: Aula M1 Mineralogia
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.
Propagazione degli errori nei metodi iterativi funzionali. Test di arresto.
Esempi: radice quadrata di un numero, inverso di un numero.
Definizione di ordine di convergenza di una successione; ordine di convergenza di Newton.
Metodo delle secanti, teorema di convergenza, ordine di convergenza, confronto con Newton.
Errore inerente del problema.
- Gi.4/12/14, ore 11.00-13.30: Aula M1 Mineralogia
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)
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.
- Me.10/12/14, ore 11.00-13.30: Aula M1 Mineralogia
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.
Stabilita` numerica della fattorizzazione LU; fattorizzazione LU
con scambio delle righe e perno massimo. Esempi numerici.
Richiami su norme vettoriali.
- Me.10/12/14, ore 16.30-18.30: Aula E1
Richiami su norme vettoriali e matriciali. Condizionamento del problema Ax=b.
Perturbazione di b, poi di A, quindi risultato perturbando contemporaneamente A e b.
Soluzione di un sistema lineare mediante fattorizzazione QR.
Matrici elementari di Householder.
Metodo di Householder per fattorizzazione QR.
- Gi.11/12/14, ore 11.00-13.30: Aula M1 Mineralogia
Esempio numerico; implementazione metodo di Househilder; complessita` computazionale; 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. Test di arresto. 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