creativity \(\equiv\) Extrapolation \(\oplus\) analytic continuation
Story:
There are only three fundamental problems to be solved in this class:
- Decoupled Non-Linear Equation: \(g(x^*)=x^*\) – fixed-point iteration
- System of Linear Equations: \(Ax=b\) – Ax=b
- 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:
- 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.
- 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.
- 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:
- Method of Undetermined Coefficients
- Quadrature
- Interpolation
- Stability Diagrams for Integrators
- Richardson Extrapolation
- Norm and Condition Number
Topics:
- Floating Point Number System
- Truncation and Rounding Error
- Norm and Condition Number
- Factorization: LU, Cholesky (LL), QR, SVD
- Transformation: Householder Reflection, Givens Rotation
- Iterative Methods:
- Power Iteration
- Inverse and Rayleigh-Ritz Power Iteration
- Jacobi and QR Iteration
- Arnoldi and Lanczos Iteration
- Convergence Rate of Iterative Methods
- Non-linear Solvers (Roots of function):
- Bracket and Golden Section
- Fixed-Point Iteration, Newton and Broyden
- Optimizers (Roots of gradient):
- Successive Parabolic Approx. (Golden Section++)
- Newton and BFGS (Broyden++)
- Direct Search, Steepest Decent and Conjugate Gradient
- Non-linear Least Squares
- Linear Programming
- Interpolation
- Polynomial: Monomial, Lagrange and Newton basis
- Piecewise: Hermite Cubic, Cubic Spline and Basis Spline
- Integration
- Newton-Cotes Quadrature Rules
- Method of Undetermined Coefficients
- Gaussian Quadrature Rule
- Error Estimation
- Richardson Extrapolation
- Differentiation
- Richardson Extrapolation
- Differential Equations
- Ordinary Differential Equations (ODE)
- Finite Difference
- Integrators
- Forward Euler and Runge-Kutta
- Backward Euler and Backward Differential Formula (BDF)
Other Useful Stuff:
- Projection
- Sherman-Morrison Rank-One Update
- Gram-Schmidt Orthogonalization
- Normal Equation (and relation to SVD)
Gotchas:
- Rank deficiency
- Python