Metodi Numerici per il Calcolo (C.d.S. Informatica per il Management (L)) A.A.2020/21
(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 lunedì 21 settembre 2020 con il seguente orario:
lunedì ore 11:00-13:00 Aula M1 (Dip. Mineralogia) e on-line (Aula Virtuale)
martedì ore 15:00-18:00 solo on-line (Aula Virtuale)
venerdì ore 12:00-14:00 Aula Tonelli (Dip. Matematica) e on-line (Aula Virtuale)
Lezioni e Argomenti trattati
- Lu.21/09/20, ore 11:00-13:00: Aula Virtuale (solo on-line)
Slide: Introduzione e informazioni sul corso.
(file .pdf)
- Ma.22/09/20, ore 15:00-18:00: Aula Virtuale (solo on-line)
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.
Standard ANSI/IEEE 754 (1985): Basic-Single e Basic-Double.
Attivita' di Laboratorio
Esercitazione 01: ambiente MatLab (istruzioni/comandi, built-in function) (vedi slide su 'MATLAB/Octave I parte' in Documenti);
- Ve.25/9/20, ore 12:00-14:00: Aula Virtuale (solo on-line)
Soluzione dell'Esercizio 1. Rappresentazione in memoria dei numeri Finiti (segno, esponente e mantissa).
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). Esempi in base 10.
Standard ANSI/IEEE 754 (1985): ripresi Basic-Single e Basic-Double rispettivamente a 32 e 64 di bit; arrotondamento ai pari, Nan, Infinity e cenno ai Gradual underflow.
Esercizio 2:
Si consideri il numero -13.9 in base 10 e si determini la sua rappresentazione in F(2,5,-3,4).
- Lu.28/09/20, ore 11:00-13:00: Aula M1 e on-line
Soluzione dell'Esercizio 2.
Richiamata conversione da base 10 a base 2 di un numero reale (parte intera e frazionaria);
decodifica del numero memorizzato.
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.
Definizione di unita' di arrotondamento.
Teorema di maggiorazione dell'errore relativo di rappresentazione.
Corollario sulla rappresentazione di fl(a).
Numero di cifre di precisione in base 10.
- Ma.29/09/20, ore 15:00-18:00: Aula Virtuale (solo on-line)
Attivita' di Laboratorio
Esercitazione 01: primi script in Matlab (vedi slide su 'MATLAB/Octave I parte' in Documenti);
(vedi file pdf e archivio tgz in Download Materiale Lab).
- Ve.2/10/20, ore 12:00-14:00: Aula Tonelli e on-line
Soluzione degli Esercizi 3 e 4.
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 sull'addizione di
due numeri reali ed errore di cancellazione numerica. Esempio di cancellazione numerica.
- Lu.5/10/20, ore 11:00-13:00: Aula M1 e on-line.
Altri esempi sulla cancellazione numerica. Esempio di analisi in avanti sulla moltiplicazione di due numeri reali.
Modellizzazione di un problema come f:R->R e piu' in generale come f:R^n->R.
Problema ben posto.
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.
- Ma.6/10/20, ore 15:00-18:00: Aula Virtuale (solo on-line)
Attivita' di Laboratorio
Esercitazione 2: Linguaggio Matlab (vedi slide su 'MATLAB/Octave II parte' in Documenti);
(vedi file pdf e archivio tgz in Download Materiale Lab).
- Ve.9/10/19, ore 12:00-14:00: Aula Tonelli e on-line
Stima di E_IN nel caso di un problema modellizzato come f:R->R differenziabile; numero di condizione.
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 addizione e moltiplicazione fra numeri reali.
Esempio: sqrt(x_1+x_2) - sqrt(x_1).
Esempio: radici di un'equazione di secondo grado.
- Lu.12/10/20, ore 11:00-13:00: Aula M1 e on-line.
Funzioni Polinomiali
Richiami sulle funzioni polinomiali. Valutazione numerica di una funzione polinomiale.
Metodo dalla definizione in base canonica, metodo di Horner,
metodo di Ruffini e complessità computazionale. Esempio numerico di valutazione.
- Ma.13/10/20, ore 15:00-18:00: Aula Virtuale (solo on-line)
Attivita' di Laboratorio
Esercitazione 3: Ancora sul Linguaggio Matlab e i Numeri Finiti
(vedi file pdf e archivio tgz in Download Materiale Lab).
- Ve.16/10/19, ore 12:00-14:00: Aula Tonelli e on-line
Valutazione numerica della derivata di un polinomio.
Esempio numerico di valutazione e derivata. Errore Algoritmico sulla valutazione polinomiale con 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.
Stima di E_IN per il problema della valutazione polinomiale; valutazione polinomio lineare: esempio numerico ed errore inerente.
Stima di E_IN per valutazione di polinomi espressi in una generica base.
Scomposizione in E_IN1 e E_IN2.
Base dei polinomi di Bernstein su un intervallo.
Esempio numerico nella base di Bernstein con riduzione di E_IN1.
Polinomi e cambio di variabile. Riduzione di E_IN2.
Cambio di variabile per polinomi nella base di Bernstein.
- Lu.19/10/20, ore 11:00-13:00: Aula M1 e on-line.
Esempio numerico nella base di Bernstein con riduzione di E_in2.
Proprieta' dei polinomi base di Bernstein. Formula ricorrente per polinomi base di Bernstein.
Esercizio 6:
Analizzare la formula ricorrente e progettare una function Matlab che la implementi; l'intestazione sia function bs=bernst(g,x)
Algoritmo di valutazione (Alg.1), complessita' computazionale.
Algoritmo di valutazione di de Casteljau (Alg.2), complessita' computazionale.
- Ma.20/10/20, ore 15:00-18:00: Aula Virtuale (solo on-line)
Attivita' di Laboratorio
Esercitazione 4: Su rappresentazione grafica in Matlab e valutazione polinomiale
(vedi file pdf e archivio tgz in Download Materiale Lab).
- Ve.23/10/19, ore 12:00-14:00: Aula Tonelli e on-line
Ripreso l'Alg.2 di valutazione. Esempio numerico di valutazione con de Casteljau.
Algoritmo di de Casteljau e Suddivisione.
Esercizio 7:
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. Derivata prima e successive di un polinomio nella base di Bernstein.
Valutazione della derivata di un polinomio nella base di Bernstein (Alg.1); valutazione della derivata (Alg.2).
primitiva di una funzione polinomiale nella base di Bernstein; primitiva e integrale definito, di una funzione polinomiale
nella base di Bernstein.
Esercizio 8:
Determinare l'integrale in [0,1] dei polinomi base di Bernstein di grado n.
- Lu.26/10/20, ore 11:00-13:00: Aula M1 e on-line.
Interpolazione Polinomiale
Problema di interpolazione polinomiale di dati e funzioni (Interpolazione alla Lagrange).
Esistenza e unicità del polinomio interpolante: sistema lineare e matrice di Vandermonde. Esempi numerici.
Interpolazione nella Forma di Newton (base con n-centri). Soluzione via sistema lineare triangolare inferiore.
Pseudocodice per risolvere un sistema lineare triangolare inferiore per sostituzioni in avanti.
Esempi su interpolazione nella base di Newton. Valutazione polinomio nella base di Newton.
- Ma.27/10/20, ore 15:00-18:00: Aula Virtuale (solo on-line)
Applicazione dei polinomi nella base di Bernstein (presentate slide 'Curve di Bézier e Grafica Vettoriale').
Metodo incrementale per determinare il polinomio di interpolazione nella Forma di Newton.
Interpolazione nella forma di Bernstein, soluzione via sistema lineare con matrice totalmente positiva; complessità
computazionale. Interpolazione nella Forma di Lagrange: funzioni elementari di Lagrange.
Valutazione polinomio nella base di Lagrange: prima e seconda forma baricentrica; complessità computazionale.
- Ve.30/10/20, ore 12:00-14:00: Aula Tonelli e on-line
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. Distribuzione di Chebyshev e teorema di convergenza.
Numero di condizione assoluto per l'interpolazione 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.
Interpolazione di Hermite ed esempio.
- Lu.2/11/20, ore 11:00-13:00: Aula M1 e on-line.
Interpolazione cubica di Hermite C^1 (n=3) e convergenza.
Integrazione Numerica
Formule di quadratura di Newton-Cotes (formule interpolatorie polinomiali nella forma di Lagrange su punti equispaziati);
caso n=1 (trapezi); caso n=2 (Simpson); esempio numerico.
- Ma.3/11/20, ore 15:00-18:00: Aula Virtuale (solo on-line)
Attivita' di Laboratorio
Esercitazione 5: Su interpolazione polinomiale di dati e funzioni.
- Ve.6/11/20, ore 12:00-14:00: Aula Virtuale (solo on-line)
Errori di integrazione per trapezi e Simpson; Errore di integrazione per n dispari ed n pari. Grado di precisione di una formula di quadratura.
Formule di quadratura composte; formule composte dei trapezi e di Simpson;
errore per le formule composte. Esercizio su formula dei trapezi composta.
Esercizio 9:
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; introduzione ai metodi adattivi di integrazione basati su stima dell'errore.
- Lu.9/11/20, ore 11:00-13:00: Aula Virtuale (solo on-line).
Ancora sui metodi adattivi di integrazione basati su stima dell'errore. Errore Inerente nelle formule di quadratura.
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.
Introduzione al Metodo di Newton: ipotesi di applicazione, derivazione del metodo, iterazioni del metodo.
- Ma.10/11/20, ore 15:00-18:00: Aula Virtuale (solo on-line)
Attivita' di Laboratorio
Esercitazione 6: Su integrazione numerica.
- Ve.13/11/20, ore 12:00-14:00: Aula Virtuale (solo on-line)
Metodo di Newton: ipotesi di applicazione, derivazione del metodo, iterazioni del metodo.
Interpretazione geometrica del metodo di Newton.
Metodi di iterazione funzionale per punto fisso di una funzione.
Teorema di convergenza per metodi di iterazione funzionale con dimostrazione;
interpretazione geometrica. Teorema di convergenza del metodo di Newton con dimostrazione.
Test di arresto. Condizionamento del problema f(x)=0.
- Lu.16/11/20, ore 11:00-13:00: Aula Virtuale (solo on-line)
Definizione di ordine di convergenza; ordine dei metodi di iterazione e funzionale e del
metodo di Newton, per radici semplici e multiple.
Esempio numerico. Esempi: radice quadrata di un numero e inverso di un numero.
Metodo delle secanti, teorema di convergenza, Ordine di convergenza.
- Ma.17/11/20, ore 15:00-18:00: Aula Virtuale (solo on-line)
Attivita' di Laboratorio
Esercitazione 7: Su equazioni non lineari.
- Ve.20/11/20, ore 12:00-14:00: Aula Virtuale (solo on-line)
Algebra Lineare Numerica
Soluzione di sistemi lineari quadrati. Introduzione ai metodi diretti.
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 e loro complessita' computazionale).
Metodo di Gauss e matrici elementari di Gauss per la fattorizzazione LU.
Esempio di fattorizzazione di una matrice.
- Lu.23/11/20, ore 11:00-13:00: Aula Virtuale (solo on-line)
Esempio di soluzione di un sistema lineare.
Formalizzazione dell'algoritmo di fattorizzazione di Gauss.
Complessita' computazionale della fattorizzazione LU.
Applicazione della fattorizzazione per il calcolo dell'inversa e del determinante di una matrice.
Esempio di fattorizzazione di una matrice.
Fattorizzazione LU con scambio delle righe (o pivoting parziale).
Esempio numerico sulla fattorizzazione con scambio delle righe.
- Ma.24/11/20, ore 15:00-18:00: Aula Virtuale (solo on-line)
Applicazione delle equazioni non-lineari (presentate slide 'PoV-Ray (Persistence of Vision Raytracer)').
Ancora sull'esempio numerico sulla fattorizzazione con scambio delle righe.
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.
- Ve.27/11/20, ore 12:00-14:00: Aula Virtuale (solo on-line)
Esempio di fattorizzazione e soluzione numerico in aritmetica floating point,
sia senza perno massimo che con perno massimo. Esempio numerico per fattorizzare
matrice 4x4.
Condizionamento del problema Ax=b. Richiami su norme vettoriali con esempi.
Norme matriciali.
- Lu.30/11/20, ore 11:00-13:00: Aula Virtuale (solo on-line)
Ancora su 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.
- Ma.1/12/20, ore 15:00-18:00: Aula Virtuale (solo on-line)
Attivita' di Laboratorio
Esercitazione 8: Su soluzione sistemi lineari.
- Ve.4/12/20, ore 12:00-14:00: Aula Virtuale (solo on-line)
Ancora su fattorizzazione QR. Esempi numerici. Algoritmo di fattorizzazione. Esempio.
Complessita` computazionale e Stabilita` numerica per soluzione di Ax=b con fattorizzazione QR.
- Lu.7/12/20, ore 11:00-13:00: Aula Virtuale (solo on-line)
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.
Metodi di Jacobi e Gauss-Seidel: formule matriciali e per componenti. Esempi numerici.
Confronto per velocita' di convergenza.
Fine delle Lezioni
Documenti
Download Materiale Lab
Sitografia
Modalita' d'Esame
Torna alla
home page di Giulio Casciola