Burden & Faires, 9th Ed. - §2.1
Chapter 2: The Bisection Method
Root-finding by repeated halving · Error bound & iteration count · Convergence rate · Practical pitfalls
The Bisection Method is the least clever way to find a root - and precisely because of that, it is the most reliable. It needs nothing about $f$ except that it is continuous and changes sign; it always converges when those conditions hold; and its error at every step is known exactly in advance. Later chapters trade this bulletproof reliability for speed - Newton's Method converges far faster but can fail outright from a bad starting guess. Understanding exactly what Bisection guarantees, and exactly what it costs to guarantee it, is what makes that trade legible.
Section 2.1
The Bisection Algorithm
Root-Finding and Bracketing
The Problem
Given $f\in C[a,b]$, find $p\in[a,b]$ with $f(p)=0$. The Bisection Method assumes we already have a bracket: an interval $[a,b]$ with $f(a)$ and $f(b)$ of opposite sign. By the Intermediate Value Theorem (Theorem 1.1.1), a root is then guaranteed to exist somewhere in $(a,b)$ - not necessarily unique, but at least one.
The Algorithm
Bisection Method
Given $f(a)$ and $f(b)$ of opposite sign, and tolerance $\text{TOL}$:
- Compute the midpoint $p = \dfrac{a+b}{2}$.
- If $f(p)=0$ or $\dfrac{b-a}{2}<\text{TOL}$, stop - $p$ is the (approximate) root.
- If $f(a)$ and $f(p)$ have the same sign, set $a\leftarrow p$ (root is in the right half); otherwise set $b\leftarrow p$ (root is in the left half).
- Repeat from step 1 - the bracket width exactly halves on every pass.
n = 0 · [a, b] = [1.000000, 2.000000] · width = 1.000000
Bisection applied to $f(x)=x^3-x-2$ on $[1,2]$ (root $p\approx1.521380$). Each click halves the bracket (shaded) and re-tests the sign of $f$ at the new midpoint (dot) against the sign at the left endpoint.
📘 Example 2.1 - First Four Iterations by Hand
Apply Bisection to $f(x)=x^3-x-2$ on $[1,2]$ and tabulate the first four midpoints.
Solution
$f(1)=-2<0$, $f(2)=4>0$ - valid bracket.
After 4 iterations, the bracket has shrunk to $[1.50000, 1.56250]$, width $0.0625 = (2-1)/2^4$, closing in on the true root $p\approx1.521380$.
| $n$ | $a_n$ | $b_n$ | $p_n=\frac{a_n+b_n}{2}$ | $f(p_n)$ | Sign vs. $f(a_n)$ |
|---|---|---|---|---|---|
| 1 | 1.00000 | 2.00000 | 1.50000 | $-0.12500$ | same → $a_2=p_1$ |
| 2 | 1.50000 | 2.00000 | 1.75000 | $1.60938$ | opposite → $b_3=p_2$ |
| 3 | 1.50000 | 1.75000 | 1.62500 | $0.66602$ | opposite → $b_4=p_3$ |
| 4 | 1.50000 | 1.62500 | 1.56250 | $0.25146$ | opposite → $b_5=p_4$ |
Section 2.2
Error Analysis & Convergence
The Error Bound
Theorem 2.1 - Bisection Error Bound
Suppose $f\in C[a,b]$ with $f(a)f(b)<0$. Bisection generates a sequence $\{p_n\}_{n=1}^\infty$ approximating a root $p$ with
$$|p_n - p| \le \frac{b-a}{2^n}, \qquad n\ge1$$
Proof sketch. Each pass exactly halves the bracket width, so after $n$ passes the bracket containing $p$ has width $(b-a)/2^n$; since $p_n$ is the midpoint of the $n$th bracket, it is at most half that width away from $p$ (and the theorem states the slightly looser full-width bound, which also holds and is the version quoted in the textbook). The key point either way: the bound depends only on $n$ and the original interval - never on $f$ itself.
Bisection is Linearly Convergent
Since $|p_n - p|\le (b-a)2^{-n}$, we have $|p_{n+1}-p| \le \frac12|p_n-p|$ - bisection converges with order $\alpha=1$ and asymptotic error constant $\lambda=\tfrac12$ (Definition, Chapter 1). Every iteration is guaranteed to gain roughly $\log_{10}2 \approx 0.3$ correct decimal digits - no more, no less, no matter how "nice" $f$ is. Compare this to Newton's Method's quadratic convergence in Chapter 4, which can double the number of correct digits every single step.
How Many Iterations to Guarantee Tolerance $\varepsilon$?
Solving the Bound for $n$
To guarantee $|p_n-p|<\varepsilon$, it suffices that $(b-a)/2^n < \varepsilon$, i.e.
$$n > \log_2\!\left(\frac{b-a}{\varepsilon}\right) = \frac{\ln(b-a)-\ln\varepsilon}{\ln 2}$$
This can be computed before running a single iteration - a guarantee no other method in this course offers up front.
📘 Example 2.2 - How Many Iterations for $10^{-8}$ Accuracy?
Using $[a,b]=[1,2]$ for $f(x)=x^3-x-2$, how many bisection iterations guarantee $|p_n-p|<10^{-8}$?
Solution
$$n > \log_2\left(\frac{2-1}{10^{-8}}\right) = \log_2(10^8) = 8\log_2(10) = 8(3.32193) = 26.575$$
$n=27$ iterations guarantee accuracy of $10^{-8}$ - regardless of where in $[1,2]$ the root actually sits. Contrast with Newton's Method reaching the same accuracy from a good start in about 5 iterations (Chapter 4, Example 4.1) - the price of Bisection's guaranteed reliability is roughly $5\times$ more function evaluations here, and the gap widens for tighter tolerances.
Actual bisection error $|p_n-p|$ (blue dots) for $f(x)=x^3-x-2$ against the theoretical bound $(b-a)/2^n$ (dashed). The bound is never violated - by construction it cannot be - but the true error can dip below it whenever a midpoint happens to land close to $p$.
Section 2.3
Stopping Criteria & Pitfalls
Practical Stopping Criteria
Solving for $n$ in advance is elegant, but real implementations usually stop on whichever of these triggers first:
- $|p_n - p_{n-1}| < \text{TOL}$ (bracket width small enough)
- $|f(p_n)| < \text{TOL}$ (function value near zero) - dangerous alone if $f'(p)$ is very small or very large near the root, since a small $f(p_n)$ doesn't always mean $p_n$ is close to $p$
- A maximum iteration count, as insurance against an infinite loop from a coding error
Pitfall - Even-Multiplicity Roots Have No Bracket
Consider $f(x)=(x-1)^2$ on $[0,2]$. There is a genuine root at $x=1$, but $f(0)=1>0$ and $f(2)=1>0$ - no sign change. Bisection cannot even start, despite the root's existence, because it only ever detects roots of odd multiplicity (where $f$ actually crosses the axis). A root where $f$ merely touches zero and turns back needs a different method entirely - typically Newton's Method (Chapter 4), which uses derivative information $f$ itself doesn't carry.
Pitfall - Multiple Roots in One Bracket
If $[a,b]$ contains several roots with alternating sign changes, Bisection is only guaranteed to converge to one of them - and which one depends on where the midpoints happen to fall, not on any notion of "the nearest" or "the smallest." Always narrow the bracket with a plot or a coarse sign-change scan first.
📘 Example 2.3 - A Bracket Hiding Three Roots
$f(x) = \sin(4x)\,e^{-x}$ has roots at $x=0, \pi/4, \pi/2, \ldots$. Show that bisecting the single interval $[0.1, 1.7]$ is unsafe.
Solution
On $[0.1,1.7]$: $f(0.1)\approx0.331>0$. Checking the sign at several interior points: $f(0.5)\approx\sin(2)e^{-0.5}\approx0.551>0$; $f(0.9)\approx\sin(3.6)e^{-0.9}\approx-0.183<0$; $f(1.3)\approx\sin(5.2)e^{-1.3}\approx-0.234<0$; $f(1.7)\approx\sin(6.8)e^{-1.7}\approx0.166>0$. So $f$ changes sign twice inside $[0.1,1.7]$ (once near $x=\pi/4\approx0.785$ and once near $x=\pi/2\approx1.571$) while $f(0.1)$ and $f(1.7)$ have the same sign - bisecting this bracket as given would immediately discard the half actually containing both roots, or in a narrower bracket variant could silently converge to only one of the two roots depending on rounding.
A single coarse bracket is not enough when $f$ oscillates - always scan for sign changes on a fine grid first, then bisect each sub-bracket separately.
Practice
Practice Problem
Try this problem yourself before expanding the solution below.
✏️ Practice Problem 2.1 - Bisection on $f(x)=e^x-3x^2$
Consider $f(x) = e^x - 3x^2$ on $[0.5, 1]$. Confirm the interval brackets a root, determine the minimum number of iterations needed to guarantee accuracy $10^{-5}$, and hand-compute $p_1$ through $p_4$.
Solution
$f(0.5) = e^{0.5}-3(0.25) = 1.6487-0.75 = 0.8987 > 0$ and $f(1) = e-3 = -0.2817 < 0$. Since $f$ is continuous and changes sign, the Intermediate Value Theorem guarantees a root in $(0.5,1)$.
For the iteration count, solve $\dfrac{b-a}{2^n} < 10^{-5}$: $$\frac{0.5}{2^n} < 10^{-5} \implies 2^n > 50000 \implies n \ge \lceil \log_2 50000 \rceil = 16.$$
Bisecting by hand:
Each row keeps the sub-interval whose endpoints still bracket the sign change.
16 iterations guarantee $10^{-5}$ accuracy; $p_1=0.75$, $p_2=0.875$, $p_3=0.9375$, $p_4=0.90625$, converging toward the root near $0.9127$.
For the iteration count, solve $\dfrac{b-a}{2^n} < 10^{-5}$: $$\frac{0.5}{2^n} < 10^{-5} \implies 2^n > 50000 \implies n \ge \lceil \log_2 50000 \rceil = 16.$$
Bisecting by hand:
| $n$ | $a_n$ | $b_n$ | $p_n$ (midpoint) | $f(p_n)$ |
|---|---|---|---|---|
| 1 | 0.500000 | 1.000000 | 0.750000 | $+0.429500$ |
| 2 | 0.750000 | 1.000000 | 0.875000 | $+0.102000$ |
| 3 | 0.875000 | 1.000000 | 0.937500 | $-0.083129$ |
| 4 | 0.875000 | 0.937500 | 0.906250 | $+0.011157$ |
Connections Across the Course
- The Intermediate Value Theorem that guarantees a bracketed root exists comes straight from Chapter 1.
- Bisection's linear convergence ($\alpha=1$) is the baseline every faster method in Chapter 3 and Chapter 4 is measured against.
- Bisection is frequently used to generate a safe starting guess for Newton's Method - reliable but slow, handing off to fast but locally convergent.