≈

Numerical methods

Calculus as an algorithm: finding roots, interpolating, differentiating and integrating with finite arithmetic — and knowing how wrong the answer can be.

10 topics

Closed-form answers are the exception. Most equations of engineering, physics and machine learning are solved by iterating a simple step until the answer stops changing:

x₀ → f(x₀), f'(x₀) → x₁ → f(x₁), f'(x₁) → x₂ → … → solution

Three questions decide whether that works: does the iteration converge, how fast, and how much do rounding errors and badly conditioned problems spoil the result?

Topics

Absolute and relative error

Absolute error $|x - \hat x|$ and relative error $|x - \hat x|/|x|$ . Relative error counts correct significant digits, and it is what floating point controls: every operation is exact up to a relative error of at most $\varepsilon_{\text{mach}} \approx 1.1 \cdot 10^{-16}$ in double precision.

Fundamental

Conditioning

How much a problem amplifies relative errors in its data, independently of the algorithm. Its condition number $\kappa$ says you can lose about $\log_{10}\kappa$ digits however cleverly you compute.

University

Numerical stability

Whether an algorithm keeps rounding errors under control. Two mathematically equal formulas can behave very differently: subtracting nearly equal numbers (catastrophic cancellation) or iterating an unstable recurrence destroys accuracy.

University

Order of convergence

How fast the error $e_k = |x_k - x^\ast|$ shrinks: linear ( $e_{k+1} \approx c\,e_k$ , a fixed number of digits per step), quadratic ( $e_{k+1} \approx c\,e_k^2$ , digits double each step). Bisection is linear; Newton is quadratic.

University

Bisection method

Keep an interval where $f$ changes sign and halve it each step. Slow (one bit per step) but impossible to break: Bolzano's theorem guarantees a root inside. It is binary search on a continuous function.

FundamentalMethod

Newton's method

To solve $f(x) = 0$ , replace $f$ by its tangent line at the current guess and jump to where the tangent hits zero: $x_{k+1} = x_k - f(x_k)/f'(x_k)$ . Near a simple root the number of correct digits doubles every step.

UniversityMethod◐ demo

Fixed-point iteration

Rewrite the equation as $x = g(x)$ and iterate $x_{k+1} = g(x_k)$ . If $g$ is a contraction ( $|g'| \le q < 1$ ), Banach's theorem guarantees a unique fixed point and linear convergence with ratio $q$ .

UniversityMethod

Interpolation

Building a function that passes through given data points. Linear interpolation (lerp) is everywhere in graphics and animation; polynomials of high degree oscillate wildly (Runge's phenomenon), so practice uses piecewise polynomials: splines.

University

Numerical differentiation

Estimating derivatives from function values: $\frac{f(x + h) - f(x - h)}{2h}$ has error $O(h^2)$ . Too large an $h$ gives truncation error, too small an $h$ rounding error; the best $h$ for central differences in double precision is around $10^{-5}$ .

UniversityMethod

Numerical integration (quadrature)

Approximating $\int_a^b f$ by a weighted sum of samples. Trapezoid ( $O(h^2)$ ), Simpson ( $O(h^4)$ ) and Gaussian quadrature are excellent in one or a few dimensions; in high dimensions Monte Carlo takes over.

UniversityMethod

Where this area leads in computing

Topics

Absolute and relative error

Conditioning

Numerical stability

Order of convergence

Bisection method

Newton's method

Fixed-point iteration

Interpolation

Numerical differentiation

Numerical integration (quadrature)

Where this area leads in computing

λ Scientific computing and algorithms ★★★★★

ℒ AI and machine learning ★★★★★

⚛ Physics and simulation ★★★★★

∿ Signals, media and vision ★★★★★

3D Computer graphics ★★★★★

⚙ Robotics and control ★★★★★