Implementing root-finding from scratch — Newton-Raphson, bisection: Question bank

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

True or false — justify

Bisection guaranteed hai ki

[a, b]

par kisi bhi function ka root dhundhega jab

f (a) f (b) < 0

ho.

False. Isko

f

[a, b]

par continuous hona chahiye; guarantee Intermediate Value Theorem se aati hai, jiske liye koi jump nahi hona chahiye.

f (x) = 1/ x

par

[- 1, 1]

ke upar signs flip karte hain lekin koi root nahi hai — "crossing" ek vertical asymptote hai.

Agar

f (a) f (b) > 0

ho toh

[a, b]

mein definitely koi root nahi hai.

False. Iska sirf matlab hai ki bisection shuru nahi ho sakta. Ek parabola jaise

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

[- 2, 2]

mein

f (- 2) f (2) = 2 \cdot 2 > 0

hai phir bhi do roots hain — even number of crossings sign change ko chupa deti hai.

Newton-Raphson ko hamesha bisection se kam

f

-evaluations chahiye honge tolerance hit karne ke liye.

Cost mein False hai, chahe step count mein true bhi ho. Har Newton step par ek

f

aur ek

f^{'}

evaluation lagti hai, toh ek iteration roughly do guna expensive hai; faayda tabhi dikhta hai jab root ke paas quadratic convergence kick kare.

Quadratic convergence ka matlab hai error har step par square hoti hai, toh error kahan se bhi shuru karo, sidhti jaati hai.

False.

e_{n + 1} \approx C e_{n}^{2}

law ek local statement hai — yeh tabhi hold karta hai jab

e_{n}

chhota ho. Door se,

e_{n}^{2}

e_{n}

se bada ho sakta hai, toh "squaring" cheezein better nahi, balki worse banata hai.

Tolerance

ε

ko half karne par bisection ko ek extra iteration lagti hai.

True. Steps

lo g_{2} \frac{b - a}{ε}

jaise scale karte hain;

ε

ko 2 se divide karne par us count mein exactly

lo g_{2} 2 = 1

add hota hai — har step par accuracy ka ek aur bit.

Newton's method Fixed-point iteration ka ek special case hai.

True.

g (x) = x - \frac{f ( x )}{f ^{'} ( x )}

likhne par, Newton sirf

x_{n + 1} = g (x_{n})

iterate kar raha hai;

f

ka root

g

ka fixed point hai, aur

g^{'} (x^{*}) = 0

exactly wahi reason hai ki yeh quadratically converge karta hai.

Secant method sirf Newton hai jisme derivative ko do points ke beech ke slope se replace kar diya gaya ho.

True. Yeh

f^{'} (x_{n})

ki jagah

\frac{f ( x _{n} ) - f ( x _{n - 1} )}{x _{n} - x _{n - 1}}

use karta hai, koi derivative nahi chahiye; keemat hai slower (order

\approx 1.618

, 2 nahi) convergence.

Bisection ki convergence rate

f

ki shape par depend karti hai.

False. Bracket width har step par half hoti hai chahe

f

kuch bhi ho — rate hamesha exactly

\frac{1}{2}

hai. Sirf starting width

b - a

aur root bracket ke andar kahaan hai woh constant ko affect karta hai, ratio ko nahi.

Spot the error

"Main fa ek baar store karunga, phir har loop mein check karunga if f(a)*f(m) < 0." — kya galat hai?

Tum har iteration mein f(a) recompute kar rahe ho (wasted calls) — aur isse bhi bura, jab tum a move karte ho, toh woh nayi f(a) ek naya value hai jabki tumhara logic purana sign assume kar raha ho sakta hai. Stored fa ko fm se compare karo aur fa tabhi update karo jab tum left endpoint rakhte ho.

"Meri bisection ne midpoint return kar diya chahe f(a)f(b)>0 tha, toh phir bhi kaam kiya."

Yeh ek red flag hai. Koi sign change nahi hone par return kiya gaya midpoint meaningless hai — shayad koi root hi nahi hai. Routine ko bad bracket par raise karna chahiye, na ki chupke se ek number return karna.

"Newton diverge ho gaya, toh mera derivative formula galat hoga." — kya yahi akela cause hai?

Nahi. Sahi

f^{'}

bhi diverge karta hai agar

x_{0}

door ho, agar

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

ho (giant step), ya agar iterates cycle karein. Algebra bug suspect karne se pehle starting guess aur flat-derivative cases check karo.

"Newton rok ne ke liye main f(x) == 0 test karta hun."

Floating point arithmetic almost kabhi exactly 0 par nahi utarta, toh yeh rarely trigger hota hai aur tum maxit tak loop karte ho. abs(step) < tol (ya abs(f(x)) < tol) test karo — ek exact hit nahi, ek neighbourhood.

"Bisection tab ruk jaati hai jab f(m) == 0 ho, toh (b-a)/2 < tol check redundant hai."

Ulta hai. Exact-zero case rare hai; width test hi woh hai jo normally loop khatam karta hai. Ise hata do aur bisection almost har real problem par maxit tak chala jaayega.

"Maine bisection(f, 2, 1, ...) (a>b) pass kiya aur garbage mila."

Width

b - a

ab negative hai, toh (b-a)/2 < tol turant true hoti hai aur tum step zero par exit karte ho. Bisection assume karta hai

a < b

; ya toh endpoints sort karo ya precondition document karo.

"Newton on

x^{2} - 2

starting at

x_{0} = 0

theek hai, yeh ek sundar smooth function hai."

f^{'} (0) = 2 \cdot 0 = 0

, toh pehla hi step zero se divide karta hai — tangent horizontal hai aur kabhi x-axis se nahi milti. Smoothness kaam nahi aata; ek zero derivative tumhe le doobata hai.

Why questions

Bisection ko har step par ek bit accuracy kyun milti hai, na zyada na kam?

Har step interval ko half karta hai, aur halving ka matlab hai leading uncertain binary digit known ho jaata hai — exactly ek bit. Yeh bisection ko conceptually Binary search se jodata hai, jo bhi har comparison mein half space discard karta hai.

Newton ko quadratic convergence ke liye root par

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

kyun chahiye?

Error law mein

\frac{f ^{''} ( x ^{*} )}{2 f ^{'} ( x ^{*} )}

carry hota hai; agar

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

ho toh yeh constant blow up ho jaata hai. Geometrically root ek tangent touch hai (repeated root), tangent line nearly flat hai, aur convergence merely linear ho jaati hai.

Newton ki speed explain karne ke liye Taylor Series tangent draw karne se better tool kyun hai?

Tangent picture dikhata hai ki Newton kya karta hai;

x^{*}

ke around

f

ki Taylor expansion leftover error term

\propto e_{n}^{2}

quantify karta hai, humein batata hai kitni tezi se. Picture intuition deta hai, series exponent deta hai.

brentq jaisa hybrid dono pure methods ko kyun beat kar sakta hai?

Yeh ek guaranteed bracket rakhta hai (bisection ki safety) lekin usme fast interpolation try karta hai (Newton/secant-like speed), aur jab bhi fast guess bracket se bahar jaaye tab bisection step par fallback karta hai — tumhe robustness aur speed milti hai. Dekho scipy.optimize.

scipy.optimize.brentq ko derivative ki zaroorat kyun nahi jabki Newton ko hai?

Brent Secant method aur inverse-quadratic interpolation use karta hai, dono sirf function values se curvature estimate karte hain — koi

f^{'}

callback required nahi, isliye yeh black-box functions ke liye go-to hai.

"Step size below tolerance" "function value below tolerance" se better stopping test kyun hai?

Steep root ke paas tiny

x

-error bada

∣ f ∣

deta hai, toh ek

∣ f ∣

test kabhi trigger nahi ho sakta; flat root ke paas bada

x

-error tiny

∣ f ∣

deta hai, toh

∣ f ∣

test bahut jaldi ruk jaata hai. Step

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

actual position change measure karta hai aur zyada predictably behave karta hai.

Edge cases

Bisection mein kya hota hai jab root exactly endpoint par ho, jaise

f (a) = 0

Tab

f (a) f (b) = 0

hoga,

< 0

nahi, toh bracket test fail ho jaata hai aur loop kabhi run nahi karta — ek real root miss ho jaata hai. Isliye tum loop se pehle endpoints check karke return karte ho.

Newton

f (x) = x^{1/3}

par root ke alawa kahin se bhi shuru ho toh kya karta hai?

Yeh diverge karta hai — har step opposite side par aur door jaata hai:

x_{n + 1} = - 2 x_{n}

. 0 par root ka tangent infinite-slope hai, toh linear model jhooth hai aur iterates bhaag jaate hain. Bisection ise nail kar deta.

Do roots ek bracket ke andar hain, jaise

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

[0, 2]

[- 2, 2]

— bisection kya deta hai?

[0, 2]

par ek sign change hai toh yeh

2

dhundhta hai;

[- 2, 2]

par signs match karte hain (

f (- 2) f (2) > 0

) toh yeh start karne se mana kar deta hai. Bisection ek valid odd-crossing bracket mein ek root dhundhta hai, kabhi promise nahi karta kaun sa agar tum even count ghus aao.

Bilkul flat plateau: Newton ke dauran

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

— code ko kya karna chahiye?

Division by zero (flat tangent, koi x-intercept nahi). Error raise karo ya guess nudge karo; blindly

f / f^{'}

compute karne par inf/nan milta hai aur run silently corrupt ho jaata hai.

Newton cycles:

x_{0} \to x_{1} \to x_{0} \to \dots

hamesha — kya yeh possible hai?

Haan. Kuch

f

aur starting points ke liye tangent do values ke beech bounce karta hai aur kabhi converge nahi karta (jaise kuch odd functions jo root ke baare mein symmetric hain). Sirf ek maxit guard tumhe bachata hai — step size kabhi tol se neeche nahi shrinkta.

Bracket astronomically wide hai, maan lo

[- 1 0^{9}, 1 0^{9}]

— kya bisection tab bhi theek hai?

Haan, sirf log se slower: width

2 \cdot 1 0^{9}

ε = 1 0^{- 9}

ke liye lagbhag

lo g_{2} (2 \cdot 1 0^{9} / ε) \approx 61

steps chahiye. Linear-per-bit ka matlab hai ki bahut bade brackets par bhi sirf tens of iterations lagte hain — robustness size ko hardly notice karta hai.

Agar

f

bracket mein kahin NaN return kare (jaise negative

x

ke liye

x

) toh kya hoga?

NaN ke saath har sign comparison False hai, toh bisection baar baar galat half rakh sakti hai aur garbage value par converge kar sakti hai. NaN/inf function outputs se guard karo; ek valid bracket assume karta hai ki

f

[a, b]

paar defined hai.

Recall Ek-line summary

Bisection speed ke badle ek pakka guarantee leta hai (continuity + sign change chahiye); Newton guarantee ke badle quadratic speed leta hai (derivative chahiye, accha start chahiye, aur flat root nahi hona chahiye). Upar har trap unhi preconditions mein se ek hai jo chupke se violate ho rahi hai.