Bisection: finding a root by halving

When there is no formula

Quadratics have a formula for their roots (lesson 1.2.2), and cubics and quartics have long, awkward ones. From degree 5 on, no general formula built from arithmetic and roots exists. Most equations that mix powers with other functions have no formula either.

A numerical method finds a root without a formula. It starts from a rough answer and improves it step by step, until the answer is as accurate as you need. The accuracy is a distance along the $x$-axis, in the units of $x$.

The guarantee: a sign change traps a root

A function is continuous when its graph has no gaps or jumps: you can draw it without lifting your pen. Polynomials are continuous everywhere. Lesson 2.1.2 makes the idea exact.

An interval $[a, b]$ with a sign change is a bracket. For $f(x) = x^2 - 2$, $f(1) = -1$ and $f(2) = 2$, so $[1, 2]$ is a bracket. It holds the root $\sqrt{2}$.

Bisection: halve the bracket

Bisection shrinks a bracket while keeping the root inside. Cut the bracket at its midpoint and check the sign there. One of the two halves still has a sign change, so it is a smaller bracket.

Here are six steps for $x^2 - 2$ on $[1, 2]$.

At step 1, $f(1.5)$ is positive, like $f(2)$, so the sign change is in $[1, 1.5]$. At step 2, $f(1.25)$ is negative, like $f(1)$, so the root is in $[1.25, 1.5]$. After six steps the bracket is $[1.40625, 1.421875]$, of width 0.015625, and it holds $\sqrt{2} \approx 1.41421$.

Press Next step to run the table yourself and watch the shaded bracket halve. Then pick $x^3 - x - 1$, whose root is near 1.3247, and watch the bracket close in on it.

A falling function

The step only compares signs, so it works whether the graph rises or falls. Take $h(x) = 3 - x^2$ on $[1, 2]$: $h(1) = 2$ is positive and $h(2) = -1$ is negative. The graph falls through zero at $\sqrt{3} \approx 1.73205$.

At 1.5 the value is positive, like $h(1)$, so the new bracket is $[1.5, 2]$. For a rising function a positive value would have kept the left half instead. So compare the sign of $f(m)$ with the sign at $a$; its sign alone does not say which half to keep.

Several roots in one bracket

The cubic $p(x) = (x - 1)(x - 2)(x - 3)$ from lesson 1.3.1 has three roots in $[0, 4]$. The first midpoint is 2, and $p(2) = 0$, so bisection stops at once with the root 2. On $[0, 3.5]$ it finds 1 instead, and on $[0.5, 4]$ it finds 3: the bracket decides which root you get.

How close, and how many steps

Each step halves the width of the bracket, whatever the function. After $n$ steps a bracket of width $b - a$ has width $\frac{b - a}{2^n}$. The root is inside it, so the midpoint is within half that width of the root.

Every 10 steps divide the width by $2^{10} = 1024$, which is about 1000. So each 10 halvings buy about three more correct decimal places.

From width 1 to $10^{-6}$, you need $2^n \ge 1{,}000{,}000$. $2^{19} = 524{,}288$ is too small and $2^{20} = 1{,}048{,}576$ is enough, so it takes 20 steps. Reaching $10^{-8}$ takes 27 steps, and $10^{-10}$ takes 34.

The count depends only on the bracket and the accuracy, never on $f$. That is bisection's strength: it is slow, but certain once the root is bracketed.

Where bisection fails

The guarantee needs a sign change and a continuous function. Take either away, and bisection can miss a root or report one that is not there.

• No sign change, so no bracket. $x^2 + 1$ is 2 at both $-1$ and 1, and it has no root. But equal signs can also hide roots: $p(0.5)$ and $p(2.5)$ are both negative, with the roots 1 and 2 between them.
• A double root. $(x - 1)^2$ is 1 at both 0 and 2. It touches zero at 1 without changing sign (lesson 1.3.1), so no bracket around 1 exists, however small. Bisection cannot find a double root at all.
• A jump. Take the piecewise function (lesson 1.1.2) that is $x - 2$ for $x < 1$ and $x + 1$ for $x \ge 1$. It changes sign on $[0, 2]$, from $-2$ to 3, yet it has no root. It leaps from just below $-1$ to 2 at $x = 1$, and bisection closes in on the jump.

So bisection needs two checks. Before starting, make sure $f(a)$ and $f(b)$ have opposite signs. After finishing, check that $f$ is close to 0 at the answer.

In practice: brentq

SciPy's brentq(f, a, b) takes the same bracket. It mixes bisection steps with faster guesses from lines and curves drawn through recent points, so it is both safe and quick. Without a sign change it refuses to start and raises ValueError.

Lesson 1.3.3 meets a faster method that also uses the steepness of the graph. Case study 1.3.5 brackets interest rates with brentq.

Common mistakes

1. Check the bracket first. If $f(a) \cdot f(b) > 0$, there is nothing to trap.
2. Compare the sign of $f(m)$ with the sign at $a$. For a falling function, a positive $f(m)$ means keep $[m, b]$.
3. Keep the half with the sign change, not the half whose midpoint value looks smaller.
4. A sign change needs a continuous function. A jump or a blow-up changes sign without a root, so check $f$ at the answer.
5. No sign change does not mean no root. Two roots, or a double root, hide behind equal signs.
6. A bracket with several roots gives one of them, and the bracket decides which.
7. The width halves each step. After $n$ steps it is $\frac{b - a}{2^n}$, not $\frac{b - a}{2n}$.