Numerical Analysis¶
Job: analyze algorithms that approximate continuous mathematical objects by finite computation — stability, consistency, convergence, complexity, and conditioning.
Core¶
Numerical analysis separates problem sensitivity (conditioning) from algorithm reliability (stability), then quantifies discretization error for ODEs, PDEs, integrals, and algebraic systems. Research statements always name norms, grids, and floating-point models.
| Layer | Content |
|---|---|
| Error calculus | forward / backward error; \(\kappa\); floating-point model |
| Approximation | interpolation, quadrature, best approx; Lebesgue constants |
| Linear algebra | dense/sparse solvers; Krylov; preconditioning |
| ODE IVPs | one-step/multistep; absolute stability; stiffness |
| Spectral methods | global bases; spectral accuracy; aliasing |
| PDE discretizations | FD / FEM / FV; CFL; Céa; conservation |
Reading map¶
| Page | Focus |
|---|---|
| Foundations | conditioning vs stability; Lax; spectral methods; ODE/PDE pointers; Newton/Krylov |
| FEM & Variational | Galerkin/Céa, a priori/a posteriori, adaptivity, mixed/Stokes |
| Geometric Integration | symplectic Stormer–Verlet, variational, KAM/backward error |
| Iterative & Multigrid | CG/GMRES, multigrid V-cycle, Schwarz/FETI, FFT/butterfly |
| High-Dimensional & UQ | curse, sparse grids Smolyak, QMC/Koksma–Hlawka, gPC/UQ |
Dependency order¶
- Linear algebra + real analysis (norms, Lipschitz, compactness)
- Foundations — error, stability, basic discretizations
- Fourier analysis for spectral / FFT methods
- PDE + optimization for specialized layers
- Implementation: IEEE-754, BLAS/LAPACK contracts (engineering, not pure math)
Where it appears¶
- PDE: well-posedness \(\leftrightarrow\) discrete energy estimates
- Optimization: gradient / Newton / proximal rates
- Fourier analysis: FFT, spectral differentiation
- Linear algebra: \(\kappa(A)\), iterative methods
- Scientific computing / ML training: same stability vocabulary
Signature themes¶
| Principle | Statement |
|---|---|
| Conditioning vs stability | problem sensitivity \(\neq\) algorithm backward-error quality |
| Lax equivalence | consistent + stable \(\Leftrightarrow\) convergent (linear well-posed IVP schemes) |
| Spectral accuracy | analytic data \(\Rightarrow\) exponential coeff decay (Fourier/Chebyshev) |
| Dahlquist barriers | order vs \(A\)-stability tradeoffs for multistep methods |
| Céa lemma | FEM error \(\le C\times\) best-approx error (coercive elliptic) |
See it¶
Hilbert matrix \(H_{ij}=1/(i+j-1)\). \(\kappa_2(H_n)\) grows roughly like \(e^{cn}\). A perfectly backward-stable solver in double precision can return a solution with zero correct digits for moderate \(n\) — diagnose the problem, not the vendor LAPACK.
Check¶
State Lax equivalence carefully.
For a consistent approximation to a well-posed linear evolution (discrete semigroup setting), stability in the appropriate norms is equivalent to convergence. Nonlinear or ill-posed continuous problems need separate theories.
Why is equispaced high-degree polynomial interpolation unstable (Runge)?
Lebesgue constant \(\|\mathcal{L}_n\|_\infty\) grows exponentially on equispaced nodes; Chebyshev nodes give \(O(\log n)\). Stability of the map data \(\to\) interpolant is node-dependent.
Pitfalls¶
- Subtractive cancellation destroys digits even when the expression is mathematically continuous.
- Stiffness: absolute stability region, not just local truncation order, dominates step size.
- Gibbs / spectral pollution on discontinuous data: need filtering, \(hp\)-adaptivity, or shock capturing.
- Preconditioning is problem-dependent art; unpreconditioned Krylov can stagnate.
Refs¶
Trefethen–Bau; Higham, Accuracy and Stability; Hairer–Nørsett–Wanner; Trefethen, Spectral Methods in MATLAB; Brenner–Scott (FEM); Quarteroni–Sacco–Saleri.
Next¶
Foundations · Optimization · PDE · Fourier analysis · Linear algebra · FEM & Variational · Geometric Integration · Iterative & Multigrid · High-Dimensional & UQ