Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 37 ยท Root Finding

The Bisection Method

Learn the bisection method for finding roots: the intermediate value theorem, a Python implementation, how many iterations you need, its limits, and a SciPy comparison.

A root of a function f is a number r with f(r) = 0. Finding roots is the most common numerical task: the break-even price, the angle at which a projectile lands, the interest rate that makes a loan balance. The bisection method is the simplest and most reliable root finder. It works like a number-guessing game: pick the middle, learn which half contains the answer, and throw the other half away.

Bisection is slow compared with the methods in the next lessons, but it almost cannot fail, and that makes it the safety net behind many professional solvers.

The idea: bracket and halve

The method rests on the intermediate value theorem: if f is continuous on [a, b] and f(a) and f(b) have opposite signs, then f has at least one root inside [a, b]. We say the interval brackets a root.

The algorithm:

  1. Compute the midpoint m = (a + b) / 2.
  2. If f(m) is zero (or the interval is small enough), stop.
  3. If f(a) and f(m) have opposite signs, the root is in [a, m]: set b = m. Otherwise set a = m.
  4. Repeat.
flowchart TD
    A["Start with [a, b], f(a) f(b) < 0"] --> B["m = (a + b) / 2"]
    B --> C{"f(a) and f(m)<br/>differ in sign?"}
    C -->|"yes"| D["b = m"]
    C -->|"no"| E["a = m"]
    D --> F{"b - a small enough?"}
    E --> F
    F -->|"no"| B
    F -->|"yes"| G["Return midpoint"]

Every pass cuts the bracketing interval in half and keeps the half where the sign changes.

Implementation

Python Bisection from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The interval [1, 2] brackets the root of xยณ - x - 2 because f(1) = -2 and f(2) = 4. After about 33 steps the answer is correct to 1e-10.

Notice that the code multiplies fa * fm to compare signs. That works, but fa * fm can underflow to zero for tiny values or overflow for huge ones. Comparing the signs themselves ((fa < 0) != (fm < 0)) is safer in serious code.

How many iterations do you need?

After n steps the interval has width (b - a) / 2^n, and the midpoint is within half of that of the root. This is a guaranteed error bound:

|m_n - r| โ‰ค (b - a) / 2^(n+1)

Solving for n gives the number of steps needed for a tolerance tol:

n โ‰ฅ log2((b - a) / tol) - 1

Python Predict the number of steps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You gain one binary digit per step, so about 3.3 steps per decimal digit: this is linear convergence with ratio 1/2. The bound depends only on the interval, not on f, which is what makes bisection predictable. The cost of reliability is speed: Newton's method, next lesson, needs maybe five steps for the same job.

Choosing the starting bracket

Finding a bracket is the only difficult part. Two practical approaches:

  • Plot or tabulate the function over a wide range and look for sign changes.
  • Scan automatically: evaluate f on a fine grid and report each subinterval where the sign changes.
Python Find all brackets automatically, then bisect

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Scanning can miss two roots that fall inside one grid cell (the sign changes twice and the product is positive), so use a finer grid when roots may be close together.

When bisection fails or misleads

Situation What happens
No sign change (f(a) f(b) > 0) There may be zero or an even number of roots; the method cannot start
Root of even multiplicity, like xยฒ f touches zero without changing sign, so no bracket exists
Several roots in the bracket It converges to one of them (which one is not predictable)
A discontinuity, like 1/x on [-1, 1] The sign changes, but there is no root: bisection converges to the jump
Python Bisection can converge to a pole

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sign change at x = 0 fooled the method. Always check that |f(root)| is small afterwards.

Comparing with SciPy

SciPy offers scipy.optimize.bisect, and its more advanced relative brentq, which combines bisection with faster interpolation steps but keeps the guaranteed bracketing. In practice you would nearly always reach for brentq; you will meet it in the last lesson of this chapter.

Python
from scipy.optimize import bisect
print(bisect(lambda x: x**3 - x - 2, 1, 2, xtol=1e-12))

Use bisection when you need guaranteed convergence, when f is only continuous (no derivative available), or to get a good starting value for a faster method.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What condition must hold to start bisection on [a, b]?

    By the intermediate value theorem a continuous function with opposite signs at the endpoints has a root inside.
  2. 2. Starting with an interval of width 1, about how many bisection steps give an error below 1e-6?

    n >= log2(1/1e-6) - 1 is about 19, so roughly 20 steps.
  3. 3. What is the order of convergence of bisection?

    The error bound is halved each step.
  4. 4. Why can bisection fail on f(x) = x^2 near its root?

    x^2 touches zero but is non-negative everywhere; without opposite signs bisection cannot start.
  5. 5. After bisection returns, what should you check?

    A discontinuity like 1/x changes sign without a root, so verify the residual.

Summary

  • Bisection keeps a bracketing interval and halves it each step.
  • It needs only continuity and a sign change; it never diverges.
  • The error after n steps is at most (b - a) / 2^(n+1), so you can predict the steps in advance.
  • Convergence is linear: one bit (about 0.3 digits) per step.
  • Check the residual afterwards; poles and even-multiplicity roots break the assumptions.

Next: Newton-Raphson Method