Numerical Analysis — Foundations¶
Job: Quantify rounding and discretization error; separate problem conditioning from algorithmic stability; outline spectral, finite-difference, and iterative paradigms.
Core¶
Error, conditioning, floating point¶
Forward error \(\|\hat y-y\|\); backward error: smallest \(\delta A,\delta b\) such that \(\hat y\) solves a perturbed problem exactly. Condition number of a problem: sensitivity of output to input perturbations. For square linear systems, \(\kappa(A)=\|A\|\|A^{-1}\|\); relative residual small + \(\kappa\) large \(\Rightarrow\) large forward error possible.
Floating point: fl\((x\ \mathrm{op}\ y)=(x\ \mathrm{op}\ y)(1+\varepsilon)\), \(|\varepsilon|\le u\) (unit roundoff), barring overflow/underflow. Backward stability: algorithm produces the exact solution of a nearby problem (Higham/Wilkinson). IEEE-754 double: \(u\approx 2^{-53}\).
| Concept | Object |
|---|---|
| Conditioning | intrinsic to the problem |
| Stability | property of the algorithm |
| Consistency | discrete operator \(\to\) continuous as \(h\to0\) |
| Convergence | discrete solution \(\to\) true solution |
Approximation theory¶
Interpolant vs best approximation; Lebesgue constant for nodes: equispaced \(\|\mathcal{L}_n\|_\infty\sim 2^n/(n\log n)\); Chebyshev \(O(\log n)\). Quadrature: Gaussian \(n\)-point exact for deg \(\le 2n-1\); Clenshaw–Curtis; sparse grids / QMC in high \(D\). Weierstrass: polynomials dense in \(C[a,b]\); rates from smoothness (Jackson theorems).
ODE IVPs¶
One-step \(y_{n+1}=y_n+h\Phi(t_n,y_n,h)\). Consistency: \(\Phi\to f\) as \(h\to0\). 0-stability + consistency \(\Rightarrow\) convergence (Dahlquist). Absolute stability regions constrain stiff problems; \(A\)-stability (implicit trapezoid, many IRK). Lipschitz stiffness \(\Rightarrow\) need implicit or exponential integrators. Multistep: Dahlquist barriers (order vs \(A\)-stability). Geometric integration: symplectic methods for Hamiltonian systems preserve structure (pointer).
Spectral methods¶
Expand \(u\approx\sum_{k=0}^N\hat u_k\phi_k\) (Fourier on periodic; Chebyshev/Legendre on intervals). Galerkin / collocation: residual orthogonal to test space. For analytic periodic \(u\), Fourier coefficients decay exponentially \(\Rightarrow\) spectral accuracy. Differentiation matrices dense; use FFT for Fourier. Alias / quadrature consistency (exactness for products up to degree \(N\)) required for discrete conservation. Gibbs on jumps: fix height overshoot; filter or \(hp\)-adapt.
PDE discretizations¶
| Method | Structure |
|---|---|
| Finite differences | stencil truncation \(O(h^p)\); easy on grids |
| Finite elements | weak form; Céa: \(\|u-u_h\|\le C\inf_{v\in V_h}\|u-v\|\) |
| Finite volumes | flux conservation; natural for conservation laws |
| Spectral / SEM | global or high-order elements |
CFL for hyperbolic explicit schemes: \(c\Delta t/\Delta x\le\mathrm{const}\). Energy estimates should mirror continuous well-posedness (Lax–Richtmyer philosophy).
Linear and nonlinear algebra¶
Krylov: CG for SPD (rate via \(\kappa_2\)); GMRES/MINRES for nonsymmetric/indefinite; preconditioning is the art. Multigrid: optimal \(O(N)\) for elliptic model problems under hyp.
Newton: local quadratic under nonsingular Jacobian + Lipschitz \(DJ\); globalization by line search / trust region. Inexact Newton: Krylov force tolerance linked to residual for superlinear rates.
Matrix factorizations: QR (Householder) backward stable for least squares; LU with partial pivoting usually stable in practice (Wilkinson), not always in theory; Cholesky for SPD.
Complexity one-liners¶
Dense \(n\times n\) Gaussian elimination \(\sim\frac23 n^3\) flops; FFT \(O(N\log N)\); sparse direct fill-in depends on ordering (nested dissection \(O(n^{3/2})\) in 2D mesh model).
See it¶
Hilbert matrix \(H_{ij}=1/(i+j-1)\): \(\kappa_2(H_n)\) grows exponentially in \(n\). Even a backward-stable solver can yield no correct digits for moderate \(n\) in double precision — the problem is ill-conditioned, not necessarily the algorithm.
Stiff ODE: Robertson chemical kinetics — explicit RK needs tiny steps; \(A\)-stable implicit methods take steps set by accuracy, not the fastest timescale.
Check¶
State Lax equivalence for linear well-posed IVPs.
For a consistent finite-difference (or discrete semigroup) approximation to a well-posed linear evolution, stability \(\Leftrightarrow\) convergence in the appropriate norms.
Why do equispaced polynomial interpolants of high degree fail (Runge)?
Lebesgue constant \(\|\mathcal{L}_n\|_\infty\sim 2^n/(n\log n)\) on equispaced nodes \(\Rightarrow\) small perturbations / Runge function oscillations. Chebyshev nodes: \(\|\mathcal{L}_n\|_\infty=O(\log n)\).
What does backward stability of QR least-squares guarantee?
Computed \(\hat x\) is the exact least-squares solution of a nearby \((A+\delta A,b+\delta b)\) with \(\|\delta A\|/\|A\|,\|\delta b\|/\|b\|\) on the order of \(u\) times modest dimension factors — forward error then scales with \(\kappa\) of the least-squares problem.
Pitfalls¶
- Cancelling subtractive cancellation destroys digits even if the expression is mathematically stable.
- “Spectral method” on discontinuous data yields Gibbs; need filtering / \(hp\)-adaptivity / shock capturing.
- Stability regions of multistep methods limited by Dahlquist barriers.
- Confusing absolute stability (stiff) with 0-stability (convergence as \(h\to0\) at fixed \(t\)).
- FEM assembly vs solver: optimal complexity needs multigrid/domain decomposition, not only sparse matrices.
Refs¶
Trefethen–Bau; Higham, Accuracy and Stability of Numerical Algorithms; Hairer–Nørsett–Wanner; Trefethen, Spectral Methods in MATLAB; Brenner–Scott (FEM); Golub–Van Loan.
Next¶
Index · PDE · Fourier analysis · Optimization · Linear algebra · ML mathematics — approximation theory as a numerical-analysis / function-approximation frontier · FEM & Variational · Geometric Integration · Iterative & Multigrid · High-Dimensional & UQ