Bisection: halving the interval

What you will be able to do

After this lesson you can

• find an interval that holds a root by looking for a change of sign,
• write the bisection method and use it to solve an equation, and
• say when bisection works and when it fails.

Equations without a formula

In maths class, you solved $x^2 - 5x + 6 = 0$ by factorising, and there is a formula for every quadratic. But many equations have no formula that solves them. Try $\cos x = x$: where does the graph of cosine meet the line $y = x$? No algebra gives the answer. For a polynomial of degree five or more, mathematicians have proved that there is no general formula. Even for the cubic $x^3 - 2x - 5 = 0$, the formula exists, but it is long and nobody uses it.

In science, such equations are common. A computer solves them by a numerical method: a method that makes better and better guesses, until the answer is as accurate as we need. Two such methods are the topic of this lesson and the next one.

A root of a function $f$ is a number $x$ for which $f(x) = 0$. Solving the equation $g(x) = h(x)$ is the same as finding a root of $f(x) = g(x) - h(x)$. So we need only one tool: a way to find roots.

The idea: a change of sign

Look at the graph of $f(x) = x^3 - 2x - 5$. At $x = 2$ the value is $8 - 4 - 5 = -1$, below zero. At $x = 3$ it is $27 - 6 - 5 = 16$, above zero. The graph goes from below the axis to above it without a break, so it must cross the axis somewhere between 2 and 3. This is the idea of the intermediate value theorem: a continuous function that has opposite signs at $a$ and $b$ has a root between $a$ and $b$.

Here is a way to find such a pair of numbers with an array. Calculate $f$ at many points, and look for places where the sign changes.

Predict first. The values at 2 and 2.5 are $-1$ and $5.625$. Where does the sign change? Then run it.

• np.sign(y) is $-1$, $0$ or $1$ for each value. y[:-1] is all values but the last, and y[1:] is all but the first, so np.sign(y[:-1]) != np.sign(y[1:]) compares each value with the next one. Where they differ, the sign changed.
• np.where(...)[0] gives the places of those changes. There is one, between $x = 2$ and $x = 2.5$.

So the root is between 2 and 2.5. Such a pair is called a bracket of the root.

Bisection

The method is to cut the bracket in half again and again.

1. Find the middle point $m = (a + b) / 2$.
2. Look at the sign of $f(m)$. If the sign changes between $a$ and $m$, the root is in the left half, so make $m$ the new $b$. Otherwise, the root is in the right half, so make $m$ the new $a$.
3. Repeat until the interval is as narrow as you want.

Predict first. The first interval is 2 to 2.5, with the width 0.5. How wide will it be after 3 steps? Then run it.

The root is 2.09455. It took 19 steps. Why 19? After $n$ steps the width is $0.5 / 2^n$. We need $0.5 / 2^n$ to be less than $10^{-6}$, so $2^n$ must be more than $500\,000$, and $2^{19} = 524\,288$. Bisection is slow but sure: a gain of one digit takes about 3.3 steps, and it always works when there is a bracket.

The last line checks the answer: $f(\text{root})$ is close to zero. A good habit is to always put the answer back in the equation.

The root is about 1.5214. After 6 steps the bracket is 1/64 wide, so its middle is within 0.008 of the root, however hard the formula is.

Two uses

When bisection fails

Common mistakes

• Starting without a bracket. Always check the signs at the two ends.
• Putting the middle point in the wrong half. The half that holds the sign change is the one to keep.
• A tolerance that is too small. With decimals that are not exact, a tolerance below $10^{-15}$ can loop for ever.
• Not checking the answer. Put it in the equation.
• Looking for a root of a function that has a break. The sign change can be a jump.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

1. Warm-up. Open the lab Bisection. You write the method as a function.
2. Build. Open the problem Find the bracket and the problem Time of fall by bisection.

Remember these

• A root of $f$ is a number $x$ for which $f(x) = 0$.
• If $f$ is continuous and has opposite signs at $a$ and $b$, there is a root between them.
• Bisection halves the bracket at each step, and keeps the half with the change of sign.
• It always works when there is a bracket, but a gain of one digit takes about three steps.
• It fails when there is no change of sign.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. $f(1) = -3$ and $f(2) = 4$. Is there a root between 1 and 2? What do you need to assume?

2. A bracket has the width 1. What is its width after 10 steps of bisection?

3. Why can bisection not find the root of $x^2$ in $[-1, 1]$?

4. Where does the next step of bisection look for the root of $f$ on $[2, 3]$ if $f(2.5) < 0$ and $f(3) > 0$?