## Roundoff Error Floating-point numbers are stored as $x = m b^e$ where $b$ is the base (usually 2), and $b^{-1} \leq m < 1$. This leads to roundoff error due to limited precision. Minimize roundoff by: - Adding small numbers before large ones. - Avoiding subtraction of nearly equal values. - Rewriting or reordering operations when possible. ## Standard Error Root-mean-square version of differential error (assumes independent errors): $E(\Delta_s y) = \sqrt{ \sum_{i=1}^{n} \left( \frac{\partial f}{\partial x_i} \right)^2 \varepsilon_i^2 }$ Gives a typical error size instead of a worst-case bound ## Differential Error Estimates worst-case error propagation in a function $y = f(x_1, \dots, x_n)$: $\varepsilon_y \leq \sum_{i=1}^{n} \left| \frac{\partial f}{\partial x_i} \right| \varepsilon_i$ Used when each input has a known uncertainty $\varepsilon_i$. ## Condition Number Measures **sensitivity** of a function to input error. For $f(x)$: $K_p = \left| \frac{\bar{x} f'(\bar{x})}{f(\bar{x})} \right|$ - $K_p \approx 1$: well-conditioned - $K_p \gg 1$: ill-conditioned (small input error $\Rightarrow$ big output error) Used to assess whether a problem is **numerically stable** or inherently sensitive. ## Truncation Error The part of the Taylor series you **cut off** when forming an approximation. Operator $\mathcal{L}$ Truncation error ${} \tau_{\Delta x} {}$ $\tau_{\Delta x}=\lvert \mathcal{L}(\theta)-\hat{\mathcal{L}}(\theta)\rvert$ ### Consistency $\tau_{\Delta x} \to 0$ as $\Delta x \to 0$ ### Order of Accuracy $\tau_{\Delta x} = O(\Delta x^{p})$ $p=$ order of accuracy ## Discretization Error $\theta = \hat{\theta}_{T}\varepsilon$ ## Stability $\varepsilon = -\hat{\mathcal{L}}^{-1}(\tau)$ Stability: $||\hat{\mathcal{L}}^{-1}|| < \text{const}$ ### Lax-Equivalence Theorem $\lvert \varepsilon \rvert \leq ||\hat{\mathcal{L}}^{-1}||~||\tau||$ convergence, stability, consistency ## High-Order FD $\left( \frac{ \partial^{m}U }{ \partial x^{m} } \right)_{j}-\sum_{i=-\gamma}^{s}a_{i}U_{j+1}=\tau_{\Delta x}$ Systematic way to improve truncation error (taylor and pade tables) ## Richardson Extrapolation ### Improving Accuracy - Combine results from two grid spacings ($h$ and $h/2$) to cancel leading error. - Boosts order from $p$ to $p+1$ (or better). $\phi_{\text{rich}} = \frac{2^p \phi_{h/2} - \phi_{h}}{2^p - 1}$ where $\phi_{h}$ is a numerical approximation with step size $h$ and order of accuracy $p$ $\phi_{\text{rich}}$ has error $\mathcal{O}(h^{p+1})$ or better! ### Estimating Discretization Error If no exact solution is known, the error can be approximated as: $\text{Error} \approx \frac{\phi_{h/2} - \phi_h}{2^p - 1}$ ### Convergence Rate Compute the observed order $p$ using: $p \approx \log_2 \left( \frac{\phi_h - \phi_{h/2}}{\phi_{h/2} - \phi_{h/4}} \right)$ ## Fourier Error Analysis We can decompose any function and its error into their fourier modes: $f(x,t) = \sum_{k=-\infty}^{\infty} f_{k}(t)e^{ikx}$ $\epsilon(x,t) = \sum_{\beta=-\infty}^{\infty} \epsilon_{\beta}(t)e^{i\beta x}$ **Angular Wavenumber** $k$ is defined as radians per unit distance (spatial frequency): $k = \frac{2\pi}{\lambda}$ **Wave Speed** $c$ is the speed that the wave travels They are related by $c = \frac{\omega}{k}$ Define $c_\text{eff}$ as $k_\text{eff}c = kc_\text{eff}$ then we have $c_\text{eff} = c\frac{k_\text{eff}}{k}$ $\frac{df_{k}(t)}{dt} = -(ik)^{n} f_{k}(t)$ | Spatial Derivative | Effect on PDE | | ------------------ | ------------- | | $n=1$ | Propagation | | ${} n=2 {}$ | Diffusion | | $n=3$ | Dispersion | | Dispersion | Diffusion (Dissipation) | | -------------------------- | ------------------------------ | | Wrong phase speed | Decreasing amplitude | | Distorted wave shape | Smoothed/damped solution | | Centered differences | Upwind, implicit methods | | $\arg(G(\beta)) \ne$ exact | $G(\beta)< 1$ for some $\beta$ | | ${} c = f(k) {}$ | $k_{eff} < k$ | ## Von Neuman Stability A scheme must be stable if error amplitude modes always decays with time Von Nueman only works if we have: - periodic boundary conditions - linear PDEs Using fourier decomposition, we have $\epsilon^{n}_j=\xi^{n}e^{i\beta j\Delta x}$ $\xi =e^{\gamma\Delta t}$ is the amplification factor Von Neuman requires that $\lvert \xi \rvert<1$ Ex. $\frac{ \partial \phi }{ \partial t }+c\frac{ \partial \phi }{ \partial x }=0$ 1. Derive the FD scheme: $\phi^{n+1}_{j}=\left( 1-\mu \right)\phi^{n}_{j}+\mu\phi^{n}_{j-1}$, $\mu = \frac{c\Delta t}{x}$ 2. Insert the mode: $\xi^{n+1}e^{i\beta\,j\Delta x}=(1-\mu)\,\xi^{n}e^{i\beta\,j\Delta x}+\mu\,\xi^{n}e^{i\beta\,(j-1)\Delta x}$ 3. Cancel $e^{n}_{j}$ from both sides: $\xi =(1-\mu)+\mu e^{-i\beta\Delta x}$ 4. Solve for the magnitude using complex conjugates: $\left|\xi\right|^{2}=\Bigl((1-\mu)+\mu\,e^{-i\,\beta\,\Delta x}\Bigr)\Bigl((1-\mu)+\mu\,e^{i\,\beta\,\Delta x}\Bigr)=\left|1-4\mu(1-\mu)\sin^{2}(\frac{\beta\,\Delta x}{2})\right|\leq1$ ## CFL Condition The numerical domain of dependence of FD scheme must include the mathematical domain of dependence of the PDE. In other words, the scheme will be unstable if a wave can travel further than $\Delta x$ in a single timestep. For a 2nd order centered difference stencil, we have the condition: $\frac{c\Delta t}{\Delta x} \leq 1$ - The constant on the right corresponds to the stencil slope - larger stencils have looser CFL conditions - CFL is a necessary condition for stability but not sufficient - you can meet CFL but not be stable ![[Pasted image 20250412082642.png]]