Newton-Raphson method for root finding — Hinglish notes

4.1.33 · Maths › Calculus I — Limits & Derivatives

Method kya hai?

HAR PIECE KA MATLAB

$f (x_{n})$ : abhi hum zero se kitna upar/neeche hain.
$f^{'} (x_{n})$ : current guess par tangent ki slope.
$f (x_{n}) / f^{'} (x_{n})$ : tangent kitni horizontal distance travel karke axis tak pahunhchti hai.

Isse scratch se derive karo (tangent-line argument)

Alternative derivation (Taylor series — dikhata hai yeh itna fast kyun hai)

$f$ ko $x_{n}$ ke paas expand karo aur demand karo $f (root) = 0$ : $0 = f (x_{n}) + f^{'} (x_{n}) (r - x_{n}) + \frac{1}{2} f^{''} (ξ) (r - x_{n})^{2}$ Quadratic term drop karne aur $r$ ke liye solve karne par wohi formula milta hai. Discarded term $O ((r - x_{n})^{2})$ hai — yahi quadratic convergence ki buniyaad hai: error roughly har step mein square ho jaati hai.

Figure — Newton-Raphson method for root finding

Worked Example 1 — $2$ compute karo

$f (x) = x^{2} - 2 = 0$ solve karo, toh $f^{'} (x) = 2 x$ . Iteration: $x_{n + 1} = x_{n} - \frac{x _{n}^{2} - 2}{2 x _{n}} = \frac{x _{n}}{2} + \frac{1}{x _{n}}$ Yeh step kyun? Simplify karne par classic "apne guess ka $2/ x$ ke saath average karo" formula milta hai.

$x_{0} = 1$ se shuru karo:

$x_{1} = \frac{1}{2} + 1 = 1.5$ — Kyun? $x_{0} = 1$ plug in karo.
$x_{2} = 0.75 + 0.6667 = 1.41667$ — Kyun? $x_{1}$ wapas feed karo.
$x_{3} = 1.41421568...$ — Kyun? ek aur pass; ab 6 digits tak sahi.

Saccha $2 = 1.41421356...$ — compare karo $x_{2} = 1.41667$ (3 sahi digits: $1, 4, 1$ ) ko $x_{3} = 1.41421568$ se (6 sahi digits: $1, 4, 1, 4, 2, 1$ ). Ek step mein sahi digits roughly double ho gayi (3→6), yahi quadratic convergence ki pehchaan hai.

Worked Example 2 — ek transcendental root

$f (x) = cos x - x = 0$ solve karo, $f^{'} (x) = - sin x - 1$ . $x_{n + 1} = x_{n} - \frac{c o s x _{n} - x _{n}}{- s i n x _{n} - 1}$ $x_{0} = 1$ (radians) se shuru karo:

$f (1) = 0.5403 - 1 = - 0.4597$ , $f^{'} (1) = - 0.8415 - 1 = - 1.8415$ . Kyun? dono ko guess par evaluate karo.
$x_{1} = 1 - \frac{- 0.4597}{- 1.8415} = 1 - 0.2497 = 0.7503$ .
$x_{2} \approx 0.73911$ , $x_{3} \approx 0.73909$ — Dottie number par converge ho gaya.

Worked Example 3 — jab yeh BIGAD JAATA HAI

$f (x) = x^{3} - 2 x + 2 = 0$ solve karo $x_{0} = 0$ se. $f^{'} (x) = 3 x^{2} - 2$ , toh $f^{'} (0) = - 2$ .

$x_{1} = 0 - \frac{2}{- 2} = 1$ .
$f (1) = 1$ , $f^{'} (1) = 1$ , $x_{2} = 1 - 1 = 0$ .
Wapas $0$ par! Iteration cycle karta hai $0 \to 1 \to 0 \to \dots$ hamesha ke liye. Yeh kyun matter karta hai: Newton-Raphson local hai, globally guaranteed nahi.

Common mistake Classic errors ko steel-man karo

1. "Agar root exist karta hai toh yeh hamesha converge karta hai." Kyun sahi lagta hai: tangent trick itni clean hai ki foolproof lagti hai. Fix: convergence ke liye kaafi achha starting guess aur well-behaved $f^{'}$ chahiye. Example 3 cycle karta hai; bure guesses diverge kar sakte hain.

2. "Bas iterate karo, $f^{'} (x_{n})$ check mat karo." Kyun sahi lagta hai: aap rarely exactly flat spot par padte ho. Fix: agar $f^{'} (x_{n}) \approx 0$ hai, toh tangent lagbhag horizontal hai aur $x_{n + 1}$ ko bahut door shoot kar deti hai. Chhoti derivatives ke khilaf hamesha guard karo.

3. "Har root par quadratic convergence." Kyun sahi lagta hai: humne prove kiya ki error square hoti hai. Fix: woh proof simple root maanta tha ( $f^{'} (root) \neq = 0$ ). Double root par convergence sirf linear rah jaati hai (errors half hoti hain, square nahi).

4. Sign slip: $x_{n + 1} = x_{n} + f / f^{'}$ likhna. Fix: yeh minus hai — aap overshoot subtract karte ho. $2$ se sanity check karo: $1 + 1/1 = 2$ door jaata hai, jabki $1 - (- 1) /2 = 1.5$ paas aata hai.

Recall Feynman: 12 saal ke bacche ko explain karo

Socho curve ek andhera pahaad hai aur aap sirf apne paon ke neeche ki slope feel kar sakte ho. Aap dekh nahi sakte ki zameen samudra ke level par kahan milti hai. Toh aap pretend karte ho ki pahaad bilkul seedha rehta hai (jo slope aap feel karte ho) aur aap wahan chalte ho jahan woh seedhi line samudra ke level ko chhooti hai. Aap abhi wahan nahi hain, lekin aap kareeb hain. Aap phir slope feel karte ho, nayi seedhi line kheenchte ho, phir chalte ho. Kuch walks ke baad aap almost exactly us jagah khade hain — aur har walk aapki bachi hui doori ko bahut zyaada kam karta hai, sirf thoda nahi.

Flashcards

Newton-Raphson update formula kya hai?

x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}

Formula kis geometric object se derive hota hai?

(x_{n}, f (x_{n}))

par tangent line se, yeh dekhte hue ki woh

x

-axis kahan cross kaarti hai.

f / f^{'}

add karne ki bajay subtract kyun karte hain?

Aap current error ke against move karte ho: term

f / f^{'}

woh horizontal jump hai jo tangent zero tak pahunchne ke liye leta hai.

Simple root par NR ki convergence rate kya hai?

Quadratic — error roughly har step mein square hoti hai (sahi digits double ho jaati hain).

Kaun si condition NR ko blow up ya oscillate kara sakti hai?

f^{'} (x_{n}) \approx 0

(near-horizontal tangent) ya bura starting guess; yeh cycle ya diverge kar sakta hai.

Double root par convergence ka kya hota hai?

Yeh quadratic se linear mein degrade ho jaati hai.

f (x) = x^{2} - a

ke zariye

a

ke liye Newton-Raphson iteration?

x_{n + 1} = \frac{1}{2} (x_{n} + \frac{a}{x _{n}})

Typically kaun sa stopping criterion use kiya jaata hai?

∣ x_{n + 1} - x_{n} ∣ < ε

∣ f (x_{n}) ∣ < ε

Quadratic-convergence guarantee kahan se aati hai?

Dropped Taylor term

O ((error)^{2})

hai, isliye agली error current error ke square ke proportional hai.

Connections

Tangent line and linear approximation — NR hai hi repeated linearization.
Taylor series — quadratic convergence explain karta hai.
Derivatives — definition and rules — $f^{'}$ supply karta hai.
Fixed-point iteration — NR ek special, fast fixed-point scheme hai $g (x) = x - f / f^{'}$ .
Bisection method — slower lekin guaranteed; aksar NR ke saath combine hota hai (safeguarded Newton).
Roots of polynomials — common application domain.