Cheatsheet 3

1 Floating Point Numbers
Normalized Form of Real Numbers

Representation: $\pm 0. d_{1} d_{2} d_{3} . . . d_{t} \times β^{p}$ where $d_{1} \neq 0$
System Parameters: $β, t, L, U$ where:
- $β$ = base
- $t$ = precision (mantissa length)
- $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$
  Error Metrics
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} |}$
Rule of Thumb: Result correct to $s$ digits if $E_{r e l} \approx 10^{- s}$
Machine Epsilon ( $E$ ): Smallest value where $f l (1 + E) > 1$
- Rounding: $E = \frac{1}{2} β^{1 - t}$
- Truncation: $E = β^{1 - t}$
  Round-off Error Analysis
  For $(a \oplus b) \oplus c$ , error bound: $$E_{rel} \leq \frac{|a|+|b|+|c|}{|a+b+c|}(2E + E^2)$$
  Catastrophic Cancellation
Occurs when subtracting numbers of similar magnitude containing errors
Critical when $| a + b + c | ≪ | a | + | b | + | c |$
Algorithm Stability
Well-conditioned problem: Small changes in input → small changes in output
Ill-conditioned problem: Small changes in input → large changes in output
Stable algorithm: Does not magnify errors in computation

2 Interpolation & Splines
Polynomial Interpolation

Unisolvence Theorem: Given $n$ distinct data points, there exists a unique polynomial of degree $\leq n - 1$ that interpolates the data
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) = \prod_{j=1,j\neq i}^n \frac{x-x_j}{x_i-x_j}$$
Hermite Interpolation
Fits polynomials given function values and derivatives
On interval $[x_{i}, x_{i + 1}]$ : $p_{i} (x) = a_{i} + b_{i} (x - x_{i}) + c_{i} (x - x_{i})^{2} + d_{i} (x - x_{i})^{3}$
Coefficients:
- $a_{i} = y_{i}$
- $b_{i} = s_{i}$
- $c_{i} = \frac{3 y_{i}^{'} - 2 s_{i} - s_{i + 1}}{Δ x_{i}}$
- $d_{i} = \frac{s_{i + 1} + s_{i} - 2 y_{i}^{'}}{Δ x_{i}^{2}}$
- Where $Δ x_{i} = x_{i + 1} - x_{i}$ and $y_{i}^{'} = \frac{y_{i + 1} - y_{i}}{Δ x_{i}}$
  Cubic Splines
Piecewise cubic polynomials with continuous first and second derivatives
Requirements: $n$ data points, $4 (n - 1)$ unknowns
Constraints:
- Interpolation: $S_{i} (x_{i}) = y_{i}$ , $S_{i} (x_{i + 1}) = y_{i + 1}$
- First derivatives match: $S_{i}^{'} (x_{i + 1}) = S_{i + 1}^{'} (x_{i + 1})$
- Second derivatives match: $S_{i}^{″} (x_{i + 1}) = S_{i + 1}^{″} (x_{i + 1})$
- Plus 2 boundary conditions
  Boundary Conditions
Clamped: Specified first derivatives at endpoints
Natural/Free: $S^{″} (x_{1}) = S^{″} (x_{n}) = 0$
Periodic: $S^{'} (x_{1}) = S^{'} (x_{n})$ , $S^{″} (x_{1}) = S^{″} (x_{n})$
Not-a-knot: Third derivatives match at second and second-to-last knots
- $S_{1}^{‴} (x_{2}) = S_{2}^{‴} (x_{2}), S_{n - 2}^{‴} (x_{n - 1}) = S_{n - 1}^{‴} (x_{n - 1})$
  Efficient Tridiagonal System
  For interior nodes $(i = 2, . . ., n - 1)$ : $$\Delta x_i s_{i-1} + 2(\Delta x_{i-1}+\Delta x_i)s_i + \Delta x_{i-1}s_{i+1} = 3(\Delta x_i y'{i-1} + \Delta xy'_i)$$
  Parametric Curves
Represent curve as $\vec{P} (t) = (x (t), y (t))$
Can handle self-intersections and vertical segments
Arc-length parameterization: $t$ represents distance along curve
Common parameterizations:
- Node index: $t_{i} = i$
- Approximate arc-length: $t_{i + 1} = t_{i} + \sqrt{(x_{i + 1} - x_{i})^{2} + (y_{i + 1} - y_{i})^{2}}$

3 Ordinary Differential Equations
Initial Value Problem

Form: $y^{'} (t) = f (t, y (t))$ with $y (t_{0}) = y_{0}$
Systems of ODEs: Multiple interacting variables (vector form)
Higher-Order ODEs: Involve derivatives of order > 1
- Convert to first-order system by substitution: $y_{i} = y^{(i - 1)}$
  Time-Stepping Methods
Local Truncation Error (LTE): Error in a single step
Global Error: Total accumulated error (typically one order less than LTE)
Forward Euler (Explicit, Single-step)
$y_{n + 1} = y_{n} + h f (t_{n}, y_{n})$
LTE: $O (h^{2})$
Conditionally stable: $0 < h < \frac{2}{λ}$
Backward Euler (Implicit, Single-step)
$y_{n + 1} = y_{n} + h f (t_{n + 1}, y_{n + 1})$
LTE: $O (h^{2})$
Unconditionally stable
Improved/Modified Euler (Explicit, Single-step)
$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: $h < \frac{2}{λ}$
Trapezoidal Rule (Implicit, Single-step)
$y_{n + 1} = y_{n} + \frac{h}{2} [f (t_{n + 1}, y_{n + 1}) + f (t_{n}, y_{n})]$
LTE: $O (h^{3})$
Midpoint Method (Explicit, Single-step)
$y_{n + \frac{1}{2}}^{*} = y_{n} + \frac{h}{2} f (t_{n}, y_{n})$
$y_{n + 1} = y_{n} + h f (t_{n} + \frac{h}{2}, y_{n + \frac{1}{2}}^{*})$
LTE: $O (h^{3})$
4th Order Runge-Kutta (Explicit, Single-step)
$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})$

Multi-step Methods
BDF (Implicit, Multi-step)

BDF1 = Backward Euler
BDF2: $y_{n + 1} = \frac{4}{3} y_{n} - \frac{1}{3} y_{n - 1} + \frac{2}{3} h f (t_{n + 1}, y_{n + 1})$
LTE: $O (h^{3})$
Adams-Bashforth (Explicit, Multi-step)
2nd order: $y_{n + 1} = y_{n} + \frac{3}{2} h f (t_{n}, y_{n}) - \frac{1}{2} h f (t_{n - 1}, y_{n - 1})$
LTE: $O (h^{3})$
Adaptive Time-Stepping

Run methods of order $p$ and $p + 1$
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{α \cdot t o l}{| y_{n + 1}^{A} - y_{n + 1}^{B} |})^{1 / p}$