Analisi Numerica (C.d.S. Informatica per il Management (L)) A.A.2011/12
(1^ semestre, 2^ anno)
Esame: prova scritta e/o orale
Crediti: 6
Docente: Giulio Casciola
Attenzione
da mercoledi' 16 novembre gli studenti di chimica avranno attivitą di Laboratorio.
Dipartimento di Matematica - piano terra (Laboratorio Multimediale)
Attenzione
le lezioni frontali (4 CFU) di Laboratorio di Programmazione e Calcolo (C.d.S. in Chimica) A.A.2011/12
sono mutuate con Analisi Numerica
(C.d.S. Informatica per il Management)
il Modulo di Laboratorio (2 CFU) è tenuto dalla Dott.ssa Germana Landi
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
- A. Quarteroni, R.sacco, F. Saleri, Matematica Numerica,
Springer (2008);
- A. Quarteroni, F. Saleri, Calcolo Scientifico esercizi e problemi risolti con Matlab e Octave.
Springer (2008);
- V.Comincioli, Analisi Numerica Metodi Modelli Applicazioni,
McGraw-Hill Libri Italia, (1995)
Altri testi in italiano
- 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)
- 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 13:30-15:30 Aula Ercolani 1
Giovedi' ore 11:30-14:30 Aula Ercolani 1
Lezioni e Argomenti trattati
- Me.28/09/11, ore 13.30-15.30: Aula Ercolani 1
Introduzione e informazioni sul corso (vedi lucidi).
(file .pdf)
Dispensa:
I Numeri Finiti e l'Aritmetica Floating Point.
(file .pdf)
Numeri Finiti
Iniziamo a parlarne: ambiente MatLab (comandi, built-in function, script, work-space);
un esempio insieme: come si puo' calcolare exp(x) per un assegnato x? Prima idea e sua formulazione.
- Gi.29/09/11, ore 11.30-14.30: Aula Ercolani 1
Ripreso esempio sul calcolo di exp(x): formulazione alternativa e confronto risultati
rispetto alla prima formulazione e al valore di exp(x) calcolato da MatLab.
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.
esercizio 1:
determinare gli elementi di F(2,3,-1,2) e collocarli sull'asse reale.
Rappresentazione in memoria dei numeri Finiti (segno, esponente e mantissa). Esempi in base 10 ed in base 2.
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 13.30-15.30: Aula Ercolani 1
Conversione da base 10 a base B (parte intera e decimale).
Definizione di unita' di arrotondamento, teorema di maggiorazione dell'errore
relativo di rappresentazione, corollario sulla rappresentazione di fl(a).
Aritmetica floating point e precisione di calcolo.
esercizio2:
verificare che in aritmetica finita non vale la proprieta' associativa dell'addizione.
Caratterizzazione dell'unita' di arrotondamento;
esercizio 3:
realizzare un piccolo codice di calcolo per determinare l'unitą di
arrotondamento utilizzando la sua caratterizzazione.
Unita' di arrotondamento in IEEE Basic-Single e Basic-Double.
Precisione di rappresentazione in termini di cifre decimali.
- Gi.06/10/11, ore 11.30-14.30: Aula Ercolani 1
Correzione esercizio 1 assegnato. Ripreso ambiente MatLab/Octave ed
esaminati alcuni esempi insieme: realmin, realmax, eps, gradual underflow,
exp2.m, compute_u.m, dimezza.m, sum_0_1.m
Download programmi MatLab/Octave di esempio:
(an1112_1.tgz)
esercizio4:
realizzare un piccolo codice di calcolo per sommare il numero reale 0.1 10 volte;
verificare l'attendibilitą del risultato.
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 sulla cancellazione numerica.
esercizio5:
realizzate un piccolo codice che implementi l'esempio numerico visto sulla cancellazione.
- Me.12/10/11, ore 13.30-15.30: Aula Ercolani 1
Condizionamento di un problema e stabilita' di un algoritmo:
Errore Inerente, Algoritmico e Totale, teorema su E_TOT, E_IN ed E_ALG.
E_IN ed il numero di condizione, E_ALG e il numero di operazioni;
esempio: operazioni aritmetiche di moltiplicazione e addizione fra numeri reali;
esempio: calcolare sqrt(x1+x2) - sqrt(x1).
- Me.19/10/11, ore 13.30-15.30: Aula Ercolani 1
Dispensa:
Funzioni Polinomiali e Interpolazione.
(file .pdf)
Funzioni Polinomiali e Interpolazione
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 nella valutazione di un polinomio: esempio numerico;
stima di E_IN in questo caso.
- Gi.20/10/11, ore 11.30-14.30: Aula Ercolani 1
Componenti di E_IN: dipendenza dalla rappresentazione e non.
Polinomi nella base con centro; analisi di E_IN in questa base;
polinomi e invarianza per traslazioene scala; esempio numerico
e variazione della componente di E_IN.
Base dei polinomi di Bernstein su un intervallo.
Introduzione all'ambiente Matlab/Octave;
Slide: Octave e Matlab.
(file .pdf)
Visionati alcuni script Matlab/Octave come soluzione agli esercizi proposti:
ripreso esempio di approssimazione di e^x con sviluppo di taylor per calcolare e^(-9);
problema esempio per la determinazione delle radici di un'eq. di secondo grado.
- Me.26/10/11, ore 13.30-15.30: Aula Ercolani 1
Problema dell'interpolazione polinomiale di dati. Esempi numerici.
Esistenza e unicita' del polinomio interpolante: sistema lineare con matrice di Vandermonde;
Forma di Newton: base con centri e differenze divise; formula ricorrente per differenze divise.
- Gi.27/10/11, ore 11.30-14.30: Aula Ercolani 1
Esempi numerici di interpolazione nella forma di Newton.
Forma di Lagrange: funzioni elementari di Lagrange e base cardinale; esempi numerici.
Riformulazione forma di Lagrange e complessitą computazionale.
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.
esercizio6:
Determinare (con carta e penna) gli interpolanti di Newton e Lagrange della funzione f(x)=|x|
per x=(-1,-1/2,0,1/2,1).
esercizio7:
Modificare il codice Octave/Matlab "an_pol_interp.m" per interpolare una funzione
polinomiale e poter sperimentare gli errori algoritmici presenti nei metodi di
Newton e Lagrange.
Download programmi MatLab/Octave di esempio:
(an1112_2.tgz)
- Me.02/11/11, ore 13.30-15.30: Aula Ercolani 1
Cenno alle funzioni polinomiali a tratti: motivazione, definizione, regolarita', interpolazione.
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.
Esempio: retta di regressione lineare nella base delle potenze.
- Gi.03/11/11, ore 11.30-14.30: Aula Ercolani 1
Esempio: retta di regressione lineare nella base con centro.
Diminuzione del residuo scegliendo Pn con n maggiore.
Integrazione Numerica.
(file .pdf)
Integrazione Numerica
Formule di Quadratura;
formule interpolatorie polinomiali nella forma di Lagrange su punti equispaziati
(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.
Dimostrazione in aula mediante programmi test in linguaggio Matlab:
Download programmi MatLab/Octave di esempio:
(an1112_3.tgz)
- Me.09/11/11, ore 13.30-15.30: Aula Ercolani 1
Formule composte interpolatorie;
formule composte dei trapezi e di Simpson; cenno a metodi adattivi.
Dispensa:
Equazioni non lineari
(file .pdf)
Equazioni non lineari
Errore inerente; 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.
- Gi.10/11/11, ore 11.30-14.30: Aula Ercolani 1
Metodo di Newton: interpretazione geomerica; teorema di
convergenza; test di arresto. Esempi: radice quadrata di un numero, inverso di un numero.
Definizione di ordine di convergenza, ordine di convergenza dei metodi visti.
Metodo delle secanti, teorema di convergenza, ordine di convergenza.
Download programmi MatLab/Octave di esempio:
(an1112_4.tgz)
- Me.16/11/11, ore 13.30-15.30: Aula Ercolani 1
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 su Pov-Ray (vedi lucidi).
(file .pdf)
- Gi.17/11/11, ore 11.30-14.30: Aula Ercolani 1
Dispensa:
Algebra Lineare Numerica.
(file .pdf)
Algebra Lineare Numerica
Sistemi lineari quadrati: motivazione per
metodi con complessita` computazionale accettabile.
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).
Metodo di Gauss e matrici elementari di Gauss
per la fattorizzazione LU, 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).
- Gi.24/11/11, ore 11.30-14.30: Aula Ercolani 1
Un esempio numerico sulla fattorizzazione con scambio delle righe.
Stabilita` numerica della fattorizzazione LU; fattorizzazione LU
con scambio delle righe e perno massimo.
Richiami su norme vettoriali e norme matriciali; condizionamento del problema Ax=b.
Soluzione di un sistema lineare mediante fattorizzazione QR.
Matrici elementari di Householder.
- Me.30/11/11, ore 13.30-15.30: Aula Ercolani 1
Metodo di Householder per fattorizzazione QR; esempio;
implementazione del metodo per risolvere un sistema lineare;
complessita` computazionale.
- Gi.01/12/11, ore 11.30-14.30: Aula Ercolani 1
Stabilita` della fattorizzazioen QR.
Richiami su: autovalori di una matrice, raggio spettrale, polinomio
caratteristico.
Convergenza di una successione di vettori.
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.
Download programmi MatLab/Octave di esempio:
(an1112_5.tgz)
- Me.07/12/11, ore 13.30-15.30: Aula Ercolani 1
Ricerca degli autovalori e autovettori di una matrice;
matrici simili e trasformazioni per similitudine, matrice diagonalizzabile;
teorema di Schur. Matrici di Hessemberg.
Metodi per la determinazione degli autovalori di una matrice: fase di riduzione a
matrici in forma di Hessemberg, fase di convergenza.
Esempio numerico su riduzione a matrice di Hessemberg;
Metodo QR per la ricerca degli autovalori.
- Me.14/12/11, ore 13.30-15.30: Aula Ercolani 1
Applicazione: Page Rank di Google. Dimostrazione pratica in Matlab/Octave
della ricerca di autovalori e autovettori, della riduzione a matrici di Hessemberg
e dell'algoritmo QR.
Fine delle Lezioni.
Sitografia
Modalita' d'Esame
Torna alla
home page di Giulio Casciola