Metodi Numerici per il Calcolo (C.d.S. Informatica per il Management (L)) A.A.2022/23
(1^ semestre, 2^ anno)
Esame: prova orale
CFU 8
Docente: Giulio Casciola
Scopo
Dare i fondamenti del calcolo numerico.
Contenuto
Rappresentazione dei dati su un elaboratore e aritmetica floating point. Approssimazione di dati sperimentali e approssimazione di funzioni mediante interpolazione polinomiale. Formule di quadratura per la stima di integrali di funzioni, calcolo degli zeri di funzioni non lineari e risoluzione di sistemi lineari. La parte teorica sarà affiancata da una attività di laboratorio in cui verrà utilizzato il sistema Matlab/Octave per la sperimentazione dei metodi proposti.
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 il 19 settembre 2022 con il seguente orario:
martedì ore 9:00-12:00 Aula Cremona (Dip. Mat.)
mercoledì ore 12:00-14:00 Aula Cremona (Dip. Mat.)
giovedì ore 13:00-16:00 Aula Cremona (Dip. Mat.)
Lezioni e Argomenti trattati
- Ma.20/09/22, ore 9:00-12:00: Aula Cremona
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:
dato l'insieme F(2,3,-1,2), determinare i suoi elementi e posizionarli sull'asse reale.
Standard ANSI/IEEE 754 (1985): formati Basic-Single e Basic-Double,
rispettivamente a 32 e 64 bit, rappresentazione in memoria (segno, esponente e mantissa)
e relativi insiemi dei numeri finiti.
- Me.21/09/22, ore 12:00-14:00: Aula Cremona
Ripresa rappresentazione in memoria a 32 e 64 bit.
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 e base 2.
Standard ANSI/IEEE 754 (1985): ripresi Basic-Single e Basic-Double, arrotondamento ai pari, Nan, Infinity e cenno ai Gradual underflow.
Esercizio: 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).
- Gi.22/09/22, ore 13:30-16:30: Aula Cremona
Ripreso l'Esercizio iniziato la lezione precedente. Decodifica del numero memorizzato come risultato dell'Esercizio.
Definizioni di Errore Assoluto e Relativo. Calcolo dell'errore relativo sulla rappresentazione del numero -13.9 dell'Esercizio.
Esercizio 1:
Si consideri il numero +13.9 in base 10 e si determini la sua rappresentazione in F(2,4,-7,8).
Definizione di unita' di arrotondamento.
Teorema di maggiorazione dell'errore relativo di rappresentazione.
Verifica sull'errore relativo ottenuto nell'Esercizio.
Corollario sulla rappresentazione di fl(a).
Precisione e cifre significative in base 10 rispetto alle cifre di mantissa in base 2.
Unita' di arrotondamento in Basic-Single e Basic-Double.
Aritmetica floating point e precisione di calcolo.
Esempio che in aritmetica finita non vale la proprieta' associativa dell'addizione.
Caratterizzazione dell'unita' di arrotondamento, sia per arrotondamento (fl_A) che per arrotondamento ai pari (fl_AP).
- Ma.27/09/22, ore 9:30-11:30: Aula Cremona
Soluzione dell Esercizio 1.
Problema ben posto. Modellizzazione di un problema come f:R->R e piu' in generale come f:R^n->R.
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.
- Me.28/09/22, ore 12:00-14:00: Aula Cremona
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).
- Gi.29/09/22, ore 13:30-16:30: Aula Cremona
Attivita' di Laboratorio
Ambiente MatLab (istruzioni/comandi, built-in function) (vedi slide su 'MATLAB/Octave I parte' in Documenti).
Vedi Esercitazione 1 in Download Materiale LAB: svolti insieme gli esercizi A1, A2 e A3; lasciato come
compito di svolgere l'esercizio A4. L'esercitazione verrà completata la prossima lezione di LAB.
- Me.5/10/22, ore 12:00-14:00: Aula Cremona
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. Errore Analitico.
- Gi.6/10/22, ore 13:30-16:30: Aula Cremona
Attivita' di Laboratorio
Completata Esercitazione 1: svolti insieme gli esercizi B1, B2, B3 e B4.
Linguaggio MatLab (Script e Function, strutture di controllo) (vedi slide su 'MATLAB/Octave II parte' in Documenti).
Vedi Esercitazione 2 in Download Materiale LAB: svolti insieme gli esercizi A1 e A2; iniziato l'esercizio B1 e lasciato
da completare.
- Ma.11/10/22, ore 9:30-11:30: Aula Cremona
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.
Valutazione numerica della derivata. Esempio numerico di valutazione e valutazione della derivata.
Errore Algoritmico nella valutazione polinomiale con Ruffini/Horner.
Esercizio 2:
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.
- Me.12/10/22, ore 12:00-14:00: Aula Cremona
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.
Base dei polinomi di Bernstein su un intervallo. E_IN per l'esempio del polinomio lineare nella base di Bernstein ed esempio numerico.
- Gi.13/10/22, ore 13:30-16:30: Aula Cremona
Attivita' di Laboratorio
Completato l'esercizio B1; progettata la soluzione per B2 e lasciato da completare, visto insieme il B3.
Vedi Esercitazione 3 in Download Materiale LAB: svolti insieme gli esercizi A e iniziato l'esercizio B.
Lasciato come compito di leggere cosa viene richiesto negli esercizi successivi.
- Ma.18/10/22, ore 9:30-11:30: Aula Cremona
Suddivisione di E_IN nella valutazione polinomiale in E_IN1 e E_IN2.
Esempio numerico nella base di Bernstein che comporta un E_IN2 grande.
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).
- Me.19/10/22, ore 12:00-14:00: Aula Cremona
Ripreso Alg.1: complessita' computazionale.
Algoritmo di valutazione di de Casteljau (Alg.2), complessita' computazionale.
Esempii numerici di valutazione con Alg.1 e Alg.2.
Esercizio 3:
Valutare il polinomio nella base di Bernstein di coefficienti [2,-2,2] nei punti [0,1/4,1/2,3/4,1].
Presentate slide Curve di Bézier e Grafica Vettoriale (vedi Documenti).
- Gi.20/10/22, ore 13:30-16:30: Aula Cremona
Attivita' di Laboratorio
Ripresa l'Esercitazione 3: completato l'esercizio B e svolti gli esercizi C e D (lasciato indietro l'esercizio E).
Grafici e funzioni polinomiali in Matlab (vedi slide su 'MATLAB/Octave III parte' in Documenti).
Vedi Esercitazione 4 in Download Materiale LAB: svolti gli esercizi A e B; iniziato e lasciato da completare l'esercizio C.
- Ma.25/10/22, ore 9:30-11:30: Aula Cremona
Interpolazione Polinomiale
Problema di interpolazione polinomiale di dati.
Teorema di esistenza e unicità del polinomio interpolante: sistema lineare e matrice di Vandermonde. Esempi numerici.
Problema di interpolazione polinomiale di funzioni.
- Me.26/10/22, ore 12:00-14:00: Aula Cremona
Interpolazione nella Forma di Newton (base con n-centri). Soluzione via sistema lineare triangolare inferiore.
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.
- Gi.27/10/22, ore 13:30-16:30: Aula Cremona
Attivita' di Laboratorio
Ripresa l'Esercitazione 4: completato l'esercizio C e svolti gli esercizi D, E, F ed H (lasciato indietro
l'esercizio G).
- Me.2/11/22, ore 12:00-14:00: Aula Cremona
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.
Errore Inerente (condizionamento) per l'interpolazione polinomiale.
Funzioni polinomiali a tratti: motivazioni, differenze con il modello polinomiale, regolarita' e flessibilita'.
- Gi.3/11/22, ore 13:30-16:30: Aula Cremona
Attivita' di Laboratorio
Vedi Esercitazione 5 in Download Materiale LAB: svolti insieme gli esercizi A, B e C; iniziato l'esercizio D e
lasciato da completare lo script main.
- Ma.8/11/22, ore 9:30-11:30: Aula Cremona
Interpolazione con funzioni polinomiali a tratti; esempio: interpolazione lineare a tratti C^0 (n=1);
risultato sulla convergenza e velicità di convergenza. Esempio: interpolazione quadratica a tratti C^0 (n=2).
Integrazione Numerica
Formule di quadratura di Newton-Cotes (formule interpolatorie nella forma di Lagrange su punti equispaziati); caso n=1 (trapezi).
- Me.9/11/22, ore 12:00-14:00: Aula Cremona
Formule di quadratura di Newton-Cotes (formule interpolatorie nella forma di Lagrange su punti equispaziati); caso n=2 (Simpson).
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.
- Gi.10/11/22, ore 13:30-16:30: Aula Cremona
Attivita' di Laboratorio
Ripresa l'Esercitazione 5: completato l'esercizio D e svolti gli esercizi E ed F.
- Ma.15/11/22, ore 9:30-11:30: Aula Cremona
Lezione Annullata
- Me.16/11/22, ore 12:00-14:00: Aula Cremona
Lezione Annullata
- Gi.17/11/22, ore 13:30-16:30: Aula Cremona
Lezione Annullata
- Ma.22/11/22, ore 9:30-11:30: Aula Cremona
Ripresa l'integrazione numerica; Esercizio: 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.
Esercizio 4:
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: caso trapezi ed esempi numerici, caso Simpson; introduzione ai 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.
- Me.23/11/22, ore 12:00-14:00: Aula Cremona
Ripreso il metodo di bisezione: test di arresto, velocità di convergenza.
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.
Interpretazione geometrica. Teorema di convergenza del metodo di Newton con dimostrazione.
- Gi.24/11/22, ore 13:30-16:30: Aula Cremona
Attivita' di Laboratorio
Vedi Esercitazione 6 in Download Materiale LAB. Svolti gli esercizi A, B e C.
- Ma.29/11/22, ore 9:30-11:30: Aula Cremona
Ancora sul metodo di Newton: test di arresto. Condizionamento del problema f(x)=0.
Definizione di ordine di convergenza; ordine di convergenza dei metodi di iterazione funzionale e del
metodo di Newton, per radici semplici.
Esempio numerico per radici multiole. Esempi: radice quadrata di un numero e inverso di un numero.
Metodo delle secanti, teorema di convergenza, Ordine di convergenza.
- Me.30/11/22, ore 12:00-14:00: Aula Cremona
Presentate slide PoV-Ray (Persistence of Vision Raytracer) (vedi Documenti).
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.
- Gi.1/12/22, ore 13:30-16:30: Aula Cremona
Attivita' di Laboratorio
Vedi Esercitazione 7 in Download Materiale LAB. Svolti gli esercizi A, B, C e D; descritto l'esercizio E e lasciato
da fare in autonomia.
- Ma.6/12/22, ore 9:30-11:30: Aula Cremona
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.
- Me.7/12/22, ore 12:00-14:00: Aula Cremona
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.
Fattorizzazione LU con scambio delle righe e perno massimo. Esempi numerici.
- Ma.13/12/22, ore 9:00-12:00: Aula Cremona
Definizioni di stabilita` numerica della fattorizzazione LU;
Condizionamento del problema Ax=b. Richiami su norme vettoriali con esempi e norme matriciali con esempi. Indice di condizionamento di una matrice.
Soluzione di un sistema lineare mediante fattorizzazione QR. Matrici elementari di Householder.
Esempio. Algoritmo di fattorizzazione. Complessita` computazionale.
- Me.14/12/22, ore 9:00-12:00: Aula Cremona
Attivita' di Laboratorio
Vedi Esercitazione 8 in Download Materiale LAB. Svolti gli esercizi A, B, C, D ed E.
- Me.14/12/22, ore 13:00-14:00: Aula Cremona
Stabilita` numerica della fattorizzazione 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.
Cenno ai metodi di Jacobi e Gauss-Seidel.
Fine delle Lezioni
Documenti
Download Materiale Lab
Sitografia
Modalità d'Esame
Torna alla
home page di Giulio Casciola