Implementing root-finding from scratch — Newton-Raphson, bisection: Visual walkthrough

5.4.25 · D2 · Coding › Scientific Computing (Python) › Implementing root-finding from scratch — Newton-Raphson, bis

Step 1 — "Root" kya hota hai, ek picture mein?

KYA. Hum ek wiggly curve draw karte hain. Horizontal line woh jagah hai jahan height $= 0$ ho. Ek root woh koi bhi jagah hai jahan curve us zero-line ko touch karta ya cross karta hai.

KYUN. Har root-finding method ek specific $x$ value ki talaash hai: woh wali jo kisi crossing point ke seedha neeche (ya upar) ho. Agar hum yeh nahi dekh sakte ki hum kya dhundh rahe hain, toh baad ki algebra sirf shor hai. Isliye hum poore page ko ek picture se anchor karte hain: root = ek crossing ka x-coordinate.

PICTURE. Figure mein curve black mein draw hai; single red dot exactly wahan baitha hai jahan woh zero-line ko chhedta hai. Us dot ki horizontal position ko $x^{*}$ kaho (padho "x-star" — star matlab woh asli jawab jo hum abhi nahi jaante).

Figure — Implementing root-finding from scratch — Newton-Raphson, bisection

Step 2 — Sign change kya hota hai, aur yeh root ko kaise trap karta hai

KYA. Do points chuno — $a$ (left) aur $b$ (right). Dono heights $f (a)$ aur $f (b)$ padho. Agar ek zero-line ke neeche (negative) hai aur doosra upar (positive), toh humein ek sign change mila.

KYUN. Ek continuous curve zero-line ke neeche se upar nahi ja sakta bina us line ko kahin beech mein touch kiye — woh "kahin" ek root hai. Yahi Intermediate Value Theorem hai saral shabdon mein. Yeh woh ek hi guarantee hai jo hume free mein milti hai, aur bisection poori tarah isi par bani hai.

PICTURE. $f (a)$ neeche point karta hai (negative, black arrow axis ke neeche); $f (b)$ upar point karta hai (positive). Red segment region $[a, b]$ ko mark karta hai jo ab ek crossing contain karne ki guarantee rakhta hai.

Step 3 — Bisection: trapped region ko half mein kato

KYA. Midpoint $m = \frac{a + b}{2}$ lo aur uski height $f (m)$ mapo. $f (m)$ ke sign ko $f (a)$ ke sign se compare karo.

KYUN. Root kahin $[a, b]$ mein hai. Midpoint us region ko do equal halves mein split karta hai. Root us half mein rehta hai jisme abhi bhi sign change dikhta ho. Hum woh half rakhte hain, doosra phenk dete hain — aur ab uncertainty exactly half reh jaati hai jo pehle thi.

PICTURE. Poora bracket black hai. Midpoint $m$ red tick hai. Kept half (jiske ends par abhi bhi opposite sign hai) shaded hai; discarded half faded hai.

Ab naam dete hain jo shrink hota hai. Surviving interval ki length ko uski width kaho. Hum yeh cut baar baar karte hain — pehla cut, doosra cut, teesra cut — toh $n$ se count karte hain kitne cuts ab tak ho chuke hain, aur $w_{n}$ likhte hain un $n$ cuts ke baad ki width ke liye. Toh $w_{0} = b - a$ starting width hai (abhi zero cuts), $w_{1}$ ek cut ke baad ki width hai, wagairah. Yeh exactly woh loop hai jo $n$ baar run hota hai.

Ek cut ke baad kaun sa half bachta hai? ::: Woh jiske dono endpoints ki heights ke abhi bhi opposite signs hon.
Bisection reliability mein kyun unbeatable hai? ::: Yeh root ko shrinking bracket se kabhi escape nahi karne deta — trap sirf tighter hota jaata hai.

Step 4 — Newton ka idea: curve ko uski tangent se replace karo

