Conditioning and Stability

Conditioning measures how sensitive a problem is to input perturbations; stability measures how faithfully an algorithm solves the problem it was given.

Two independent ideas

Numerical accuracy has two distinct sources of trouble. Conditioning is a property of the mathematical problem: an ill-conditioned problem amplifies small changes in the input into large changes in the output, no matter how the answer is computed. Stability is a property of the algorithm: a stable algorithm does not introduce error beyond what the problem's conditioning forces.

The condition number quantifies conditioning. For evaluating a function f at x, the relative condition number is roughly |x f'(x) / f(x)|. A value near 1 is well conditioned; a large value warns that accuracy will be lost even with perfect arithmetic.

Backward stability

An algorithm is backward stable if its computed answer is the exact answer to a slightly perturbed problem. Combined with the condition number, this gives the fundamental error bound: forward error is bounded by condition number times backward error. Good algorithms make backward error near machine epsilon; the rest is up to the problem.

Why the distinction matters

Blaming an algorithm for a wildly wrong answer is often misplaced: an ill-conditioned problem cannot be solved accurately by any method in finite precision. Conversely, an unstable algorithm can ruin a well-conditioned problem. Diagnosing which is at fault decides whether to change the method or reformulate the problem.

import numpy as np
# Hilbert matrix is famously ill-conditioned
n = 8
H = np.array([[1.0/(i+j+1) for j in range(n)] for i in range(n)])
print(np.linalg.cond(H))   # ~1.5e10, tiny input errors get amplified

In large physics simulations, both concerns appear together: an operator may be ill-conditioned near a physical singularity, and a solver must be chosen for stability so it does not add error the problem does not already require.