Exercises — Newton-Raphson method for root finding

KYA karte hain: rule ek baar apply karo. KYUN: L1 bas check karta hai ki tum $f$, $f^{\prime }$ identify karke plug in kar sako.

• $f(x)=x^2-5$, isliye $f^{\prime }(x)=2x$ (power rule from Derivatives — definition and rules).
• $x_0=2$ par: $f(2)=4-5=-1$ (hum axis ke neeche hain), $f^{\prime }(2)=4$ (slope upar ja raha hai). $x_1=2-\frac{-1}{4}=2+0.25=\mathrm{2.25.}$ Sanity check: $\sqrt{5}\approx 2.2360$, isliye $2.25$, $2$ se zyada close hai. Height negative thi, isliye hum right gaye (add kiya) — sign ne automatically direction ka khayal rakha.

KYUN yeh matter karta hai: iterate karne se pehle tumhe sahi se differentiate karna hoga; galat $f^{\prime }$ sab kuch kharab kar deta hai.

• $\frac{d}{dx}\cos x=-\sin x$ aur $\frac{d}{dx}(-2x)=-2$, isliye $f^{\prime }(x)=-\sin x-2$. $x_{n+1}=x_n-\frac{\cos x_n-2x_n}{-\sin x_n-2}.$

Galat plus sign ke saath: $x_1=2+\frac{-1}{4}=1.75$. Lekin $\sqrt{5}\approx 2.236$, isliye hum distance $0.236$ se distance $0.486$ tak jump kar gaye — aur door. Sahi minus sign ne $2.25$ diya (distance $0.014$). Subtraction hi hai jo tumhe root ki taraf point karta hai.

Set-up: $f^{\prime }(x)=3x^2$. Update rule mein seedha substitute karke, $x_{n+1}=x_n-\frac{x_n^3-7}{3x_n^2}.$ KYUN rearrange karein? Fraction ko split karna "purana guess minus ek correction" ko ek self-contained recipe mein badal deta hai jise tum ek pass mein evaluate kar sako, aur yeh step ki structure expose karta hai. Denominator ko numerator par distribute karo: $x_n-\frac{x_n^3}{3x_n^2}+\frac{7}{3x_n^2}=x_n-\frac{x_n}{3}+\frac{7}{3x_n^2}=\frac{2x_n}{3}+\frac{7}{3x_n^2}.$ Is form se kya pata chalta hai: $\frac{2x_n}{3}$ purane guess ka zyaadatar hissa rakhta hai, aur $\frac{7}{3x_n^2}$ true root ki taraf ek pull hai — yahi woh "weighted average" flavour hai jo Newton root-finding mein leta hai.

• $x_0=2$: $x_1=\frac{4}{3}+\frac{7}{12}=1.33333+0.58333=\mathrm{1.91667.}$
• $x_1=1.91667$: $x_1^3=7.0408$, isliye $x_2=1.91667-\frac{7.0408-7}{3(1.91667{)}^2}$ $=1.91667-\frac{0.0408}{11.0208}=1.91667-0.003705=\mathrm{1.91293.}$ Check: $\sqrt[3]{7}=1.912931\dots$ — do steps mein already 6 correct digits. Quadratic speed! $\epsilon =10^{-6}$ ke saath hum agले hi step par ruk jaate, kyunki $|x_3-x_2|$ iske neeche aa jaata hai.

$f^{\prime }(x)=2x-3$.

• $x_0=3$: $f=9-9+2=2$, $f^{\prime }=3$. $x_1=3-\frac{2}{3}=\mathrm{2.33333.}$
• $x_1=2.33333$: $f=5.44444-7+2=0.44444$, $f^{\prime }=1.66667$. $x_2=2.33333-0.26667=\mathrm{2.06667.}$ Guesses $x=2$ ki taraf girte hain. KYUN woh root aur $x=1$ nahi? Newton local hai: dono roots ke right se start karne par, tangent tumhe nazdiki root ki taraf point karta hai, jo $2$ hai.

KYUN yeh $f$: iska root $x=1/a$ hai, aur iska derivative re-divide karne se bachata hai.

• $f(x)=x^{-1}-a$, $f^{\prime }(x)=-x^{-2}$. $x_{n+1}=x_n-\frac{x_n^{-1}-a}{-x_n^{-2}}=x_n+x_n^2\left(\frac{1}{x_n}-a\right)=x_n(2-a{x}_n).$ Sirf multiplications — kitna elegant hai.
• $a=3$, $x_0=0.3$: $x_1=0.3(2-0.9)=0.3\times 1.1=\mathrm{0.33.}$
• $x_1=0.33$: $x_2=0.33(2-0.99)=0.33\times 1.01=\mathrm{0.3333.}$ Check: $1/3=0.33333\dots$ — bina kisi division ke converge ho raha hai.

