Algorithms for approximating mathematical operations on a finite machine: floating-point arithmetic, conditioning, root-finding, linear-system solvers, ODE/PDE discretization, spectral methods. Bridges pure math to computational practice…
numerical-analysis
Floating-point arithmetic
IEEE 754 standard: numbers represented as ±(1.f)₂ × 2^e, with finite precision (typ. 53 bits). Introduces round-off error on every…
Condition number
Sensitivity of a problem's output to small input perturbations. For linear systems Ax=b, κ(A) = ||A||·||A⁻¹||; ill-conditioned problems…
Newton's method
Iteration x_{n+1} = x_n − f(x_n)/f'(x_n) finds roots of differentiable f with quadratic convergence near a simple root. Generalizes to…
Gaussian elimination
Row-reduction algorithm solving Ax = b in O(n³) ops. With partial pivoting, numerically stable for well-conditioned A. Produces LU…
Runge-Kutta methods
Single-step ODE integrators that combine multiple slope evaluations per step. Classical RK4 achieves O(h⁴) global error; standard workhorse…
Fast Fourier transform (FFT)
Cooley-Tukey divide-and-conquer algorithm computing the discrete Fourier transform in O(N log N) instead of O(N²). Single most widely used…
Finite-difference methods
Approximate derivatives as differences: f'(x) ≈ (f(x+h) − f(x))/h. Discretize PDEs on a grid to produce large sparse linear systems.…
Numerical quadrature
Approximate ∫f dx by a weighted sum of samples Σ w_i f(x_i). Newton-Cotes (trapezoidal, Simpson), Gauss-Legendre, adaptive quadrature.…
Bisection method
Root-finding via repeated interval halving on a sign change, exploiting the intermediate value theorem. Linear convergence (one bit per…
Lagrange interpolation
Unique polynomial p of degree ≤ n passing through (x_0,y_0),…,(x_n,y_n): p(x) = Σ y_i ℓ_i(x) with ℓ_i(x) = Π_{j≠i} (x−x_j)/(x_i−x_j).
Spline interpolation
Piecewise-polynomial interpolation with prescribed smoothness at knots (cubic splines: C² and second derivative continuous). Minimises…
Conjugate gradient method
Iterative solver for symmetric positive-definite systems Ax = b that exactly solves in n steps (exact arithmetic). Builds Krylov subspace…
Finite element method
Variational numerical method for PDE: weak form a(u,v) = L(v) discretised on a finite-dim subspace V_h of piecewise-polynomial functions on…
Spectral method
PDE discretisation in a basis of globally-smooth functions (Fourier, Chebyshev, Legendre). For analytic solutions, achieves exponential…
Krylov subspace method
Iterative linear solvers operating on K_k(A, b) = span{b, Ab, A²b, …, A^{k−1}b}: GMRES (non-symmetric), CG (SPD), MINRES (symmetric…
Multigrid method
Combines smoothing on a fine grid with coarse-grid correction across a hierarchy of grids. For elliptic PDE, achieves optimal O(N)…
Newton's method
x_{n+1} = x_n − f(x_n)/f'(x_n). Quadratic convergence for simple roots; basin of attraction fractal for polynomials.
Secant / bisection methods
Secant: x_{n+1} = x_n − f(x_n)(x_n−x_{n−1})/(f(x_n)−f(x_{n−1})), φ-convergence. Bisection: linear, guaranteed.
Lax equivalence theorem
For consistent linear PDE scheme: stability ⟺ convergence. Central result of PDE numerics. von Neumann stability analysis via Fourier.
Finite-difference schemes
Derivative approximations u'_i ≈ (u_{i+1}−u_i)/h etc. Consistency O(h^p), stability CFL for hyperbolic, upwind for advection.
Fast Fourier transform
Cooley-Tukey 1965: DFT in O(n log n) via divide-and-conquer. Bluestein, Rader for non-power-of-two. Convolution theorem → O(n log n)…
Gauss quadrature
n-point rule exact for polynomials of degree ≤ 2n−1; nodes = orthogonal polynomial roots. Gauss-Legendre, Gauss-Chebyshev, Gauss-Hermite.
Monte Carlo integration
∫ f dμ ≈ (1/N) Σ f(X_i), X_i ∼ μ. O(N^{−1/2}) error independent of dimension; importance sampling variance reduction.
Krylov subspace methods
Iterative linear solvers via K_m(A,b) = span{b, Ab, …, A^{m−1}b}. GMRES, CG, BiCGStab, Arnoldi, Lanczos eigensolver.
Conjugate gradient method
Solves Ax = b (SPD) minimizing ½x^T A x − b^T x. Convergence in ≤ n steps exact; O(√κ) practical. Hestenes-Stiefel 1952.
Condition number & perturbation
κ(A) = ||A|| ||A^{-1}||. Bounds relative error amplification in Ax = b. Well-conditioned vs ill-conditioned systems.
BFGS quasi-Newton
Updates approximate Hessian B_{k+1} = B_k + rank-2 correction using gradient + step. L-BFGS limited-memory for large-scale. Super-linear…
Stochastic gradient descent
θ_{k+1} = θ_k − η_k ∇ f_i(θ_k), i random. Robbins-Monro convergence; momentum, Nesterov, Adam. ML workhorse.
LU factorization
Factor a non-singular A as a lower-triangular L times upper-triangular U (after a partial-pivoting permutation P). Reduces solving Ax = b…
Cholesky decomposition
Every symmetric positive-definite matrix admits a unique factorization A = LL^T with L lower-triangular and strictly positive diagonal.…
QR factorization (Gram-Schmidt / Householder)
Every full-rank m×n matrix (m ≥ n) factors as an orthonormal Q (m×n) times upper-triangular R (n×n). Classical Gram-Schmidt is numerically…
Singular value decomposition (SVD)
Every real m×n matrix factors as A = UΣV^T with U, V orthogonal and Σ diagonal of non-negative singular values σ_k. Yields rank, condition…
Power iteration
Iterative method for the dominant eigenpair. Starting from a generic x_0, the normalized iterate Ax_k/‖Ax_k‖ converges to the top…
Householder reflection
Orthogonal matrix that reflects ℝⁿ across the hyperplane v^⊥. Choosing v = x + sign(x_1)‖x‖e_1 yields Hx = −sign(x_1)‖x‖e_1: a single…
Courant-Friedrichs-Lewy (CFL) condition
Necessary stability condition for explicit finite-difference schemes for hyperbolic PDEs: the numerical domain of dependence must contain…
Richardson extrapolation
Systematic error-cancellation for sequences with known leading-order expansion. Eliminates the O(h^p) error term by combining two…