Maths › Numerical methods › Locating roots and iteration

Locating roots and iteration

Plenty of equations refuse to be solved 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.

Year 13EDEXCEL 9MA0 9.1, 9.2

Builds on Sequences and sigma notation and Polynomials and the factor theorem.

IN THIS TOPIC

  • Trap a root by a change of sign, and justify accuracy claims with a tighter trap.
  • Know how the sign change test fails: discontinuities and evenly many roots.
  • Iterate xn+1 = g(xn), reading convergence from staircase and cobweb diagrams.

WHAT YOU PROBABLY THINK

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. What can be said cheaply: f(1) = −1 and f(2) = 5, and a continuous curve cannot get from below the axis to above it without crossing. The sign change traps a root in (1, 2), and tighter intervals sharpen the trap: f(1.25) < 0 and f(1.35) > 0, which is precisely the working that proves the root is 1.3 to one decimal place.

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 there rounds to 1.3.

Choosing the bounds is the thinking: they come from the rounding claim, not from the original interval, and quoting f at both of them is compulsory working.

Two ways the sign change test misleads: a parabola touching the axis at its double root keeps the same sign either side, and the reciprocal curve changes sign across its asymptote without any root at allf = (x − 1)²no sign change, root anywayf = 1/xsign change, no rootthe sign change test needs a continuous curve and one crossing
FIG. 1The two standard failures: a double root touches without crossing, so no sign change; an asymptote jumps sign with no root anywhere near.

The lie at the top oversells the test in both directions, and the figure shows the two directions. (x − 1)2 has a root at 1 with no sign change, the curve touching and retreating, and any interval holding an even number of crossings looks rootless from the endpoints alone. Meanwhile 1/x changes sign across 0 with no root at all, the jump belonging to an asymptote. The test needs continuity, and it counts crossings only in parity.

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. For the cubic above, one rearrangement is

xn+1 = (xn + 1)1/3

and from x0 = 1 the sequence runs 1.2599, 1.3123, 1.3224, 1.3243, …, settling on 1.3247, which is the root. Each iterate is found by replacing x with the previous answer, an exam-calculator one-liner using the ANS key.

A staircase diagram for the iteration x next equals the cube root of x plus 1 starting from 1: vertical steps up to the curve and horizontal steps across to the line y equals x climb into the corner where the curve and line cross at the root 1.3247x₀ = 1y = ∛(x + 1)y = xroot 1.3247…up to the curve, across to the line
FIG. 2The staircase: up to the curve applies g, across to y = x recycles the output as input. A shallow curve at the crossing means the steps shrink and the walk converges.

The picture explains when this works. Where y = g(x) crosses y = x is a solution, and near the crossing the curve's steepness decides everything: a shallow curve (gradient between −1 and 1) pulls iterates in, staircase-fashion when the gradient is positive, spiralling cobweb-fashion when it is negative, while a steep curve throws them out. The rearrangement x = x3 − 1 aims at the same root, and from 1.3 it produces 1.197, 0.715, −0.634, escaping at speed: same equation, wrong staircase.

TRY IT UNSEEN

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.

Quote iterates unrounded until the final answer, and confirm the accuracy the sign-change way if the question asks for a proof rather than a value.

THE EXAM BIT

  • Quote f at both interval endpoints, note the sign change, and say f is continuous; all three parts carry marks.
  • 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.
  • Staircase means the curve's gradient at the crossing is positive, cobweb negative; convergence needs it between −1 and 1.

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, a cobweb closing rather than 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 the sequence in, a steep one throws it out.

CHECK YOUR PROGRESS

Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.

  • Trap a root by a change of sign, and justify accuracy claims with a tighter trap.
  • Know how the sign change test fails: discontinuities and evenly many roots.
  • Iterate xn+1 = g(xn), reading convergence from staircase and cobweb diagrams.

No animated video for this topic yet; these notes stand alone.