Cheatsheet 2

Floating Point Numbers

Normalized Form: $\pm 0. d_{1} d_{2} . . . d_{t} \times β^{p}$ where $L \leq p \leq U$ , $d_{1} \neq 0$
Parameters: $β, t, L, U$ where $β$ = base, $t$ = mantissa, $L$ & $U$ = exponent bounds
IEEE Standards:
- Single Precision (32 bits): $β = 2, t = 24, L = - 126, U = 127$
- Double Precision (64 bits): $β = 2, t = 53, L = - 1022, U = 1023$
Errors:
- Absolute Error: $E_{a b s} = | x_{e x a c t} - x_{a p p r o x} |$
- Relative Error: $E_{r e l} = \frac{| x_{e x a c t} - x_{a p p r o x} |}{| x_{e x a c t} |}$
- $s$ significant digits if $0.5 \times 10^{- s} \leq E_{r e l} \leq 5 \times 10^{- s}$
Machine Epsilon ( $E$ ): Smallest value where $f l (1 + E) > 1$
- Rounding: $E = \frac{1}{2} β^{1 - t}$
- Truncation: $E = β^{1 - t}$
Arithmetic Operations: $f l (x \circ y) = (x \circ y) (1 + δ)$ where $| δ | \leq E$
Cancellation Errors: Occur when subtracting similar magnitude numbers

Interpolation: Given points $(x_{i}, y_{i})$ , estimate $p (x)$ where $x_{1} \leq x \leq x_{n}$
Unique Polynomial: Degree $\leq n - 1$ for $n$ distinct points
Monomial Form: $p (x) = \sum_{i = 1}^{n} c_{i} x^{i - 1}$
Lagrange Form: $p (x) = \sum_{i = 1}^{n} y_{i} L_{i} (x)$ where $L_{i} (x_{j}) = δ_{i j}$
- $L_{i} (x) = \frac{(x - x_{1}) . . . (x - x_{i - 1}) (x - x_{i + 1}) . . . (x - x_{n})}{(x_{i} - x_{1}) . . . (x_{i} - x_{i - 1}) (x_{i} - x_{i + 1}) . . . (x_{i} - x_{n})}$
Cubic Splines: Piecewise cubic polynomials with C² continuity
- $4 (n - 1)$ unknowns, $4 n - 6$ equations + 2 boundary conditions
- Boundary Conditions: Clamped ( $S^{'} (x_{1})$ , $S^{'} (x_{n})$ specified), Natural ( $S^{″} (x_{1}) = S^{″} (x_{n}) = 0$ ), Periodic, Not-a-knot ( $S_{1}^{‴} (x_{2}) = S_{2}^{‴} (x_{2}), S_{n - 2}^{‴} (x_{n - 1}) = S_{n - 1}^{‴} (x_{n - 1})$ )
Parametric Curves: $\vec{P} (t) = (x (t), y (t))$ for more general curves

First-Order ODE: $y^{'} (t) = f (t, y (t))$ , $y (t_{0}) = y_{0}$
Time-Stepping Methods:
- Forward Euler (explicit): $y_{n + 1} = y_{n} + h f (t_{n}, y_{n})$
  - LTE: $O (h^{2})$ , conditionally stable if $0 < h < \frac{2}{λ}$
- Backward Euler (implicit): $y_{n + 1} = y_{n} + h f (t_{n + 1}, y_{n + 1})$
  - LTE: $O (h^{2})$ , unconditionally stable
- Trapezoidal Rule (implicit): $y_{n + 1} = y_{n} + \frac{h}{2} [f (t_{n}, y_{n}) + f (t_{n + 1}, y_{n + 1})]$
  - LTE: $O (h^{3})$
- Improved Euler (explicit):
  - $y_{n + 1}^{*} = y_{n} + h f (t_{n}, y_{n})$
  - $y_{n + 1} = y_{n} + \frac{h}{2} [f (t_{n}, y_{n}) + f (t_{n + 1}, y_{n + 1}^{*})]$
  - LTE: $O (h^{3})$ , conditionally stable if $h < \frac{2}{λ}$
- RK4 (explicit):
  - $k_{1} = h f (t_{n}, y_{n})$
  - $k_{2} = h f (t_{n} + \frac{h}{2}, y_{n} + \frac{k_{1}}{2})$
  - $k_{3} = h f (t_{n} + \frac{h}{2}, y_{n} + \frac{k_{2}}{2})$
  - $k_{4} = h f (t_{n} + h, y_{n} + k_{3})$
  - $y_{n + 1} = y_{n} + \frac{1}{6} (k_{1} + 2 k_{2} + 2 k_{3} + k_{4})$
  - LTE: $O (h^{5})$
Local vs Global Error:
- Local Truncation Error (LTE): Error in one step
- Global Error ≈ Local Error × Number of steps = $O (h^{p - 1})$ where $p$ is LTE order
Adaptive Time-Stepping:
- Run two methods of different orders
- Estimate error: $e r r = | y_{n + 1}^{A} - y_{n + 1}^{B} |$
- Adjust step size: $h_{n e w} = h_{o l d} (\frac{t o l}{| y_{n + 1}^{A} - y_{n + 1}^{B} |})^{1 / p}$