Error Analysis and Numerical Stability

Error analysis asks a deceptively simple question: when a computer returns a number, how close is it to the true answer? Because real numbers cannot be stored exactly in finite memory, every arithmetic operation introduces a tiny rounding error, and these can accumulate or be amplified catastrophically. The discipline distinguishes between conditioning — a property of the mathematical problem itself — and stability — a property of the algorithm used to solve it. The surprising fact is that a perfectly correct mathematical formula (like the quadratic formula) can give answers with no correct digits when implemented naively, while a cleverly rearranged version of the same formula is flawless. Understanding this separation is the foundation of all reliable scientific computing.

The Core Insight

A numerical result can be wrong for two fundamentally different reasons. Either the problem is intrinsically sensitive (small changes in input cause large changes in output — ill-conditioning), or the algorithm mishandles roundoff so that it computes the right answer to a badly perturbed problem (instability). The central organizing principle of the field is:

A good algorithm has small backward error; a good problem has small condition number. You need both for an accurate answer.

Formal Statement

Absolute and Relative Error

Let $\hat{x}$ be an approximation to a true value $x$. The absolute error and relative error are

Here $\hat{x}$ is the computed/measured quantity and $x$ the exact one. Relative error of $10^{-6}$ means roughly 6 correct significant decimal digits.

Machine Epsilon and Floating-Point Representation

In IEEE-754 floating point, a number is stored as $\pm m\times {\beta }^e$ with base $\beta$ (usually 2), mantissa $m$, and exponent $e$. The machine epsilon ${\epsilon }_{\text{mach}}$ is the gap between $1$ and the next representable number:

For IEEE double precision ($\beta =2$, $p=53$): ${\epsilon }_{\text{mach}}=2^{-52}\approx 2.22\times 10^{-16}$, $u\approx 1.11\times 10^{-16}$.

Conditioning and Condition Number

For a differentiable problem $y=f(x)$, the (relative) condition number measures output sensitivity to input:

Backward Stability

An algorithm $\hat{f}$ for computing $f$ is backward stable if for every input $x$ the computed result equals the exact answer for a slightly perturbed input:

Rule of Thumb: Forward = Condition × Backward

If $\hat{f}$ is backward stable with backward error $\eta$, the forward (relative) error obeys

Why It Holds / Derivation

Forward-Error Bound from Conditioning and Backward Stability

The key insight: even a perfect algorithm ($\eta \sim u$) cannot beat the problem's conditioning. If $\kappa =10^{10}$ in double precision, expect to lose 10 of your 16 digits no matter how clever the code.

James H. Wilkinson | 1919–1986

Wilkinson, working at Britain's National Physical Laboratory on the ACE computer with Alan Turing, invented modern backward error analysis in the 1950s–60s. His revolutionary insight was to stop asking "how wrong is my answer?" (often intractable) and instead ask "what nearby problem did I solve exactly?" His 1963 Rounding Errors in Algebraic Processes and 1965 The Algebraic Eigenvalue Problem became foundational. He showed Gaussian elimination with partial pivoting is backward stable, explaining why a method without rigorous a priori bounds works so reliably in practice. Wilkinson won the Turing Award in 1970.

Building Intuition

Think of solving a problem as reading a faint message through a lens.

The condition number is the lens's distortion: an ill-conditioned problem is like a warped lens that magnifies any smudge on the input into a huge blur on the output. You cannot fix this by being careful — it's baked into the problem.

The algorithm's stability is whether you smudged the input yourself before looking. A backward-stable algorithm adds only a microscopic smudge (size ${\epsilon }_{\text{mach}}$). An unstable algorithm adds a giant fingerprint, then complains the output is blurry.

The product — distortion times smudge — determines how blurry the final reading is. The classic disaster is catastrophic cancellation: subtracting two nearly equal numbers. The true digits agree and cancel, leaving only the noisy trailing digits. The relative error explodes because the result is small but its absolute error stayed the same.

Error propagation: condition number amplifies backward error into forward error

