Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Big Idea

The bisection method exploits the Intermediate Value Theorem: if a continuous function changes sign on an interval, it must have a root there. By repeatedly halving the interval, we trap the root with guaranteed convergence.

The Intermediate Value Theorem

Theorem 1 (Intermediate Value Theorem)

Suppose f∈C([a,b])f \in \mathcal{C}([a, b]) and f(a)<ϕ<f(b)f(a) < \phi < f(b). Then there exists c∈(a,b)c \in (a, b) such that f(c)=ϕf(c) = \phi.

Remark 1 (Application to Root Finding)

Setting ϕ=0\phi = 0: if ff is continuous and f(a)f(b)<0f(a)f(b) < 0 (i.e., ff changes sign), then a root exists in (a,b)(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.

Algorithm 1 (Bisection)

Input: ff, interval [a,b][a, b] with f(a)f(b)<0f(a)f(b) < 0, tolerance ε\varepsilon

Output: Approximate root cc

  1. while (b−a)/2>ε(b - a)/2 > \varepsilon:

  2. c←(a+b)/2\qquad c \gets (a + b)/2

  3. \qquad if f(c)=0f(c) = 0: return cc

  4. \qquad if sign⁡(f(c))=sign⁡(f(a))\operatorname{sign}(f(c)) = \operatorname{sign}(f(a)):

  5. a←c\qquad\qquad a \gets c

  6. \qquad else:

  7. b←c\qquad\qquad b \gets c

  8. return (a+b)/2(a + b)/2

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

Convergence Analysis

Theorem 2 (Bisection Convergence)

Suppose f∈C([a,b])f \in \mathcal{C}([a, b]) with f(a)f(b)<0f(a)f(b) < 0. If {xn}\{x_n\} is the sequence of midpoints generated by bisection, then

∣ℓ−xn∣≤b−a2n+1|\ell - x_n| \leq \frac{b - a}{2^{n+1}}
(1)

where ℓ\ell is the root.

Proof 1

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

∣ℓ−xn∣≤12∣bn−an∣≤122∣bn−1−an−1∣≤⋯≤b−a2n+1|\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 2n+1→∞2^{n+1} \to \infty, we have xn→ℓx_n \to \ell.

Corollary 1 (Predictable Iteration Count)

To achieve ∣xn−ℓ∣<ε|x_n - \ell| < \varepsilon, we need:

n≥⌈log⁡2(b−a2ε)⌉n \geq \left\lceil \log_2\left(\frac{b - a}{2\varepsilon}\right) \right\rceil
(3)

Proof 2

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

2n+1>b−aε  ⟹  n+1>log⁡2(b−aε)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 2\sqrt{2} (root of x2−2=0x^2 - 2 = 0) on [1,2][1, 2] with accuracy 10-10:

n≥log⁡2(12×10−10)=log⁡2(5×109)≈32.2n \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

See Also

Bisection Method Demo — Finding 3\sqrt{3}, interval visualization, Newton comparison

Advantages and Disadvantages

Advantages:

Disadvantages:

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

Introduction to Scientific Computing
Nonlinear Equations
Introduction to Scientific Computing
§2 Fixed-Point Iteration