### 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