4.8.5
Intuition Ek-sentence ideaComputers numbers ko finite precision ke saath store karte hain. Jab tum do nearly-equal numbers subtract karte ho , toh leading agreeing digits cancel ho jaate hain, aur last digits mein chhupe tiny rounding errors achanak aage aa jaate hain — accuracy tabah ho jaati hai. Isse catastrophic cancellation kehte hain.
Definition Floating-point aur relative errorEk real number x fl ( x ) = x ( 1 + δ ) ∣ δ ∣ ≤ u u unit roundoff hai (machine epsilon /2 u ≈ 1.1 × 1 0 − 16 16 significant decimal digits ).
Definition Catastrophic cancellationJab do nearly equal, rounded quantities subtract ki jaati hain, tab relative accuracy ki badi loss hoti hai. Absolute error chhota rehta hai, lekin relative error badh jaata hai kyunki bachne wale significant digits bahut kam hote hain.
Definition Stability vs instabilityEk algorithm numerically stable hota hai agar chhote input/rounding errors computation ke through bounded rehein (amplify na hon) . Woh unstable hota hai agar woh errors uncontrollably badhein. Cancellation instability ka ek common mechanism hai.
Maano true values a b a ≈ b a ^ = a ( 1 + δ a ) , b ^ = b ( 1 + δ b ) , ∣ δ a ∣ , ∣ δ b ∣ ≤ u .
Ab difference a ^ − b ^ Error hai:
a ^ − b ^ = ( a − b ) + ( a δ a − b δ b ) .
Toh absolute error hai a δ a − b δ b u ( ∣ a ∣ + ∣ b ∣ ) chhota , bilkul expected.
Dikkat relative error mein hai:
a − b ( a ^ − b ^ ) − ( a − b ) = a − b a δ a − b δ b .
Intuition Yeh step kyun matter karta haiNumerator order u ⋅ ∣ a ∣ a − b tiny hai jab a ≈ b huge relative error . a b
Bound karte hain:
rel error ≲ u ∣ a − b ∣ ∣ a ∣ + ∣ b ∣ Factor ∣ a − b ∣ ∣ a ∣ + ∣ b ∣ condition number hai. Jab a ≈ b yahi catastrophe hai.
Ilaaj almost hamesha algebra hai: expression ko aise rewrite karo ki khatarnak subtraction kabhi na ho.
Worked example Example 1 —x + 1 − x x x = 1 0 10 ≈ 1 0 5 Fix: rationalise karo (conjugate se multiply karo):
x + 1 − x = x + 1 + x ( x + 1 − x ) ( x + 1 + x ) = x + 1 + x 1 . Yeh step kyun? Conjugate ek difference ko denominator mein sum mein badal deta hai — positive numbers ka addition kabhi cancel nahi hota. Naya form ≈ 2 × 1 0 5 1 = 5 × 1 0 − 6
Worked example Example 2 — quadratic formulax 2 − 200 x + 1 = 0 x = 100 ± 9999 9999 ≈ 99.995 x 2 = 100 − 99.995 … catastrophically cancel ho jaata hai.
Fix: pehle safe root compute karo, phir roots ka product x 1 x 2 = c / a x 1 = 100 + 9999 ( safe, addition ) , x 2 = x 1 c / a = x 1 1 . Yeh step kyun? Vieta ka relation x 1 x 2 = c / a division se deta hai subtraction ki jagah — well-behaved numbers ka division stable hota hai.
Worked example Example 3 —1 − cos x x x = 0 cos x ≈ 1 1 − cos x Fix: identity use karo 1 − cos x = 2 sin 2 2 x Yeh step kyun? sin 2 x ≈ x /2 squaring kabhi cancel nahi hoti. (Ya Taylor series 2 x 2 − 24 x 4 + ⋯
Worked example Example 4 — variance, two-pass cure"Textbook" one-pass formula σ 2 = n 1 ∑ x i 2 − x ˉ 2 Fix: two-pass — pehle x ˉ σ 2 = n 1 ∑ ( x i − x ˉ ) 2
Common mistake Galat intuitions ko steel-man karna"Rounding errors random hote hain, average ho jaayenge — koi badi baat nahi."
Kyun sahi lagta hai: zyaadatar additions/multiplications mein relative error sach mein u Fix: subtraction special hai. Woh error create nahi karta — woh already present error ko expose aur magnify karta hai. Error absolute terms mein nahi badhta; sach wala answer uske neeche sink ho jaata hai . Toh koi averaging kaam nahi aata.
"Higher precision use karna (zyada digits) isse solve kar dega."
Kyun sahi lagta hai: zyada digits problem ko aur aage push kar dete hain.
Fix: yeh sirf problem ko delay karta hai. x + 1 − x x
"Catastrophic cancellation = unstable algorithm."
Kyun sahi lagta hai: cancellation instability ka mashoor source hai.
Fix: dono alag concepts hain. Conditioning problem ki property hai; stability algorithm ki property hai. Ek stable algorithm unnecessary cancellation se bachta hai; ek ill-conditioned problem chahe kuch bhi karo sensitive ho sakti hai.
Recall Feynman: ek 12-saal ke bachche ko samjhaoSocho do lambe block towers hain, ek 1000 blocks oonchi, doosri 1001. Tumne har ek ko sirf nearest block tak measure kiya — toh har ek aadhe block tak off ho sakti hai. Ab tum poochho "doosri kitni zyada oonchi hai?" Jawab hai lagbhag 1 block — lekin tumhari aadhe-block uncertainties ab us 1-block answer ke comparison mein BAHUT BADI hain! Tum towers ke baare mein confident ho lekin chhote se difference ke baare mein clueless. Trick yeh hai: dono towers measure karke subtract mat karo — ek aisa tarika dhundho jo gap directly measure kare.
"Big minus Big ek Jhooth hai." Jab do bade, nearly-equal numbers ladte hain, sirf noise bachti hai. → Rationalise karo, factor karo, ya identity use karo is duel se bachne ke liye.
Cancellation mein relative error kyun phatta hai lekin absolute error chhota rehta hai?
Kaun sa ek quantity govern karta hai ki subtraction kitni buri hai?
x + 1 − x Conditioning aur stability mein fark kya hai?
Catastrophic cancellation kya hai? Do nearly-equal rounded numbers subtract karne par relative accuracy ki badi loss; bachne wale significant digits bahut kam hote hain.
Kya cancellation absolute error badhata hai? Nahi — absolute error ≲ u ( ∣ a ∣ + ∣ b ∣ ) relative error magnify karta hai kyunki a − b
a − b ∣ a − b ∣ ∣ a ∣ + ∣ b ∣ a ≈ b
Khoye hue digits ka rule of thumb? Agar a , b k a − b k
x + 1 − x Conjugate se multiply karo:
x + 1 + x 1 (difference ko sum mein badal deta hai).
Chhote quadratic root ka stable fix? Addition se large-magnitude root compute karo, phir chhote ke liye Vieta x 1 x 2 = c / a
Chhote x 1 − cos x 2 sin 2 ( x /2 ) x 2 /2 − x 4 /24 + ⋯
Conditioning vs stability? Conditioning = problem ki sensitivity; stability = algorithm ka error-amplification.
Kya higher precision cancellation cure karta hai? Nahi, yeh sirf delay karta hai; algorithm ko reformulate karna asli ilaaj hai.
IEEE double ke liye unit roundoff u ≈ 1.1 × 1 0 − 16
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
