Bisection Method - Introduction to Scientific Computing

The Intermediate Value Theorem¶

Remark 1 (Application to Root Finding)

Setting $\phi = 0$ : if $f$ is continuous and $f(a)f(b) < 0$ (i.e., $f$ changes sign), then a root exists in $(a, b)$ .

This gives us an existence guarantee—something bisection exploits at every step.

The Algorithm¶

The bisection method is a divide and conquer algorithm.

At each step, the interval width is halved. This geometric reduction is why bisection always converges.

Convergence Analysis¶

Proof 1

At each step, the interval width halves. The midpoint $x_n$ is at most half the interval width away from any point in the interval, including the root $\ell$ :

|\ell - x_n| \leq \frac{1}{2}|b_n - a_n| \leq \frac{1}{2^2}|b_{n-1} - a_{n-1}| \leq \cdots \leq \frac{b - a}{2^{n+1}}

(2)

Since $2^{n+1} \to \infty$ , we have $x_n \to \ell$ .

Proof 2

We want $\frac{b-a}{2^{n+1}} < \varepsilon$ , which gives:

2^{n+1} > \frac{b-a}{\varepsilon} \implies n+1 > \log_2\left(\frac{b-a}{\varepsilon}\right)

(4)

Rearranging and taking the ceiling gives the result.

Example 1 (How Many Iterations?)

To find $\sqrt{2}$ (root of $x^2 - 2 = 0$ ) on $[1, 2]$ with accuracy 10^-10:

n \geq \log_2\left(\frac{1}{2 \times 10^{-10}}\right) = \log_2(5 \times 10^9) \approx 32.2

(5)

So 33 iterations suffice—regardless of the function’s complexity!

Demonstrations¶

Advantages and Disadvantages¶

Advantages:

Guaranteed convergence — Cannot fail if you have a sign change
Predictable — Know exactly how many iterations before you start
Simple — Only needs function evaluations, no derivatives
Robust — Immune to pathologies that break faster methods

Disadvantages:

Slow — Linear convergence; ~34 iterations for 10 digits (vs. 4-5 for Newton)
Requires bracket — Must find interval with sign change first
Scalar only — No generalization to systems in $\mathbb{R}^n$

Practical wisdom: Use bisection to get close, then switch to Newton for speed.