Metodi Numerici per il Calcolo (C.d.S. Informatica per il Management (L)) A.A.2016/17
(1^ semestre, 2^ anno)
Esame: prova orale
Crediti: 8
Docente: Giulio Casciola
Esito Prova di Fine Corso
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
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 19 settembre 2016 con il seguente orario:
Lunedi' ore 13:00-15:00 Aula Tonelli (Dip. Mat.)
Mercoledi' ore 16:30-18:30 Aula Tonelli (Dip. Mat.)
Venerdi' ore 13:30-16:30 Aula Ercolani 1
Lezioni e Argomenti trattati
- Lu.19/09/16, ore 13:00-15:00: Aula Tonelli
Introduzione e informazioni sul corso (vedi lucidi).
(file .pdf)
Numeri Finiti
Poche parole di introduzione.
- Me.21/09/16, ore 16:30-18:30: Aula Tonelli
Richiami sui numeri reali, rappresentazione in base, forma scientifica o normalizzata.
Insieme F dei numeri finiti: base, mantissa, range degli esponenti.
esercizio 1:
Dato l'insieme F(2,3,-1,2), determinare tutti i suoi elementi; disporli sull'asse reale e
discutere come sono distribuiti.
Rappresentazione di un numero reale nell'insieme dei numeri finiti:
casi di underflow e overflow; approssimazione della mantissa per troncamento e arrotondamento.
Rappresentazione in memoria dei numeri Finiti (segno, esponente e mantissa).
Esempi in base 10.
- Ve.23/09/16, ore 13:30-16:30: Aula Ercolani 1
Svolto l'esercizio1 in aula.
Cenni su ANSI/IEEE Std.754-1985: Basic-Single e Basic-Double,
Definizioni di Errore Assoluto e Relativo.
Teorema di maggiorazione dell'errore assoluto di rappresentazione.
Definizione di unita' di arrotondamento.
Teorema di maggiorazione dell'errore relativo di rappresentazione.
Corollario sulla rappresentazione di fl(a).
Esempi in base 2 di conversione, memorizzazione e riconversione nel caso di troncamento e arrotondamento;
richiamata conversione da base 10 a base 2 di un numero reale (parte intera e frazionaria);
calcolo dell'errore relativo e confronto con u in questo esempio.
esercizio 2:
Ripetere l'esercizio di conversione, memorizzazione e riconversione per +13.9 in F(2,4,-7,8).
- Lu.26/09/16, ore 13:00-15:00: Aula Tonelli
Ripresi gli algoritmi di conversione di parte intera e decimale da base 10 a base <10.
Precisione e cifre significative.
L'unita' di arrotondamento in Basic-Single e Basic-Double.
Esercitati su conversione e rappresentazione in memoria.
Aritmetica floating point e precisione di calcolo.
Esempio su proprieta' associativa dell'addizione in aritmetica finita.
Caratterizzazione dell'unita' di arrotondamento.
Arrotondamneto ai pari e caratterizzazione dell'unita' di arrotondamento in ANSI/IEEE.
esercizio 3:
Realizzare uno pseudocodice di calcolo per determinare l'unità di
arrotondamento e il numero t di cifre dedicate alla mantissa nel
sistema floating point in uso.
- Me.28/09/16, ore 16:30-18:30: Aula Tonelli
Problema ben posto. Modellizzazione di un problema come f:R^n->R.
Analisi degli errori: in avanti e all'indietro. Esempio di analisi in avanti sulla moltiplicazione di due numeri reali, esempio sull'addizione di due numeri reali e cancellazione numerica. Esempio numerico di cancellazione: sqrt(x_1+x_2) - sqrt(x_1) con x_1 e x_2 reali positivi.
Errori Totale, Inerente e Algoritmico. Teorema su E_TOT, E_IN ed E_ALG. Esempio di analisi in avanti per
ricavare E_ALG ed E_IN.
- Ve.30/09/16, ore 13:30-16:30: Aula Ercolani 1
E_IN o condizionamento di un problema, E_ALG o stabilita' di un algoritmo.
Esempio: espressione ((1+x)-1)/x: analisi in avanti di stabilita'.
Stima di E_IN nel caso di un problema
modellizzato come f:R->R derivabile; generalizzazione della stima di E_IN
nel caso di problemi f:R^n->R; numero/i di condizione.
Esempi sulle operazioni aritmetiche di moltiplicazione
e addizione fra numeri reali. Esempio: sqrt(x_1+x_2) - sqrt(x_1).
Ripreso Esempio sqrt(x_1+x_2) - sqrt(x_1).
Esempio: radici di un'eq. di secondo grado.
- Lu.3/10/16, ore 13:00-15:00: Aula Tonelli
Funzioni Polinomiali e Interpolazione
Richiami sui polinomi. Valutazione numerica di un polinomio.
Valutazione numerica di un polinomio: metodo dalla definizione, metodo di Horner,
metodo di Ruffini; complessità computazionale. Valutazione numerica della derivata del polinomio.
Esempio numerico di valutazione e derivate. Cenno alla stabilita' dell'algoritmo di Ruffini/Horner.
- Me.5/10/16, ore 16:30-18:30: Aula Tonelli
Valutazione polinomiale: esempio ed errore inerente. Stima di E_IN nell'esempio visto.
Polinomi nella base con centro; stima di E_IN in questa base;
variazione delle componenti di E_IN: dipendenza dalla rappresentazione e non.
Base dei polinomi di Bernstein su un intervallo.
Polinomi e invarianza per traslazione e scala (cambio di variabile).
Cambio di variabile per polinomi nella base di Bernstein;
analisi di E_IN nella base di Bernstein. Ripreso esempio numerico.
- Ve.7/10/16, ore 13:30-16:30: Aula E1
Attivita' di Laboratorio.
Ambiente MatLab (istruzioni/comandi, built-in function) (vedi slide su 'MATLAB/Octave I parte' in Documenti);
Esercitazione 1 (vedi file pdf e archivio tgz in Download Materiale Lab).
- Lu.10/10/16, ore 13:00-15:00: Aula Tonelli
Proprieta' dei polinomi base di Bernstein; algoritmo di valutazione mediante
formula ricorrente sui pol. base di Bernstein (Alg.1).
Algoritmo di valutazione di de Casteljau (Alg.2).
Cenno ad applicazioni dei polinomi nella base di Bernstein (curve di Bezier).
Problema dell'interpolazione polinomiale di dati e funzioni (Interpolazione alla Lagrange).
- Me.12/10/16, ore 16:30-18:30: Aula Tonelli
Richiami ed esempio su polinomio di Taylor (Interpolazione alla Hermite).
Esistenza e unicita' del polinomio interpolante: sistema lineare e matrice di Vandermonde.
Esempi numerici. Interpolazione nella Forma di Newton: base con centri. Soluzione di sistema lineare
triangolare inferiore. Esempio numerico. Newton e interpolazione di punti aggiuntivi.
- Ve.14/10/16, ore 13:30-16:30: Aula E1
Attivita' di Laboratorio.
MatLab/Octave (script e function) ancora su Esercitazione 1;
MatLab /Octave II (vedi lucidi 'IIparte' in Documenti);
Esercitazione 2 (vedi file pdf e archivio tgz in Download Materiale Lab).
- Lu.17/10/16, ore 13:00-15:00: Aula Tonelli
Valutazione polinomi nella base di Newton.
Interpolazione nella Forma di Lagrange: funzioni elementari di Lagrange.
Prima e seconda forma di Lagrange e complessità computazionale. Esempi numerici.
Interpolazione polinomiale nella base di Bernstein.
Numero di condizione assoluto per l'interpolazione polinomiale.
- Me.19/10/16, ore 16:30-18:30: Aula Tonelli
Teorema sull'Errore di interpolazione polinomiale. Esempio.
Sulla convergenza dell'interpolante all'aumentare del numero dei punti; esempio test di Runge;
distribuzione di Chebyshev, teorema di convergenza.
Funzione polinomiale a tratti: motivazioni, differenze con il modello polinomiale, regolarita' e flessibilita';
polinomi a tratti di interpolazione. Applicazioni.
- Ve.21/10/16, ore 13:30-16:30: Aula E1
Attivita' di Laboratorio.
Ancora su Esercitazione 2; ripreso esercizio A su gradual underflow, e svolti insieme esercizi B, C e D.
MatLab/Octave III (vedi lucidi 'III parte' in Documenti); Esercitazione 3 (vedi file pdf e archivio tgz in Download Materiale Lab).
Grafici in MATLAB.
- Lu.24/10/16, ore 13:00-15:00: Aula Tonelli
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;
- Me.26/10/16, ore 16:30-18:30: Aula Tonelli
Grado di precisione di una formula di quadratura.
Errore di integrazione per n dispari ed n pari.
Formule di quadratura composte; formule composte dei trapezi e di Simpson;
errore per le formule composte. Esempi numerici su formule composte.
- Ve.28/10/16, ore 13:30-16:30: Aula E1
Attivita' di Laboratorio.
Ancora su Esercitazione 3 ed in particolare su valutazione polinomi (svolti insieme gli esercizi C e D);
Esercitazione 4: recupero esercitazioni precedenti (vedi file pdf).
- Lu.31/10/16, ore 13:00-15:00: Aula Tonelli
Estrapolazione di Richardson; metodi adattivi di integrazione basati su stima dell'errore.
Cenno all'errore inerente relativo al problema di integrare una funzione.
Equazioni non lineari
Metodo di bisezione: ipotesi di applicazione, iterazioni del metodo e
test di arresto; metodo della falsa posizione.
- Me.2/11/16, ore 16:30-18:30: Aula Tonelli
Ancora su metodo della falsa posizione: iterazioni del metodo e test di arresto.
Metodo di Newton: ipotesi di applicazione, derivazione del metodo, iterazioni del metodo.
Interpretazione geometrica del metodo di Newton. Teorema di convergenza per metodi di iterazione
funzionale e interpretazione geometrica. Teorema di convergenza del metodo di Newton.
Test di arresto.
- Ve.4/11/16, ore 13:30-16:30: Aula E1
Attivita' di Laboratorio.
Esercitazione 5: Interpolazione polinomiale (vedi file pdf e archivio tgz in Download Materiale Lab).
Svolti esercizi A, B e C.
- Lu.7/11/16, ore 13:00-15:00: Aula Tonelli
Esempi: radice quadrata di un numero e inverso di un numero.
Definizione di ordine di convergenza, risultati su ordine di convergenza per x_k+1=g(x_k).
Ordine di convergenza del metodo di Newton, per radici semplici; esempi.
Metodo delle secanti, teorema di convergenza, Ordine di convergenza.
- Me.9/11/16, ore 16:30-18:30: Aula Tonelli
Ancora su Equazioni Non Lineari: Errore Inerente.
Algebra Lineare Numerica
Soluzione di sistemi lineari quadrati: motivazioni;
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.
- Ve.11/11/16, ore 13:30-16:30: Aula E1
Attivita' di Laboratorio.
Esercitazione 6: Integrazione Numerica (vedi file pdf e archivio tgz in Download Materiale Lab).
Svolti esercizi A, B e C.
- Lu.14/11/16, ore 13:00-15:00: Aula Tonelli
Complessita' computazionale della fattorizzazione LU.
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).
Esempio numerico sulla fattorizzazione con scambio delle righe.
- Me.16/11/16, ore 16:30-18:30: Aula Tonelli
Ancora su fattorizzazione LU con scambio delle righe.
Stabilita` numerica della fattorizzazione LU; fattorizzazione LU
con scambio delle righe e perno massimo. Esempi numerici.
- Ve.18/11/16, ore 13:30-16:30: Aula E1
Attivita' di Laboratorio.
Esercitazione 7: Equazioni non lineari (vedi file pdf e archivio tgz in Download Materiale Lab).
Svolti esercizi A, B e C; l'esercizio D e' stato lasciato da fare a casa.
- Lu.21/11/16, ore 13:00-15:00: Aula Tonelli
Richiami su norme vettoriali e norme matriciali; condizionamento del problema Ax=b.
Indice di condizionamento di una matrice.
- Me.23/11/16, ore 16:30-18:30: Aula Tonelli
Esempio numerico di fattorizzazione LU con scambio delle righe e perno massimo.
Soluzione di un sistema lineare mediante fattorizzazione QR. Matrici elementari di Householder. Metodo di Householder. Complessita` computazionale. Stabilita`.
- Ve.25/11/16, ore 13:30-16:30: Aula E1
Attivita' di Laboratorio.
Esercitazione 8: Algebra Lineare Numerica (vedi file pdf e archivio tgz in Download Materiale Lab).
Svolti esercizi A, B, D e C.
- Lu.28/11/16, ore 13:00-15:00: Aula Tonelli
Metodi iterativi per la soluzione di sistemi lineari: motivazioni.
Richiami su autovalori e autovettori e convergenza di una successione di vettori.
Decomposizione della matrice, riscrittura del sistema e idea del metodo iterativo.
Teorema di convergenza; condizioni sufficienti per la convergenza. Test di arresto.
- Me.30/11/16, ore 16:30-18:30: Aula Tonelli
Sulla complessita' computazionale, stabilita' e velocita' di convergenza.
Metodi di Jacobi e Gauss-Seidel: formule matriciali e per componenti.
Condizioni sufficienti di convergenza. Esempi numerici.
- Ve.2/12/16, ore 13:30-16:30: Aula E1
Ripresi gli argomenti del corso in preparazione all'esame.
- Ve.16/12/16, ore 13:30-16:30: Aula E1
Simulazione della prova d'esame per chi ha seguito il corso.
Fine delle Lezioni.
Documenti
Download Materiale Lab
Sitografia
Modalita' d'Esame
Torna alla
home page di Giulio Casciola