KYA. Curve par guess $x_{n}$ par khado. Woh straight line draw karo jo wahan curve ko just graze kare — tangent line. Uski steepness $f^{'} (x_{n})$ kehlati hai (padho "f-prime"), woh spot par curve ka slope.

KYUN. Curve kahan zero hit karta hai dhundhna mushkil hai. Straight line kahan zero hit karti hai dhundhna primary school algebra hai. Toh Newton ka trick ek swap hai: sirf ek step ke liye maan lo ki curve APNI tangent line HI hai, aur line ke easy zero ko next guess banao. $x_{n}$ ke paas tangent curve se chipki rehti hai, toh uska zero asli root ke paas land karta hai.

PICTURE. Black curve, guess $x_{n}$ par touch karne wali red tangent line. Dekho red line neeche zero-line cross karne ke liye jaati hai ek naye point par — woh crossing hamara next guess hai.

Step 5 — Tangent se update derive karo, term by term

KYA. Us red tangent line ki equation likho aur pucho: yeh height zero kahan hit karti hai?

KYUN. Woh zero-crossing hi next guess $x_{n + 1}$ hai. Uske liye solve karna exact Newton formula deta hai — koi magic nahi, sirf line-crossing algebra.

PICTURE. Wahi tangent, ab do moving parts labelled hain: current height $f (x_{n})$ (vertical black drop) aur horizontal jump $x_{n + 1} - x_{n}$ (red arrow axis ke along).

Point $(x_{n}, f (x_{n}))$ se slope $f^{'} (x_{n})$ wali line:

$line par height y = start height f (x_{n}) + slope f^{'} (x_{n}) horizontal walk (x - x_{n})$

Hum crossing chahte hain, toh $y = 0$ set karo aur special $x$ ko $x_{n + 1}$ naam do:

$0 = f (x_{n}) + f^{'} (x_{n}) (x_{n + 1} - x_{n})$

Horizontal walk isolate karo (subtract karo, phir slope se divide karo):

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

$x_{n + 1} = x_{n} - \frac{f ( x _{n} ) zero se kitna dur}{kitna steep f ^{'} ( x _{n} )}$

Step 6 — Degenerate case: flat tangent ( $f^{'} = 0$ )

KYA. Maan lo $x_{n}$ par tangent horizontal hai — slope $f^{'} (x_{n}) = 0$ .

KYUN. Ek horizontal line zero-line ko kabhi cross nahi karti (jab tak woh zero-line hi na ho). Algebraically hum $\frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ mein zero se divide karenge. Step undefined hai — method ke paas koi next guess nahi hai.

PICTURE. Red horizontal tangent sides ki taraf shoot kar rahi hai, axis se kabhi nahi milti; "next guess" infinity ki taraf fly karta hai.

Jab $f^{'} (x_{n}) = 0$ hota hai toh geometrically kya galat hota hai? ::: Tangent horizontal hoti hai, uska koi zero-crossing nahi hota, aur update zero se divide karta hai — step undefined / infinite ho jaata hai.

Step 7 — Doosra degenerate case: endpoint already ek root hai

KYA. Bisection mein koi caller tumhe $[a, b]$ de sakta hai jahan $f (a) = 0$ (ya $f (b) = 0$ ) exactly ho.

KYUN. Tab $f (a) \cdot f (b) = 0$ hoga, jo not $< 0$ hai. Strict bracket test fail ho jaata hai, loop kabhi run nahi karta, aur tum ek perfectly good root jo endpoint par hi baitha hai phenk doge.

PICTURE. Curve exactly $a$ par zero-line ko graze karta hai — red dot boundary par baitha hai, andar nahi.

Agar $f (a) = 0$ exactly ho aur tum endpoint check skip karo toh kya hoga? ::: Product $f (a) f (b) = 0$ hai jo $< 0$ nahi hai, loop kabhi run nahi karta, aur $a$ par asli root discard ho jaata hai.

Step 8 — Newton digits kyun double karta hai (quadratic convergence)

KYA. $e_{n} = x_{n} - x^{*}$ ko error maano — guess asli root se kitna door hai. Hum track karte hain ki $e_{n + 1}$ kaise $e_{n}$ par depend karta hai.

KYUN. Yeh payoff picture hai: Newton ka error previous error ke square ke proportional nikalta hai. Ek chhote number ko square karna use tiny bana deta hai — isliye correct digits roughly har step double hote hain. Lekin is claim ko earn karne ke liye hume isse derive karna hoga, aur derive karne ke liye ek aur tool chahiye: second derivative.

PICTURE. Do nested red gaps: step $n$ par ek wide gap $e_{n}$ , aur step $n + 1$ par dramatically narrow gap $e_{n + 1} \approx (const) e_{n}^{2}$ .

Derivation, term by term. Hum Taylor Series use karte hain — woh recipe jo ek curve ko ek point ke paas uski height, slope, aur bending se rebuild karti hai. $f$ aur $f^{'}$ ko asli root $x^{*}$ ke aaspaas expand karo, yeh maante hue ki $f$ twice differentiable hai taaki $f^{''}$ exist kare. Sab kuch error $e_{n} = x_{n} - x^{*}$ ke terms mein likho:

$f (x_{n}) = = 0 f (x^{*}) + f^{'} (x^{*}) e_{n} + \frac{1}{2} f^{''} (x^{*}) e_{n}^{2} + \dots$

Pehla term $0$ hai kyunki $x^{*}$ ek root hai. Toh $f (x_{n}) \approx f^{'} (x^{*}) e_{n} + \frac{1}{2} f^{''} (x^{*}) e_{n}^{2}$ .

$f^{'} (x_{n}) = f^{'} (x^{*}) + f^{''} (x^{*}) e_{n} + \dots$

Ab Newton correction banao aur dono sides se $x^{*}$ subtract karo. Kyunki $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ aur $x_{n} - x^{*} = e_{n}$ :

$e_{n + 1} = e_{n} - \frac{f ^{'} ( x ^{*} ) e _{n} + \frac{1}{2} f ^{''} ( x ^{*} ) e _{n}^{2}}{f ^{'} ( x ^{*} ) + f ^{''} ( x ^{*} ) e _{n}}$

Ab key move — WHY leading terms cancel karte hain. Fraction ke top aur bottom se $f^{'} (x^{*})$ factor out karo taaki uska shape clearly dikhe. Maano $r = \frac{f ^{''} ( x ^{*} )}{f ^{'} ( x ^{*} )}$ (ek fixed number: bending divided by slope). Tab

$\frac{f ( x _{n} )}{f ^{'} ( x _{n} )} = e_{n} \cdot \frac{1 + \frac{1}{2} r e _{n}}{1 + r e _{n}} .$

Messy part hai $\frac{1 + \frac{1}{2} r e _{n}}{1 + r e _{n}}$ . Chhote $e_{n}$ ke liye hum $\frac{1}{1 + r e _{n}}$ ko geometric series $1 - r e_{n} + (r e_{n})^{2} - \dots$ ki tarah expand karte hain (yeh binomial/geometric expansion hai; valid hai kyunki $r e_{n}$ tiny hai, toh squared-aur-higher terms negligible hain). Multiply out karo aur sirf $e_{n}$ tak rakho:

$\frac{1 + \frac{1}{2} r e _{n}}{1 + r e _{n}} = (1 + \frac{1}{2} r e_{n}) (1 - r e_{n} + \dots) = 1 - \frac{1}{2} r e_{n} + \dots$

Toh poori correction hai

$\frac{f ( x _{n} )}{f ^{'} ( x _{n} )} = e_{n} (1 - \frac{1}{2} r e_{n} + \dots) = e_{n} - \frac{1}{2} r e_{n}^{2} + \dots$

Ise $e_{n}$ se subtract karo — aur yahan $e_{n}$ terms exactly cancel ho jaate hain, yahi poora point hai: $+ e_{n}$ aur $- e_{n}$ annihilate ho jaate hain, sirf squared piece bachta hai:

$e_{n + 1} = e_{n} - (e_{n} - \frac{1}{2} r e_{n}^{2} + \dots) = \frac{1}{2} r e_{n}^{2} + \dots$

$e_{n + 1} \approx fixed bending constant \frac{f ^{''} ( x ^{*} )}{2 f ^{'} ( x ^{*} )} error, squared e_{n}^{2}$

Jo kuch hum ne drop kiya (woh " $\dots$ ") woh $e_{n}^{3}$ ya usse chhote terms ke proportional hai — tiny $e_{n}$ ke liye woh $e_{n}^{2}$ ke against bilkul negligible hain, yahi wajah hai ki hum unhe phenk sakte hain. Boxed line quietly assume karti hai ki $f^{'} (x^{*}) \neq = 0$ (warna $r$ zero se divide hoga — Step 6 wali Newton ki flat-spot bimari, ab root par hi) aur $f$ twice differentiable (warna $f^{''}$ ka koi matlab nahi aur expansion collapse ho jaata hai).

Agar $e_{n} = 1 0^{- 3}$ (3 good digits), tab $e_{n}^{2} = 1 0^{- 6}$ — 6 good digits. 3 → 6 → 12, parent ke worked example $x_{0} = 2$ for $2$ se match karta hai. Compare bisection se: woh error ko $\frac{1}{2}$ se multiply karta hai har step, sirf ek bit kharidta hai — yeh linear-vs-quadratic speed gap hai, aur isliye scipy.optimize ka brentq ek bracket (safety) ko fast interpolation (Secant method idea) ke saath blend karta hai.

Ek picture mein summary

Ek hi canvas, dono methods ek hi curve par: bisection ka shrinking red bracket dono sides se crawl karta hai; Newton ke red tangents root ki taraf leap karte hain. Slow-but-safe versus fast-but-fragile.

Recall Feynman retelling — plain words mein wapas bolo

Root wahan hota hai jahan curve zero-line ko touch kare. Agar curve line ke neeche hai ek jagah aur upar doosri jagah, toh beech mein zaroor cross kiya hoga — yahi root ka trap hai. Bisection is trap ka faayda uthata hai: middle check karo, woh half rakho jo abhi bhi line straddle karta ho, aur trap har baar half ho jaata hai. Dead slow, kabhi fail nahi.

Newton impatient hai. Woh curve par khada hota hai, woh straight line draw karta hai jo wahan use graze kare, aur us line par slide karta hai jahan line zero hit kare — kyunki straight line ka zero compute karna trivial hai. Woh landing spot next guess hai. Formula "current height ÷ steepness, backwards step" wahi line-crossing hai kaagaz par solve kiya hua. Jab slope healthy ho, har jump roughly error ko square kar deta hai (kyunki tangent sirf curve ki bending miss karta hai, jo $f^{''}$ se measure hoti hai), toh correct digits double ho jaate hain — lekin agar slope flat ho jaaye, toh line axis se kabhi nahi milti, step blow up ho jaata hai, aur Newton bhaag jaata hai. Yahi poora story hai: bisection ek trap tighten karta hai; Newton ek tangent par ride karta hai; ek safe hai, doosra fast, aur pros dono ko glue karke use karte hain.

Flashcards

Geometrically, Newton ka next-guess

x_{n + 1}

kya hai?

Woh point jahan

x_{n}

par tangent line zero-line cross karti hai (tangent ka x-intercept).

Newton formula mein

f^{'} (x_{n})

se divide karne par step ka kya hota hai?

Steep slope chhota step deta hai; flat slope bahut bada (dangerous) step deta hai — step hai height ÷ steepness.

Sign change

f (a) f (b) < 0

root guarantee kyun karta hai?

Ek continuous curve zero-line ke neeche se upar nahi ja sakta bina use touch kiye — Intermediate Value Theorem.

Jab

f^{'} (x_{n}) = 0

ho toh Newton geometrically kyun fail hota hai?

Tangent horizontal hai, isliye zero-line kabhi cross nahi karta; update zero se divide hota hai aur guess fly off ho jaata hai.

Bisection ko loop se pehle endpoints kyun check karne chahiye?

Agar

f (a) = 0

f (b) = 0

exactly ho, toh product

f (a) f (b) = 0

hai jo

< 0

nahi hai, strict bracket test fail ho jaata hai, loop skip ho jaata hai, aur boundary par baitha real root silently discard ho jaata hai; endpoint pehle return karna isse rokta hai.

Newton "digits double" kyun karta hai?

Uska error

e_{n + 1} \approx \frac{f ^{''} ( x ^{*} )}{2 f ^{'} ( x ^{*} )} e_{n}^{2}

follow karta hai; chhote error ko square karna roughly correct digits double kar deta hai.

Newton ki quadratic convergence ke liye kaun si do assumptions zaroori hain?

f^{'} (x^{*}) \neq = 0

(root par koi flat spot nahi) aur

f

twice differentiable (taaki

f^{''}

exist kare).