Update: $x_{n+1}=\frac{x_n}{2}+\frac{1}{x_n}$. $\sqrt{2}=1.4142136$ ke saath:

• $x_0=1.5$, $e_0=\mathrm{0.0857864.}$
• $x_1=0.75+0.6666667=1.4166667$, $e_1=\mathrm{0.0024531.}$
• $x_2=0.7083333+0.7058824=1.4142157$, $e_2=\mathrm{0.0000021.}$ Analysis: theory kehti hai $e_{n+1}\approx \frac{f^{\prime \prime }}{2f^{\prime }}{e}_n^2=\frac{1}{2\sqrt{2}}{e}_n^2\approx 0.3536e_n^2$. Check: $0.3536\times e_0^2=0.3536\times 0.007359=0.002602$ vs actual $e_1=0.002453$ ✓. Aur $0.3536\times e_1^2=0.3536\times 6.018\times 10^{-6}=2.13\times 10^{-6}$ vs $e_2=2.1\times 10^{-6}$ ✓. Error sach mein square ho raha hai — yeh Taylor series convergence zinda jaagti hai.

$f^{\prime }(x)=3x^2-2$; note karo ki $f^{\prime }=0$ at $x=\pm \sqrt{2/3}\approx \pm 0.8165$. Humara start $0.9$ uss flat spot ke thoda aage hai.

• $x_0=0.9$: $f=0.729-1.8+2=0.929$, $f^{\prime }=2.43-2=0.43$ (bahut chhota!). $x_1=0.9-\frac{0.929}{0.43}=0.9-2.161=-\mathrm{1.261.}$ Yeh kaisa dikhta hai (neeche figure dekho): ek almost-horizontal tangent barely slope karta hai, isliye woh axis ko door tak hit karta hai — guess $0.9$ se $-1.26$ tak phek diya jaata hai. Yahi "small $f^{\prime }$" ka danger clearly visible hai.
• $x_1=-1.261$: $f=-2.005+2.522+2=2.517$, $f^{\prime }=4.770-2=2.770$. $x_2=-1.261-0.9086=-\mathrm{2.170.}$ Yeh ab $-1.77$ ke paas real root par home in karta hai.

$f^{\prime }(x)=2x-4=2(x-2)$. Update khoobsoorti se simplify hota hai: $x_{n+1}=x_n-\frac{(x_n-2{)}^2}{2(x_n-2)}=x_n-\frac{x_n-2}{2}=\frac{x_n+2}{2}.$ Isliye error $e_n=x_n-2$ follow karta hai $e_{n+1}=\frac{e_n}{2}$ — yeh linear hai, quadratic nahi.

• $x_0=3$ ($e_0=1$) → $x_1=2.5$ ($e_1=0.5$) → $x_2=2.25$ ($e_2=0.25$) → $x_3=2.125$. KYUN: quadratic-convergence proof ko chahiye $f^{\prime }(\text{root})\ne 0$. Double root par slope target par vanish ho jaati hai, "$f/f^{\prime }$" ratio $0/0$ ki tarah behave karta hai, aur tum squaring bonus kho dete ho.

"Intersection" ko "root" mein badlo: do curves milte hain jahaan unka difference zero hota hai, isliye $f(x)=e^{-x}-x$ lo. Phir $f^{\prime }(x)=-e^{-x}-1$. $x_{n+1}=x_n-\frac{e^{-x_n}-x_n}{-e^{-x_n}-1}.$

• $x_0=0.5$: $e^{-0.5}=0.606531$, $f=0.106531$, $f^{\prime }=-1.606531$. $x_1=0.5+0.066311=\mathrm{0.566311.}$
• $x_1=0.566311$: $e^{-0.566311}=0.567560$, $f=0.001249$, $f^{\prime }=-1.567560$. $x_2=0.566311+0.000797=\mathrm{0.567108.}$ Abhi khatam nahi: $|x_2-x_1|=0.000797>10^{-6}$, isliye tolerance test fail hoti hai — humein ek aur step lena hoga.
• $x_2=0.567108$: $e^{-0.567108}=0.567107$, $f=-1.0\times 10^{-6}$, $f^{\prime }=-1.567107$. $x_3=0.567108-0.00000064=\mathrm{0.567143.}$ Ab $|x_3-x_2|=6.4\times 10^{-7}<10^{-6}$, isliye hum $x\approx 0.567143$ par ruk jaate hain. Yeh special number (woh value $w$ jo $w{e}^w=1$ solve karta hai) omega constant kehlata hai; do curves exactly wahan ek hi baar milte hain.

