Metodi Numerici per il Calcolo (C.d.S. Informatica per il Management (L)) A.A.2017/18
(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 mercoledi' 27 settembre 2017 con il seguente orario:
Mercoledi' ore 16:00-19:00 Aula Tonelli (Dip. Mat.)
Giovedi' ore 14:00-16:00 Aula Tonelli (Dip. Mat.)
Venerdi' ore 13:30-17:30 Aula Ercolani 2
Lezioni e Argomenti trattati
- Me.27/09/17, ore 16:00-18:00: Aula Tonelli
Slide: Introduzione e informazioni sul corso.
(file .pdf)
Numeri Finiti
Richiami sui numeri reali, rappresentazione in base, forma scientifica o normalizzata.
- Gi.28/09/17, ore 14:00-16:00: Aula Tonelli
Insieme F dei numeri finiti: base, mantissa, range degli esponenti. Esempio su F(2,3,-1,2).
esercizio 1:
Dato l'insieme F(10,3,-4,5), determinare i suoi elementi.
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.29/09/17, ore 13:30-16:30: Aula Ercolani 2
Svolto l'esercizio1 in aula.
Cenni su ANSI/IEEE Std.754-1985: Basic-Single e Basic-Double,
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);
esercizio 2:
Ripetere l'esercizio di conversione, memorizzazione e riconversione per +13.9 in F(2,4,-7,8).
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.
Calcolo dell'errore relativo e confronto con u negli esempi visti all'inizio della lezione.
Corollario sulla rappresentazione di fl(a). Precisione e cifre significative.
L'unita' di arrotondamento in Basic-Single e Basic-Double.
Caratterizzazione dell'unita' di arrotondamento.
Esercitati su conversione e rappresentazione in memoria.
- Gi.5/10/17, ore 14:00-16:00: Aula Tonelli
Visto l'esercizio2 in aula. Ancora sul'unita' di arrotondamento;
Aritmetica floating point e precisione di calcolo.
Esempio su proprieta' associativa dell'addizione in aritmetica finita.
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.
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.
- Ve.6/10/17, ore 13:30-16:30: Aula E2
Esempio numerico di cancellazione.
Condizionamento di un problema e stabilita' di un algoritmo:
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 negli esempi di moltiplicazione e addizione di due reali.
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; numero di condizione; esempio con sqrt(1-x).
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) con x_1 e x_2 reali positivi.
- Me.11/10/17, ore 16:00-18:00: Aula Tonelli
Ancora su Esempio: sqrt(x_1+x_2) - sqrt(x_1) con x_1 + x_2 e x_1 reali positivi
Esempio: radici di un'eq. di secondo grado.
Funzioni Polinomiali e Interpolazione
Richiami sui polinomi. Valutazione numerica di un polinomio:
metodo dalla definizione, metodo di Horner, metodo di Ruffini.
- Gi.12/10/17, ore 14:00-16:00: Aula Tonelli
Ripreso il metodo di Ruffini, complessità computazionale. Valutazione numerica della derivata di un polinomio.
Esempio numerico di valutazione e derivata. Cenno alla stabilita' dell'algoritmo di Ruffini/Horner.
esercizio 4:
Per un polinomio lineare (e poi quadratico) fare l'analisi in avanti per determinare E_ALG dell'algoritmo di valutazione
di Ruffini-Horner.
E_IN per il problema della 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;
generalizzazione di E_IN per la valutazione di un polinomio di grado n. Scomposizione in E_IN1 e E_IN2.
Base dei polinomi di Bernstein su un intervallo.
- Ve.13/10/17, ore 13:30-16:30: Aula E2
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).
- Me.18/10/17, ore 16:00-18:00: Aula Tonelli
Ripreso E_IN per valutazione polinomiale e polinomi base di Bernstein;
Proprieta' dei polinomi base di Bernstein.
Esempio numerico nella base di Bernstein con riduzione di E_IN1.
Polinomi e invarianza per traslazione e scala (cambio di variabile).
Cambio di variabile per polinomi nella base di Bernstein. Ripreso esempio numerico con riduzione di E_IN2.
Formula ricorrente per polinomi base di Bernstein; algoritmo di valutazione (Alg.1)
- Gi.19/10/17, ore 14:00-16:00: Aula Tonelli
Algoritmo di valutazione di de Casteljau (Alg.2). Suddivisione. Formula ricorrente per la derivata.
Derivata di un polinomio nella base di Bernstein; valutazione della derivata.
Cenno ad applicazioni dei polinomi nella base di Bernstein (curve di Bezier).
- Ve.20/10/17, ore 13:30-16:30: Aula E2
Attivita' di Laboratorio.
Linguaggio Matlab (vedi Slide su 'Matlab/Octave IIparte' in Documenti);
Esercitazione 2 (vedi file pdf e archivio tgz in Download Materiale Lab).
- Me.25/10/17, ore 16:00-18:00: Aula Tonelli
Richiami ed esempio su polinomio di Taylor (Interpolazione alla Hermite).
Problema di interpolazione polinomiale di dati e funzioni (Interpolazione alla Lagrange).
Esistenza e unicita' del polinomio interpolante: sistema lineare e matrice di Vandermonde.
Esempi numerici.
- Gi.26/10/17, ore 14:00-16:00: Aula Tonelli
Interpolazione nella Forma di Newton: base con centri. Soluzione di sistema lineare
triangolare inferiore. Esempio numerico. Newton e interpolazione di punti aggiuntivi.
Valutazione polinomi nella base di Newton.
Interpolazione nella Forma di Lagrange: funzioni elementari di Lagrange.
Prima e seconda forma di Lagrange e complessità computazionale.
esercizio 5:
Determinare e rappresentare graficamente i polinomi elementari di Lagrange di grado 2
a partire dai punti [0,1,2].
- Ve.27/10/17, ore 13:30-16:30: Aula E2
Attivita' di Laboratorio.
Esercitazione 3 (vedi file pdf e archivio tgz in Download Materiale Lab).
- Gi.2/11/17, ore 14:00-16:00: Aula Tonelli
Visto l'esercizio 4 assegnato. Interpolazione nella forma di Bernstein in [a,b] e in [0,1].
Numero di condizione assoluto per l'interpolazione polinomiale.
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.
- Ve.3/11/17, ore 13:30-16:30: Aula E2
Attivita' di Laboratorio.
Esercitazione 4 (vedi file pdf e archivio tgz in Download Materiale Lab).
- Me.8/11/17, ore 16:00-18:00: Aula Tonelli
Funzione polinomiale a tratti: motivazioni, differenze con il modello polinomiale, regolarita' e flessibilita';
polinomi a tratti di interpolazione C^1 cubici. Risultato di convergenza.
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).
- Gi.9/11/17, ore 14:00-16:00: Aula Tonelli
Esempio numerico. Grado di precisione di una formula di quadratura.
Errore di integrazione per trapezi e Simpson;
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.
esercizio 4:
Si determini il passo da utilizzare nella formula dei trapezi composta affinche' l'integrale fra
0 ed 1 di 1/(1+x) sia approssimato alla tolleranza 0.5x10^-3.
- Ve.10/11/17, ore 13:30-16:30: Aula E2
Attivita' di Laboratorio.
Esercitazione 5 (vedi file pdf e archivio tgz in Download Materiale Lab).
- Me.15/11/17, ore 16:00-18:00: Aula Tonelli
Svolto esercizio assegnato su formula trapezi composto; stesso esercizio con simpson composto.
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, iterazione del metodo e test di arresto.
- Gi.9/11/17, ore 14:00-16:00: Aula Tonelli
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.
Esempi: radice quadrata di un numero e inverso di un numero.
- Ve.17/11/17, ore 13:30-16:30: Aula E2
Attivita' di Laboratorio.
Esercitazione 6: Integrazione Numerica (vedi file pdf e archivio tgz in Download Materiale Lab).
- Me.22/11/17, ore 16:00-18:00: Aula Tonelli
Metodo di Newton: test di arresto. Condizionamento del problema f(x)=0.
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.
- Gi.23/11/17, ore 14:00-16:00: Aula Tonelli
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.
Complessita' computazionale della fattorizzazione LU.
Esempio di fattorizzazione e di soluzione di un sistema lineare.
Applicazione della fattorizzazione per il calcolo dell'inversa di una matrice.
- Ve.24/11/17, ore 13:30-16:30: Aula E2
Attivita' di Laboratorio.
Esercitazione 7: Equazioni non lineari (vedi file pdf e archivio tgz in Download Materiale Lab).
- Me.29/11/17, ore 16:00-18:00: Aula Tonelli
Applicazione della fattorizzazione per il calcolo del
determinante di una matrice.
Fattorizzazione LU con scambio delle righe (o pivoting parziale).
Esempio numerico sulla fattorizzazione con scambio delle righe.
Stabilita` numerica della fattorizzazione LU; fattorizzazione LU
con scambio delle righe e perno massimo. Esempio numerico.
- Gi.30/11/17, ore 14:00-16:00: Aula Tonelli
Un altro esempio numerico. Esempio numerico in aritmetica floating point.
Richiami su norme vettoriali e norme matriciali; condizionamento del problema Ax=b.
- Ve.1/12/17, ore 13:30-16:30: Aula E2
Indice di condizionamento di una matrice.
Soluzione di un sistema lineare mediante fattorizzazione QR. Matrici elementari di Householder. Metodo di Householder.
- Me.6/12/17, ore 14:00-18:30: Aula Tonelli
Attivita' di Laboratorio.
Esercitazione 8: Algebra Lineare Numerica (vedi file pdf e archivio tgz in Download Materiale Lab).
- Gi.7/12/17, ore 14:00-16:00: Aula Tonelli
Esempio numerico di fattorizzazione QR.
Complessita` computazionale e Stabilita` per soluzione di Ax=b con fatt. QR.
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.13/12/17, ore 14:00-18:00: Aula Tonelli
Metodi iterativi: Condizioni sufficienti di convergenza.
Sulla complessita' computazionale, stabilita' e velocita' di convergenza.
Metodi di Jacobi e Gauss-Seidel: formule matriciali e per componenti. Esempi numerici.
- Gi.14/12/17, ore 14:00-16:00: Aula Tonelli
Ripresi gli argomenti del corso in preparazione all'esame.
Fine delle Lezioni.
- Ve.22/12/13, ore 13:30-16:30: Aule E1 ed E2
Simulazione della prova d'esame per chi ha seguito il corso.
Documenti
Download Materiale Lab
Sitografia
Modalita' d'Esame
Torna alla
home page di Giulio Casciola