Analisi Numerica 2016-17

 

Laurea triennale in Matematica

Analisi Numerica (12 CFU)

Primo semestre del secondo anno.

Inizio lezioni: 4 Ottobre 2016

Sono previste 24 lezioni teoriche di 2 ore ciascuna in aula, e 48 ore di esercitazioni in laboratorio con l’utilizzo di MatLab.

Orario e aula:

  • Martedì 9-11 Aula D (teoria) – 15-17 Lab. 5 (esercitazione)
  • Giovedì  9-11 Aula D (teoria) –  15-17 Lab. 5 (esercitazione)
  • Venerdì 9-11 Aula D (teoria),  solo nei giorni 21/10, 4/11 e 18/11

Ricevimento studenti: Tutti i giorni 9-13. Pomeriggio su appuntamento.

Materiale didattico:

Programma dettagliato del corso:

Lezioni teoriche
1. Introduzione al corso. Richiami. Presentazione del corso. Orari e libri di testo. Modalità d’esame. Contenuti del corso. Cosa è l’Analisi
Numerica. Problema ben posto e ben condizionato. Algoritmo stabile e instabile. Complessità computazionale. Richiami di Algebra Lineare: spazi lineari, sottospazi. Basi, spazi a dimensione infinita. Norma, seminorma e distanza. Norme di vettore in R^n , norma 1, 2 e norma infinito. Le sfere unitarie in R^2 nelle differenti norme. Equivalenza delle norme. Definizione di norma di matrice indotta dalla norma naturale di vettore. Consistenza e proprietà submoltiplicativa delle norme di matrice (cd). Norma del massimo di matrice indotta dalla norma di vettore (cd). Esempi di norme di matrice: di Manhattan, euclidea e di Frobenius. Teorema: il raggio spettrale di una matrice quadrata è minore o uguale della sua norma naturale (cd). Definizione di matrice convergente. Legame tra matrice convergente, norma e raggio spettrale. Prodotto scalare e spazi di Hilbert. Ortogonalità. Esempi di prodotto scalare (in particolare negli spazi L_p [a, b]).

2. Rappresentazione dei numeri nel calcolatore. Analisi degli errori. Tipi di errore: errore nel modello; errore nei dati; errori di arrotondamento; errori di troncamento. Notazione posizionale di un numero reale rispetto ad una base beta (in particolare in base 2). Notazione esponenziale normalizzata di un numero reale. Mantissa ed esponente. L’insieme dei numeri macchina o sistema floating point: definizione. Cardinalità dell’insieme dei numeri macchina. Approssimazione di un numero reale con un numero macchina: arrotondamento e troncamento. Valutazione dell’errore commesso nel caso di arrotondamento (cd) e troncamento. Precisione macchina. Aritmetica floating point: operazioni macchina. Condizionamento di un problema: definizione di errore inerente. Analisi di un problema in relazione all’errore inerente. Stabilità di un algoritmo: definizione di errore algoritmico. Analisi in avanti di un errore algoritmico.

3. Sistemi lineari. Risoluzione di un sistema lineare di n equazioni ed n incognite: considerazioni generali. Problematiche relative agli algoritmi che risolvono Ax=b. Calcolo dell’inversa. Tecniche di scaling. Sistemi triangolari, superiori e inferiori. Metodi di sostituzione in avanti e all’indietro per sistemi triangolari. Complessità computazionale dei due algoritmi. Metodo di Gauss “naive” per risolvere un sistema lineare: idea base, algoritmo in pseudo codice e sua complessità computazionale. Tecniche di pivoting parziale e totale nella risoluzione di Ax=b con il metodo di Gauss. Utilità del pivoting. Gauss con pivoting scalato. L’algoritmo di Gauss in forma matriciale, sia naive che con scambio di righe. Realizzazione della fattorizzazione A=LU con il metodo di Gauss. Risoluzione di un sistema lineare mediante fattorizzazione della matrice dei coefficienti. Metodo di Doolitle. Metodo di Cholesky per la risoluzione di un sistema lineare con matrice definita positiva. Matrici sparse e matrici a bande. Algoritmo di Gauss per matrici a banda. Condizionamento di un sistema lineare: variazione della soluzione al variare dei dati (analisi dettagliata nel caso di variazione del solo termine noto e della sola matrice). Definizione di numero di condizionamento della matrice dei coefficienti. Proprietà del numero di condizionamento. Esempi di matrici malcondizionate. Metodi iterativi per la risoluzione di un sistema lineare. Metodi di Jacobi e Gauss-Seidel: schema generale, matrice di iterazione. Algoritmi di Jacobi e Gauss-Seidel. Convergenza dei due metodi.

