~~NOTOC~~ ======= Final curriculum ======== Literature: * Sauer, //Numerical Analysis//, Pearson, 2.edition. \\ 0.2-0.4, 3.1-2, 5.1.1-5.1.2. * Quarteroni, Sacco and Saleri, //Numerical Mathematics//, Springer, 2.edition. \\ 1.1-1.2, 1.11-1.12, 3.1, 3.2.1, 3.3.1,.3.3.3-4, 3.4.3, 3.5, 4.1-4.2.3, 5.1, 5.3, 5.4-5.6, 7.1-7.1.2, 7.1.5, 8.7-8.7.3 * [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/odenote.pdf|Note on numerical ODEs (NODE)]] \\ All //except// 4.3, 4.4, 5.2 and 5.3. * [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/collection_of_notes.pdf|Collection of additional notes]]. All. * Handwritten notes: * [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/ConvNoteODEHW|Proof of Theorem 4.2]] in the NODE note. * [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/QR.pdf|Note on QR-decomposition]] (24.10: p.5, the equation above "Application" is corrected.) * [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/NewtonAdditionalLemma.pdf|Lemma to prove the last inequality in Quarteroni et.al. p. 287]] * [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/B-splines.pdf|Lecture note on B-splines]] * Exercise 1-10 and solutions. See the lecture plan for details. ====== Lecture plan ======= ^ Week(s) ^ Topics ^ Reading | | ^ 34 | Introduction. \\ How to set up and present a numerical experiment. \\ Convergence plot. Numerical differentiation were used as an example. | [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/DevAnalVer.pdf|Note]]. \\ Sauer 5.1.1-5.1.2 | | ^ | Floating point representation, rounding errors, machine precision, condition numbers, error propagation. | Sauer 0.2-0.4 \\ [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/ErrorPropagation.pdf|Note on error propagation.]] | | ^ ^ Numerical solution of ODEs ^ [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/odenote.pdf|Note on numerical ODEs (NODE) (pdf).]] \\ | | ^ 35 | Norms in \(\mathbb{R}^m\). The Lipschitz condition. \\ Existence and uniqueness of solutions of ODE. \\ The one-sided Lipschitz condition. | [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/NormAndInnerProduct.pdf|Note on norms and inner products in \(\mathbb{R}^m \)]] \\ NODE note, section 2. | | ^ | One-step methods, in particular Runge-Kutta methods. \\ The definitions of increment functions, global error and the local truncation error. \\ Convergence of one-step methods (Theorem 4.2) with proof. | NODE note, section 1, 3, 4.1. \\ [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/ConvNoteODEHW|Proof of Theorem 4.2]] \\ [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/CorrW2.pdf|Correction of an example in the lecture]] | | ^ 36 | Order conditions for RK-methods \\ How to find the order conditions from rooted trees. | [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/b-series.pdf|Order conditions for RK-methods]] (updated 08.09). \\ This is Section 4.1 from the NODE note, but corrected and extended, \\ and with an [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/TreeOrderCond.pdf|Example]]. | | ^ | B-series and rooted trees, Proof of Theorem 4.5. | Section 4.1 (cont.) | | ^ 37 | **NB!** // Monday 12.09, 17:15-18:00 in EL2. \\ Error control and stepsize selection, embedded Runge-Kutta methods \\ This was partly covered in TMA4320 // | Section 4.2 in the NODE note. \\ [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/adaptiveERK.pdf|Algorithm: Adaptive explicit RK method]] | | ^ | Stiff ODEs. Linear stability analysis \\ The linear test equation \(y'=\lambda y\), the stability function \(R(z)\), the stability domain and A-stability. | Section 5.0-5.1 in the NODE note | | ^ | Linear multistep methods \\ Convergence, local discretization error, consistency and order of consistency. | Section 6-6.1 + def. 6.1 in the NODE note | | ^ 38 | **NB!** // Monday 19.09, 17:15-18:00 \\ Polynomial interpolation // | Sauer 3.1-2 | | ^ | Zero-stability. Necessary and sufficient conditions for convergence (Theorem 6.2), and the first Dahlquist-barrier) | Section 6.2 and 6.3 in the NODE note \\ The Matlab-code [[http://www.math.ntnu.no/emner/TMA4215/2016h/matlab/lmm.m|lmm.m]] for simple experiments with 2-step methods. | | ^ | How to construct LMM by interpolation, e.g. Adams-Bashforth-Moulton methods, \\ Predictor-corrector pair. Milne's device for error estimation. | [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/AdamsPredCorr.pdf|Note on Adams methods and predictor-corrector schemes]] \\ For BDF-methods, see exercise 5. | | ^ 39(1) | Numerical differentiation. Extrapolation methods | Sauer 5.1 + [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/Extrapolation.pdf|Note on extrapolation methods.]] \\ The matlab code [[http://www.math.ntnu.no/emner/TMA4215/2016h/matlab/extrapolation.m|extrapolation.m]] | | ^ 39-42 ^ Numerical linear algebra and solution of nonlinear systems of equations ^ Quarteroni et.al [[http://link.springer.com/book/10.1007%2Fb98885|Numerical Mathematics]] | | ^ 39 | Efficient computations in Matlab (work directly on vectors and matrices whenever possible) \\ Matrices, (natural) matrix norms. \\ Forward error analysis and condition numbers (Thm. 3.1 and 3.2). \\ Symmetric positive definite (SPD) matrices and their properties (Q: Property 1.18), diagonal dominant matrices. | \\ Q: 1.1-1.2, 1.11-1.12, 3.1 | | ^ 40 | Gauss-elimination (GE) and LU-factorizations for solving \(Ax=b\). \\ Useful result: if \(A\) is strictly diagonal dominant then \(A=LU\) exist. \\ GE with pivoting will be taught on Friday. | Q: 3.2.1, 3.3.1, 3.3.3-4 \\ [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/Gauss.pdf|Slides from the lecture]] \\ Matlab: [[http://www.math.ntnu.no/emner/TMA4215/2016h/matlab/gauss.m|gauss.m]] | | ^ | Cholesky decomposition \( A=C^TC \) for \(A\) SPD . \\ Gauss elimination with partial pivoting . \\ Started a little bit with iterative methods for solving \(Ax=b\) | Q: 3.5 \\ Matlab: [[http://www.math.ntnu.no/emner/TMA4215/2016h/matlab/gauss_piv.m|gauss_piv.m]] | | ^ 41 | Classical iterative methods for solving \(Ax=b\). \\ Convergence results for a generic iteration scheme \( x^{(k+1)}=Bx^{(k)}+f\). \\ Jacobi-, Gauss-Seidel- and SOR-iterations, including the convergence results. \\ | Q: 4.1-4.2.3 [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/slideIter.pdf|Slides with example]] \\ with corresponding Matlab-file: [[http://www.math.ntnu.no/emner/TMA4215/2016h/matlab/poisson_GS.m|poisson_GS.m]] | ^ | Eigenvalues and eigenvectors \\ The Gershgorin theorems \\ The power method and the inverse power method | Q: 5.1, 5.3 | ^ 42 | QR-factorizations | Q: 3.4.3, 5.4-5.6 \\ [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/QR.pdf|Note on QR-decomposition]]| ^ | Numerical solution of nonlinear systems of equations \\ Newton's method. Convergence result (Theorem 7.1 + proof). | Q: 7.1-7.1.1 \\ [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/NewtonAdditionalLemma.pdf|Lemma]] to prove the last inequality on page 287. | ^ 43 | Modifications of Newton's method. Numerical Jacobians. \\ Fixed point iterations, convergence (Theorem 7.2 + proof) and Property 7.2. \\ Steepest descent. | Q:7.1.2 and 7.1.5 \\ Additional [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/NonLinear.pdf|note]], with steepest descent included. | ^ ^ Splines ^ | | ^ 43 | Definition of splines. Cubic splines, and how to find them. | Q: 8.7-8.7.1 \\ [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/Splines.pdf|Note on interpolating cubic splines]]| ^ 44 | B-splines, Definition, properties, evaluation. | Q: 8.7.2 \\ [[http://www.math.ntnu.no/emner/TMA4215/2016h/notater/B-splines.pdf|Lecture notes on B-splines]] | ^ | Parametric splines and Bezier curves | Q: 8.7.3 \\ see also the [[https://en.wikipedia.org/wiki/Bézier_curve|Wikipedia page on Bezier-curves]] | ^ 45-46 ^ Project work (deadline Monday November 21) | | ^ 47 ^ Repetition | | \\ ====== Topics ====== The preliminary curriculum consists of the following topics: ===== Error analysis ====== * Floating point arithmetic * Error analysis * Condition number ===== Numerical solution of ordinary differential equations ===== * Numerical differentiation * Linear multistep methods * Runge--Kutta methods * Stability analysis and stiff problems. * Implementation issues * Two point boundary problems. * Extrapolation (not only for ODEs) ===== Numerical linear algebra and solution of nonlinear equations. ===== * Direct methods for linear systems * Iterative methods for linear systems * Eigenvalue and eigenvector computations * Iterative methods for nonlinear system of equations. ===== Splines (curve approximation) ===== * Interpolating splines * B--splines * Bezier-curves The topics //numerical integration// and //polynomial interpolation// have been covered in the courses //Introduction to scientific computing// or //Mathematics 4M/N/D/ //. For students that have taken none of those (or need to refresh their knowledge), additional lectures be offered whenever needed. These will be during the exercise hours on Monday and will be announced in advance.