Metodi Numerici per il Calcolo (C.d.S. Informatica per il Management (L)) A.A.2024/25
(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 e la loro applicazione al disegno 2D vettoriale.
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 17 settembre 2024 con il seguente orario:
martedì ore 9:00-12:00 Aula E2
mercoledì ore 13:00-15:00 Aula E1
giovedì ore 13:00-16:00 Aula E2
Lezioni e Argomenti trattati
- Ma.17/09/24, ore 9:00-12:00: 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:
dato l'insieme F(2,3,-1,2), determinare i suoi elementi e posizionarli sull'asse reale.
- Me.18/09/24, ore 13:00-15:00: Aula E1
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.
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): 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), quindi
lo si rirappresenti in base 10.
Richiamata conversione da base 10 a base 2 di un numero reale (parte intera e frazionaria).
- Gi.19/09/24, ore 13:00-16:00: Aula Virtuale (lezione online)
Completato l'Esercizio iniziato la lezione scorsa.
Definizioni di Errore Assoluto e Relativo. Calcolo degli errori assoluto e 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).
Unita' di arrotondamento in Basic-Single e Basic-Double.
Precisione e cifre significative in base 10 rispetto alle cifre di mantissa in base 2.
Aritmetica floating point e precisione di calcolo.
Esempio che in aritmetica finita non vale la proprieta' associativa dell'addizione.
Caratterizzazione dell'unita' di arrotondamento.
- Ma.24/09/24, ore 9:00-12:00: Aula E2
Caratterizzazione dell'unita' di arrotondamento, sia per arrotondamento (fl_A) che per arrotondamento ai pari (fl_AP).
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 degli errori in avanti sulla moltiplicazione e sull'addizione di due numeri reali.
Cancellazione numerica. Esempio numerico di cancellazione numerica.
Errori Totale, Inerente e Algoritmico: condizionamento di un problema e stabilita' di un algoritmo.
- Me.25/09/24, ore 13:00-15:00: Aula E1
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 di analisi in avanti per ricavare E_ALG ed E_IN per l'espressione ((1+x)-1)/x.
Stima di E_IN nel caso di un problema modellizzato come f:R->R continuo e differenziabile; numero di condizione.
Esempio su sqrt(1-x) ed esempio numerico.
- Gi.26/09/24, ore 13:00-16:00: Aula Cremona (Dip.Mat.)
Attivita' di Laboratorio
Esercitazione 1
: Ambiente MatLab e script (istruzioni/comandi, built-in function) (vedi slide su 'MATLAB/Octave I parte' in Documenti).
Vedi Esercitazione 1 in Download Materiale LAB:
svolto insieme l'esercizio A1 e lasciato da terminare l'A2; svolto insieme l'esercizio B1 e lasciati da completare il B2 e B3;
L'esercitazione 1 verrà ripresa e completata la prossima lezione di LAB.
- Ma.1/10/24, ore 10:00-12:00: Aula E2
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.
- Me.02/09/24, ore 13:00-15:00: Aula E1
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.
Esempio: E_ALG nel caso di valutazione polinomiale con il metodo di Ruffini-Horner di un polinomio lineare.
Esercizio 2:
Applicare l'analisi in avanti degli errori per determinare E_ALG per la valutazione di a_0 + a_1 x.
- Gi.03/10/24, ore 13:00-16:00: Aula E2
Attivita' di Laboratorio
Completata Esercitazione 1: chiesto per l'esercizio A.2 e svolti insieme gli esercizi B.2, B.3 e B.4.
Esercitazione 2
: Script, function e grafici in Matlab (vedi slide su 'MATLAB/Octave II parte' in Documenti).
Vedi Esercitazione 2 in Download Materiale LAB: svolti insieme gli esercizi A.1 e A.2 su function.
Svolto insieme l'esercizio B.1, lasciato da completare il B.2 e da fare il B.3 su script, function e disegno in Matlab.
L'esercitazione 2 verrà ripresa e completata la prossima lezione di LAB.
- Ma.08/10/24, ore 10:00-12:00: Aula E2
Ripreso e svolto l'Eesercizio 2.
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.
Base dei polinomi di Bernstein su un intervallo. E_IN per l'esempio del polinomio lineare nella base di Bernstein ed esempio numerico.
Polinomi e cambio di variabile. Cambio di variabile per polinomi nella base di Bernstein.
Propietà dei polinomi base di Bernstein.
- Me.09/10/24, ore 13:00-15:00: Aula E1
Esempio numerico nella base di Bernstein con riduzione di E_IN dopo il cambio di variabile.
Formula ricorrente per polinomi base di Bernstein. Algoritmo di valutazione (Alg.1) e considerazioni sulla
stabilità (E_ALG).
Presentazione delle slide Trasformazioni Geometriche (vedi trasformazioni_2D.pdf in Documenti).
- Gi.10/10/24, ore 13:00-16:00: Aula E2
Attivita' di Laboratorio
Ripresa e comletata l'Esercitazione 2; verificato che il B.2 sia stato completato e visionati insieme i B.3, B.4 e B.5; su quest'ultimo lasciato da fare l'ultima parte.
Esercitazione 3
: Numeri Finiti e libreria anmglib_4.1 per il disegno (vedi slide su 'Numeri Finiti' e su 'Matlab/Octave III parte' in Documenti).
Vedi Esercitazione 3 in Download Materiale LAB: svolti insieme gli esercizi A.1, A.2 e A.3; lasciato da fare l'A.4. Laciati da fare gli esercizi B.1, B.2 e B.3.
- Ma.15/10/24, ore 10:00-12:00: Aula E2
Ripreso algoritmo di valutazione (Alg.1), complessità computazionale e stabilità.
Esempio numerico di valutazione con Alg.1.
Algoritmo di valutazione di de Casteljau (Alg.2), complessità computazionale.
Esempio numerico di valutazione con Alg.2.
Presentazione delle slide Curve di Bézier e Grafica Vettoriale (vedi bezier_vector_graphics.pdf in Documenti).
Suggerito corso online su Curve di Bézier e gli Esercizi relativi (vedi Corso online su Curve di Bézier)
e quali sezioni ed esercizi guardare.
- Me.16/10/24, ore 13:00-15:00: Aula E1
Suddivisione di una funzione polinomiale.
Formula per la derivata di polinomi base di Bernstein.
Valutazione delle derivate e funzioni derivate di polinomi nella base di Bernstein. Esempio numerico.
Esercizio 3:
Dato il polinomio p(x) di grado 2 nella base di Bernstein di coefficienti [2,-2,2] definito in [0,1] valutarlo insieme alla
sua derivata prima nei punti x=0, x=1/2, x=1/4 e x=1 utilizzando tutti i metodi visti.
- Gi.17/10/24, ore 13:00-16:00: Aula E2
Attivita' di Laboratorio
Ripresa e completata l'Esercitazione 3: svolto l'esercizio A.3, corretti gli esercizi B.1, B.2 e B.3, svolto insieme l'esercizio B.4 e lasciato da fare in autonomia il B.5.
Esercitazione 4
: Funzioni Polinomiali e Curve 2D (Curve di Bézier) (vedi slide su 'Valutazione polinomiale e curve 2D' in Documenti)
Vedi Esercitazione 4 in Download Materiale LAB: svolto insieme l'esercizio A.1 e lasciato da implementare l'algoritmo di Ruffini-Horner e stampare gli addendi in corrispondenza dei punti di maggiore E_ALG. Svolto insieme l'esercizio A.3 e lasciato come compito di fare l'A.4.
- Ma.22/10/24, ore 9:00-11:00: Aula E2
Illustrato nuovamente il corso online sulle Curve di Bézier (vedi Corso online su Curve di Bézier)
Primitiva o antiderivata di una funzione polinomialiale nella base di Bernstein e calcolo del suo integrale.
Integrale di una funzione base di Bernstein.
Esercizio 4:
Dato il polinomio p(x) di grado 2 nella base di Bernstein di coefficienti [2,-2,2] definito in [0,1] determinare una sua primitiva e calcolare l'integrale fra 0 ed 1.
Interpolazione Polinomiale
Problema di interpolazione polinomiale.
Teorema di esistenza e unicitŕ del polinomio interpolante: sistema lineare e matrice di Vandermonde. Esempi numerici.
- Me.23/10/24, ore 13:00-15:00: Aula E1 e online (aula Virtuale)
Interpolazione nella Forma di Newton (base di Newton o con n centri). Soluzione via sistema lineare triangolare inferiore.
Complessità computazionale. Metodo tipo Horner per valutazione di polinomi nella base di Newton.
Esempi su interpolazione nella base di Newton.
Esercizio 4:
Determinare il polinomio di interpolazione nella forma di Newton dei seguenti dati: x=[0,2,1],y=[0,0,1].
Interpolazione nella forma di Bernstein, soluzione via sistema lineare con matrice totalmente positiva; complessità
computazionale.
Interpolazione nella Forma di Lagrange: funzioni elementari di Lagrange; complessità computazionale.
- Gi.24/10/24, ore 13:00-16:00: Aula E2
Attivita' di Laboratorio
Ripresa l'Esercitazione 4. Completato l'esercizio A.1 e svolto insieme l'esercizio A.2. Ripreso l'A.3 e svolti insieme gli esercizi A.4 e A.5. Svolti insieme gli esercizi B.1 e B.2 e lasciati da fare gli esercizi B.3, B.4, B.5 e B.6.
L'Esercitazione 5 verrà svolta la prossima lezione di LAB.
- Ma.4/11/24, ore 10:00-12:00: Aula E2
Valutazione polinomio nella base di Lagrange: prima e seconda forma baricentrica; complessitŕ computazionale.
Problema di interpolazione polinomiale di dati e funzioni, di punti e curve 2D.
Interpolazione di punti 2D con una curva 2D nella base di Bernstein; parametrizzazione uniforme e della corda.
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; esempio di Runge;
distribuzione di Chebyshev e teorema di convergenza.
- Me.6/11/24, ore 13:00-15:00: Aula E1
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: interpolazione lineare a tratti C^0;
risultato sulla convergenza e velicità di convergenza; interpolazione quadratica a tratti C^0;
interpolazione cubica a tratti C^1 (interpolazione di Hermite).
- Gi.7/11/24, ore 13:00-16:00: Aula E2
Attivita' di Laboratorio
Ripresa l'Esercitazione 4. Ripreso l'esercizio B.1 e seguendo le slide, lasciato da fare lo script scardio_tan.m; svolti gli esercizi B.3, B.4, B.5 e B.6 e in quest'ultimo seguendo le slide sono state calcolati i vettori tangenti nei punti di raccordo.
Esercitazione 5
: Interpolazione Polinomiale (vedi slide su 'Curve di Bézier e Bézier a tratti di interpolazione' in Documenti)
Vedi Esercitazione 5 in Download Materiale LAB:
svolti gli esercizi A.1, A.2 e A3; lasciato come compito di rivederli fissando le cose più importanti; l'esercitazione 5 verrà completata la prossima lezione di LAB.
- Ma.12/11/24, ore 10:00-12:00: Aula E2
Teorema di convergenza per l'interpolazione cubica a tratti C^1 (interpolazione di Hermite).
Sulla valutazione di una funzione polinomiale a tratti nella base di Bernstein.
Integrazione Numerica
Formule di quadratura di Newton-Cotes (formule interpolatorie nella forma di Lagrange su punti equispaziati); caso n=1 (trapezi), caso n=2 (Simpson). Tabella coefficienti pesi per formule di quadratura per n=3,4,5,ecc. Errori di integrazione per trapezi e Simpson.
- Me.13/11/24, ore 13:00-15:00: Aula E1
Riprese formule dei Trapezi e Simpson; errori e generalizzazione per n pari ed n dispari. Grado di precisisone di una formula di quadratura. Esempio numerico. Formule composte; formule composte dei Trapezi e Simpsono; errori e convergenza; esempio.
Esercizio 5:
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 nel caso Trapezi Composto; cenno ai metodi adattivi.
- Gi.14/11/24, ore 13:00-16:00: Aula E2
Attivita' di Laboratorio
Ripresa l'Esercitazione 5. Svolto l'esercizio A.4 e lasciato da fare a casa l'esercizio A.5. Svolti gli esercizio B.1, B.2, B.3 e B.4. Scaricare le slide LAB5_curve2d_interp.pdf e cimentarsi nell'ultimo esercizio proposto.
Esercitazione 6
: Integrazione Numerica. (vedi slide su 'Lunghezza ed Area di Curve di Bézier e Bézier a tratti' in Documenti)
Vedi Esercitazione 6 in Download Materiale Lab.
Introdotto l'esercizio A.1; svolta la prima parte e lasciato da completare.
- Ma.19/11/24, ore 9:00-11:00: Aula E2
Estrapolazione di Richardson nel caso Trapezi e Simpson Composto; metodi adattivi.
Errore inerente nelle formule di quadratura.
Applicazione alla lunghezza ed area di una curva 2D nella base di Bernstein (curva di Bézier).
Equazioni non lineari
Metodo di bisezione: ipotesi di applicazione, iterazioni del metodo,
test di arresto, velocità di convergenza.
- Me.20/11/24, ore 13:00-15:00: Aula E1
Metodo della falsa posizione, iterazione del metodo e test di arresto.
Metodo di Newton o delle tangenti: ipotesi di applicazione, derivazione del metodo, regola di iterazione 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 della condizione di convergenza. Teorema di convergenza del metodo di Newton con dimostrazione.
- Gi.21/11/24, ore 13:00-16:00: Aula E2
Attivita' di Laboratorio
Ripreso e svolto l'esercizio A.5 del LAB5 e l'esercizio presentato nelle slide del LAB5.
Ripresa l'Esercitazione 6; completato l'esercizio A.1 e lasciato da fare per casa l'esercizio A.2. Svolti gli esercizi B.1 e B.3, proposto di generalizzare la progettazione procedurale di un poligono regolare con angoli curvi. Lasciati da completare B.2 (simile a B.1) e B.4 (simile al B.6 del LAB4). Introdotto e lasciato da provare il B.5.
- Ma.26/11/24, ore 10:00-12:00: Aula E2
Metodo di Newton: test di arresto; definizione di ordine di convergenza; ordine di convergenza dei metodi di iterazione funzionale e del
metodo di Newton, per radici semplici; esempio numerico; esempi: radice quadrata di un numero e inverso di un numero.
Metodo delle secanti, teorema di convergenza, Ordine di convergenza. Errore inerente per f(x)=0.
Proprietà di variazione di segno per polinomi nella base di Bernstein; rappresentazione di p(x) nella base di Bernstein come una curva di Bézier e interpretazione geometrica dei coefficienti di p(x) come punti di controllo della curva di Bézier.
- Me.27/11/24, ore 13:00-15:00: Aula E1
Algoritmo di Lane-Riesenfeld per zeri di un polinomio nella base di Bernstein in un intervallo; applicazioni al disegno vettoriale.
Algebra Lineare Numerica
Soluzione di sistemi lineari quadrati. Motivazioni.
Soluzione di un sistema lineare Ax=b mediante fattorizzazione LU della matrice A.
Sistemi Ly=b ed Ux=y per sostituzioni in avanti e all'indietro e loro complessità computazionale.
- Gi.28/11/24, ore 13:00-16:00: Aula E2
Attivita' di Laboratorio
Ripresa e completata l'Esercitazione 6.
Esercitazione 7
: Equazioni Non Lineari e Applicazione alle curve.
(vedi slide su 'Intersezione di Curve di Bézier e Bézier a tratti' in Documenti)
Vedi Esercitazione 7 in Download Materiale LAB.
Svolti gli esercizi A.1, A.2 e A.4, lasciato da fare A.3; Introdotti gli esercizi B utilizzando le slide LAB7_itersezione_curve2d.pdf in Documenti; lasciati da svolgere in autonomia a casa, oltre all'eserczio finale proposto nelle slide.
- Ma.3/12/24, ore 10:00-12:00: Aula E2
Metodo di Gauss semplice 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.
Fattorizzazione LU con scambio delle righe (o pivoting parziale).
Esempio numerico sulla fattorizzazione con scambio delle righe.
- Me.4/12/24, ore 13:00-15:00: Aula E1
Ripreso esempio numerico su fattorizzazione di Gauss con scambio delle righe.
Analisi all'indietro per la stabilita' della fattorizzazione LU e definizione di stabilità in senso forte e debole
della fattorizzazione LU. Fattorizzazione LU con scambio delle righe e perno massimo. Esempi numerici.
Esempio in cui si confronta il risultato ottenuto in aritmetica finita operando senza e con perno massimo.
Condizionamento del problema Ax=b. Norme vettoriali.
- Gi.5/12/24, ore 13:00-16:00: Aula E2
Attivita' di Laboratorio
Ripresa l'Esercitazione 7. Lasciato da fare l'A.3 e svolti gli esercizi B.1, B.2, B.3 e B.4.
Esercitazione 8
: Ax=b e Fattorizzazione LU. (vedi slide su 'Disegno Vettoriale 2D' in Documenti)
Vedi Esercitazione 8 in Download Materiale LAB.
Svolti gli esercizi A.1 e parzialmente A.2. Lasciati da fare A.3 e rimandato l'A.4. Descritta la procedura per realizzare i due script richiesti nell'esercizio B e lasciati da fare.
- Ma.10/12/24, ore 10:00-12:00: Aula E2
Norme matriciali e norma matriciale indotta. Indice di condizionamento di una matrice.
Soluzione di un sistema lineare mediante fattorizzazione QR. Matrici elementari di Householder. Esempio.
Esercizio di fattorizzazione da svolgere in autonomia. Algoritmo di fattorizzazione QR.
- Me.11/12/24, ore 13:00-15:00: Aula E1
Algoritmo di fattorizzazione QR, implementazione ottimale, complessita` computazionale, stabilita` numerica.
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.
- Gi.12/12/24, ore 13:00-16:00: Aula E2
Attivita' di Laboratorio
Ripresa e completata Esercitazione 8. Ripreso e finito A.2, fatti A.3 e A.4.
Simulazione della procedura d'esame e di un esercizio d'esame.
Fine delle Lezioni
Preappello d'esame del 17 dicembre 2024: Aula Cremona ore 9:00
Documenti
Corso online su Curve di Bézier
Download Materiale Lab
Sitografia
Modalità d'Esame
Torna alla
home page di Giulio Casciola