Metodi Numerici per il Calcolo (C.d.S. Informatica per il Management (L)) A.A.2021/22
(1^ semestre, 2^ anno)
Esame: prova orale
CFU 8
Docente modulo 1: Giulio Casciola
Docente modulo 2: Davide Palitta
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ì 20 settembre 2021 con il seguente orario:
lunedì ore 12:00-14:00 Aula Magna (via Filippo Re, 10) e on-line (Aula Virtuale)
martedì ore 15:00-18:00 Aula Tonelli (Dip. di Matematica) e on-line (Aula Virtuale)
mercoledì ore 9:00-12:00 Aula Magna (via Filippo Re, 10) e on-line (Aula Virtuale)
Lezioni e Argomenti trattati
- Lu.20/09/21, ore 12:00-14:00: Aula Magna (via Filippo Re) e on-line
Slide: Introduzione e informazioni sul corso.
(file .pdf)
- Ma.21/09/21, ore 15:00-18:00: Aula Tonelli e on-line
Esercitazione di LAB
- Me.22/09/21, ore 9:00-12:00: Aula Magna (Via Filippo Re) e 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:
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,
rispettivamente a 32 e 64 bit e loro rappresentazione in memoria.
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.
Definizioni di Errore Assoluto e Relativo.
Standard ANSI/IEEE 754 (1985): ripresi Basic-Single e Basic-Double, arrotondamento ai pari, Nan, Infinity e cenno ai Gradual underflow.
Esercizio 1:
Si consideri il numero -13.9 in base 10 e si determini la sua rappresentazione in F(2,5,-3,4).
Richiamata conversione da base 10 a base 2 di un numero reale (parte intera e frazionaria).
- Lu.27/09/21, ore 12:00-14:00: Aula Magna (via Filippo Re) e on-line
Soluzione dell'Esercizio 1.
Decodifica del numero memorizzato come risultato dell'esercizio.
Esercizio 2:
Conversione, memorizzazione e riconversione per +13.9 in F(2,4,-7,8) per arrotondamento.
Definizione di unita' di arrotondamento.
Teorema di maggiorazione dell'errore relativo di rappresentazione.
Corollario sulla rappresentazione di fl(a).
Precisione e cifre significative in base 10.
Unita' di arrotondamento in Basic-Single e Basic-Double.
Aritmetica floating point e precisione di calcolo.
Esercizio 3:
Verificare con un esempio che in aritmetica finita non vale la proprieta' associativa dell'addizione.
Caratterizzazione dell'unita' di arrotondamento, anche in ANSI/IEEE.
- Ma.28/09/21, ore 15:00-18:00: Aula Tonelli e on-line
Esercitazione di LAB
- Me.29/09/21, ore 9:00-12:00: Aula Magna (Via Filippo Re) e on-line
Modellizzazione di un problema come f:R->R e piu' in generale come f:R^n->R.
Problema ben posto.
Analisi degli errori: in avanti e all'indietro. Esempio di analisi in avanti sulla moltiplicazione e sull'addizione di due numeri reali; cancellazione numerica. Esempio di cancellazione numerica.
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 nell' esempio dell'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.
Esempio su sqrt(1-x).
- Ma.5/10/21, ore 15:00-18:00: Aula Tonelli e on-line
Esercitazione di LAB
- Me.6/10/21, ore 9:00-12:00: Aula Magna (Via Filippo Re) e on-line
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.
Funzioni Polinomiali
Richiami sulle funzioni polinomiali. Valutazione numerica di una funzione polinomiale.
Metodo dalla definizione in forma canonica, metodo di Horner,
metodo di Ruffini; complessità computazionali. Esempio numerico di valutazione.
- Lu.11/10/21, ore 12:00-14:00: Aula Magna (via Filippo Re) 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 4:
Per un polinomio lineare 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.
Base con centro ed E_IN per l'esempio del polinomio lineare.
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.
- Ma.12/10/21, ore 15:00-18:00: Aula Tonelli e on-line
Esercitazione di LAB
- Me.13/10/21, ore 9:00-12:00: Aula Magna (Via Filippo Re) e on-line
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.
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), complessita' computazionale.
Esempio numerico di valutazione con de Casteljau.
Esercizio 5:
Valutare il polinomio nella base di Bernstein di coefficienti [2,-2,2] nei punti [0,1/4,1/2,3/4,1].
- Lu.18/10/21, ore 12:00-14:00: Aula Magna (via Filippo Re) e on-line
Interpolazione Polinomiale
Problema di interpolazione polinomiale di dati e funzioni.
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.
- Ma.19/10/21, ore 15:00-18:00: Aula Tonelli e on-line
Esercitazione di LAB
- Me.21/10/21, ore 9:00-12:00: Aula Magna (Via Filippo Re) e on-line
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.
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.
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; fenomeno di Runge
Distribuzione di Chebyshev e teorema di convergenza.
- Lu.25/10/21, ore 12:00-14:00: Aula Magna (via Filippo Re) e on-line
Errore Inerente (condizionamento) per l'interpolazione polinomiale.
Funzioni polinomiali 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).
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.26/10/21, ore 15:00-18:00: Aula Tonelli e on-line
Esercitazione di LAB
- Me.27/10/21, ore 9:00-12:00: Aula Magna (Via Filippo Re) e 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 6:
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. Errore Inerente nelle formule di quadratura.
- Ma.2/11/21, ore 15:00-18:00: Aula Tonelli e on-line
Esercitazione di LAB
- Me.3/11/21, ore 9:00-12:00: Aula Magna (Via Filippo Re) e on-line
Esercitazione di LAB
- Lu.8/11/21, ore 12:00-14:00: Aula Magna (via Filippo Re) e on-line
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.
Metodi di iterazione funzionale per punto fisso di una funzione.
Teorema di convergenza per metodi di iterazione funzionale con dimostrazione.
- Ma.9/11/21, ore 15:00-18:00: Aula Tonelli e on-line
Recupero su esercitazioni di LAB
- Me.10/11/21, ore 9:00-12:00: Aula Magna (Via Filippo Re) e on-line
Interpretazione geometrica. Teorema di convergenza del metodo di Newton con dimostrazione.
Test di arresto. Condizionamento del problema f(x)=0.
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.
- Lu.15/11/21, ore 12:00-14:00: Aula Magna (via Filippo Re) e 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.
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.
- Ma.16/11/21, ore 15:00-18:00: Aula Tonelli e on-line
Esercitazione di LAB
- Me.17/11/21, ore 9:00-12:00: Aula Magna (Via Filippo Re) e on-line
Fattorizzazione LU con scambio delle righe (o pivoting parziale).
Esempio numerico sulla fattorizzazione con scambio delle righe.
Lasciati alcuni esercizi di fattorizzazione da svolgere in autonomia.
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.
Condizionamento del problema Ax=b. Richiami su norme vettoriali con esempi
e norme matriciali con esempi. Indice di condizionamento di una matrice.
- Lu.22/11/21, ore 12:00-14:00: Aula Magna (via Filippo Re) e on-line
Soluzione di un sistema lineare mediante fattorizzazione QR. Matrici elementari di Householder.
Esempi numerici. Algoritmo di fattorizzazione. Esempio.
Complessita` computazionale; stabilita` numerica della fattorizzazione QR.
- Ma.23/11/21, ore 15:00-17:00: Aula Tonelli e on-line
Esercitazione di LAB
- Me.24/11/21, ore 9:00-12:00: Aula Magna (Via Filippo Re) e on-line
Esercitazione di LAB
- Lu.29/11/21, ore 12:00-14:00: Aula Magna (via Filippo Re) e 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.
- Ma.30/11/21, ore 15:00-17:00: Aula Tonelli e on-line
Esercitazione di LAB
- Me.1/12/21, ore 9:00-12:00: Aula Magna (Via Filippo Re) e on-line
Esercitazione di LAB
- Ma.7/12/21, ore 15:00-17:00: Aula Tonelli e on-line
Esercitazione di LAB
- Ma.14/11/21, ore 15:00-18:00: Aula Tonelli e on-line
Ricevimento Tutors.
Fine delle Lezioni
Documenti
Download Materiale Lab
- Vedi pagina del corso su Virtuale
Sitografia
Modalità d'Esame
Torna alla
home page di Giulio Casciola