Metodi Numerici per il Calcolo (C.d.S. Informatica per il Management (L)) A.A.2018/19
(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' 26 settembre 2018 con il seguente orario:
Mercoledi' ore 15:30-18:30 Aula Ercolani 2
Giovedi' ore 13:00-15:00 Aula Tonelli (Dip. Mat.)
Venerdi' ore 14:00-17:00 Aula Tonelli (Dip. Mat.)
Lezioni e Argomenti trattati
- Me.26/09/18, ore 15:30-18:30: Aula E2
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.
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.
- Gi.27/09/18, ore 13:00-15:00: Aula Tonelli
Svolto l'Esercizio 1 in aula.
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 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) sia per arrotondamento che troncamento.
Definizioni di Errore Assoluto e Relativo, esempi numerici.
- Ve.28/09/18, ore 14:00-17:00: Aula Tonelli
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).
Unita' di arrotondamento in Basic-Single e Basic-Double.
Aritmetica floating point e precisione di calcolo.
Esercizio 5:
Verificare che in aritmetica finita non vale la proprieta' associativa dell'addizione nel seguente caso:
F(10,2,lambda,omega), a=0.11x10^0, b=0.13x10^-1, c=0.14x10^-1.
Caratterizzazione dell'unita' di arrotondamento.
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.
Esercitati su conversione e rappresentazione in memoria.
- Me.3/10/18, ore 15:30-18:30: Aula E2
Ripreso l'esempio sulla cancellazione numerica.
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'.
Stima di E_IN nel caso di un problema modellizzato come f:R->R differenziabile; 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.
Esempio sull'operazione aritmetica di moltiplicazione.
- Ve.5/10/18, ore 14:00-17:00: Aula Tonelli
Ripresa stima di E_IN ed esempi. Esempio sull'operazione aritmetica di
addizione fra numeri reali. Esempio: sqrt(x_1+x_2) - sqrt(x_1) con x_1 e x_2 reali positivi.
Esempio: radici di un'equazione di secondo grado.
Funzioni Polinomiali
Richiami sulle funzioni polinomiali. Valutazione numerica di una funzione polinomiale:
metodo dalla definizione in base canonica, metodo di Horner.
- Me.10/10/18, ore 15:30-18:30: Aula E2
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 6:
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;
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.
- Gi.11/10/18, ore 13:00-15:00: Aula Tonelli
Ripreso discorso di riduzione di E_IN utilizzando base di Bernstein e cambio di variabile.
Esempio numerico nella base di Bernstein con riduzione sia di E_IN1 che E_in2.
Proprieta' dei polinomi base di Bernstein.
Formula ricorrente per polinomi base di Bernstein; algoritmo di valutazione (Alg.1), complessita'
computazionale.
- Ve.12/10/18, 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 tgz in Download Materiale Lab).
Info su consegna esercizi (vedi slide su 'mnc1819_info_lab' in Documenti);
- Me.17/10/18, ore 15:30-17:30: Aula E2
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.
- Gi.18/10/18, ore 13:00-15:00: Aula Tonelli
Esempio numerico di valutazione con de Casteljau.
Primitiva di una funzione polinomiale nella base di Bernstein; indegrale definito.
Cenno ad applicazioni dei polinomi nella base di Bernstein (vedi slide 'Curve di Bézier e Grafica Vettoriale' in Documenti).
- Ve.19/10/18, 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 tgz in Download Materiale Lab).
- Me.24/10/18, ore 15:30-17:30: Aula E2
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.
Ripresi ed analizzati gli esercizi di Laboratorio rimasti dell'Esercitazione 2.
- Gi.25/10/18, ore 13:00-15:00: Aula Tonelli
Interpolazione nella Forma di Newton: base con centri. Soluzione di sistema lineare
triangolare inferiore. Esempi numerici. Valutazione polinomiale nella base di Newton.
Newton e interpolazione di punti aggiuntivi.
Interpolazione nella Forma di Lagrange: funzioni elementari di Lagrange.
- Ve.26/10/18, ore 14:00-17:00: Aula Tonelli
Attivita' di Laboratorio .
Script, Function, Numeri Finiti (vedi Slide numerifiniti_1819.pdf in Documenti);
Esercitazione 3 (vedi file pdf e archivio tgz in Download Materiale Lab).
- Me.31/10/18, ore 15:30-17:30: Aula E2
Prima e seconda forma di Lagrange e complessità computazionale.
Esercizio 7:
Determinare e rappresentare graficamente i polinomi elementari di Lagrange di grado 2
a partire dai punti [0,1,2].
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. Esempioi su e^x.
Sulla convergenza dell'interpolante all'aumentare del numero dei punti; esempio test di Runge;
distribuzione di Chebyshev, teorema di convergenza.
- Me.7/11/18, ore 15:30-17:30: Aula E2
Osservazioni su interpolazione polinomiale di funzioni polinomiali.
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,k=0) e convergenza.
Interpolazione alla Hermite; esercizio di interpolazione polinomiale alla Hermite di due punti (valori e derivate)
con cubica nella base di Bernstein; interpolazione cubica di Hermite C^1 (n=3, k=1). Caso spline cubica C^2 (n=3, k=2).
- Gi.8/11/18, 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).
Grado di precisione di una formula di quadratura.
Errore di integrazione per trapezi e Simpson;
Errore di integrazione per n dispari ed n pari.
- Ve.9/11/18, 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 tgz in Download Materiale Lab).
- Me.14/11/18, ore 15:30-17:30: Aula E2
Esempi su formule dei trapezi e di Simpson.
Formule di quadratura composte; formule composte dei trapezi e di Simpson;
errore per le formule composte.
Esercizio 8:
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; metodi adattivi di integrazione basati su stima dell'errore.
- Gi.15/11/18, ore 13:00-15:00: Aula Tonelli
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.
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.
- Ve.16/11/18, ore 14:00-17:00: Aula Tonelli
Attivita' di Laboratorio .
Interpolazione polinomiale;
Esercitazione 5 (vedi file pdf e archivio tgz in Download Materiale Lab).
- Me.21/11/18, ore 15:30-17:30: Aula E2
Ancora su interpretazione geometrica della convergenza dei metodi di iterazione funzionale.
Dimostrazione del teorema di convergenza. Teorema di convergenza del metodo di Newton.
Definizione di ordine di convergenza; ordine di convergenza del metodo di Newton, per radici semplici e non.
Test di arresto. Condizionamento del problema f(x)=0.
Metodo delle secanti, teorema di convergenza, Ordine di convergenza.
Esempi: radice quadrata di un numero e inverso di un numero.
- Gi.22/11/18, ore 13:00-15:00: Aula Vitali
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 di una matrice.
Applicazione della fattorizzazione per il calcolo dell'inversa e del determinante di una matrice.
- Ve.23/11/18, ore 14:00-17:00: Aula Tonelli
Attivita' di Laboratorio .
Integrazione numerica;
Esercitazione 6 (vedi file pdf e archivio tgz in Download Materiale Lab).
- Me.28/11/18, ore 15:30-18:30: Aula E2
Esempio di fattorizzazione di una matrice.
Fattorizzazione LU con scambio delle righe (o pivoting parziale).
Esempio numerico sulla fattorizzazione con scambio delle righe.
Analisi all'indietro di 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.
- Gi.29/11/18, 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.
- Ve.30/11/18, ore 14:00-17:00: Aula Tonelli
Attivita' di Laboratorio .
Equazioni non lineari;
Esercitazione 7 (vedi file pdf e archivio tgz in Download Materiale Lab).
- Me.5/12/18, ore 15:30-18:30: Aula E2
Soluzione di un sistema lineare mediante fattorizzazione QR. Matrici elementari di Householder.
Esempio. Fattorizzazione QR. Esempio numerico di fattorizzazione QR.
Complessita` computazionale e Stabilita` per soluzione di Ax=b con fatt. QR.
Introduzione alla soluzione di sistemi lineari mediante metodi iterativi: motivazioni.
Richiami su convergenza di una successione di vettori.
- Gi.6/12/18, ore 13:00-15:00: Aula Tonelli
Decomposizione della matrice, riscrittura del sistema e idea del metodo iterativo.
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.7/12/18, ore 14:00-17:00: Aula Tonelli
Attivita' di Laboratorio .
Algebra lineare;
Esercitazione 8: Algebra Lineare Numerica (vedi file pdf e archivio tgz in Download Materiale Lab).
- Ve.14/12/18, ore 14:00-17:00: Aula VII piano
Ripassiamo insieme?
Fine delle Lezioni.
- Ve.21/12/18, ore 14:00-17:00: Aula Tonelli
Prova scritta d'esame
Documenti
Download Materiale Lab
Sitografia
Modalita' d'Esame
Torna alla
home page di Giulio Casciola