<svg viewBox="0 0 640 360" xmlns="http://www.w3.org/2000/svg">
  <rect width="640" height="360" fill="#0a0e17"/>
  <text x="320" y="30" fill="#e2e8f0" font-size="18" text-anchor="middle">forward error ≈ κ × backward error</text>

  <!-- input space -->
  <ellipse cx="130" cy="200" rx="90" ry="70" fill="none" stroke="#94a3b8" stroke-width="1.5"/>
  <text x="130" y="120" fill="#e2e8f0" font-size="13" text-anchor="middle">input space</text>
  <circle cx="120" cy="190" r="4" fill="#e2e8f0"/>
  <text x="120" y="180" fill="#e2e8f0" font-size="11" text-anchor="middle">x</text>
  <circle cx="148" cy="206" r="4" fill="#d4a853"/>
  <text x="172" y="212" fill="#d4a853" font-size="11" text-anchor="middle">x̃</text>
  <line x1="120" y1="190" x2="148" y2="206" stroke="#d4a853" stroke-width="1.2"/>
  <text x="100" y="245" fill="#d4a853" font-size="10" text-anchor="middle">backward error (tiny)</text>

  <!-- output space -->
  <ellipse cx="510" cy="200" rx="100" ry="80" fill="none" stroke="#94a3b8" stroke-width="1.5"/>
  <text x="510" y="105" fill="#e2e8f0" font-size="13" text-anchor="middle">output space</text>
  <circle cx="480" cy="180" r="4" fill="#e2e8f0"/>
  <text x="480" y="170" fill="#e2e8f0" font-size="11" text-anchor="middle">f(x)</text>
  <circle cx="560" cy="240" r="4" fill="#d4a853"/>
  <text x="560" y="262" fill="#d4a853" font-size="11" text-anchor="middle">f(x̃)=f̂(x)</text>
  <line x1="480" y1="180" x2="560" y2="240" stroke="#d4a853" stroke-width="1.2"/>
  <text x="520" y="155" fill="#d4a853" font-size="10" text-anchor="middle">forward error (large)</text>

  <!-- map arrows -->
  <path d="M 220 190 Q 360 130 480 180" fill="none" stroke="#94a3b8" stroke-width="1.5" stroke-dasharray="4 3"/>
  <path d="M 196 206 Q 380 290 560 240" fill="none" stroke="#94a3b8" stroke-width="1.5" stroke-dasharray="4 3"/>
  <text x="360" y="150" fill="#e2e8f0" font-size="12" text-anchor="middle">f (exact)</text>

  <text x="320" y="340" fill="#94a3b8" font-size="11" text-anchor="middle">A small input perturbation is stretched by κ into a large output error.</text>
</svg>

Worked Examples

Catastrophic Cancellation in the Quadratic Formula

Condition Number of a Linear System

Common Misconceptions

Stability ≠ Accuracy

A backward-stable algorithm does not guarantee an accurate answer. If the problem is ill-conditioned ($\kappa$ huge), even a perfect algorithm returns garbage — because [7] says forward error $\sim \kappa u$. Conversely, an unstable algorithm on a well-conditioned problem also fails. Accuracy requires good conditioning AND a stable algorithm together. Never blame the computer for an ill-conditioned problem, and never trust a "correct formula" without analyzing its numerical behavior.

Floating-Point Arithmetic Is Not Associative

In exact math $(a+b)+c=a+(b+c)$, but in floating point this fails. Summing $10^{20}+1-10^{20}$ left-to-right gives $0$ (the $1$ is lost when added to $10^{20}$), while $10^{20}-10^{20}+1$ gives $1$. Reordering, parallelizing, or compiler-optimizing floating-point sums can change results. This is why algorithms like Kahan summation exist to recover lost precision.

A Convergent Recurrence That Diverges Numerically

Consider computing $I_n={\int }_0^1\frac{x^n}{x+5}dx$ via the forward recurrence $I_n=\frac{1}{n}-5I_{n-1}$, starting from $I_0=\ln (6/5)\approx 0.18232$.

