CSE 401 Numerical Analysis

creativity \(\equiv\) Extrapolation \(\oplus\) analytic continuation

 

Story:

There are only three fundamental problems to be solved in this class:

  1. Decoupled Non-Linear Equation: \(g(x^*)=x^*\) – fixed-point iteration
  2. System of Linear Equations: \(Ax=b\) – Ax=b
  3. Differential Equation: \(y’= \lambda y\) – exponential growth

We only solve a non-linear problem directly about 5% of the time. 80% of the time we will be solving linear systems, so there is also a big portion devoted to a bag of tricks in linear algebra. 15% of the time we will be converting non-linear problems to linear problems with the following recipe:

  1. A problem is either linear or non-linear. If the problem can be formulated as a single non-linear equation, then variants of the fixed-point iteration method can be used.
  2. If coupled non-linear equations are present, we need to convert the system of non-linear equations to a system of linear equations. The conversion is achieved by using a basis set and expressing non-linear terms as linear combination of the basis elements.
  3. If a problem is linear, then it can be expressed as a system of linear equations \(Ax=b\), which can be diagonalized to be a set of de-coupled equations, each of algebraic form or \(y’=\lambda y\) form.

Goodies:

  1. Method of Undetermined Coefficients
    1. Quadrature
    2. Interpolation
  2. Stability Diagrams for Integrators
  3. Richardson Extrapolation
  4. Norm and Condition Number

Topics:

  1. Floating Point Number System
  2. Truncation and Rounding Error
  3. Norm and Condition Number
  4. Factorization: LU, Cholesky (LL), QR, SVD
  5. Transformation: Householder Reflection, Givens Rotation
  6. Iterative Methods:
    1. Power Iteration
    2. Inverse and Rayleigh-Ritz Power Iteration
    3. Jacobi and QR Iteration
    4. Arnoldi and Lanczos Iteration
  7. Convergence Rate of Iterative Methods
  8. Non-linear Solvers (Roots of function):
    1. Bracket and Golden Section
    2. Fixed-Point Iteration, Newton and Broyden
  9. Optimizers (Roots of gradient):
    1. Successive Parabolic Approx. (Golden Section++)
    2. Newton and BFGS (Broyden++)
    3. Direct Search, Steepest Decent and Conjugate Gradient
    4. Non-linear Least Squares
    5. Linear Programming
  10. Interpolation
    1. Polynomial: Monomial, Lagrange and Newton basis
    2. Piecewise: Hermite Cubic, Cubic Spline and Basis Spline
  11. Integration
    1. Newton-Cotes Quadrature Rules
    2. Method of Undetermined Coefficients
    3. Gaussian Quadrature Rule
    4. Error Estimation
    5. Richardson Extrapolation
  12. Differentiation
    1. Richardson Extrapolation
  13. Differential Equations
    1. Ordinary Differential Equations (ODE)
    2. Finite Difference
    3. Integrators
      1. Forward Euler and Runge-Kutta
      2. Backward Euler and Backward Differential Formula (BDF)

Other Useful Stuff:

  1. Projection
  2. Sherman-Morrison Rank-One Update
  3. Gram-Schmidt Orthogonalization
  4. Normal Equation (and relation to SVD)

Gotchas:

  1. Rank deficiency
  2. Python