Iterative methods

Iterative methods

Spec 6.2 · Edexcel International A Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A recurrence relation xn+1=f(xn)x_{n+1}=f(x_n) gives each term from the one before.
  • To solve f(x)=0f(x)=0 by iteration, rearrange it to x=g(x)x=g(x) and use xn+1=g(xn)x_{n+1}=g(x_n).
  • If the terms settle, the limit α\alpha satisfies α=g(α)\alpha=g(\alpha).
  • Use full calculator values and round only at the end.
  • Confirm a root to k decimal places with a change of sign.

Recurrence relations

Each term is found by putting the previous term into the rule.

A recurrence relation xn+1=f(xn)x_{n+1}=f(x_n) defines a sequence from a starting value x0x_0.

For example xn+1=4xn+33x_{n+1}=\sqrt[3]{4x_n+3} with x0=2x_0=2 gives x1=113=2.224x_1=\sqrt[3]{11}=2.224, then x2=2.2828x_2=2.2828, x3=2.2977x_3=2.2977, and so on.

If the terms settle towards a value, the sequence converges to a limit LL. Iteration finds approximate solutions of equations that cannot be solved algebraically.

  1. 1

    Start with xₙ

    the current term

  2. 2

    Apply the rule

    put xₙ into f

  3. 3

    Get xₙ₊₁

    the next term, which becomes the new xₙ

Then back to step 1

Each term feeds the next

If xn+1=2xn−1x_{n+1}=2x_n-1 and x0=3x_0=3, what is x2x_2?

Rearranging into x = g(x)

Rearrange f(x)=0f(x)=0 so that xx is on its own side, then iterate.

There are many possible rearrangements. For x3−4x−3=0x^3-4x-3=0 you can write x3=4x+3x^3=4x+3 and so x=4x+33x=\sqrt[3]{4x+3}, or x=x3−34x=\frac{x^3-3}{4}.

In an exam the rearrangement is usually given and you are asked to show that it holds: write each algebraic step, isolate the required term and finish on exactly the printed form. Take care with signs and with dividing every term.

0.511.522.533.540.511.522.533.54xyroot ≈ 2.30y = xy = ∛(4x + 3)
The iteration x = ∛(4x + 3) converges where the curve meets the line y = x, at the root of x³ − 4x − 3 = 0.
  • x3−4x−3=0x^3-4x-3=0x=4x+33x=\sqrt[3]{4x+3}

Worked example

Show that x3−3x2−2=0x^3-3x^2-2=0 can be written as x=3+2x2x=3+\frac{2}{x^2}.

Rearrange x3=4x+3x^3=4x+3 to make xx the subject in the form x=…3x=\sqrt[3]{\dots}.

Finding the limit

The limit α\alpha satisfies α=g(α)\alpha=g(\alpha), so it solves the original equation.

For large nn both xnx_n and xn+1x_{n+1} are approximately α\alpha, so α=g(α)\alpha=g(\alpha). This is a fixed point of the iteration.

For xn+1=4xn+33x_{n+1}=\sqrt[3]{4x_n+3} the limit satisfies α=4α+33\alpha=\sqrt[3]{4\alpha+3}, which cubes to α3−4α−3=0\alpha^3-4\alpha-3=0.

Work with full calculator values and round only at the end, to a stated number of decimal places.

0.511.522.533.540.511.522.533.54xylimit ≈ 2.30y = ∛(4x + 3)y = x
The limit is where y = ∛(4x + 3) meets y = x, at about x = 2.30.

An iteration xn+1=g(xn)x_{n+1}=g(x_n) converges to α\alpha. Which equation does α\alpha satisfy?

Confirming a root

Test f at two values half a unit in the last place either side.

To show 2<α<2.52<\alpha<2.5 for f(x)=ln⁡x+x−3f(x)=\ln x+x-3: f(2)=−0.307<0f(2)=-0.307<0 and f(2.5)=0.416>0f(2.5)=0.416>0; ff is continuous, so a root lies in (2,2.5)(2,2.5).

A full answer gives both values (or their signs), states that ff is continuous, and states the conclusion.

To confirm α=3.196\alpha=3.196 (3 d.p.), test f(3.1955)f(3.1955) and f(3.1965)f(3.1965): opposite signs show 3.1955<α<3.19653.1955<\alpha<3.1965.

3.1953.19523.19543.19563.19583.1963.19623.19643.19663.19683.1973.19553.1965

To confirm a root is 2.31 to 2 d.p., which two values should you test?

Worked example

Show a root exists, rearrange, iterate, then confirm with a sign change.

Put the whole method together: locate the root by sign change, rearrange, iterate from the starting value, then confirm the accuracy.

2.62.833.23.43.63.8−4−22468xy(3, −2)(3.5, 4.125)α ≈ 3.196y = x³ − 3x² − 2
y = x³ − 3x² − 2 crosses the axis at α ≈ 3.196, between 3 and 3.5.

Full worked example

The equation x3−3x2−2=0x^3-3x^2-2=0 has a root α\alpha between 3 and 3.5. Show that x=3+2x2x=3+\frac{2}{x^2}, use x0=3.2x_0=3.2 to find x1x_1, x2x_2, x3x_3, and show that α=3.196\alpha=3.196 to 3 d.p.

Why do you stop iterating when consecutive terms agree to the required accuracy?

When iteration goes wrong

No: a sequence may diverge, oscillate, or settle on a different root.

Different rearrangements of the same equation behave differently, and a poor starting value can also cause failure. A sequence may diverge (terms grow without limit) or converge to a different root.

A converging sequence can oscillate about the root while closing in on it, such as xn+1=3−ln⁡xnx_{n+1}=3-\ln x_n with x0=2x_0=2 (2.307, 2.164, 2.228, ...).

In examination questions a suitable rearrangement is supplied.

00.511.52x₀x₁x₂x₃TermValue
Terms of xₙ₊₁ = 3 − ln xₙ with x₀ = 2 alternate above and below the root while closing in on it.

Successive terms are 1.2, 1.8, 3.1, 6.4. What is happening?

Try an exam question

f(x)=x3−x−3f(x)=x^3-x-3. (a) Show that f(x)=0f(x)=0 has a root α\alpha between 1 and 2. (b) Show that the equation f(x)=0f(x)=0 can be rearranged to x=x+33x=\sqrt[3]{x+3}.

[5 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find x1x_1, to 3 decimal places.

1 mark, marked against the mark scheme

Revision notes