Mathematically each $I_n$ is a small positive number $\to 0$. But each step multiplies the previous error by $-5$. After ~10 steps the accumulated roundoff (initial error $\sim 10^{-6}$) is amplified by $5^{10}\approx 10^7$, giving wildly oscillating negative values like $I_{15}\approx -1000$ — absurd for an integral bounded by $1/6$.

Connections

Error analysis is the connective tissue of all of numerical mathematics. The condition number of a matrix is central to Linear Algebra and Singular Value Decomposition (where ${\kappa }_2={\sigma }_{\max }/{\sigma }_{\min }$). Stability of Numerical Methods for ODEs (e.g. stiff equations, A-stability) is a direct application of error propagation. Floating Point Arithmetic (IEEE-754) supplies the model [4] for individual operation errors. Taylor Series underpins both truncation-error analysis and the linearization used to define $\kappa$. The interplay of truncation and roundoff error is the heart of Numerical Differentiation, where shrinking the step $h$ first reduces truncation error then explodes roundoff.

Real-World Applications

• Climate and weather modeling (ECMWF, NOAA): chaotic systems with $\kappa$ effectively growing exponentially; error analysis sets the predictability horizon (~2 weeks) and justifies ensemble forecasting.
• GPS positioning: solving for receiver location from satellite ranges is ill-conditioned when satellites cluster ("poor geometric dilution of precision," GDOP), directly a condition-number issue.
• Finite element structural analysis (ANSYS, Abaqus): stiffness matrices for thin or nearly-rigid components are ill-conditioned; engineers monitor $\kappa$ to validate bridge and aircraft simulations.
• Computer graphics & robotics: inverting near-singular Jacobians near kinematic singularities requires regularization (e.g. damped least squares) informed by conditioning.
• Financial computation (Black–Scholes near expiry): catastrophic cancellation in option-price differences demands reformulated stable expressions.
• Machine learning: ill-conditioned Hessians slow gradient descent; batch-normalization and preconditioning explicitly improve conditioning.
• Signal processing (FFT): the Fast Fourier Transform is backward stable with error $O(\log N\cdot u)$, vastly better than the naive DFT, enabling reliable spectral analysis.

Historical Development

• 1947 — von Neumann & Goldstine publish the first rigorous rounding-error analysis of matrix inversion, introducing condition-number ideas.
• 1948 — Alan Turing coins the term "condition number" and analyzes ill-conditioning of linear systems on the ACE/Pilot ACE machines.
• 1950s — Wilkinson at NPL develops backward error analysis, reframing accuracy questions around perturbed inputs.
• 1961 — Wilkinson publishes the backward-stability analysis of Gaussian elimination, proving partial pivoting's reliability.
• 1963 — Wilkinson, Rounding Errors in Algebraic Processes — the field's first textbook.
• 1965 — Wilkinson, The Algebraic Eigenvalue Problem — definitive treatment of eigenvalue conditioning and stability.
• 1965 — William Kahan begins work on robust floating-point summation and arithmetic, later shaping IEEE-754.
• 1985 — IEEE-754 standard ratified, formalizing ${\epsilon }_{\text{mach}}$, rounding modes, and the error model [4] across all hardware.
• 1996/2002 — Nicholas Higham, Accuracy and Stability of Numerical Algorithms, becomes the modern comprehensive reference.

Subtleties & Limits

Backward stability is the gold standard, but many important algorithms are only mixed forward-backward stable or merely forward stable, and rigorously classifying them remains delicate. For nonlinear and large-scale problems, the worst-case condition number can be enormously pessimistic, motivating probabilistic / smoothed analysis (Spielman–Teng, Demmel) that asks how ill-conditioned a random perturbation of a problem typically is. In iterative and randomized linear algebra (sketching, stochastic gradient methods) the interaction of statistical noise with roundoff is still being mapped out. A further open frontier is rigorous, automated error certification for low-precision and mixed-precision hardware (bfloat16, FP8) now dominant in machine learning, where ${\epsilon }_{\text{mach}}$ is as large as $10^{-2}$ and classical bounds become loose or vacuous.

See Also