Intuition The one-sentence ideaComputers store numbers with finite precision . When you subtract two nearly-equal numbers , the leading agreeing digits cancel out, and the tiny rounding errors hiding in the last digits suddenly get promoted to the front — destroying accuracy. This is catastrophic cancellation .
Definition Floating-point & relative errorA real number x x x fl ( x ) = x ( 1 + δ ) \text{fl}(x) = x(1+\delta) fl ( x ) = x ( 1 + δ ) ∣ δ ∣ ≤ u |\delta| \le u ∣ δ ∣ ≤ u unit roundoff (machine epsilon / 2 /2 /2 u ≈ 1.1 × 10 − 16 u \approx 1.1\times 10^{-16} u ≈ 1.1 × 1 0 − 16 16 significant decimal digits ).
Definition Catastrophic cancellationThe large loss of relative accuracy that occurs when subtracting two nearly equal, rounded quantities. The absolute error stays small, but the relative error blows up because the surviving significant digits are few.
Definition Stability vs instabilityAn algorithm is numerically stable if small input/rounding errors stay bounded (don't get amplified) through the computation. It is unstable if those errors grow uncontrollably. Cancellation is one common mechanism of instability.
Suppose the true values are a a a b b b a ≈ b a \approx b a ≈ b a ^ = a ( 1 + δ a ) , b ^ = b ( 1 + δ b ) , ∣ δ a ∣ , ∣ δ b ∣ ≤ u . \hat a = a(1+\delta_a), \qquad \hat b = b(1+\delta_b), \qquad |\delta_a|,|\delta_b|\le u. a ^ = a ( 1 + δ a ) , b ^ = b ( 1 + δ b ) , ∣ δ a ∣ , ∣ δ b ∣ ≤ u .
Now form the difference a ^ − b ^ \hat a - \hat b a ^ − b ^ error is:
a ^ − b ^ = ( a − b ) + ( a δ a − b δ b ) . \hat a - \hat b = (a-b) + (a\,\delta_a - b\,\delta_b). a ^ − b ^ = ( a − b ) + ( a δ a − b δ b ) .
So the absolute error is a δ a − b δ b a\delta_a - b\delta_b a δ a − b δ b u ( ∣ a ∣ + ∣ b ∣ ) u(|a|+|b|) u ( ∣ a ∣ + ∣ b ∣ ) small , just as expected.
The trouble is the relative error :
( a ^ − b ^ ) − ( a − b ) a − b = a δ a − b δ b a − b . \frac{(\hat a - \hat b) - (a-b)}{a-b} = \frac{a\delta_a - b\delta_b}{a-b}. a − b ( a ^ − b ^ ) − ( a − b ) = a − b a δ a − b δ b .
Intuition Why this step mattersThe numerator is order u ⋅ ∣ a ∣ u\cdot|a| u ⋅ ∣ a ∣ a − b a-b a − b tiny when a ≈ b a\approx b a ≈ b huge relative error . The closer a a a b b b
Bounding it:
∣ rel error ∣ ≲ u ∣ a ∣ + ∣ b ∣ ∣ a − b ∣ \boxed{\ \left|\frac{\text{rel error}}{} \right| \lesssim u\,\frac{|a|+|b|}{|a-b|}\ } rel error ≲ u ∣ a − b ∣ ∣ a ∣ + ∣ b ∣ The factor ∣ a ∣ + ∣ b ∣ ∣ a − b ∣ \dfrac{|a|+|b|}{|a-b|} ∣ a − b ∣ ∣ a ∣ + ∣ b ∣ condition number of subtraction . When a ≈ b a\approx b a ≈ b that is the catastrophe.
The cure is almost always algebra : rewrite the expression so the dangerous subtraction never happens .
Worked example Example 1 —x + 1 − x \sqrt{x+1}-\sqrt{x} x + 1 − x x x x x = 10 10 x = 10^{10} x = 1 0 10 ≈ 10 5 \approx 10^5 ≈ 1 0 5 Fix: rationalise (multiply by the conjugate):
x + 1 − x = ( x + 1 − x ) ( x + 1 + x ) x + 1 + x = 1 x + 1 + x . \sqrt{x+1}-\sqrt{x} = \frac{(\sqrt{x+1}-\sqrt{x})(\sqrt{x+1}+\sqrt{x})}{\sqrt{x+1}+\sqrt{x}} = \frac{1}{\sqrt{x+1}+\sqrt{x}}. x + 1 − x = x + 1 + x ( x + 1 − x ) ( x + 1 + x ) = x + 1 + x 1 . Why this step? The conjugate turns a difference into a sum in the denominator — addition of positives never cancels. The new form gives ≈ 1 2 × 10 5 = 5 × 10 − 6 \approx \frac{1}{2\times10^5}=5\times10^{-6} ≈ 2 × 1 0 5 1 = 5 × 1 0 − 6
Worked example Example 2 — the quadratic formulaSolve x 2 − 200 x + 1 = 0 x^2 - 200x + 1 = 0 x 2 − 200 x + 1 = 0 x = 100 ± 9999 x = 100 \pm \sqrt{9999} x = 100 ± 9999 9999 ≈ 99.995 \sqrt{9999}\approx 99.995 9999 ≈ 99.995 x 2 = 100 − 99.995 … x_2 = 100 - 99.995\ldots x 2 = 100 − 99.995 … cancels catastrophically .
Fix: compute the safe root first, then use the product of roots x 1 x 2 = c / a x_1 x_2 = c/a x 1 x 2 = c / a x 1 = 100 + 9999 ( safe, addition ) , x 2 = c / a x 1 = 1 x 1 . x_1 = 100 + \sqrt{9999}\ (\text{safe, addition}), \qquad x_2 = \frac{c/a}{x_1} = \frac{1}{x_1}. x 1 = 100 + 9999 ( safe, addition ) , x 2 = x 1 c / a = x 1 1 . Why this step? Vieta's relation x 1 x 2 = c / a x_1 x_2 = c/a x 1 x 2 = c / a division instead of subtraction — division of well-behaved numbers is stable.
Worked example Example 3 —1 − cos x 1-\cos x 1 − cos x x x x x = 0 x=0 x = 0 cos x ≈ 1 \cos x \approx 1 cos x ≈ 1 1 − cos x 1-\cos x 1 − cos x Fix: use the identity 1 − cos x = 2 sin 2 x 2 1-\cos x = 2\sin^2\!\frac{x}{2} 1 − cos x = 2 sin 2 2 x Why this step? sin x 2 \sin\frac{x}{2} sin 2 x ≈ x / 2 \approx x/2 ≈ x /2 squaring never cancels. (Or use the Taylor series x 2 2 − x 4 24 + ⋯ \frac{x^2}{2}-\frac{x^4}{24}+\cdots 2 x 2 − 24 x 4 + ⋯
Worked example Example 4 — variance, the two-pass cureThe "textbook" one-pass formula σ 2 = 1 n ∑ x i 2 − x ˉ 2 \sigma^2 = \frac{1}{n}\sum x_i^2 - \bar x^2 σ 2 = n 1 ∑ x i 2 − x ˉ 2 Fix: two-pass — first compute x ˉ \bar x x ˉ σ 2 = 1 n ∑ ( x i − x ˉ ) 2 \sigma^2 = \frac{1}{n}\sum (x_i-\bar x)^2 σ 2 = n 1 ∑ ( x i − x ˉ ) 2
Common mistake Steel-manning the wrong intuitions"Rounding errors are random, they'll average out — no big deal."
Why it feels right: in most additions/multiplications the relative error really does stay near u u u The fix: subtraction is special. It doesn't create error — it exposes and magnifies error already present. The error doesn't grow in absolute terms; the true answer shrinks beneath it . So no averaging saves you.
"Using higher precision (more digits) solves it."
Why it feels right: more digits do push the failure further out.
The fix: it only delays the problem. x + 1 − x \sqrt{x+1}-\sqrt{x} x + 1 − x x x x
"Catastrophic cancellation = an unstable algorithm."
Why it feels right: cancellation is a famous source of instability.
The fix: they're different concepts. Conditioning is a property of the problem ; stability is a property of the algorithm . A stable algorithm avoids unnecessary cancellation; an ill-conditioned problem may be sensitive no matter what.
Recall Feynman: explain it to a 12-year-oldImagine two tall towers of blocks, one 1000 blocks high, the other 1001. You only measured each to the nearest block — so each could really be off by half a block. Now you ask "how much taller is the second?" The answer is about 1 block — but your half-block uncertainties are now HUGE compared to that 1-block answer! You're confident about the towers but clueless about the tiny difference. The trick: don't measure both towers and subtract — find a way to measure the gap directly.
"Big minus Big is a Lie." When two big, nearly-equal numbers fight, only the noise survives. → Rationalise, factor, or use an identity to dodge the duel.
Why does the relative error explode but the absolute error stay small in cancellation?
What single quantity governs how bad subtraction is?
How do you fix x + 1 − x \sqrt{x+1}-\sqrt{x} x + 1 − x
Difference between conditioning and stability?
What is catastrophic cancellation? A severe loss of relative accuracy when subtracting two nearly-equal rounded numbers; surviving significant digits are few.
Does cancellation increase the absolute error? No — absolute error stays
≲ u ( ∣ a ∣ + ∣ b ∣ ) \lesssim u(|a|+|b|) ≲ u ( ∣ a ∣ + ∣ b ∣ ) . It magnifies the
relative error because
a − b a-b a − b is tiny.
What is the condition number of subtracting a − b a-b a − b ∣ a ∣ + ∣ b ∣ ∣ a − b ∣ \dfrac{|a|+|b|}{|a-b|} ∣ a − b ∣ ∣ a ∣ + ∣ b ∣ — huge when
a ≈ b a\approx b a ≈ b .
Rule of thumb for lost digits? If
a , b a,b a , b agree to
k k k leading digits,
a − b a-b a − b loses about
k k k significant digits.
Stable fix for x + 1 − x \sqrt{x+1}-\sqrt{x} x + 1 − x Multiply by conjugate:
1 x + 1 + x \dfrac{1}{\sqrt{x+1}+\sqrt{x}} x + 1 + x 1 (turns difference into a sum).
Stable fix for the small quadratic root? Compute the large-magnitude root by addition, then use Vieta
x 1 x 2 = c / a x_1x_2=c/a x 1 x 2 = c / a to divide for the small one.
Stable form of 1 − cos x 1-\cos x 1 − cos x x x x 2 sin 2 ( x / 2 ) 2\sin^2(x/2) 2 sin 2 ( x /2 ) , or the Taylor series
x 2 / 2 − x 4 / 24 + ⋯ x^2/2 - x^4/24+\cdots x 2 /2 − x 4 /24 + ⋯ .
Conditioning vs stability? Conditioning = sensitivity of the problem ; stability = error-amplification of the algorithm .
Does higher precision cure cancellation? No, it only delays it; reformulating the algorithm is the real cure.
Unit roundoff u u u ≈ 1.1 × 10 − 16 \approx 1.1\times10^{-16} ≈ 1.1 × 1 0 − 16 (~16 significant decimal digits).
stores as fl x = x 1+delta
absolute error stays small
e.g. conjugate rationalise
Finite precision floating-point
Rounding error bounded by u
Subtract nearly-equal numbers
Catastrophic cancellation
Absolute error ~ u times abs a + abs b
Condition number abs a + abs b over abs a - b
Lose about k significant digits
Stable: errors stay bounded
Rewrite to avoid subtraction
sqrt x+1 minus sqrt x becomes a sum
Intuition Hinglish mein samjhoDekho, computer numbers ko sirf ~16 significant digits tak store karta hai (double precision). Jab tum do bahut close numbers ko subtract karte ho — jaise x + 1 − x \sqrt{x+1}-\sqrt{x} x + 1 − x catastrophic cancellation kehte hain. Mazedaar baat: absolute error chhota hi rehta hai, lekin relative error phat jaata hai, kyunki asli answer to bahut chhota hai aur error uske saamne bada lagne lagta hai.
Kitni digits gayi? Simple rule: agar do numbers pehle k k k k k k ∣ a ∣ + ∣ b ∣ ∣ a − b ∣ \frac{|a|+|b|}{|a-b|} ∣ a − b ∣ ∣ a ∣ + ∣ b ∣ a ≈ b a\approx b a ≈ b
Fix kya hai? Algebra se subtraction ko dodge karo. x + 1 − x \sqrt{x+1}-\sqrt{x} x + 1 − x 1 x + 1 + x \frac{1}{\sqrt{x+1}+\sqrt{x}} x + 1 + x 1 addition hai, koi cancellation nahi. Quadratic ke chhote root ke liye pehle bada root (addition se) nikaalo, fir Vieta x 1 x 2 = c / a x_1 x_2 = c/a x 1 x 2 = c / a 1 − cos x 1-\cos x 1 − cos x 2 sin 2 ( x / 2 ) 2\sin^2(x/2) 2 sin 2 ( x /2 ) higher precision sirf problem ko aage tak khinchta hai, solve nahi karta — asli ilaaj formula ko rewrite karna hai.
Ek important distinction: conditioning problem ki property hai (problem khud sensitive hai kya), aur stability algorithm ki property hai (tumhara method error ko badhata hai kya). Catastrophic cancellation ek unstable algorithm ka famous example hai — same maths, smart reformulation, full accuracy back.