4. Approssimazione di funzioni. Problematiche generali del problema dell’approssimazione di funzioni. Tecniche di interpolazione: definizione generale del problema di interpolazione. Interpolazione lineare, polinomiale e trigonometrica. Esistenza e unicità del polinomio interpolante (cd). Costruzione del polinomio interpolante mediante il metodo di Lagrange: polinomi L i e loro proprietà. Interpolazione di Hermite, formulazione matematica generale. Definizione del problema generale dell’interpolazione polinomiale in uno spazio lineare. Algoritmo di Neville sia con la notazione P ij che con la notazione T_ij . Studio della convergenza nell’interpolazione polinomiale. Teorema di Weierstrass. Definizione di matrice di interpolazione. Teorema di Faber. Rappresentazione dell’errore puntuale (cd) e suo corollario. Esempio di Runge. Polinomi di Chebichev e loro proprietà. Teorema di Bernstein. Funzioni splines: definizione generale di funzione spline di grado p, suoi gradi di libertà. Esempi. Vantaggi dell’uso di funzioni splines. Funzioni splines di grado 1: loro rappresentazione nel piano. Algoritmo per il calcolo di una spline lineare in un dato punto. Errore per una spline di grado 1. Spline cubiche: gradi di libertà. Spline cubiche naturali e periodiche. Migliore approssimazione: definizione generale. Formulazione matematica del problema in spazi lineari normati. Risultati di esistenza e unicità dell’elemento di migliore approssimazione. Applicazioni: migliore approssimazione nel senso dei minimi quadrati, caso continuo e caso discreto.

5. Integrazione numerica. Formule di quadratura: definizione e generalità. Grado di precisione di una formula di quadratura. Metodo dei coefficienti indeterminati. Formule di quadratura elementari e composte. Formule di quadratura interpolatorie elementari. (Integrale di riferimento di estremi -1, 1). Formule di Newton-Cotes chiuse e aperte: formula dei trapezi, formula di simpson, formula del punto medio (rettangolo) e loro interpretazione geometrica. Formule composte: rettangolo, trapezi, simpson e trapezi modificata. Interpretazione geometrica. Convergenza delle formule composte (cd). Errore delle formule di quadratura. Teorema di Peano. Applicazione del teorema di Peano: errore della formula del rettangolo. Corollari del teorema di peano (cd) e loro applicazione. Errore delle formule composte, dimostrazione nel caso specifico della formula dei trapezi. Formule di quadratura gaussiane: costruzione delle formule Gaussiane. Esempio di formula di quadratura gaussiana a due punti. Funzione peso in una formula di quadratura. Formule di Gauss-Legendre e di Gauss-Chebishev. Generalità sulle formule di quadratura adattive. Formula di quadratura adattiva di Simpson: algoritmo dettagliato.

