Bisection Method (Convergence, Error)

At a Glance

• Frequency: 1 sub-part across 1 of 13 years (2018)
• Priority tier: T4
• Marks (count): 10 (1)
• Average solve time: ~18 min
• Difficulty mix: medium 1
• Section: A | Dominant type: derivation

Why This Chapter Matters

Bisection is the canonical example of a bracketing root-finding method and the benchmark against which all other methods are measured. UPSC 2018 tested the convergence and error analysis rather than mere computation, so the derivation of the error bound is the core skill. Knowing how many iterations are needed for a given precision is the clean, marks-focused answer UPSC rewards.

Minimum Theory

Existence (Intermediate Value Theorem). If $f$ is continuous on $[a, b]$ and $f(a)f(b) < 0$, then there exists at least one root $x^* \in (a, b)$.

Algorithm. At each step, compute the midpoint:

$c_n = \frac{a_n + b_n}{2}$

• If $f(a_n) f(c_n) < 0$, set $b_{n+1} = c_n$, $a_{n+1} = a_n$.
• If $f(a_n) f(c_n) > 0$, set $a_{n+1} = c_n$, $b_{n+1} = b_n$.
• If $f(c_n) = 0$, stop — $c_n$ is exact.

The bracket length is halved at every step: $b_n - a_n = (b - a)/2^n$.

Error bound. After $n$ steps the approximate root is $c_n$ and the true root satisfies

$|c_n - x^*| \le \frac{b - a}{2^{n+1}}$

because $x^*$ lies inside the bracket $[a_n, b_n]$ of length $(b-a)/2^n$ and $c_n$ is its midpoint.

Number of iterations for tolerance $\varepsilon$. We need

$\frac{b - a}{2^{n+1}} \le \varepsilon \implies 2^{n+1} \ge \frac{b-a}{\varepsilon} \implies n \ge \log_2\!\left(\frac{b-a}{\varepsilon}\right) - 1$

A conservative round-up formula is

$n \ge \left\lceil \log_2\!\left(\frac{b-a}{\varepsilon}\right) \right\rceil$

Rate of convergence. Let $e_n = |c_n - x^*|$. Then $e_{n+1} \le e_n / 2$, so

$e_{n+1} \le \frac{1}{2}\, e_n$

This is linear convergence with rate constant $p = 1$ and asymptotic constant $C = 1/2$.

Comparison table.

Question Archetypes

error-bound-derivation (1 question; 2018)

Recognition Cues

• “Derive the convergence” or “prove the error bound” for bisection.
• Examiner wants a clean mathematical argument, not just the formula.

Solution Template

1. State the IVT condition: $f$ continuous on $[a,b]$, $f(a)f(b)<0$.
2. Define $[a_n, b_n]$ as the bracket after $n$ steps; note $b_n - a_n = (b-a)/2^n$.
3. Since $x^* \in [a_n, b_n]$ and $c_n = (a_n+b_n)/2$ is the midpoint, $|c_n - x^*| \le (b_n - a_n)/2 = (b-a)/2^{n+1}$.
4. Take limits: as $n \to \infty$ the bound $\to 0$, so $c_n \to x^*$.
5. State the convergence rate: $e_{n+1}/e_n \le 1/2$ — linear convergence.

Worked Example

2018 Paper 2, 2018-P2-Q1a (10 marks)

Show that the bisection method converges linearly to a root of $f(x) = x^3 - x - 2 = 0$ in $[1, 2]$, and find how many iterations are needed to locate the root with error less than $0.001$.

Check bracket. $f(1) = 1 - 1 - 2 = -2 < 0$ and $f(2) = 8 - 2 - 2 = 4 > 0$. Since $f$ is continuous and signs differ, IVT guarantees a root in $(1,2)$.

Error bound derivation.

Define the $n$-th bracket $[a_n, b_n]$ with $a_0 = 1$, $b_0 = 2$, so $b_0 - a_0 = 1$. After each bisection step the bracket is halved, giving

$b_n - a_n = \frac{1}{2^n}$

The approximation $c_n = (a_n + b_n)/2$ satisfies $x^* \in [a_n, b_n]$, hence

$|c_n - x^*| \le \frac{b_n - a_n}{2} = \frac{1}{2^{n+1}}$

Since $e_{n+1} \le e_n / 2$ for all $n$, the ratio $e_{n+1}/e_n \le 1/2$ independently of $f$ — this is linear convergence (order $p=1$, asymptotic constant $C = 1/2$).

Iteration count for $\varepsilon = 0.001$.

We need $1/2^{n+1} \le 0.001$, i.e.

$2^{n+1} \ge 1000 \implies (n+1)\log_2 10 \ge 3\log_2 10$

More directly:

$2^{n+1} \ge 1000 \implies n+1 \ge \log_2 1000 = \frac{\ln 1000}{\ln 2} = \frac{6.9078}{0.6931} \approx 9.97$

So $n + 1 \ge 10$, giving $n \ge 9$.

Conclusion. A minimum of $\mathbf{9}$ bisection iterations guarantee $|c_9 - x^*| \le 1/2^{10} = 1/1024 < 0.001$.

$\boxed{n \ge 9 \text{ iterations; error bound } \le \frac{1}{2^{n+1}}}$

Common Traps

• Off-by-one: the bound after step $n$ is $(b-a)/2^{n+1}$, not $(b-a)/2^n$.
• Forgetting to verify $f(a)f(b) < 0$ before claiming the root exists.
• Confusing “linear convergence” (order 1) with “convergence is slow” — these are not the same statement; it is a precise mathematical order.
• Using $\log_{10}$ instead of $\log_2$ in the iteration-count formula without converting.

Marks-Aware Writing

For a 10-mark derivation question, structure your answer in three explicit parts: (1) state the IVT and bracket halving, (2) derive the error bound with a brief proof, (3) solve the iteration count inequality with visible arithmetic. Each part is worth 3–4 marks. The examiner expects you to show the inequality $2^{n+1} \ge (b-a)/\varepsilon$ explicitly — do not skip to the answer.

Practice Set

Only one historical question on this atom (shown above).