Programma dettagliato dell'insegnamento Calcolo Numerico Corso di Studi in Matematica (LT), a.a. 2013-2014. PROGRAMMA DEL I SEMESTRE Esempi motivazionali (lucidi sul sito) ------------------------------------------------ Problemi ben/mal posti e ben/mal condizionati [QSS, Cap.2] ------------------------------------------------ Ben posizione di un problema. Numero di condizionamento assoluto e relativo. Consistenza e stabilita' di un metodo numerico. Convergenza. Errore relativo ed assoluto. Concetto di stime a priori e a posteriori. Teorema di Lax-Richtmyer (con dimostrazione). Concetto di errore in avanti e all'indietro. Stabilita' all'indietro. Precisione vs accuratezza. ------------------------------------------------ Aritmetica esatta ed in precisione finita [QSS, Cap.2, Par.2.5] ------------------------------------------------ Rappresentazione di numeri su calcolatore: alcuni esempi di calcoli affetti da errori macchina. Numeri floating point. Range dei numerifloating point (con dim.). Alcuni valori particolari. Precisione macchina. Errore relativo di rappresentazione (con dim.) Modello di aritmetica per numeri floating point: arrotondamento; Formalizzazione: fl(x)=x(1+delta); Un modello di aritmetica per operazioni con numeri floating point. Proprieta' che valgono e che non valgono con +, *, /. Errori nelle operazioni con fl(x): esempio della moltiplicazione e della somma algebrica. Costo computazionale: flops, (d)axpy, (d)dots, A*x. -------------------- Algebra lineare -------------------- ---------------------------------- Risoluzione di sistemi lineari [BCM, Cap.4-5], [QSS, Cap.3-4] ---------------------------------- Concetti generali: Metodi diretti e iterativi (pros e cons). Numero di condizionamento di una matrice. Norme matriciali. Lemma. || inv(A+I)|| <= 1/(1-||A||) (con dim.) (BCM, Teorema 3.13) Teorema: Distanza da problema mal posto (singolare). (con dim.) Par.4.1. (anche [QSS, Par.3.1.2]) Teorema sulla stima dell'errore di perturbazione nella risoluzione di sistemi lineari (con dim.) cond_2(A) per A simmetrica (con dim.) Corollario: stima (da sopra e da sotto) dell'errore relativo per deltaA=0. (con dim.) Esempio: la matrice di Hilbert e sistemi lineari con essa. Par.4.2. (anche [QSS, Par.3.2]) Algoritmo per la risoluzione di sistemi lineari con matrici triangolari (inf e superiore). Costo computazionale. Calcolo e costo dell'inversa di m. triangolare. Par.4.3. (anche [QSS, Par.3.3]) Algoritmo di eliminazione di Gauss per sistemi generici. Costo computazionale. L'algoritmo come metodo di fattorizzazione. Par.3.17 (anche [QSS, Par.3.4.2]) Fattorizzazione di Cholesky per matrici sim.def.pos (con dim.). Costruzione algoritmica (con dim.) e algoritmo. Costo computazionale e stabilita'. Par.3.8. (anche [QSS, Par.3.3.2]) Analisi dell'errore per il metodo di Gauss. Analisi all'indietro con stima (con dim.).Il parametro g_pp nella stima. [QSS, Par.3.7.1] Risoluzione di sistemi con matrici tridiagonali. Costo Computazionale dell'algoritmo di Thomas. [D, Par.2.7.4] Matrici sparse: considerazioni generali. Esercizi di algebra lineare con aspetti numerici. Metodi iterativi per sistemi lineari: [QSS, Par.4.1] Concetti generali. Par.5.2 (anche [QSS, Par.4.2]) Metodi classici stazionari: splitting di matrici e convergenza di metodi di punto fisso. Condizione sul raggio spettrale (con dim). Par 5.4. Il metodo di Jacobi, il metodo di Gauss-Seidel, aspetti computazionali ed esempi numerici di performance. Par 5.6. Il metodo SOR. Risultati di convergenza per i metodi classici: T: A diag.dominante, allora J e GS convergono (semi-dim) T:A sim e D>0. GS converge ss A>0 (dim) T: A tridiag, rho(BGS)=rho^2(BJ) T (Kahan). SOR converge per omega in (0,2) (dim) T(Ostrowski): omega_opt per SOR [SB, Par.8.7], [GvL, Par.10.2] Metodo dei gradienti coniugati. Derivazione dell'algoritmo. Proprieta' principali. Stima dell'errore (senza dimostrazione). ------------------------- Problema agli autovalori [BCM, Cap.2 e 6] ------------------------- Cap.2.7 Localizzazione di autovalori. Teorema di Hirsch (con dim.). Cerchi di Gerschgorin: I e II teorema (no dim.) Par.6.2 Teoremi di perturbazione: Bauer-Fike per matrici diagonalizzabili (con dim); T. Perturbazione di autovalori semplici (no dim.). T. di Courant-Fisher (o minmax) (no dim) Par.6.10-11. Il metodo delle potenze. Considerazioni sulla convergenza. Convergenza per matrici simmetriche (con dim.). Metodo delle potenze inverse traslate. Proprieta' di convergenza e aspetti implementativi. Par.6.7-8. L'iterazione QR: L'algoritmo di base. La fattorizzazione QR con rotazioni di Givens; trasformazione della matrice in forma di Hessenberg. L'algoritmo piu' efficiente. Cenni ad ulteriori miglioramenti: la traslazione e la doppia traslazione per gli autovalori complessi. Proprieta' di stabilita' (senza dim.) PROGRAMMA DEL II SEMESTRE ------------------------ Minimi Quadrati: [BCM, Cap.7], anche [QSS, Par.3.12], [D, Cap.3] ------------------------ Data fitting: un esempio motivazionale, la regressione lineare multivariata. Par.7.1. (solo alcune parti) Problema ai minimi quadrati. Esistenza della soluzione e unicita'. Risoluzione dell'equazione normale e difficolta' associate. Par.7.2. Fattorizzazione QR e minimi quadrati. Trasformazioni di Householder (Cap.4.4(b)). Loro uso nel problema dei minimi quadrati. Complessita' computazionale. Par.7.4. (solo alcune parti) Decomposizione in valori singolari: Proprieta' principali. Numero di condizionamento per matrici rettangolari. Vettori singolari e basi di spazio immagine e spazio nullo. La SVD per il problema ai minimi quadrati. Alcune strategie per il calcolo delle decomposizione. -------------------- Interpolazione [QSS, Cap.7] -------------------- Par.7.1. Forma di Lagrange per l'interpolazione. Definizione di convergenza del polinomio interpolante. Teorema di rappresentazione dell'errore (dim). Considerazioni sulla convergenza. L'esempio di Runge. Par.7.1.2-3 Stabilita'. I Polinomi di Chebyshev ed i nodi di Chebyshev per l'interpolazione. Risultati di convergenza. Par.7.2 (solo alcune parti) Forma di Newton per il polinomio interpolatorio. Proprieta' ed esempi. Par.7.3 Interpolazione composita. Stima dell'errore e ordine di convergenza. Valutazione dell'ordine. Introduzione alle splines. Par.7.6 Splines: definizione. gradi di liberta. Basi locali. Spline di grado 3: costruzione mediante sistema lineare. Spline not-a-knot, completa, naturale. Proprieta' di regolarita' e convergenza --------------------- Equazioni non lineari (da [DS]) --------------------- Definizione del problema non lineare f(x)=0 Condizionamento di un'equazione non lineare (caso di zeri semplici e multipli) Definizioni di convergenza e di velocita` di convergenza di metodi iterativi per equazioni non lineari. Il metodo di Bisezione: algoritmo, proprieta` di convergenza, calcolo delle iterazioni necessarie per ottenere un'approssimazione della soluzione con una accuratezza prefissata. criteri per valutare e confrontare metodi iterativi per equazioni non lineari (costo computazionale, velocita` di convergenza, convergenza globale/locale). Il Metodo di Newton: algoritmo (definizione geometrica e mediante modelli lineari), proprieta` di convergenza (caso zeri semplici) in ipotesi di Lipschitzianita` della derivata della funzione Varianti del Metodo di Newton: cenno agli algoritmi e alle proprieta` di convergenza (Newton Stazionario, Metodo delle Secanti, Newton alle differenze). Criteri d'arresto per metodi iterativi per equazioni non lineari. Cenni a sistemi di equazioni non lineari. Il Metodo di Newton per sistemi non lineari: algoritmo e enunciato del Teorema di Convergenza. [SB, Par.5.5] Approssimazione degli zeri di polinomi e regola di Horner. [GvL, Par.7.4.6] Matrice companion di un polinomio e proprieta'. Un esempio. [SB, Par.5.8] Perturbazione di radici di polinomi. ------------------------ Integrazione Numerica [QSS, Cap.8] ------------------------ Par.8.1. Integrazione numerica. Concetti generali. Grado di precisione. Formula del rettangolo e suo errore (con dim.) Formula del trapezio e suo errore. Formula di Cavalieri-Simpson e suo errore. Formule composite delle strategie viste. Stima dell'ordine di accuratezza. Par.8.2-3. (solo alcune parti) Formule generali di Newton-Cotes. Proprieta'. Par.8.5.2. Integrazione adattativa: derivazione dell'algoritmo adattivo di Simpson. Esercizi con il metodo dei coefficienti indeterminati. -------------------------------------------------- FINE -------------------------------------------------- BIBLIOGRAFIA [BCM] "Metodi numerici per l'algebra lineare", D. Bini, M. Capovani e O. Menchi, Zanichelli 1988. [D] "Applied Numerical Linear Algebra", J. W. Demmel, SIAM 1997. [DS] "Numerical methods for unconstrained optimization and nonlinear equations", J.E. Dennis e R.B. Schnabel, Prentice Hall, Englewood Cliffs, NJ, 1983. [GvL] "Matrix computations", G. H. Golub e C. F. Van Loan, The Johns Hopkins University Press, 1996 e succ. [QSS] "Matematica Numerica", A.Quarteroni R.Sacco e F.Saleri, Springer. [SB] "Introduction to Numerical Analysis", J. Stoer, R. Bulirsch, II ed., Springer 1993 e succ. ---------------------------- aggiornato al 20/05/2014