Maths › Numerical methods › Locating roots and iteration

Locating roots and iteration

Numerical methods approximate roots when an exact solution is unavailable or impractical. A sign change of a continuous function across an interval proves that at least one root lies within it. Fixed-point iteration uses xn+1 = g(xn), and staircase or cobweb diagrams show local convergence or divergence.

Year 13EDEXCEL 9MA0 9.1, 9.2

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

IN THIS TOPIC

  • Show that a root lies in an interval from a change of sign, with continuity stated.
  • Prove an accuracy claim by choosing the pair of test values the rounding requires.
  • Name the two ways the sign change test fails.
  • Iterate xn+1 = g(xn) and read convergence off a staircase or cobweb diagram.
  • Rearrange f(x) = 0 into x = g(x), and say why a fixed point of g is a root of f.

COMMON MISCONCEPTION

A sign change between a and b means exactly one root between a and b.

A sign change across an interval on which f is continuous shows that at least one root lies inside it, not that exactly one does. The test detects crossings only in odd numbers, so three roots give a sign change just as one does, an even number gives none at all, and a discontinuity such as 1/x changes sign across 0 with no root there.

Locating a root by a change of sign

The cubic x3 − x − 1 = 0 has no rational roots, so the factor theorem gives no factorisation. The sign change test still applies. If f is continuous on [a, b] and f(a)f(b) is negative, then at least one root lies in (a, b). Here f(1) = −1 and f(2) = 5, so a root lies in (1, 2). Narrowing the interval to a pair of values that round the same way proves an accuracy claim.

The cubic y equals x cubed minus x minus 1 crossing a shaded band from 1 to 2, with a coral dot at f of 1 equals minus 1 below the axis, an amber dot at f of 2 equals 5 above it, and the root 1.3247 marked where the continuous curve must cross between them.
FIG. 1The sign change, drawn. y = x³ − x − 1 enters the shaded band from 1 to 2 below the axis at f(1) = −1 and leaves it above at f(2) = 5, so the continuous curve crosses somewhere inside, and the crossing at α = 1.3247… is marked where it does.

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.

The test values come from the rounding claim rather than from the original interval, and a complete answer quotes f at both of them.

Two ways the test can mislead

The sign-change test can mislead in two ways, and the figure shows both.

Two counterexamples side by side: a parabola resting its double root on the axis, positive on both sides so the test sees nothing, and the reciprocal curve leaping from negative to positive across its asymptote with no root anywhere, the discontinuity faking a crossing.
FIG. 2The two standard failures: a double root touches without crossing, so no sign change; an asymptote jumps sign with no root anywhere near.

First failure. (x − 1)2 has a root at x = 1 with no sign change, because the curve touches the axis without crossing it, and an interval containing an even number of crossings shows no sign change at its endpoints either. Second failure. 1/x changes sign across 0 with no root there, because the function is discontinuous at 0. The test therefore requires continuity on the interval, and it detects crossings only in odd numbers. State both failures when a question asks for the limitations of the method.

Fixed-point iteration

To approximate the root, rearrange the equation into the form x = g(x) and iterate: substitute a starting value into g and substitute each output back in as the next input. One rearrangement of the cubic above is

xn+1=(xn+1)1/3x_{n+1} = (x_{n} + 1)^{1/3}

and from x0 = 1 the sequence runs 1.2599, 1.3123, 1.3224, 1.3243, … , converging to 1.3247. On a calculator, enter the expression once using the ANS key and press equals repeatedly.

An amber staircase climbing between a shallow cube-root curve and the line y equals x: each vertical step applies the iteration formula, each horizontal step hands the output back as the next input, and the computed iterates 1.2599, 1.3123, 1.3224 close on the marked root.
FIG. 3The staircase: vertically to the curve applies g, horizontally to y = x makes the output the next input. Where the curve is shallow at the crossing, successive iterates move closer to it.

The condition for this to converge is local, and it is set by the gradient of g at the crossing. A solution of x = g(x) is a point where y = g(x) meets y = x. If |g'(x)| is less than 1 at that point, iterates started sufficiently close to it converge, as a staircase when g'(x) is positive and as a cobweb when g'(x) is negative. If |g'(x)| is greater than 1, iterates started near the point move away from it, and |g'(x)| = 1 decides nothing on its own. Rearranging the same cubic as x = x3 − 1 has the same root, but there g'(x) = 3x2, which is 5.26 at the root, and from 1.3 the iterates are 1.197, 0.715, −0.634: the same equation, rearranged into a form whose iteration diverges.

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 stop changing at that accuracy, the root is 1.325 to 3 decimal places.

Keep iterates unrounded on the calculator until the final answer. A question asking for the accuracy to be proved rather than stated requires a sign change across the interval of values that round to the stated figure.

ASSESSMENT FOCUS

  • A complete sign-change argument has three parts: the values of f at both endpoints, the statement that the sign changes, and the statement that f is continuous on the interval.
  • To prove α = 1.3 to 1 d.p., test 1.25 and 1.35. The test values come from the rounding claim.
  • State both failure cases where a question asks for them: an even number of roots in the interval, or a discontinuity across which the sign changes with no root.
  • Iterate with the ANS key and write iterates to more places than the target accuracy requires.
  • A staircase diagram corresponds to a positive gradient of g at the crossing and a cobweb to a negative one. Convergence from nearby starting values requires |g'(x)| to be less than 1 there.
  • Where a question supplies a rearrangement, use that rearrangement: another form of the equation answers a different question.

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 stopped changing at 4 decimal places.

The root is 1.516 to 3 decimal places. Successive iterates lie alternately above and below it, which is the cobweb case, since g'(x) is negative at the root.

A sign change of a continuous function across an interval shows that at least one root lies inside it; a sign change across the values that round to a stated figure proves an accuracy claim.

For xn+1 = g(xn), iterates started near a solution of x = g(x) converge when |g'(x)| is less than 1 there and move away when it is greater than 1.

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.

Question workbook

PDF · 77 KB · print edition · white background

Question workbook

PDF · 78 KB · screen edition · navy

Answer book

PDF · 86 KB · fully worked · navy
15 questions on this topicAnswer them one at a time and mark yourself against the worked answer.Practise this topic

Or read them with their worked answers on the locating roots and iteration questions page.

USED LATER IN

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.

  • Show that a root lies in an interval from a change of sign, with continuity stated.
  • Prove an accuracy claim by choosing the pair of test values the rounding requires.
  • Name the two ways the sign change test fails.
  • Iterate xn+1 = g(xn) and read convergence off a staircase or cobweb diagram.
  • Rearrange f(x) = 0 into x = g(x), and say why a fixed point of g is a root of f.

Open the full revision checklist to see every objective in the course in one place.