Root finding — bisection method (convergence analysis)

4.8.6 · Maths › Numerical Methods

1. Setup aur guarantee

Method KYA karta hai (KAISE): baar baar midpoint $m = \frac{a + b}{2}$ compute karo, $f (m)$ evaluate karo, aur woh subinterval rakho jahan sign change survive kare:

Agar $f (a) f (m) < 0$ → root $[a, m]$ mein hai, set karo $b \leftarrow m$ .
Warna → root $[m, b]$ mein hai, set karo $a \leftarrow m$ .
Agar $f (m) = 0$ , seedha root pe land ho gaye — done.

Naya interval hamesha purani length ka aadha hota hai aur root ko bracket karta rehta hai.

Figure — Root finding — bisection method (convergence analysis)

2. Error bound scratch se derive karna

Step 1 — interval width recurrence. $L_{n}$ ko $n$ bisections ke baad ki length maano, starting $L_{0} = b_{0} - a_{0} = b - a$ se. $L_{n} = \frac{1}{2} L_{n - 1} .$ Ye step kyu? Har bisection literally interval ko aadha karta hai — yahi method ki definition hai.

Step 2 — recurrence solve karo. Unrolling karke: $L_{n} = \frac{1}{2} L_{n - 1} = (\frac{1}{2})^{2} L_{n - 2} = \dots = (\frac{1}{2})^{n} (b - a) = \frac{b - a}{2 ^{n}} .$ Ye step kyu? Baar baar aadha karna bas $\frac{1}{2}$ se $n$ baar multiply karna hai.

Step 3 — estimate choose karo. $n$ steps ke baad interval $[a_{n}, b_{n}]$ hai. Midpoint ko apna answer lo: $x_{n} = \frac{a _{n} + b _{n}}{2} .$ Ye step kyu? Midpoint sabse best single guess hai: true root aur $x_{n}$ dono $[a_{n}, b_{n}]$ mein hain, isliye worst-case distance width ka aadha hai, puri width nahi.

Step 4 — error bound lagao. True root $r$ , $[a_{n}, b_{n}]$ mein hai, aur $x_{n}$ bhi. Dono ke beech maximum distance interval ka aadha ho sakti hai:

3. Order of convergence: kyu "linear" hai

Bisection mein guaranteed error har step mein aadhi hoti hai: $e_{n + 1} \leq \frac{1}{2} e_{n} \Rightarrow \frac{e _{n + 1}}{e _{n}} \leq \frac{1}{2} .$ Isliye bisection linearly convergent hai rate (asymptotic constant) $C = \frac{1}{2}$ ke saath. Har iteration accuracy mein fixed factor of $2$ gain karta hai — yaani lagbhag $lo g_{10} 2 \approx 0.301$ decimal digits per step, toh roughly har $\approx 3.3$ iterations mein ek naya sahi decimal digit milta hai.

4. Ek tolerance ke liye kitne steps chahiye?

Hum chahte hain $∣ x_{n} - r ∣ \leq ε$ . Bound use karke:

\;\Longrightarrow\; 2^{\,n+1}\ge \frac{b-a}{\varepsilon} \;\Longrightarrow\; n \ge \log_2\!\left(\frac{b-a}{\varepsilon}\right) - 1.$$ > [!formula] Iteration count > $$\boxed{\,n \ge \left\lceil \log_2\!\frac{b-a}{\varepsilon}\right\rceil - 1\,}$$ > *Kyu useful hai:* ye kuch bhi run karne se **pehle** pata hota hai — bisection ka step count **predictable** hai, $f$ ki shape se independent. (Bahut se texts conservatively $n\ge \log_2\frac{b-a}{\varepsilon}$ use karte hain jab endpoint report karte hain.) --- ## 5. Worked examples > [!example] Example 1 — Pehle forecast, phir verify: kitne steps? > $f(x)=x^2-2=0$ solve karo $[1,2]$ pe tolerance $\varepsilon=10^{-6}$ ke liye. > > **Pehle forecast:** $b-a=1$. Chahiye $n\ge \log_2(1/10^{-6})-1 = \log_2(10^6)-1 \approx 19.93-1 \approx 18.93$. > Isliye **$n=19$** midpoint iterations kaam karenge. > > **Verify (KAISE har step):** > - $m_1=1.5,\ f=0.25>0$, aur $f(1)<0$ → root $[1,1.5]$ mein. *Kyu?* sign change left pe hai. > - $m_2=1.25,\ f=-0.4375<0$ → root $[1.25,1.5]$ mein. > - $m_3=1.375,\ f=-0.109<0$ → root $[1.375,1.5]$ mein. > - $m_4=1.4375,\ f=0.066>0$ → root $[1.375,1.4375]$ mein. > > 4 steps ke baad width $=1/2^4=0.0625$; $x_4$ ka error $\le 1/2^5=0.03125$. Ye $\sqrt2\approx1.41421$ ki taraf converge ho raha hai. ✓ > [!example] Example 2 — fixed number of steps ke baad error > $f(x)=\cos x - x$ on $[0,1]$. $n=10$ steps ke baad: > $$|x_{10}-r|\le \frac{1-0}{2^{11}} = \frac{1}{2048}\approx 4.88\times10^{-4}.$$ > **Ye step kyu?** Hume $r\approx0.739085$ bilkul pata hona zaruri nahi — bound sirf starting width aur step count use karta hai. Yahi predictability bisection ki superpower hai. > [!example] Example 3 — "digits per step" claim check karna > Per step decimal digits gain $=\log_{10}2 = 0.30103$. $6$ digits gain karne ke liye: $6/0.30103\approx 19.9$ steps — Example 1 ke $\approx 19$ steps se match karta hai. *Kyu match karta hai:* dono same $2^n$ shrink se aate hain; log base 10 mein "$2$" yaani $0.301$ hai. --- ## 6. Common mistakes (Steel-manned) > [!mistake] "Bisection ko $f'$ chahiye / slope weird ho to fail ho sakta hai." > **Kyu sahi lagta hai:** Newton bad slopes pe fail hota hai, isliye lagta hai ki sab root finders derivatives ke baare mein sochte hain. > **Fix:** Bisection **koi derivative nahi** use karta — sirf continuity aur sign change chahiye. Ye *sabse* robust method hai; valid bracket hone ke baad ye diverge nahi kar sakta. > [!mistake] "Ye *the* root dhundhta hai." > **Kyu sahi lagta hai:** textbook problem mein sirf ek hi answer hota hai. > **Fix:** Agar $[a,b]$ mein kai roots hain, to bisection **unme se ek** pe converge karta hai (jo sign-tracking mein survive kare) — sab pe nahi. Sign test $f(a)f(b)<0$ sirf guarantee karta hai ki *odd* number of roots present hain. > [!mistake] Bound ko actual error samajhna. > **Kyu sahi lagta hai:** formula ek single number deta hai. > **Fix:** $\dfrac{b-a}{2^{n+1}}$ ek **worst-case upper bound** hai, true error nahi. Real error aksar chhota hota hai, aur Newton ke unlike, bisection ka error absolute terms mein step-to-step *monotonically* decrease karna zaruri nahi — sirf *bound* karta hai. > [!mistake] Convergence "root ke paas speed up karti hai." > **Kyu sahi lagta hai:** Newton root ke paas accelerate karta hai. > **Fix:** Bisection ki rate **constant** $\tfrac12$ hai har jagah — ye kabhi accelerate nahi karta. Yahi price hai sirf ek bit information use karne ki. --- ## 7. Recall & Feynman > [!recall] Active recall — answers dhak lo > - Kaun sa theorem guarantee karta hai ki root exist karta hai? ==Intermediate Value Theorem== > - Bracketing condition? ==$f(a)f(b)<0$== > - $n$ steps ke baad error bound (midpoint)? ==$(b-a)/2^{n+1}$== > - Order aur rate of convergence? ==Linear, rate $1/2$== > - Tolerance $\varepsilon$ ke liye steps? ==$\lceil\log_2\frac{b-a}{\varepsilon}\rceil-1$== > - Sirf linear kyu? ==Har step mein sirf sign (1 bit) use karta hai== > [!recall]- Feynman: ek 12-saal ke bacche ko explain karo > Socho maine ek meter lambi stick pe kahin ek coin chhupa di aur main sirf bataunga "left half" ya "right half." Tum beech mein point karo, main batata hun kaun sa half, aur tum dusra half hamesha ke liye bhool jaao. Tumhara guessing zone **har baar aadha** hota jaata hai. 10 guesses ke baad tumhara zone lagbhag ek millimeter hai — practically coin dhoondh liya. Tumhe exactly pata nahi hona chahiye ki woh kahan hai, bas use *trap* karna hai. Bisection yahi karta hai us jagah ke saath jahan graph zero cross karta hai: "left/right" hint bas beech ke function ka **sign** (+ ya –) hota hai. > [!mnemonic] Yaad rakho > **"Half the gap, every lap."** Har lap (iteration) gap (interval width) ko aadha karta hai → error $\le \dfrac{b-a}{2^{n+1}}$. --- ## Connections - [[Intermediate Value Theorem]] — existence guarantee jis par bisection ride karta hai. - [[Newton-Raphson Method]] — quadratic, slope use karta hai; faster par diverge ho sakta hai. - [[Secant Method]] — superlinear ($p\approx1.618$), derivative ki zaroorat nahi. - [[Fixed-Point Iteration]] — general framework; bisection ek fixed-point map *nahi* hai par "linear rate" language share karta hai. - [[Order of Convergence]] — yahan use ki gayi linear/quadratic ki definitions. - [[Floating Point Arithmetic]] — sabse chhote useful $\varepsilon$ ki limits. #flashcards/maths $f$ ki kaun si property bisection method require karti hai? ::: $[a,b]$ pe continuity aur sign change $f(a)f(b)<0$ (taaki IVT apply ho). Kaun sa theorem guarantee karta hai ki sign-changing interval mein root exist karta hai? ::: The Intermediate Value Theorem. Width $b-a$ se start karke $n$ bisections ke baad interval width kya hai? ::: $(b-a)/2^n$. $n$ steps ke baad midpoint error bound kya hai? ::: $|x_n-r|\le (b-a)/2^{n+1}$. Bisection ka order of convergence kya hai? ::: Linear ($p=1$) asymptotic rate $C=1/2$ ke saath. Bisection sirf linearly convergent kyu hai? ::: Ye sirf $f(m)$ ka sign use karta hai — ek bit info per step — magnitude ya slope nahi. Tolerance $\varepsilon$ reach karne ke liye kitne iterations chahiye? ::: $n\ge \lceil\log_2((b-a)/\varepsilon)\rceil-1$. Per step lagbhag kitne decimal digits gain hote hain? ::: $\log_{10}2\approx0.301$ digits, yaani ~1 digit per 3.3 steps. Valid bracket hone par kya bisection diverge ho sakta hai? ::: Nahi — bracket mein hamesha root hota hai, isliye ye converge karna hi hai. Kya error bound true error hai? ::: Nahi, ye worst-case upper bound hai; true error usually chhota hota hai aur monotonically decrease karna zaruri nahi. Agar $[a,b]$ mein 3 roots hain, to kya hoga? ::: Ye unme se ek pe converge karta hai (sign-tracking ek hi root rakhta hai), sab pe nahi. ## 🖼️ Concept Map ```mermaid flowchart TD IVT[Intermediate Value Theorem] Bracket[Bracket f a f b < 0] Method[Bisection halving] Midpoint[Midpoint m = a+b over 2] Sign[Sign test on f m] Recur[Width recurrence Ln = half Ln-1] Solved[Ln = b-a over 2^n] Estimate[Estimate xn = midpoint] Bound[Error bound b-a over 2^n+1] Slow[Slow: one bit per step] Bracket -->|guarantees root via| IVT IVT -->|justifies| Method Method -->|computes| Midpoint Midpoint -->|evaluated by| Sign Sign -->|keeps half that brackets| Bracket Method -->|halves width each step| Recur Recur -->|unrolled gives| Solved Solved -->|report midpoint| Estimate Estimate -->|worst case half width| Bound Method -->|uses only sign| Slow ```