6. Equazioni e sistemi non lineari. Definizione generale di un problema non lineare (una variabile e n variabili). Metodi iterativi. Condizionamento del problema. Il metodo di bisezione: algoritmo dettagliato e significato geometrico. Analisi della convergenza. Definizione di ordine di convergenza di un metodo iterativo. Ordine di convergenza del metodo di bisezione. Il Metodo Regula Falsi sua interpretazione geometrica. Il metodo di Newton: schema iterativo e suo significato geometrico. Comportamento in caso di radici multiple. Ordine di convergenza (cd) e costante asintotica dell’errore. Considerazioni qualitative sufficienti riguardo la convergenza. Teorema generale per la convergenza globale del metodo di Newton. Casi speciali del metodo di Newton: calcolo del reciproco di un numero e metodo di Erone. Metodi quasi-Newton: corde e secanti. Interpretazione geometrica dei metodi di Newton e quasi-Newton. Criteri di stop. Metodo di Newton per la risoluzione di un sistema di equazioni non lineari. Teoria generale dei metodi iterativi. Metodo delle approssimazioni successive. Teoremi di punto fisso: teorema di Banach. Teorema di Brouwer. Funzioni contrattive. Risultati locali di punto fisso. Esempio di Newton.

7. Autovalori e autovettori. Autovalori e autovettori di una matrice quadrata: generalità e proprietà principali. Teoremi di Gerschgorin per la localizzazione degli autovalori. Condizionamento di una matrice relativamente al calcolo degli autovalori: teorema di Bauer-Fike (cd) e suo corollario. Condizionamento per matrici simmetriche, ortogonali e unitarie. Metodo delle potenze per il calcolo del primo autovalore (e corrispondente autovettore) di una matrice. Descrizione dettagliata del metodo e sua convergenza. Metodo delle potenze con scaling. Metodi per similitudine. Trasformazioni mediante matrici ortogonali. Matrici elementari di Householder. Fattorizzazione QR di una matrice mediante matrici di Householder. Metodo QR per il calcolo degli autovalori di una matrice. Convergenza del metodo. Metodo QR con traslazione d’origine (shift). Costruzione di matrici test simmetriche e non simmetriche con Matlab. Matrice compagna.

8. Equazioni differenziali ordinarie. Definizione di equazione differenziale ordinaria. Ordine e grado di una equazione differenziale. Integrale generale e integrale particolare. Equazione in forma normale. Esempi di risoluzione analtica: equazioni a variabili separabili. Esempio di Malthus. Formulazione del problema di Cauchy in forma vettoriale. Soluzioni locali e globali. Lipschitzianità. Esempio preda-predatore. Metodi discreti in analisi numerica: soluzione discreta. Costruzione di alcune formule mediante l’approssimazione della derivata con un rapporto incrementale: metodi alle differenze finite in avanti, all’indietro e differenze finite centrali. Costruzione di alcune formule mediante trasformazione del problema di Cauchy in un problema di integrazione e successiva quadratura numerica. Catalogazione dei metodi: metodi monostep e multistep, espliciti e impliciti. Rappresentazione grafica del metodo di Eulero esplicito. Metodi Runge-Kutta: procedimento dettagliato nel caso di metodi monostep espliciti del primo (m=1) e secondo ordine (m=2). Tableau per RK a 3 e 4 stadi. Metodi Runge-Kutta impliciti. Schema generale. Metodi Predictor-Corrector. Schema PECE e PEC. Analisi dell’errore nei metodi monostep espliciti. Errore globale ed errore locale di discretizzazione. Errore di troncamento (suo significato geometrico nel metodo di Eulero esplicito). Errore di propagazione. Convergenza dei metodi iterativi e ordine di convergenza. Consistenza di un metodo: definizione generale. Consistenza nel metodo di Eulero esplicito. Definizione di zero-stabilità. Teorema di equivalenza. Analisi dettagliata dell’errore nel caso del
metodo di Eulero esplicito: passo ottimale di integrazione.