Idea: $\ln 2$ woh number $x$ hai jiske liye $e^x=2$, yani $f(x)=e^x-2$ ka root. Phir $f^{\prime }(x)=e^x$. $x_{n+1}=x_n-\frac{e^{x_n}-2}{e^{x_n}}=x_n-1+2e^{-x_n}.$

• $x_0=0.7$: $e^{-0.7}=0.496585$. $x_1=0.7-1+0.993170=\mathrm{0.693170.}$
• $x_1=0.693170$: $e^{-0.693170}=0.499970$. $x_2=0.693170-1+0.999940=\mathrm{0.693110.}$ Abhi khatam nahi: $|x_2-x_1|=0.000060>10^{-6}$, isliye hum jaari rakhte hain.
• $x_2=0.693110$: $e^{-0.693110}=0.500000$. $x_3=0.693110-1+1.000000=\mathrm{0.693147.}$ Yahan $|x_3-x_2|=3.7\times 10^{-5}$ abhi bhi $>10^{-6}$ hai — aage badhte raho.
• $x_3=0.693147$: $e^{-0.693147}=0.5000000$. $x_4=0.693147-1+1.0000000=\mathrm{0.6931472.}$ Ab $|x_4-x_3|<10^{-6}$, isliye hum $x\approx 0.6931472$ par ruk jaate hain. Check: $\ln 2=0.6931472\dots$ — 7 digits tak match. Koi bhi $f$ sahi root ke saath kaam karta hai; ek clean $f^{\prime }$ bas arithmetic ko pleasant banata hai.

Update ko ek single function ke roop mein rewrite karo: $g(x)=x-\frac{f(x)}{f^{\prime }(x)}.$ Ek root $r$ satisfy karta hai $f(r)=0$, isliye $g(r)=r-0=r$ — yeh ek fixed point hai.

Ab $g$ differentiate karo, step by step. Term $x$ differentiate hokar $1$ deta hai, isliye humein sirf $\frac{d}{dx}\left[\frac{f(x)}{f^{\prime }(x)}\right]$ chahiye. Yeh ek quotient hai, isliye hum quotient rule ${\left(\frac{u}{v}\right)}^{\prime }=\frac{u^{\prime }v-u{v}^{\prime }}{v^2}$ use karte hain Derivatives — definition and rules se, jahan $u=f(x)$ aur $v=f^{\prime }(x)$:

• $u^{\prime }=f^{\prime }(x)$ ($f$ ka derivative),
• $v^{\prime }=f^{\prime \prime }(x)$ ($f^{\prime }$ ka derivative second derivative hai),
• $v^2=f^{\prime }(x{)}^2$.

Pieces ko rakhne par:

Pehle definitions: $e_n=x_n-r$ current error hai aur $e_{n+1}=x_{n+1}-r$ agla error; $r$ true root hai, isliye $f(r)=0$.

Step 1 — $f$ ko $x_n$ ke baare mein Taylor-expand karo, true root $r$ par evaluate karo (Taylor series se): $0=f(r)=f(x_n)+f^{\prime }(x_n)(r-x_n)+\frac{1}{2}{f}^{\prime \prime }(\xi )(r-x_n{)}^2.$ KYUN: hum jaante hain $f(r)=0$ exactly; Taylor's theorem remainder term ko $\xi$ ke saath (koi point $x_n$ aur $r$ ke beech) exact banata hai, approximate nahi — yahi hume error precisely pin down karne deta hai.

Step 2 — $r-x_n=-e_n$ substitute karo aur poori line ko $f^{\prime }(x_n)$ se divide karo (allowed hai kyunki simple root ke paas $f^{\prime }(x_n)\ne 0$ hota hai): $0=\frac{f(x_n)}{f^{\prime }(x_n)}-e_n+\frac{f^{\prime \prime }(\xi )}{2f^{\prime }(x_n)}{e}_n^2.$ KYUN $f^{\prime }(x_n)$ se divide karein: yeh exactly woh term $\frac{f(x_n)}{f^{\prime }(x_n)}$ manufacture karta hai jo Newton step mein appear hota hai, isliye hum ise agली line mein iterates ke difference se trade kar sakte hain.

