Root finding · Definition

Bisection method

numerical methodsroot finding

Before you start you need to know

It is one of the simplest methods for locating roots, and its convergence is guaranteed by the intermediate value theorem. Its pace is slow, but its behavior is predictable.

Definition

The bisection method is an iterative algorithm that approximates a root of a continuous function \( f(x) \) on an interval \( [a, b] \) with a sign change, halving the interval at each step.

\[c_n = \frac{a_n + b_n}{2},\quad |c_n - r| \le \frac{b-a}{2^{n+1}}\]

If \( f \) is continuous on \( [a, b] \) and \( f(a) \cdot f(b) < 0 \), the intermediate value theorem guarantees a root in \( (a, b) \). After \( n \) iterations the error of the approximation \( c_n \) is at most \( \frac{b - a}{2^{n+1}} \), so each step halves the error bound. The method needs no derivatives, only evaluations of \( f \).

For f(x) = x² − 2 on [1, 2], f(1) = −1 and f(2) = 2, so there is a root in (1, 2). The midpoint c = 1.5 gives f(1.5) = 0.25 > 0, so the root lies in [1, 1.5]; repeating the process, the interval approaches √2 ≈ 1.41421.

A typical mistake is applying the method to an interval where f(a) and f(b) have the same sign, which can hide roots or discard the one that exists. Another common error is stopping only when f(c) is small, when what matters is the size of the interval or the error.

Think about it

Why does bisection always converge if \( f \) is continuous and changes sign, even when \( f \) is very irregular?

At each step it keeps a subinterval with a sign change, which contains a root by the intermediate value theorem, and its length halves, so it tends to zero.

Exercises 10

  1. What sign condition at the endpoints of [a, b] is needed to apply the bisection method?
  2. What is the midpoint of the interval [2, 5]?
  3. If the initial interval has length 4, what is its length after one iteration?
  4. Which theorem guarantees that a root exists in an interval with a sign change?
  5. What must be evaluated at each iteration of the bisection method?
  6. For f(x) = x³ − x − 2 on [1, 2], what is the first midpoint c?
  7. For \( f(x) = x^3 - x - 2 \) on \( [1, 2] \), \( f(1) = -2 \) and \( f(1.5) = -0.125 \). In which subinterval is the root?
  8. If the error after \( n \) iterations is at most \( (b - a)/2^{n+1} \), what is the smallest number of iterations that guarantees an error below \( 0.001 \) on \( [0, 1] \)?
  9. For f(x) = cos(x) − x on [0, 1], what signs do f(0) and f(1) have?
  10. Let f be continuous on [a, b] with f(a) = 1 and f(b) = 3. Can the bisection method guarantee a root in [a, b]? Justify with a counterexample if not.

References

  • Richard L. Burden, J. Douglas Faires, Annette M. Burden, Numerical Analysis, 10th edition, Cengage Learning, 2016.
  • Lloyd N. Trefethen, David Bau III, Numerical Linear Algebra, 1st edition, SIAM, 1997.