Most equations have no formula for their roots. A numerical method finds a root to any accuracy we want. The first step is to locate it: if a continuous function changes sign on an interval, a root lies inside. Bisection then halves the interval again and again, keeping the half with the sign change. Each halving gains one binary digit, and the number of steps can be worked out in advance.
about 30 min1 simulation2 practice questions
Lesson 1 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
locate a root by a change of sign, and say when this test misleads;
show that a root is correct to a given number of decimal places;
carry out bisection and work out how many steps it needs.
An equation with no formula
Try to solve x3+2x−5=0 by factorising. You will not succeed. A cubic does have a formula, but it is long. For x=cosx there is no formula at all, and in 1824 Abel proved that the general equation of degree five has no formula in roots either. Yet engineers need such roots every day. They use numerical methods: rules that give better and better approximations.
A change of sign
Let f be continuous on [a,b], with f(a) and f(b) of opposite signs. Then the graph must cross the x-axis somewhere between a and b. So f has at least one root in (a,b). This is the intermediate value theorem.
For f(x)=x3+2x−5: f(1)=−2 and f(2)=7. So a root lies between 1 and 2.
When the test misleads.
A break in the graph.f(x)=x−21 has f(1)=−1 and f(3)=1, but no root. It is not continuous at x=2.
A root that only touches.(x−1)2 has a root at 1, but no change of sign near it.
Two roots close together. If an interval holds two roots, the signs at its ends can agree.
So a change of sign proves a root only for a continuous function. No change of sign proves nothing.
Correct to two decimal places
To show that a root is 1.33 correct to two decimal places, check the signs at 1.325 and 1.335, the ends of the rounding interval. Here f(1.325)≈−0.024 and f(1.335)≈0.049. The signs differ, so the root lies in (1.325,1.335), and every such number rounds to 1.33.
Interval bisection
Bisection repeats one step. Take the midpoint m=21(a+b). Work out f(m). Keep the half in which the sign changes. Here is the start for f(x)=x3+2x−5 on [1,2]:
Step
Midpoint
New interval
1
1.5
[1,1.5]
2
1.25
[1.25,1.5]
3
1.375
[1.25,1.375]
4
1.3125
[1.3125,1.375]
At step 1, f(1.5)=1.375>0, so the sign change is on the left. At step 2, f(1.25)<0, so it is on the right.
The curve y = x cubed + 2x - 5 for x from 0.8 to 2.1, crossing the x-axis near 1.33. Below the axis, four nested horizontal bars show the intervals kept by bisection: from 1 to 2, from 1 to 1.5, from 1.25 to 1.5 and from 1.25 to 1.375, each half as long as the one before, all containing the root.
How many steps?
After n halvings the width is 2nb−a. To make it less than ε, we need
2n>εb−a.
The midpoint of the last interval is within half the width of the root. For [1,2] and a width below 10−6, 2n>106 gives n=20. Each step gains one binary digit, so each decimal place costs about 3.3 steps. The method is slow, but it never fails once a sign change is found.
Practise with new numbers
Try it in Python
The program runs bisection on x3+2x−5=0 until the interval is narrow enough, and counts the steps.
Common mistakes
Trusting a sign change across a break. Check that f is continuous on the interval.
Missing a touching root.(x−1)2 never changes sign.
The wrong rounding interval. For 1.33 to two places, test 1.325 and 1.335, not 1.32 and 1.34.
Counting steps loosely. Solve 2n>εb−a and take the least whole n.
Remember these
A continuous f with f(a)f(b)<0 has a root in (a,b).
Bisection: keep the half with the sign change.
Width after n steps: 2nb−a.
Slow but sure: one binary digit per step.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Show that x3−4x+1=0 has a root between 0 and 1.
A student says that tanx has a root between 1 and 2, because tan1>0 and tan2<0. Is this right?
Which two values would you test to show that a root is 2.7 correct to one decimal place?
Bisection starts on [0,1]. What is the width after 10 steps?
Why can bisection not find the root of (x−3)2=0?
References
R. L. Burden and J. D. Faires, Numerical Analysis, Chapter 2, Solutions of Equations in One Variable.
Enroll free in Numerical Solution of Equations
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.