Metodi Numerici per il Calcolo (C.d.S. Informatica per il Management (L)) A.A.2019/20
(1^ semestre, 2^ anno)
Esame: prova orale
Crediti: 8
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
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' 25 settembre 2019 con il seguente orario:
Mercoledi' ore 13:00-15:00 Aula Ercolani 1
Giovedi' ore 13:00-16:00 Aula Tonelli (Dip. Mat.)
Venerdi' ore 14:00-17:00 Aula Tonelli (Dip. Mat.)
Lezioni e Argomenti trattati
- Me.25/09/19, ore 13:00-15:00: Aula E1
Slide: Introduzione e informazioni sul corso.
(file .pdf)
Numeri Finiti
Richiami sui numeri reali, rappresentazione in base, forma scientifica o normalizzata.
Insieme F dei numeri finiti: base, mantissa, range degli esponenti. Esempio su F(2,3,-1,2).
Esercizio 1:
Dato l'insieme F(2,3,-1,2), determinare i suoi elementi e posizionarli sull'asse reale.
- Gi.26/09/19, ore 13:00-16:00: Aula Tonelli
Soluzione dell'Esercizio 1.
Rappresentazione di un numero reale nell'insieme dei numeri finiti:
approssimazione della mantissa per troncamento e arrotondamento, rappresentazione dell'esponente
(casi di underflow e overflow). Rappresentazione in memoria dei numeri Finiti (segno, esponente e mantissa).
Esempi in base 10.
Esercizio 2:
Dato l'insieme F(10,2,-4,5), determinare il numero dei suoi elementi.
Standard ANSI/IEEE 754 (1985): Basic-Single e Basic-Double; cenno ad arrotondamento ai pari, a Nan, Infinity e Gradual underflow.
Esempio di conversione, memorizzazione e riconversione nel caso di arrotondamento del numero -13.9 in base 10 in F(2,5,-3,4).
Richiamata conversione da base 10 a base 2 di un numero reale (parte intera e frazionaria);
Esercizio 3:
Ripetere l'esempio di conversione, memorizzazione e riconversione, ma per troncamento.
Esercizio 4:
Conversione, memorizzazione e riconversione per +13.9 in F(2,4,-7,8) per arrotondamento.
Definizioni di Errore Assoluto e Relativo.
Teorema di maggiorazione dell'errore assoluto di rappresentazione.
- Ve.27/9/19, ore 14:00-17:00: Aula Tonelli
Definizione di unita' di arrotondamento.
Teorema di maggiorazione dell'errore relativo di rappresentazione.
Corollario sulla rappresentazione di fl(a).
Unita' di arrotondamento in Basic-Single e Basic-Double.
Aritmetica floating point e precisione di calcolo.
Esempio per verificare che in aritmetica finita non vale la proprieta' associativa dell'addizione.
Caratterizzazione dell'unita' di arrotondamento, anche in ANSI/IEEE.
Analisi degli errori: in avanti e all'indietro. Esempio di analisi in avanti sulla moltiplicazione
e sull'addizione di due numeri reali; errore di cancellazione numerica. Esempio numerico di cancellazione.
- Me.2/10/19, ore 13:00-15:00: Aula E1
Soluzioni degli Esercizi 2, 3 e 4 assegnati.
Problema ben posto. Modellizzazione di un problema come f:R->R e piu' in generale come f:R^n->R.
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' e condizionamento.
Stima di E_IN nel caso di un problema modellizzato come f:R->R differenziabile; numero di condizione.
- Gi.3/10/19, ore 13:00-16:00: Aula Tonelli
Ripresa stima di E_IN; esempio su 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).
Esempio: radici di un'equazione di secondo grado.
Funzioni Polinomiali
Richiami sulle funzioni polinomiali. Valutazione numerica di una funzione polinomiale.
- Me.9/10/19, ore 13:00-15:00: Aula E1
Metodo dalla definizione in base canonica, metodo di Horner,
metodo di Ruffini e complessità computazionale. Valutazione numerica della derivata di un polinomio.
Esempio numerico di valutazione e derivata. Cenno alla stabilita' dell'algoritmo di Ruffini/Horner.
Esercizio 5:
Per un polinomio lineare (e poi quadratico) fare l'analisi in avanti degli errori per determinare E_ALG nel caso di valutazione
polinomiale con il metodo di Ruffini-Horner.
E_IN per il problema della valutazione di un polinomio lineare; esempio numerico ed errore inerente;
stima di E_IN nell'esempio visto. Stima di E_IN per valutazione di polinomi espressi in una generica base.
Scomposizione in E_IN1 e E_IN2. Polinomi nella base con centro; stima di E_IN in questa base;
- Gi.10/10/19, ore 13:00-16:00: Aula Tonelli
Base dei polinomi di Bernstein su un intervallo.
Esempio numerico nella base di Bernstein con riduzione di E_IN1.
Polinomi e cambio di variabile.
Cambio di variabile per polinomi nella base di Bernstein.
Esempio numerico nella base di Bernstein con riduzione di E_in2.
Proprieta' dei polinomi base di Bernstein.
Formula ricorrente per polinomi base di Bernstein; algoritmo di valutazione (Alg.1), complessita'
computazionale. Algoritmo di valutazione di de Casteljau (Alg.2).
- Ve.11/10/19, ore 14:00-17:00: Aula Tonelli
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 zip in Download Materiale Lab).
- Gi.17/10/19, ore 13:00-16:00: Aula Tonelli
Ripresi gli Alg. 1 e 2 di valutazione. Alg. di de Casteljau e Suddivisione.
Esempio numerico di valutazione con de Casteljau.
Esercizio 6:
Valutare il polinomio nella base di Bernstein di coefficienti [2,-2,2] nei punti [0,1/4,1/2,3/4,1].
Formula ricorrente per la derivata.
Valutazione della derivata di un polinomio nella base di Bernstein (alg.1);
primitiva di una funzione polinomiale nella base di Bernstein; valutazione della derivata (alg.2).
Primitiva e indegrale definito di una funzione polinomiale.
Esercizio 7:
Determinare l'integrale in [0,1] dei polinomi base di Bernstein di grado n.
Applicazione dei polinomi nella base di Bernstein (presentate slide 'Curve di Bézier e Grafica Vettoriale').
- Ve.18/10/19, ore 14:00-17:00: Aula Tonelli
Attivita' di Laboratorio
Linguaggio Matlab (vedi Slide su 'Matlab/Octave IIparte' in Documenti);
Esercitazione 2 (vedi file pdf e archivio zip in Download Materiale Lab).
- Me.23/10/19, ore 13:00-15:00: Aula E1
Interpolazione Polinomiale
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.
Interpolazione nella Forma di Newton: base con centri. Soluzione di sistema lineare
triangolare inferiore.
Esercizio 8:
Riprendere gli Esempi fatti e ripeterli per trovare il pol. interpolante nella forma di Newton.
- Gi.24/10/19, ore 13:00-15:00: Aula Tonelli
Soluzione dell'Esercizio 8; stesso esempio dell'esercizio, ma con i punti ordinati in modo differente.
Pseudocodice per risolvere un sistema lineare triangolare inferiore per sostituzioni in avanti.
Valutazione polinomiale nella base di Newton. Metodo incrementale per det. l' interpolazione nella Forma di Newton (punto aggiuntivo).
Interpolazione nella forma di Bernstein, via sistema lineare con matrice totalmente positiva; metodo iterativo (PIA).
Interpolazione nella Forma di Lagrange: funzioni elementari di Lagrange.
- Ve.25/10/19, ore 14:00-17:00: Aula Tonelli
Attivita' di Laboratorio
Ancora sul Linguaggio Matlab e i Numeri Finiti (vedi Slide 'Numeri Finiti' in Documenti);
Esercitazione 3 (vedi file pdf e archivio zip in Download Materiale Lab).
- Me.30/10/19, ore 13:00-15:00: Aula E1
Prima e seconda forma di Lagrange e complessità computazionale. Esempio numerico.
Numero di condizione assoluto per l'interpolazione polinomiale.
Interpolazione di funzioni; teorema sull'Errore di interpolazione polinomiale di funzioni. Esempioi su e^x
e convergenza dell'interpolante all'aumentare del numero dei punti; funzione test di Runge su punti equispaziati
e non convergenza.
- Gi.31/10/19, ore 13:00-15:00: Aula Tonelli
Distribuzione di Chebyshev e teorema di convergenza polinomiale.
Funzione polinomiale a tratti: motivazioni, differenze con il modello polinomiale, regolarita' e flessibilita'.
Interpolazione con funzioni polinomiali a tratti; esempio: interpolazione lineare a tratti C^0 (n=1) e convergenza;
esempio: interpolazione lineare a tratti C^0 (n=2). Interpolazione cubica di Hermite C^1 (n=3) e convergenza.
- Me.6/11/19, ore 13:00-15:00: Aula E1
Integrazione Numerica
Integrazione di funzioni polinomiali espresse in differenti basi (canonica, Bernstein, Lagrange);
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). Errore di integrazione per trapezi e Simpson; Errore di integrazione per n dispari ed n pari. Grado di precisione di una formula di quadratura.
Esercizio 9:
Determinare l'integrale fra 0 ed 1 del seguente polinomio, sia in forma standard che applicando la formula di Simpson:
p(x)=8x^3-12x^2+3x+1
- Gi.7/11/19, ore 13:00-15:00: Aula Tonelli
Formule di quadratura composte; formule composte dei trapezi e di Simpson;
errore per le formule composte. Esercizio su formula dei trapezi composta.
Esercizio 10:
Si determini il passo da utilizzare nella formula di Simpson composta affinche' l'integrale fra
0 ed 1 di 1/(1+x) sia approssimato alla tolleranza 0.5x10^-3.
Estrapolazione di Richardson e risultati; metodi adattivi di integrazione basati su stima dell'errore.
- Ve.8/11/19, ore 14:00-17:00: Aula Tonelli
Attivita' di Laboratorio
Grafici e funzioni polinomiali in Matlab (vedi slide su 'MATLAB/Octave III parte' in Documenti);
Esercitazione 4 (vedi file pdf e archivio zip in Download Materiale Lab).
- Me.13/11/19, ore 13:00-15:00: Aula E1
Equazioni non lineari
Metodo di bisezione: ipotesi di applicazione, iterazioni del metodo e
test di arresto; codice sbisez.m; metodo della falsa posizione, iterazione del metodo e test di arresto.
Metodo di Newton: ipotesi di applicazione, derivazione del metodo, iterazioni del metodo.
Interpretazione geometrica del metodo di Newton.
- Gi.14/11/19, ore 13:00-15:00: Aula Tonelli
Metodi di iterazione funzionale per punto fisso di una funzione.
Teorema di convergenza per metodi di iterazione funzionale con dim.;
interpretazione geometrica. Teorema di convergenza del metodo di Newton con dim.
Test di arresto e codice stangmet.m.
Definizione di ordine di convergenza; ordine di convergenza del metodo di Newton, per radici semplici e non.
- Ve.15/11/19, ore 14:00-17:00: Aula Tonelli
Attivita' di Laboratorio
Interpolazione polinomiale;
Esercitazione 5 (vedi file pdf e archivio zip in Download Materiale Lab).
- Me.20/11/19, ore 13:00-15:00: Aula E1
Esempio numerico. Esempi: radice quadrata di un numero e inverso di un numero.
Metodo delle secanti, teorema di convergenza, Ordine di convergenza.
Condizionamento del problema f(x)=0.
Algebra Lineare Numerica
Soluzione di sistemi lineari quadrati. Introduzione ai metodi diretti.
- Gi.21/11/19, ore 13:00-15:00: Aula Tonelli
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 di una matrice. Esempio di soluzione di un sistema lineare.
- Ve.22/11/19, ore 14:00-17:00: Aula Tonelli
Attivita' di Laboratorio
Integrazione numerica;
Esercitazione 6 (vedi file pdf e archivio zip in Download Materiale Lab).
- Me.27/11/19, ore 13:00-15:00: Aula E1
Applicazione della fattorizzazione per il calcolo dell'inversa e del determinante di una matrice.
Esempi su inversa e determinante. Esempio di fattorizzazione di una matrice.
Risultato su fattorizzazione LU di una matrice PA (con righe scambiate).
Fattorizzazione LU con scambio delle righe (o pivoting parziale).
Esempio numerico sulla fattorizzazione con scambio delle righe.
- Gi.28/11/19, ore 13:00-15:00: Aula Tonelli
Analisi all'indietro per la stabilita' della fattorizzazione LU.
Definizioni di stabilita` numerica della fattorizzazione LU; fattorizzazione LU
con scambio delle righe e perno massimo. Esempi numerici.
Esempio numerico in aritmetica floating point.
Condizionamento del problema Ax=b. Richiami su norme vettoriali.
- Ve.29/11/19, ore 14:00-17:00: Aula Tonelli
Attivita' di Laboratorio
Equazioni non lineari;
Esercitazione 7 (vedi file pdf e archivio zip in Download Materiale Lab).
- Me.4/12/19, ore 13:00-15:00: Aula E1
Ancora su norme vettoriali e norme matriciali; condizionamento del problema Ax=b.
Indice di condizionamento di una matrice.
Soluzione di un sistema lineare mediante fattorizzazione QR. Matrici elementari di Householder.
Algoritmo di fattorizzazione QR. Esempio numerico di fattorizzazione QR.
- Gi.5/12/19, ore 13:00-15:00: Aula Tonelli
Complessita` computazionale e Stabilita` per soluzione di Ax=b con fatt. QR.
Soluzione di sistemi lineari mediante metodi iterativi: motivazioni.
Decomposizione della matrice, riscrittura del sistema e idea del metodo iterativo.
Richiami su convergenza di una successione di vettori.
Teorema di convergenza; condizioni sufficienti per la convergenza. Test di arresto.
Complessita' computazionale e velocita' di convergenza.
Metodi di Jacobi e Gauss-Seidel: formule matriciali e per componenti. Esempi numerici.
- Ve.6/12/19, ore 14:00-17:00: Aula Tonelli
Attivita' di Laboratorio
Algebra lineare;
Esercitazione 8: Algebra Lineare Numerica (vedi file pdf e archivio zip in Download Materiale Lab).
- Me.11/12/19, ore 13:00-15:00: Aula E1
Ripassiamo insieme?
- Ve.20/12/19, ore 14:00-17:00: Aula Tonelli
Simulazione prova d'esame
Fine delle Lezioni.
Documenti
Download Materiale Lab
Sitografia
Modalita' d'Esame
Torna alla
home page di Giulio Casciola