4.8.8
Hum f ( x ) = 0 YEH KAAM KYUN KARTA HAI: Kisi point ke paas, koi bhi smooth curve almost ek straight line jaisi dikhti hai. Toh hum mushkil curve ko uski tangent line se replace karte hain apne current guess par, woh aasaan linear equation solve karte hain (jahan tangent x-axis se milti hai), aur use apna next guess banate hain. Repeat. Kyunki tangent curve ko itni achhi tarah "hug" karti hai, error bahut tezi se shrink hoti hai.
Definition Root-finding problemEk differentiable function f r f ( r ) = 0 r f root (ya zero) kehte hain.
Humare paas ek current estimate x n r kaafi-kaafi paas hai. Hum chahte hain ek rule jo ek better estimate x n + 1
HOW hum iteration banate hain — do equivalent routes.
Point ( x n , f ( x n )) f ′ ( x n ) y − f ( x n ) = f ′ ( x n ) ( x − x n )
Hum poochte hain: yeh tangent x-axis ko kahan cross karti hai? y = 0 x n + 1
0 − f ( x n ) = f ′ ( x n ) ( x n + 1 − x n )
Yeh step kyun? Tangent curve ka stand-in hai. Curve ka root mushkil hai; tangent ka root trivial hai — woh ek line hai.
x n + 1 f ′ ( x n ) = 0
x n + 1 − x n = − f ′ ( x n ) f ( x n )
f x n x n + 1 f ( x n + 1 ) ≈ f ( x n ) + f ′ ( x n ) ( x n + 1 − x n ) = 0
Yeh step kyun? Hum Taylor ko linear term ke baad truncate karte hain. Bacha hua quadratic term 2 1 f ′′ ( x n ) ( ⋅ ) 2
Solve karne par same boxed formula milta hai. ✅
Error ko e n = x n − r e n + 1 e n
f ( r ) x n f ( r ) = 0 0 = f ( r ) = f ( x n ) + f ′ ( x n ) ( r − x n ) + 2 1 f ′′ ( ξ ) ( r − x n ) 2 ξ r x n
Yeh step kyun? Yeh ek exact equation hai (remainder form), approximation nahi. Yeh hume true error track karne deta hai.
Kyunki r − x n = − e n 0 = f ( x n ) − f ′ ( x n ) e n + 2 1 f ′′ ( ξ ) e n 2
f ′ ( x n ) f ′ ( x n ) f ( x n ) = e n − 2 f ′ ( x n ) f ′′ ( ξ ) e n 2
Ab iteration x n + 1 = x n − f ′ ( x n ) f ( x n ) x n + 1 = x n − e n + 2 f ′ ( x n ) f ′′ ( ξ ) e n 2
Lekin x n − e n = r x n + 1 − r = 2 f ′ ( x n ) f ′′ ( ξ ) e n 2
Intuition "Quadratic" ka practically matlab kya hai∣ e n + 1 ∣ ≈ C e n 2 correct digits ki number roughly har step mein double ho jaati hai .
Agar 3 correct digits hain, next step ≈ 6, phir ≈ 12. Isliye Newton-Raphson numerical solvers ka workhorse hai.
Iske liye conditions: f ′ ( r ) = 0 f ′′ r f ′ ( r ) = 0 multiple root), convergence sirf linear reh jaati hai.
Worked example Example 1 —f ( x ) = x 2 − 2 2 f ′ ( x ) = 2 x x n + 1 = x n − 2 x n x n 2 − 2 = 2 x n + x n 1 Yeh step kyun? Simplify karne par famous "Babylonian" average formula milta hai — x n 2/ x n
x 0 = 1
x 1 = 2 1 + 1 = 1.5 x 2 = 0.75 + 0.6667 = 1.41 6 67 x 3 = 1.41421 5 69
True 2 = 1.41421356 …
Worked example Example 2 —f ( x ) = x 3 − x − 2 f ′ ( x ) = 3 x 2 − 1 x n + 1 = x n − 3 x n 2 − 1 x n 3 − x n − 2 x 0 = 1.5
f ( 1.5 ) = 0.375 f ′ ( 1.5 ) = 5.75 x 1 = 1.5 − 0.0652 = 1.4348 f ( 1.4348 ) = 0.0185 f ′ = 5.176 x 2 = 1.4348 − 0.00357 = 1.43124 x 3 = 1.521 … x 3 ≈ 1.52138
Recheck kyun? Hamesha verify karo ki f ( x n + 1 ) f ( 1.43124 ) ≈ 0.00003 x 3 ≈ 1.43122 ≈ 1.521380 nahi — x 3 − x − 2 1.5214 Lesson: carefully recompute karo; method arithmetic slips ke liye unforgiving hai chahe woh fast converge kare.
Worked example Example 3 — division ke bina reciprocal:1/ a f ( x ) = x 1 − a = 0 f ′ ( x ) = − x 2 1 x n + 1 = x n − − 1/ x n 2 x n 1 − a = x n + x n 2 ( x n 1 − a ) = x n ( 2 − a x n ) Yeh kyun matter karta hai: yeh iteration sirf multiplication use karta hai — aise hi CPUs internally division compute karte hain.
Common mistake "Koi bhi starting point lo — yeh converge ho jayega."Kyun sahi lagta hai: method itna powerful hai achhe guesses ke liye ki students sochte hain yeh bulletproof hai.
Fix: Newton-Raphson sirf locally convergent hai. Bura x 0 diverge kar sakta hai, oscillate kar sakta hai (jaise arctan x x 0 alag root par jump kar sakta hai. Pehle hamesha f
f ′ ( x n ) = 0 Kyun sahi lagta hai: algebra mein hum freely divide karte hain.
Fix: agar tangent horizontal hai, woh kabhi x-axis nahi hit karti — x n + 1 f ′ ( x n ) = 0
Common mistake "Convergence hamesha quadratic hoti hai."Kyun sahi lagta hai: derivation deta hai e n + 1 ∝ e n 2 Fix: woh derivation assumed karta tha f ′ ( r ) = 0 Multiple root par f ′ ( r ) = 0 C x n + 1 = x n − m f ′ f m
Recall Quick self-test (hide karke answer karo)
Iteration formula state karo aur har part ka geometrically matlab batao.
Tangent line se derive karo.
Convergence quadratic kyun hai? Kaun sa assumption essential hai?
Multiple root par kya hota hai? f ′ ( x n ) = 0
Newton-Raphson iteration formula x n + 1 = x n − f ′ ( x n ) f ( x n )
Iteration ka geometric meaning x n + 1 ( x n , f ( x n ))
Newton-Raphson ke liye error recurrence e n + 1 = 2 f ′ ( x n ) f ′′ ( ξ ) e n 2 ∣ e n + 1 ∣ ≈ C ∣ e n ∣ 2
Convergence ka order (simple root) Quadratic — correct digits ki number roughly har step mein double hoti hai
Quadratic convergence ke liye essential condition f ′ ( r ) = 0 f ′′
Quadratic convergence ko kya khatam karta hai Multiple root (f ′ ( r ) = 0
Agar f ′ ( x n ) = 0 Horizontal tangent → x n + 1
f = x 2 − a a x n + 1 = 2 1 ( x n + x n a )
1/ a x n + 1 = x n ( 2 − a x n )
Formula ki do derivations Tangent-line geometry, aur Taylor ko linear term par truncate karna
Mnemonic Formula yaad rakho"New = Old − Height over Slope."
x new = x old − slope f ′ height f
Recall Feynman: ek 12-saal ke bachche ko explain karoSocho tum ek pahaad par ski kar rahe ho aankh bandh karke, valley ke bilkul neeche pahunchne ki koshish kar rahe ho (jahan height = 0). Tum feel kar sakte ho ki slope tumhare skis ke neeche kis taraf jhukti hai. Toh tum seedha us slope ke neeche point karte ho aur ek perfectly straight line mein slide karte ho jab tak "ground level" hit na ho, aur wahan ruk jaate ho. Tum ab bottom ke bahut paas ho. Nayi slope feel karo, phir slide karo. Har slide tumhe bahut, bahut paas le jaati hai — jaise pehle half phir quarter phir... tumhari doori super fast shrink hoti hai. "Tumhare skis ke neeche slope" f ′ f f / f ′
Bisection Method — guaranteed lekin sirf linear; robust hybrids ke liye Newton ke saath pair karo (Brent's Method ).Secant Method — f ′ ≈ 1.618 Taylor Series — formula aur error analysis dono ke peeche ka engine.Fixed-Point Iteration — Newton fixed-point iteration hai g ( x ) = x − f ′ f g ′ ( r ) = 0 Order of Convergence — formally define karta hai ki "quadratic" ka matlab kya hai.Multiple Roots — jahan method slow ho jaata hai.
truncate linear term, analytic route B
Taylor expand f around x_n
Exact Taylor remainder at root r
Quadratic convergence, error squares each step