Step 3 — Newton step pehchano aur errors mein convert karo. Update $x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$ rearrange hota hai $\frac{f(x_n)}{f^{\prime }(x_n)}=x_n-x_{n+1}$ mein. $e_n=x_n-r$ aur $e_{n+1}=x_{n+1}-r$ use karke, $x_n-x_{n+1}=(x_n-r)-(x_{n+1}-r)=e_n-e_{n+1}.$ Step 2 mein $\frac{f(x_n)}{f^{\prime }(x_n)}$ ki jagah yeh substitute karo: $0=(e_n-e_{n+1})-e_n+\frac{f^{\prime \prime }(\xi )}{2f^{\prime }(x_n)}{e}_n^2.$ KYUN: har term ab un errors mein express hai jo humein care hai, isliye algebra cleanly collapse hoti hai.

Step 4 — cancel karo aur $e_{n+1}$ solve karo. $e_n$ aur $-e_n$ cancel ho jaate hain: $0=-e_{n+1}+\frac{f^{\prime \prime }(\xi )}{2f^{\prime }(x_n)}{e}_n^2\Rightarrow \boxed{e_{n+1}=\frac{f^{\prime \prime }(\xi )}{2f^{\prime }(x_n)}{e}_n^2.}$ Agla error ek constant times current error ka square hai — quadratic convergence, proven. Kyunki $\frac{f^{\prime \prime }(\xi )}{2f^{\prime }(x_n)}$ simple root ke paas bounded rehta hai, error ko ek baar half karna roughly agले step mein correct-digit count double karta hai.

Samasya: Newton fast hai lekin unbracketed — ek chhota $f^{\prime }$ ya bura guess $x_{n+1}$ ko interest ke kisi bhi region ke bahar phenk sakta hai (L3.2 yaad karo aur parent note mein cycling example). Fix — ek bracket $[a,b]$ rakho jahan $f(a)f(b)<0$ (ek sign change root ko andar guarantee karta hai, intermediate value idea se jo Bisection method ke peeche hai). Har iteration mein:

1. Newton step propose karo $x_{\text{new}}=x_n-f(x_n)/f^{\prime }(x_n)$.
2. Reject test (precise): Newton step reject karo aur bisection use karo agar koi bhi ek condition ho:
   • $x_{\text{new}}\notin [a,b]$ (step bracket se bahar chali gayi), ya
   • $|f^{\prime }(x_n)|<\delta$ ek fixed chhote slope threshold ke liye, e.g. $\delta =10^{-8}$ (tangent trust karne ke liye bahut flat hai). Ek common alternative test yeh hai ki agar step bracket ko kam se kam half shrink karne mein fail kare, yani $|x_{\text{new}}-x_n|>\frac{1}{2}|b-a|$, toh reject karo.
   Reject hone par, guaranteed-safe bisection step lo $x_{\text{new}}=\frac{a+b}{2}$ (hamesha andar).
3. Bracket update karo: $a,b$ mein se jo $f$ ke sign share karta ho use $x_{\text{new}}$ se replace karo. KYUN kaam karta hai: jab guess achha ho tum Newton ki quadratic speed pate ho, aur jab Newton misbehave kare bisection ki guaranteed (agar slow) progress milti hai — bracket kabhi half se zyaada narrow hone se bura nahi.

$f^{\prime }(x)=\frac{1}{1+x^2}$, isliye update hai $x_{n+1}=x_n-(1+x_n^2)\arctan x_n.$ KYUN yeh explode kar sakta hai: bade $x$ ke liye, $\arctan x\to \frac{\pi }{2}$ jabki $(1+x^2)$ grow karta hai, isliye subtracted term massively overshoot karta hai — $|x_{n+1}|>|x_n|$, bahar ki taraf spiral karta hai. Critical point: converge aur diverge ke beech ki boundary woh jagah hai jahan step exactly equal magnitude ke saath sign flip karta hai, $x_{n+1}=-x_n$: $-x=x-(1+x^2)\arctan x\Rightarrow 2x=(1+x^2)\arctan x.$ Numerically solve karne par $x^{\ast }\approx 1.3917$ milta hai. $|x_0|<1.3917$ se shuru karo toh Newton $0$ par converge karta hai; $|x_0|>1.3917$ se shuru karo toh diverge karta hai (har step pichle se bada hota hai). Exactly $x^{\ast }$ par yeh hamesha ke liye $x^{\ast }\to -x^{\ast }\to x^{\ast }\to \cdots$ cycle karta hai. Neeche figure achhe starting guesses ki narrow red band dikhata hai.