Final curriculum

Literature:

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. 		Note.
Sauer 5.1.1-5.1.2
Floating point representation, rounding errors, machine precision, condition numbers, error propagation. Sauer 0.2-0.4
Note on error propagation.
Numerical solution of ODEs 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. 		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.
Proof of Theorem 4.2
Correction of an example in the lecture
36 Order conditions for RK-methods
How to find the order conditions from rooted trees. 		Order conditions for RK-methods (updated 08.09).
This is Section 4.1 from the NODE note, but corrected and extended,
and with an 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.
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 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. 		Note on Adams methods and predictor-corrector schemes
For BDF-methods, see exercise 5.
39(1) Numerical differentiation. Extrapolation methods Sauer 5.1 + Note on extrapolation methods.
The matlab code extrapolation.m
39-42 Numerical linear algebra and solution of nonlinear systems of equations Quarteroni et.al 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
Slides from the lecture
Matlab: 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: 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 Slides with example
with corresponding Matlab-file: 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
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
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 note, with steepest descent included.
Splines
43 Definition of splines. Cubic splines, and how to find them. Q: 8.7-8.7.1
Note on interpolating cubic splines
44 B-splines, Definition, properties, evaluation. Q: 8.7.2
Lecture notes on B-splines
Parametric splines and Bezier curves Q: 8.7.3
see also the 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.
2016-11-24, Anne Kværnø