Esercitazioni in laboratorio
Il laboratorio consiste nello svolgimento di 28 esercitazioni in MATLAB, suddivise in due gruppi: prima parte e seconda parte, riguardanti la realizzazione di programmi dei principali metodi studiati a lezione. Tutte le esercitazioni si possono scaricare da questo sito.
Prima parte:
Esercitazione 1: esercizi di introduzione a Matlab.
Esercitazione 2: radici reali e complesse di una equazione di secondo grado.
Esercitazione 3: calcolo dell’epsilon macchina. Esercizi sulla stabilità e instabilità numerica.
Esercitazione 4: metodi di sostituzione in avanti e all’indietro per sistemi triangolari.
Esercitazione 5: algoritmo di Gauss-naive.
Esercitazione 6: algoritmo di Gauss con scaling e pivoting parziale.
Esercitazione 7: algoritmo di Cholesky.
Esercitazione 7b: algoritmo di Gauss-Dolittle.
Esercitazione 8: metodi di Jacobi e Gauss-Seidel.
Esercitazione 9: algoritmo di Lagrange per l’interpolazione.
Esercitazione 10: algoritmo di Neville.
Esercitazione 11: utilizzo della function polyfit di Matlab per determinare il polinomio interpolante.
Esercitazione 12: costruzione di una spline lineare. Utilizzo della function spline di Matlab.
Esercitazione 13: utilizzo delle functions polyfit e polyval di Matlab nella migliore approssimazione.
Seconda parte:
Esercitazione 1: formule di quadratura composte del rettangolo, dei trapezi e dei trapezi modificata.
Esercitazione 2: formula di quadratura composta di Simpson. Valutazione degli errori a priori delle formule implementate.                              Esercitazione 3: calcolo del numero di intervalli da considerare in una formula di quadratura per ottenere una data precisione. Formule di Gauss-Legendre.
Esercitazione 3a: formula di quadratura di Simpson-adattiva.
Esercitazione 4: algoritmo di bisezione.
Esercitazione 5: algoritmo di Newton.
Esercitazione 6: algoritmo delle secanti.
Esercitazione 7: algoritmo di Newton per sistemi di equazion nonlineari.
Esercitazione 7a: esercizi sui procedimenti iterativi di punto fisso.
Esercitazione 8: metodo delle potenze.
Esercitazione 8a: metodo QR e QR con shift.
Esercitazione 9: metodi di Eulero, Eulero modificato e di Heun.
Esercitazione 10: metodo del punto medio. Applicazione a preda-predatore.
Esercitazione 11: utilizzo della function Ode45 di Matlab per la risoluzione dei problemi di Cauchy.

Testi principali di riferimento

  • V. Comincioli, Analisi Numerica, metodi modelli applicazioni, McGraw-Hill Libri Italia, srl, Milano 1990.
  • A. QUARTERONI, R. SACCO, F. SALERI, Matematica Numerica, Springer-Verlag Italia, Milano.
  • G. RODRIGUEZ, Algoritmi Numerici, Pitagora Editrice, Bologna.
  • J. STOER, R. BURLICH, Introduzione all’Analisi Numerica, Ed. Zanichelli.

Modalità d’esame.  Prova scritta + prova orale. Sono  previsti due scritti parziali in itinere.  Coloro che non superano il primo parziale dovranno sostenere lo scritto relativo all’intero corso di Analisi Numerica. Per essere ammessi all’orale bisogna superare la prova scritta. La prova scritta riguarda gli argomenti teorici trattati a lezione. Nella prova orale, oltre la teoria, verranno richieste le esercitazioni MatLab effettuate in laboratorio.

Modalità di iscrizione alla prova d’esame. Per le prove scritte, da effettuarsi mediante la procedura di iscrizione online sul sito https://webstudenti.unica.it.

Per le prove orali, da concordare dopo aver superato la prova scritta.

 Date delle prove scritte

  • Primo scritto parziale Martedì 8 Novembre ore 9:00 – 11:00 aula D.
  • Secondo scritto parziale Martedì 20 Dicembre ore 9:00-11:00 aula D.
  • Secondo scritto parziale Martedì 10 Gennaio ore 9:00-11:00 aula D.

 

Voto minimo per superare lo scritto 18/30

Date prova scritta generale:

  • 27 Gennaio ore 9:00 aula D
  • 22 Febbraio ore 9:00 aula D

 

credits unica.it | accessibilità Università degli Studi di Cagliari
C.F.: 80019600925 - P.I.: 00443370929
note legali | privacy

Nascondi la toolbar