Numerical Computation

Bisection Method: Finding Roots by Halving the Interval

Numerical Computation Study guides

The bisection method finds a root of f(x) = 0 by repeatedly halving an interval where the sign changes. See the steps, the stopping rule and the iteration count formula.

The bisection method solves f(x) = 0 for a continuous function f. It needs an interval [a, b] where f(a) and f(b) have opposite signs. By the intermediate value theorem there is at least one root inside. Compute the midpoint c = (a + b) / 2 and evaluate f(c). If f(c) = 0 you are done. Otherwise keep the half where the sign still changes: if f(a) and f(c) have opposite signs the new interval is [a, c], else it is [c, b]. Repeat.

Each iteration halves the interval, so after n iterations the interval length is (b - a) / 2^n and the midpoint is within that distance of a root. To guarantee an absolute error below a tolerance e, you need n at least log2((b - a) / e) iterations, rounded up. This gives a safe, predictable count before you start. The method always converges when the starting interval brackets a root, but the convergence is slow (linear, gaining about one binary digit per step).

Common mistakes: starting with an interval where f(a) and f(b) have the same sign, which gives no guarantee; using it for a root where the graph touches the axis without crossing (an even-multiplicity root), which has no sign change; and stopping too early. Typical stopping rules are |b - a| below a tolerance, |f(c)| below a tolerance, or a maximum number of iterations. Compared with Newton-Raphson, bisection is slower but needs no derivative and cannot diverge.

Key points

  • Need f(a) x f(b) < 0 and f continuous.
  • c = (a + b) / 2, keep the half with the sign change.
  • Interval length after n steps: (b - a) / 2^n.
  • Iterations needed: n >= log2((b - a) / tolerance).
  • Always converges but only linearly.

Worked example

Find a root of f(x) = x^2 - 2 on [1, 2]. f(1) = -1 and f(2) = 2. c1 = 1.5, f(1.5) = 0.25 > 0, so the root is in [1, 1.5]. c2 = 1.25, f = -0.4375 < 0, so [1.25, 1.5]. c3 = 1.375, f = -0.1094 < 0, so [1.375, 1.5]. c4 = 1.4375, f = 0.0664 > 0, so [1.375, 1.4375]. The root is near 1.414, the square root of 2. For tolerance 0.001 you need n >= log2(1 / 0.001) = about 10 iterations.

Common questions

When does the bisection method fail?

It cannot start if f(a) and f(b) have the same sign, and it can miss roots where the function touches zero without changing sign.

How many iterations does bisection need?

At least log2((b - a) / tolerance), rounded up.

Related topics

BASMAGLY is an independent student project, not an official Delta University site. Check lectures and your instructor for the final word.