Lectures

• Tue, 8:15-9:45 (via zoom)
• Wed, 9:00-9:45 (via zoom; nur CSE)

Exercises

• Group 1: Mon 10:00-10:45
• Group 2: Tue 10:00-10:45
• Group 3: Tue 10:00-10:45
• Group 4: Thu 10:00-10:45

Slides from class

• slide 1: introductory comments on convergence, efficiency, error estimation (PDF)
• slide 2: an example of Lagrange interpolation (PDF)
• slide 3: an example the Neville scheme (PDF)
• slide 4: schematic view of extrapolation (PDF)
• slide 5: extrapolation of one-sided difference quotients (PDF)
• slide 6: extrapolation of one-sided difference quotients: "failure exampe" (PDF)
• slide 7: extrapolation of symmetric difference quotients (PDF)
• slide 8: Chebyshev points and Chebyshev interpolation (PDF)
• slide 9: Runge example for polynomial interpolation in equidistant knots (PDF)
• slide 9a: polynomial interpolation vs. spline interpolation for Runge example (PDF)
• slide 9b: properties of the FFT (PDF)
• slide 10: illustration of composite midpoint and trapezoidal rule (PDF)
• slide 11: Newton-Cotes formulas; example why large n is not a good idea (PDF)
• slide 12: composite trapezoidal and Simpson rule for smooth and non-smooth integrands (PDF)
• slide 13: Romberg extrapolation of the composite trapezoidal rule (PDF)
• slide 13a: a proof of the Euler McLaurin formula (PDF)
• slide 14: composite trapezoidal on adapted meshes (PDF)
• slide 15: adaptive quadrature based on the trapezoidal rule (PDF)
• slide 15a: an example of polynomial division (Euclidean algorithm) (PDF)
• slide 16: Gaussian quadrature: smooth and non-smooth integrands, composite Gaussian quadrature (PDF)
• slide 17: trapezoidal rule for periodic integrands (PDF)
• slide 18: floating point numbers (PDF)
• slide 19: conditioning and stability (PDF)
• slide 19a: norms (PDF)
• slide 20: an example of an unstable algorithm (PDF)
• slide 21: cancellation when subtrating two numbers of similar size (PDF)
• slide 22: examples of cancellation and hidden cancellation (PDF)
• slide 23: Gaussian elimination (PDF)
• slide 24: Gaussian elimination: algorithms (PDF)
• slide 25: LU-factorization of banded matrices (PDF)
• slide 26: LU-factorization of skyline matrices (PDF)
• slide 27: Gaussian elimination with (partial) pivoting (PDF)
• slide 28: introduction to Least Squares Methods (PDF)
• slide 29: Wilkinson example: solving a linear system with LU-factorization fails whereas using QR-factorization works (PDF)
• slide 30: economy size SVD/data compression (PDF)
• slide 31: fixed point iteration to find zeros of functions (PDF)
• slide 32: Newton's method in 1D, damped Newton's method (PDF)
• slide 32a: example of Broyden's method (PDF)
• slide 33: power method, inverse iteration, Rayleigh quotient iteration (PDF)
• slide 34: remarks on error estimates for eigenvalues/termination conditions (PDF)
• slide 35: example of orthogonal iteration (PDF)
• slide 35a: example QR method with and without shift (PDF)
• slide 36: CG (PDF)
• slide 37a: example of GMRES (PDF)
• slide 37: why implicit methods may be better than explicit methods (simple example) (PDF)
• slide 38: why implicit methods my be better than explicit methods (still a simple example) (PDF)
• slide 39: why implicit methods may be better than explicit methods (an example of a chemical reaction) (PDF)
• slide 40: why implicit methods may be better than explicit methods (van der Pol equation) (PDF)
• slide 41: stability regions of some RK methods (PDF)

Exercise sheets

Code snippets

• gauleg.m produces Gauss points and weights for quadrature on (-1,1)
• my_cg.m the classical CG-method

Content

• 5.10.21: Chap. 1.1-1.2: introduction to polynomial interpolation: existence and uniqueness
• 6.10.21 (CSE): Chap. 1.3: Horner scheme
• 12.10.21: Chap. 1.4 (Neville scheme), Chap. 1.5 (a simple error estimate for polynomial interpolation) and application to extrapolation of one-sided difference quotients
• 13.10.21 (CSE): Chap. 1.8 (splines)
• 19.10.21: Chap. 1.6 (extrapolation of functions with special structure), Chap. 1.7 (Chebyshev interpolation), Chap 2.0 (introduction to numerical integration)
• 20.10.21 (CSE): Chap. 1.10.1 (trigonometric interpolation)
• 26.10.21 (postponed to 27.10.21): Chap. 2.1 (Newton Cotes formulas, convergence results for trapezoidal and Simpson rules, Romberg extrapolation)
• 27.10.21: Chap. 1.10.2 (FFT)
• 2.11.21 (postponed to 3.11.21): Chap. 2.3 (an adaptive quadrature algorithm), Chap 2.4 (Legendre polynomials and a glance at Gaussian quadrature)
• 3.11.21 (CSE): Chap. 1.10.3+1.10.4 (applications of FFT like fast multiplication of large numbers)
• 9.11.21: Chap. 2.5 (comments on trapezoidal rule), 2.6 (quadrature in 2D), Chap. 3 (conditioning and stability)
• 10.11.21 (CSE) Chap 2.7 (computing Gauss points and weights; Gauss-Jacobi quadrature)
• 16.11.21 Chap 4.1 (lower and upper triangular matrices), Chap 4.2 (classical Gaussian elimination), Chap 4.3 (LU-factorization via Crout),
• 17.11.21 (CSE) Chap 4.6 Householder method for QR factorization
• 23.11.21 Chap 4.4 (Gaussian elimination with pivoting), Chap 4.5 (condition number of a matrix), Chap 5.1 (least squares methods with the method of normal equations)
• 24.11.21 (CSE) Householder QR-factorization with pivoting, QR-factorization with Givens rotations
• 30.11.21 Chap 5.2 (least squares methods with QR-factorization), Chap 5.3 (SVD and its properties),
• 1.12.21 (CSE) Chap 5.3.5 (Moore-Penrose Pseudoinverse)
• 7.12.21 Chap 6.1 (Newton's method in 1d), Chap 6.2 (convergence of fixed point iterations), Chap 6.3 (Newton's method in multi-d), Chap 6.4 (implementational aspects)
• 8.12.21 (CSE) Chap 6.7.1 Broyden's method
• 14.12.21 Chap 6.5.2 (descent methods), Chap 6.5.3 globalized Newton's method, Chap 6.5.4 (Gauss-Newton method)
• 15.12.21 (CSE) Chap 6.8 (unconstrained minimization problems: gradient methods, trust region methods)
• 11.1.22 Chap 7.1 (power method), Chap 7.2 (inverse iteration, iteration with shift, Rayleigh quotient iteration), Chap 7.3 (error estimates, stopping criteria)
• 12.1.22 (CSE) Chap 7.6 (Jacobi method to compute eigenvalues)
• 18.1.22 Chap 7.4 (orthogonal iteration), chap 7.5 (basic QR algorithm)
• 19.1.22 (CSE) Chap 7.8 (QR algorithm with shift)

Literature

• current version of class notes (PDF) (will be irregularly updated during the semester)
• further literature
  • W. Dahmen, A. Reusken: Numerik für Ingenieure und Naturwissenschaftler
  • Numerical Recipes (collection of C routines for numerics). In addition to the C routines, the algorithms are also briefly "derived" and described.
  • R. Plato: Numerische Mathematik kompakt (Vieweg)