4.8.6Numerical Methods
Root finding — bisection method (convergence analysis)
2,029 words9 min readdifficulty · medium
1. The setup and the guarantee
WHAT the method does (HOW): repeatedly compute the midpoint , evaluate , and keep the subinterval where the sign change survives:
- If → root is in , set .
- Else → root is in , set .
- If , you landed exactly on the root — done.
The new interval is always half the old length and still brackets a root.
2. Deriving the error bound from scratch
Step 1 — interval width recurrence. Let be the length after bisections, starting from . Why this step? Each bisection literally cuts the interval in half — that's the definition of the method.
Step 2 — solve the recurrence. Unrolling: Why this step? Repeated halving is just multiplying by times.
Step 3 — choose the estimate. After steps the interval is . Take the midpoint as our answer: Why this step? The midpoint is the best single guess: the true root and both lie in , so the worst-case distance is half the width, not the full width.
Step 4 — bound the error. The true root lies in , and so does . The farthest apart they can be is half the interval:
3. Order of convergence: why it's "linear"
For bisection the guaranteed error halves each step: So bisection is linearly convergent with rate (asymptotic constant) . Each iteration gains a fixed factor of in accuracy — i.e. about decimal digits per step, so roughly one new correct decimal digit every iterations.
4. How many steps for a tolerance?
We want . Using the bound:
\;\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\,}$$ > *Why useful:* this is known **before** running anything — bisection's step count is **predictable**, independent of $f$'s shape. (Many texts conservatively use $n\ge \log_2\frac{b-a}{\varepsilon}$ when reporting an endpoint.) --- ## 5. Worked examples > [!example] Example 1 — Forecast-then-Verify: how many steps? > Solve $f(x)=x^2-2=0$ on $[1,2]$ to tolerance $\varepsilon=10^{-6}$. > > **Forecast first:** $b-a=1$. Need $n\ge \log_2(1/10^{-6})-1 = \log_2(10^6)-1 \approx 19.93-1 \approx 18.93$. > So **$n=19$** midpoint iterations should do it. > > **Verify (HOW each step):** > - $m_1=1.5,\ f=0.25>0$, and $f(1)<0$ → root in $[1,1.5]$. *Why?* sign change is on the left. > - $m_2=1.25,\ f=-0.4375<0$ → root in $[1.25,1.5]$. > - $m_3=1.375,\ f=-0.109<0$ → root in $[1.375,1.5]$. > - $m_4=1.4375,\ f=0.066>0$ → root in $[1.375,1.4375]$. > > Width after 4 steps $=1/2^4=0.0625$; error of $x_4$ $\le 1/2^5=0.03125$. It is converging toward $\sqrt2\approx1.41421$. ✓ > [!example] Example 2 — error after a fixed number of steps > $f(x)=\cos x - x$ on $[0,1]$. After $n=10$ steps: > $$|x_{10}-r|\le \frac{1-0}{2^{11}} = \frac{1}{2048}\approx 4.88\times10^{-4}.$$ > **Why this step?** We don't need to know $r\approx0.739085$ at all — the bound only uses the starting width and the step count. That predictability is bisection's superpower. > [!example] Example 3 — checking the "digits per step" claim > Decimal digits gained per step $=\log_{10}2 = 0.30103$. To gain $6$ digits: $6/0.30103\approx 19.9$ steps — matching Example 1's $\approx 19$ steps. *Why this matches:* both come from the same $2^n$ shrink; "$2$" in log base 10 is $0.301$. --- ## 6. Common mistakes (Steel-manned) > [!mistake] "Bisection needs $f'$ / it can fail if the slope is weird." > **Why it feels right:** Newton fails for bad slopes, so you assume all root finders care about derivatives. > **Fix:** Bisection uses **no derivative** — only continuity and a sign change. It is the *most* robust method; it cannot diverge once you have a valid bracket. > [!mistake] "It finds *the* root." > **Why it feels right:** there's only one answer in a textbook problem. > **Fix:** If $[a,b]$ contains several roots, bisection converges to **one** of them (whichever survives the sign-tracking) — not all. The sign test $f(a)f(b)<0$ only guarantees an *odd* number of roots is present. > [!mistake] Using the bound as the actual error. > **Why it feels right:** the formula gives a single number. > **Fix:** $\dfrac{b-a}{2^{n+1}}$ is a **worst-case upper bound**, not the true error. The real error is often smaller, and unlike Newton, bisection's error need **not** decrease *monotonically* in absolute terms step to step — only the *bound* does. > [!mistake] Convergence "speeds up near the root." > **Why it feels right:** Newton accelerates near a root. > **Fix:** Bisection's rate is a **constant** $\tfrac12$ everywhere — it never accelerates. That's the price of using only one bit of information. --- ## 7. Recall & Feynman > [!recall] Active recall — cover the answers > - What theorem guarantees a root exists? ==Intermediate Value Theorem== > - Bracketing condition? ==$f(a)f(b)<0$== > - Error bound after $n$ steps (midpoint)? ==$(b-a)/2^{n+1}$== > - Order and rate of convergence? ==Linear, rate $1/2$== > - Steps for tolerance $\varepsilon$? ==$\lceil\log_2\frac{b-a}{\varepsilon}\rceil-1$== > - Why only linear? ==Uses only the sign (1 bit) per step== > [!recall]- Feynman: explain to a 12-year-old > Imagine I hid a coin somewhere along a meter-long stick and I'll only tell you "left half" or "right half." You point to the middle, I tell you which half, and you forget the other half forever. Your guessing zone gets **half as wide every single time**. After 10 guesses your zone is about a millimeter — you've basically found the coin. You never need to know exactly where it is to *trap* it. Bisection does this with the spot where a graph crosses zero: the "left/right" hint is just the **sign** (+ or –) of the function at the middle. > [!mnemonic] Remember it > **"Half the gap, every lap."** Each lap (iteration) halves the gap (interval width) → error $\le \dfrac{b-a}{2^{n+1}}$. --- ## Connections - [[Intermediate Value Theorem]] — the existence guarantee bisection rides on. - [[Newton-Raphson Method]] — quadratic, uses slope; faster but can diverge. - [[Secant Method]] — superlinear ($p\approx1.618$), no derivative needed. - [[Fixed-Point Iteration]] — general framework; bisection is *not* a fixed-point map but shares "linear rate" language. - [[Order of Convergence]] — definitions of linear/quadratic used here. - [[Floating Point Arithmetic]] — limits the smallest useful $\varepsilon$. #flashcards/maths What property of $f$ does the bisection method require? ::: Continuity on $[a,b]$ and a sign change $f(a)f(b)<0$ (so IVT applies). Which theorem guarantees a root exists in a sign-changing interval? ::: The Intermediate Value Theorem. What is the interval width after $n$ bisections starting from width $b-a$? ::: $(b-a)/2^n$. What is the midpoint error bound after $n$ steps? ::: $|x_n-r|\le (b-a)/2^{n+1}$. What is the order of convergence of bisection? ::: Linear ($p=1$) with asymptotic rate $C=1/2$. Why is bisection only linearly convergent? ::: It uses only the sign of $f(m)$ — one bit of info per step — not the magnitude or slope. How many iterations to reach tolerance $\varepsilon$? ::: $n\ge \lceil\log_2((b-a)/\varepsilon)\rceil-1$. Approximately how many decimal digits are gained per step? ::: $\log_{10}2\approx0.301$ digits, i.e. ~1 digit per 3.3 steps. Can bisection diverge given a valid bracket? ::: No — the bracket always contains a root, so it must converge. Is the error bound the true error? ::: No, it's a worst-case upper bound; true error is usually smaller and need not decrease monotonically. If $[a,b]$ contains 3 roots, what happens? ::: It converges to one of them (sign-tracking keeps a single root), not all. ## 🖼️ 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 ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Bisection method ka core idea bahut simple hai: agar ek continuous function $f$ interval $[a,b]$ ke do endpoints pe **opposite sign** rakhta hai (yaani $f(a)f(b)<0$), to beech mein kahin na kahin root zaroor hoga — yeh Intermediate Value Theorem guarantee karta hai. Phir hum bas midpoint $m=(a+b)/2$ nikaalte hain, uska sign check karte hain, aur jis half mein sign-change bacha hai use rakh lete hain. Har step pe interval **aadha** ho jaata hai, isliye galti ka cage continuously sikudta jaata hai. > > Convergence ki baat karein to interval ki width $n$ steps ke baad $(b-a)/2^n$ ho jaati hai, aur agar hum midpoint ko answer maanein to error $\le (b-a)/2^{n+1}$. Isi se hum **pehle hi** bata sakte hain kitne steps chahiye: $n\ge \log_2((b-a)/\varepsilon)-1$. Yeh predictability bisection ki sabse badi khoobi hai — function chahe jitna tedha ho, step count fixed rehta hai aur method kabhi diverge nahi karta. > > Lekin yeh method sirf **linearly** converge karta hai (rate $1/2$), Newton ki tarah quadratic nahi. Reason simple hai: bisection sirf $f(m)$ ka **sign** use karta hai — ek bit information per step. Isliye har step pe sirf ek constant fraction uncertainty hatti hai. Roughly 3.3 steps mein ek naya decimal digit milta hai. > > Exam tip: yaad rakho "**half the gap, every lap**". Common galti — bound ko exact error samajh lena (woh sirf worst-case upper bound hai), aur yeh sochna ki near the root speed badhti hai (nahi badhti, rate constant $1/2$ rehta hai). Robustness chahiye to bisection, speed chahiye to Newton/secant. ![[audio/4.8.06-Root-finding-—-bisection-method-(convergence-analysis).mp3]]