Maths › Numerical methods › Locating roots and iteration
Locating roots and iteration
Plenty of equations have no solution you can reach by rearrangement, and this unit stops trying. A sign change traps a root inside an interval, a rearranged equation iterated from a starting value walks towards it, and staircase and cobweb diagrams show whether the walk is closing in or running away.
Builds on Sequences and sigma notation and Polynomials and the factor theorem.
IN THIS TOPIC
- Trap a root by a change of sign, with continuity stated.
- Prove an accuracy claim by choosing the right pair of test values.
- Name the two ways the sign change test fails.
- Iterate xn+1 = g(xn) and read convergence off a staircase or cobweb diagram.
COMMON MISCONCEPTION
A sign change between a and b means exactly one root between a and b.
Trapping a root
The cubic x3 − x − 1 = 0 has no nice roots and the factor theorem finds nothing. Here is what can be said cheaply. f(1) = −1, f(2) = 5, and a continuous curve cannot get from below the axis to above it without crossing on the way. So a root is trapped in (1, 2). Squeeze the interval and the trap tightens, and a tight enough trap proves an accuracy claim outright.
WORKED EXAMPLE
Proving an accuracy claim
Show that x3 − x − 1 = 0 has a root α, and that α = 1.3 correct to 1 decimal place.
f(1) = −1 < 0 and f(2) = 5 > 0, and f is continuous, so a root lies in (1, 2).
For the accuracy claim, test the interval of values that round to 1.3: f(1.25) = −0.297 < 0 and f(1.35) = 0.110 > 0.
The sign change puts α in (1.25, 1.35), and every number in there rounds to 1.3.
Choosing the bounds is the thinking. They come from the rounding claim, never from the original interval, and quoting f at both of them is compulsory working.
Two ways the test can mislead
The sign-change test can mislead in both directions, and the figure shows both.
First direction. (x − 1)2 has a root at x = 1 with no sign change at all, since the curve touches the axis and retreats, and any interval holding an even number of crossings looks rootless from its endpoints. Second direction. 1/x flips sign across 0 with no root anywhere, the jump belonging to an asymptote. So the test needs continuity, and even then it counts crossings only in parity. Be ready to name both failures; they are worth a mark each and take one sentence.
Iterating towards it
To close in on the trapped root, rearrange the equation into the form x = g(x) and iterate. Feed a starting value in, feed the answer back, repeat. One rearrangement of the cubic above is
and from x0 = 1 the sequence runs 1.2599, 1.3123, 1.3224, 1.3243, … , settling on 1.3247. Do it with the ANS key. Type the expression once, press equals, and keep pressing.
The picture explains when this works, and the condition is local: it is the steepness of g at the crossing that counts, and it governs starting values near enough to that crossing. Where y = g(x) crosses y = x you have a solution. A shallow curve there, gradient strictly between −1 and 1, pulls nearby iterates in, as a staircase when the gradient is positive and as a spiralling cobweb when it is negative. A steep curve, gradient beyond ±1, throws them out, and a gradient whose size is 1 settles nothing either way. Rearranging the same cubic as x = x3 − 1 aims at the same root, and from 1.3 it gives 1.197, 0.715, −0.634. Same equation, wrong staircase.
INDEPENDENT PRACTICE
Running the iteration
Using xn+1 = (xn + 1)1/3 with x0 = 1, find x1, x2 and x3 to 4 decimal places, and state the root of x3 − x − 1 = 0 to 3 decimal places.
Show the working
x1 = 21/3 = 1.2599, x2 = 1.3123, x3 = 1.3224.
Continuing until the digits freeze, the root is 1.325 to 3 decimal places.
Keep iterates unrounded on the calculator until the final answer. If the question asks you to prove the accuracy instead of just stating it, go back to a sign change.
ASSESSMENT FOCUS
- Quote f at both endpoints, note the sign change, and say f is continuous. All three parts carry marks and the continuity line is the one candidates skip.
- To prove α = 1.3 to 1 d.p., test 1.25 and 1.35. The bounds come from the rounding claim.
- Be ready to name the failure cases: an even number of roots in the interval, or a discontinuity faking a crossing.
- Iterate with the ANS key and write iterates to more places than the target accuracy asks for.
- Staircase means the gradient of g at the crossing is positive, cobweb means negative. Convergence from nearby starts needs its size below 1.
- A question that supplies the rearrangement wants that rearrangement used, so use it even where another route looks quicker.
CHECK YOURSELF
Show that x3 + x − 5 = 0 has a root in (1, 2), and use xn+1 = (5 − xn)1/3 with x0 = 1.5 to find the root to 3 decimal places.
Show a hint
h(1) and h(2) first; then three or four presses of the ANS key.
Show the answer
h(1) = −3 < 0 and h(2) = 5 > 0 with h continuous, so a root lies in (1, 2).
Iterating: 1.5183, 1.5156, 1.5160, 1.5160, and the digits have frozen.
The root is 1.516 to 3 decimal places. The iterates land alternately above and below it, so this one is a cobweb closing in, not a staircase climbing.
A sign change plus continuity traps a root; tighter traps prove accuracy claims.
Iterate x = g(x) from a start value; a shallow crossing pulls in sequences that start near it, a steep one throws them out.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the locating roots and iteration questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Trap a root by a change of sign, with continuity stated.
- Prove an accuracy claim by choosing the right pair of test values.
- Name the two ways the sign change test fails.
- Iterate xn+1 = g(xn) and read convergence off a staircase or cobweb diagram.
Open the full revision checklist to see every objective in the course in one place.