The Bisection Method

The Bisection Method at the same time gives a proof of the Intermediate Value Theorem and provides a practical method to find roots of equations. If your calculator can solve equations numerically, it most likely uses a combination of the Bisection Method and the Newton-Raphson Method.

Recall the statement of the Intermediate Value Theorem: Let f (x) be a continuous function on the interval [a, b]. If d $\in$ [f (a), f (b)], then there is a c $\in$ [a, b] such that f (c) = d.

By replacing f (x) by f (x) - d, we may assume that d = 0; it then suffices to obtain the following version: Let f (x) be a continuous function on the interval [a, b]. If f (a) and f (b) have opposite signs, then there is a c $\in$ [a, b] such that f (c) = 0.

Here is an outline of its proof: Let's assume that f (a) < 0, while f (b) > 0, the other case being handled similarly. Set a₀ = a and b₀ = b.

Now consider the midpoint m₀ = $${\frac{a_0+b_0}{2}}$$, and evaluate f (m₀). If f (m₀) < 0, set a₁ = m₀ and b₁ = b₀. If f (m₀) > 0, set a₁ = a₀ and b₁ = m₀. (If f (m₀)=0, you're already done.) What situation are we in now? f (a₁) and f (b₁) still have opposite signs, but the length of the interval [a₁, b₁] is only half of the length of the original interval [a₀, b₀]. Note also that a₀ $\leq$ a₁ and that b₀ $\geq$ b₁.

You probably guess this by now: we will do this procedure again and again.

Here is the second step: Consider the midpoint m₁ = $${\frac{a_1+b_1}{2}}$$, and evaluate f (m₁). If f (m₁) < 0, set a₂ = m₁ and b₂ = b₁. If f (m₁) > 0, set a₂ = a₁ and b₂ = m₁. (If f (m₁)=0, you're already done.) What situation are we in now? f (a₂) and f (b₂) still have opposite signs, but the length of the interval [a₂, b₂] is only a quarter of the length of the original interval [a₀, b₀]. Note also that a₀ $\leq$ a₁ $\leq$ a₂ and that b₀ $\geq$ b₁ $\geq$ b₂.

The red line shows the interval [a_n, b_n].

Continuing in this fashion we construct by induction two sequences

(a_n)_{n = 1}^$\infty$ and (b_n)_{n = 1}^$\infty$

with the following properties:

1. (a_n) is an increasing sequence, (b_n) is a decreasing sequence.
2. a_n $\leq$ b_n for all n.
3. f (a_n) < 0 for all n, f (b_n) > 0 for all n.
4. b_n - a_n = 2^-n(b - a) for all n.

It follows from the first two properties that the sequences (a_n) and (b_n) converge; set

$$\lim_{n\to\infty}^{}$$a_n = a,    $$\lim_{n\to\infty}^{}$$b_n = b.

The third property and the continuity of the function f (x) imply that f (a) $\leq$ 0 and that f (b) $\geq$ 0.

The crucial observation is the fact that the fourth property implies that a = b. Consequently, f (a) = f (b) = 0, and we are done.

Example. Let's compute numerical approximations for the $\sqrt{2}$ with the help of the bisection method. We set f (x) = x² - 2. Let us start with an interval of length one: a₀ = 1 and b₁ = 2. Note that f (a₀) = f (1) = - 1 < 0, and f (b₀) = f (2) = 3 > 0. Here are the first 20 applications of the bisection algorithm:

A comparison of the Bisection Method and the Newton-Raphson Method. The Newton-Raphson Method is often much faster than the Bisection Method. In the last example, we started with an interval of length 1. After 10 steps, the interval [a₁₀, b₁₀] has length 1/1024. Consequently every 10 steps of the Bisection Method will give us about 3 digits more accuracy - that is rather slow. (On the Newton-Raphson Method page, we did the same example, compare the speeds of convergence!)

The Newton-Raphson Method can be unreliable: If the algorithm encounters a point x where f '(x) = 0, it crashes; if it encounters points where the derivative is very close to 0, it will become very unreliable.

The Bisection Method on the other hand will always work, once you have found starting points a and b where the function takes opposite signs.

[Back] [Trigonometry] [Calculus] [Geometry] [Algebra] [Differential Equations] [Complex Variables] [Matrix Algebra]

S.O.S MATHematics home page

Copyright © 1999-2004 MathMedics, LLC. All rights reserved.
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA