§ 0. Introduction

• Example 1: Integral Recursion

§ 1. Error Analysis

1.1 Number Representation: Floating-Point and Roundoff

• Definition 1: Floating Point
• Example 1: Normalised Floats - decimal
• Example 2: Normalised Floats - dual
• Definition 2: Machine Numbers
• IEEE-Standard 754
• Example 3: Short real
• Rounding
• Definition 3: Round to nearest
• Definition 4: Machine precision
• Example 0.1 revisited
• Floating point operations

1.2 Roundoff Error Analysis

• Forward vs. Backward Analysis
• Definition 5: Backward Analysis
• Example 4: Backward Analysis for ..
• Horner-Scheme
• Algorithm 1: Horner-Scheme

1.3 Error propagation and condition

• Definition 6: Condition numbers
• Example 5:
• Condition plus roundoff error
• Error in Algorithm
• Definition 7: Acceptable result
• Definition 8: Well behaved / Numerically stable algorithm

§ 2. Vectors and Matrices

2.1 Notations

2.2 Determinant, Inverse, Eigenvalues

2.3 Special matrices

• Definition 1: symmetric/hermitian matrix
• Definition 2: orthogonal/unitary matrix
• Definition 3: positive (semi)definite matrix

2.4 Norms

• Definition 4: (vector) norm
• Definition 5: matrix norm
• Definition 6: subordinate matrix norm lub
• Definition 7: spectral radius
• Definition 8: condition of a matrix

2.5 Elementary matrices

• Scaling
• Transposition
• Permutation
• Row/column operations

2.6 BLAS Package

§ 3. Direct Methods for Linear Systems

3.1 Gaussian Elimination and LU-Decomposition

• Algorithm 1: Forward Substitution
• Algorithm 2: Backward Substitution
• Algorithm 3: Gaussian Elimination without pivoting
• Example 1:
• Theorem 1: LU-Decomposition
• Algorithm 4: LU-Decomposition
• Complexity
• Pivoting
• Example 2:
• Theorem 2:
• Cholesky-Decomposition
• Theorem 3:
• Algorithm 5: Cholesky-Decomposition

3.2 Condition and Roundoff Error

• Residual
• Roundoff errors in decompositions

3.3 Linear Least Squares

• Problem description
• Example 3: Radio-active decay
• Normal Equations
• Theorem 4:
• Condition of the least squares problem
• Computation
• Example 4:
• Householder Transformation and QR-Decomposition
• Theorem 5: Householder transformation

§ 4. Iterative Methods for Linear Systems

4.1 Illustrative Example

• Example: Poisson problem on unit square

4.2 Classical iterative methods

• Properties of iteration matrix
• Theorem 1: Convergence of classical methods
• Theorem 2: Speed of convergence
• Jacobi method
• Definition 1: strong row/column sum criterion
• Gauss-Seidel method
• Relaxation methods
• under/over-relaxation
• successive overrelaxation (SOR) method
• Application to illustrative example
• Iterative refinement

4.3 Conjugate gradient (CG) method

• Krylov space
• Krylov-subspace methods
• energy norm
• A-orthogonal basis
• Theorem 3: basis of CG method
• method of conjugate directions
• Algorithm 1: Conjugate gradient method
• Interpretation via optimization
• preconditioning
• incomplete Cholesky decomposition

4.4 GMRES method

• method of generalised minimal residuals

§ 5. Methods for Nonlinear Systems

5.1 Newton's method

• The Univariate Case
• Algorithm 1: Bisection
• Algorithm 2: Newton's method
• Definition 1: local and global convergence
• Definition 2: convergence of order p
• The Multivariate Case
• Algorithm 3: Newton-Raphson method
• Theorem 1: Convergence of multivariate Newton method
• Theorem 2 (newton-Kantorovich):

5.2 Simplified Newton method

• Theorem 3: Convergence of simplified multivariate Newton method
• Broyden's rank one method

5.3 Modified Newton method

• Algorithm 4: modified Newton method
• Theorem 4: Convergence of modified multivariate Newton method
• natural scaling

5.4 Gauss-Newton scheme

• Algorithm 5: Gauss-Newton method
• Theorem 5: Convergence of multivariate Gauss-Newton method