Iteration – A Level Maths Year 2

1 The Idea of Fixed Point Iteration

A change of sign search traps a root but closes in slowly. Iteration is a way of homing in on a root automatically: you feed each answer back into a formula and watch the numbers settle down.

Fixed point iteration

Rearrange $\mathrm{f}(x) = 0$ into the form $x = \mathrm{g}(x)$, then use
$x_{n+1} = \mathrm{g}(x_n)$ with a starting value $x_1$ (or $x_0$)

If the sequence $x_1, x_2, x_3, \ldots$ converges to a limit $\alpha$, then letting $n \to \infty$ in $x_{n+1} = \mathrm{g}(x_n)$ gives $\alpha = \mathrm{g}(\alpha)$. So $\alpha$ is a fixed point of $\mathrm{g}$ — and because $x = \mathrm{g}(x)$ is just a rearrangement of $\mathrm{f}(x) = 0$, $\alpha$ is a root.

Graphically, the roots of $x = \mathrm{g}(x)$ are where the curve $y = \mathrm{g}(x)$ meets the line $y = x$.

Calculator technique. Type the starting value and press =. Then type the formula using Ans in place of $x_n$, e.g. ³√(Ans + 4), and press = repeatedly. Each press gives the next term.

2 Rearranging and Iterating

Every equation can be rearranged into $x = \mathrm{g}(x)$ in many ways. Exam questions usually tell you which form to show, then ask you to use it.

Worked Example 1 — Three rearrangements

Show that $x^3 - x - 4 = 0$ can be written in each of the forms (a) $x = \sqrt[3]{x + 4}$ (b) $x = \sqrt{1 + \dfrac{4}{x}}$ (c) $x = x^3 - 4$.

①(a) $x^3 = x + 4$, then take cube roots: $x = \sqrt[3]{x+4}$.

②(b) Divide $x^3 = x + 4$ by $x$ (we can, since $x = 0$ is not a root): $x^2 = 1 + \dfrac{4}{x}$, so $x = \sqrt{1 + \dfrac{4}{x}}$ for the positive root.

③(c) Add $x$ to both sides of $x^3 - x - 4 = 0$: $x = x^3 - 4$.

Worked Example 2 — Carrying out the iteration

Use $x_{n+1} = \sqrt[3]{x_n + 4}$ with $x_1 = 1$ to find $x_2$, $x_3$, $x_4$ and $x_5$ to $4$ decimal places, and hence state the root to $3$ decimal places.

①$x_2 = \sqrt[3]{5} = 1.7100$

②$x_3 = \sqrt[3]{5.7100\ldots} = 1.7874$

③$x_4 = 1.7954$, $x_5 = 1.7962$, and $x_6 = 1.7963$.

④The terms are settling at $1.796\ldots$, so the root is $\alpha \approx 1.796$ to $3$ d.p.

Keep the full calculator value for each step (use Ans). Rounding $x_2$ to $1.71$ and typing it back in introduces errors that build up.

Iteration gives strong evidence, not proof. To prove $\alpha = 1.796$ to 3 d.p., do a sign check on $1.7955$ and $1.7965$ — see Locating Roots.

3 Staircase and Cobweb Diagrams

You can draw an iteration on the graphs of $y = \mathrm{g}(x)$ and $y = x$:

Start at $x_1$ on the $x$-axis and go vertically to the curve. The height is $\mathrm{g}(x_1) = x_2$.
Go horizontally to the line $y = x$. You are now above $x = x_2$.
Go vertically to the curve again (height $x_3$), horizontally to the line, and so on.

Staircase diagram — $x_{n+1} = \sqrt[3]{x_n + 4}$ from $x_1 = 1$. The terms increase steadily towards $\alpha$ from one side.

Cobweb diagram — $x_{n+1} = \sqrt{1 + 4/x_n}$ from $x_1 = 1$. The terms jump from one side of $\alpha$ to the other, spiralling in.

Worked Example 3 — An oscillating sequence

Use $x_{n+1} = \sqrt{1 + \dfrac{4}{x_n}}$ with $x_1 = 1$ to find $x_2$ to $x_6$, and describe how the sequence converges.

$n$	$1$	$2$	$3$	$4$	$5$	$6$
$x_n$	$1$	$2.2361$	$1.6700$	$1.8426$	$1.7807$	$1.8018$

①The terms are alternately above and below $1.796$, getting closer each time.

②This is oscillating convergence, shown by a cobweb diagram. It converges more slowly than the cube-root version — after five steps it is still only accurate to $1$ d.p.

A useful bonus of oscillation: consecutive terms always trap the root. Here $1.7807 < \alpha < 1.8018$.

4 Convergence and Divergence

Not every rearrangement works. Look at the third rearrangement from Worked Example 1:

Worked Example 4 — A divergent iteration

Use $x_{n+1} = x_n^3 - 4$ with $x_1 = 1.8$ to find $x_2$, $x_3$ and $x_4$.

①$x_2 = 1.8^3 - 4 = 1.832$

②$x_3 = 1.832^3 - 4 = 2.1486$

③$x_4 = 2.1486^3 - 4 = 5.919$ — the terms run away from the root even though $x_1$ was within $0.004$ of it. The sequence diverges.

Why? Near $\alpha$, $x_{n+1} - \alpha = \mathrm{g}(x_n) - \mathrm{g}(\alpha) \approx \mathrm{g}'(\alpha)(x_n - \alpha)$. So each step multiplies the error by roughly $\mathrm{g}'(\alpha)$. If that factor is less than $1$ in size the error shrinks; if it is greater than $1$ the error grows.

The convergence condition

$x_{n+1} = \mathrm{g}(x_n)$ converges to $\alpha$ (from a close enough start) if $\;|\mathrm{g}'(\alpha)| < 1$
and diverges from $\alpha$ if $\;|\mathrm{g}'(\alpha)| > 1$

Gradient at the root	Behaviour	Diagram
$0 < \mathrm{g}'(\alpha) < 1$	Converges, terms on one side	Staircase (inwards)
$-1 < \mathrm{g}'(\alpha) < 0$	Converges, terms alternate sides	Cobweb (inwards)
$\mathrm{g}'(\alpha) > 1$	Diverges, terms on one side	Staircase (outwards)
$\mathrm{g}'(\alpha) < -1$	Diverges, terms alternate	Cobweb (outwards)

The closer $\mathrm{g}'(\alpha)$ is to $0$, the faster the convergence. In words: the curve $y = \mathrm{g}(x)$ must be less steep than the line $y = x$ where they cross.

Worked Example 5 — Explaining the three behaviours

The root of $x^3 - x - 4 = 0$ is $\alpha \approx 1.796$. Use $\mathrm{g}'(\alpha)$ to explain the behaviour of each iteration in Worked Example 1.

①(a) $\mathrm{g}(x) = (x+4)^{1/3}$, $\mathrm{g}'(x) = \tfrac13(x+4)^{-2/3}$. At $1.796$: $\mathrm{g}'(\alpha) \approx 0.103$. Between $0$ and $1$ and small: fast staircase convergence.

②(b) $\mathrm{g}(x) = \left(1 + 4x^{-1}\right)^{1/2}$, $\mathrm{g}'(x) = \tfrac12\left(1 + 4x^{-1}\right)^{-1/2} \times (-4x^{-2})$. At $1.796$: $\mathrm{g}'(\alpha) \approx -0.345$. Between $-1$ and $0$: cobweb convergence, slower.

③(c) $\mathrm{g}(x) = x^3 - 4$, $\mathrm{g}'(x) = 3x^2$. At $1.796$: $\mathrm{g}'(\alpha) \approx 9.68 > 1$: divergence.

Worked Example 6 — Different rearrangements, different roots

$x^2 - 5x + 3 = 0$ has roots $\alpha \approx 0.697$ and $\beta \approx 4.303$. Investigate $x_{n+1} = \dfrac{x_n^2 + 3}{5}$.

①$\mathrm{g}'(x) = \dfrac{2x}{5}$. At $\alpha$: $\mathrm{g}'(\alpha) \approx 0.279$, so the iteration converges to $\alpha$. From $x_1 = 1$: $0.8,\ 0.728,\ 0.7060,\ 0.6997, \ldots \to 0.697$.

②At $\beta$: $\mathrm{g}'(\beta) \approx 1.72 > 1$, so it can never converge to $\beta$. From $x_1 = 5$: $5.6,\ 6.872,\ 10.04,\ \ldots$ diverges.

③To find $\beta$, use instead $x = \sqrt{5x - 3}$, with $\mathrm{g}'(\beta) = \dfrac{5}{2\sqrt{5\beta - 3}} \approx 0.581$, which converges.

The starting value matters too. Even a convergent formula can fail if $x_1$ is far from the root, or if it lands on a value where $\mathrm{g}$ is undefined (such as a negative number under a square root).

5 Quick Reference

Method

$\mathrm{f}(x) = 0 \to x = \mathrm{g}(x)$, then $x_{n+1} = \mathrm{g}(x_n)$.

Limit

If $x_n \to \alpha$ then $\alpha = \mathrm{g}(\alpha)$, a root of $\mathrm{f}(x) = 0$.

Graph

Roots where $y = \mathrm{g}(x)$ meets $y = x$.

Staircase

$0 < \mathrm{g}'(\alpha) < 1$: one-sided approach.

Cobweb

$-1 < \mathrm{g}'(\alpha) < 0$: alternating approach.

Diverges

$|\mathrm{g}'(\alpha)| > 1$.

Speed

Smaller $|\mathrm{g}'(\alpha)|$ means faster convergence.

Accuracy

Use Ans; confirm the final answer with a sign change.

Drawing

Vertical to the curve, horizontal to the line, repeat.

6 Practice Questions

Question 1

Use $x_{n+1} = \sqrt{x_n + 3}$ with $x_1 = 2$ to find $x_2$, $x_3$ and $x_4$ to $4$ decimal places.

▶ Show solution

$x_2 = \sqrt{5} = 2.2361$

$x_3 = \sqrt{5.2361\ldots} = 2.2882$

$x_4 = \sqrt{5.2882\ldots} = 2.2996$

Question 2

The sequence in Question 1 converges to $\alpha$. Find the equation that $\alpha$ satisfies, and hence find $\alpha$ exactly.

▶ Show solution

The limit satisfies $\alpha = \sqrt{\alpha + 3}$, so $\alpha^2 = \alpha + 3$, i.e. $\alpha^2 - \alpha - 3 = 0$.

$\alpha = \dfrac{1 \pm \sqrt{13}}{2}$. A square root is never negative, so $\alpha = \dfrac{1 + \sqrt{13}}{2} = 2.3028\ldots$

This agrees with the terms $2.2361, 2.2882, 2.2996, \ldots$ climbing towards $2.30$.

Question 3

(a) Show that $x^3 + x - 3 = 0$ can be written as $x = \sqrt[3]{3 - x}$. (b) Use $x_{n+1} = \sqrt[3]{3 - x_n}$ with $x_1 = 1$ to find $x_2$, $x_3$, $x_4$, $x_5$ to $4$ d.p. (c) Show that the root is $1.213$ to $3$ d.p.

▶ Show solution

(a) $x^3 = 3 - x$, so $x = \sqrt[3]{3 - x}$.

(b) $x_2 = \sqrt[3]{2} = 1.2599$, $x_3 = 1.2028$, $x_4 = 1.2158$, $x_5 = 1.2129$.

(c) Let $\mathrm{f}(x) = x^3 + x - 3$. $\mathrm{f}(1.2125) = -0.00494\ldots < 0$ and $\mathrm{f}(1.2135) = 0.000479\ldots > 0$. Change of sign and $\mathrm{f}$ continuous, so the root is $1.213$ to $3$ d.p.

Question 4

Use $x_{n+1} = \mathrm{e}^{-x_n}$ with $x_1 = 1$ to find $x_2$ to $x_5$ to $4$ d.p. What type of diagram would illustrate this iteration?

▶ Show solution

$x_2 = 0.3679$, $x_3 = 0.6922$, $x_4 = 0.5005$, $x_5 = 0.6062$.

The terms alternate above and below the limit ($0.567\ldots$), so this is a cobweb diagram. This fits $\mathrm{g}'(x) = -\mathrm{e}^{-x}$, which is between $-1$ and $0$ near the root.

Question 5

The iteration $x_{n+1} = \cos x_n$ converges to $\alpha \approx 0.739$. Calculate $\mathrm{g}'(\alpha)$ and use it to explain why the convergence is oscillating and fairly slow.

▶ Show solution

$\mathrm{g}(x) = \cos x$, so $\mathrm{g}'(x) = -\sin x$ and $\mathrm{g}'(0.739) = -0.674$ (3 s.f.).

It is negative, so successive terms are on opposite sides of $\alpha$ (cobweb). Its size, $0.674$, is quite close to $1$, so each step only cuts the error to about two-thirds — slow convergence. (From $x_1 = 1$, $x_{11} = 0.744$ is still not correct to $2$ d.p.)

Question 6

Show that the iteration $x_{n+1} = \dfrac{x_n^3 - 1}{3}$ cannot be used to find the root $\alpha \approx 1.879$ of $x^3 - 3x - 1 = 0$, even starting at $x_1 = 1.9$.

▶ Show solution

$\mathrm{g}(x) = \dfrac{x^3 - 1}{3}$, $\mathrm{g}'(x) = x^2$, so $\mathrm{g}'(\alpha) \approx 1.879^2 = 3.53 > 1$. The iteration diverges from $\alpha$.

Indeed from $x_1 = 1.9$: $x_2 = 1.953$, $x_3 = 2.1497$, $x_4 = 2.978$, $x_5 = 8.47$ — moving away.

Question 7

For the same equation $x^3 - 3x - 1 = 0$, show that $x = \sqrt[3]{3x + 1}$ is a valid rearrangement, show that it converges to $\alpha \approx 1.879$, and find $x_2$, $x_3$, $x_4$ from $x_1 = 2$.

▶ Show solution

$x^3 = 3x + 1$, so $x = \sqrt[3]{3x + 1}$.

$\mathrm{g}'(x) = \tfrac13(3x + 1)^{-2/3} \times 3 = (3x + 1)^{-2/3}$. At $1.879$: $\mathrm{g}'(\alpha) \approx 0.283$, between $0$ and $1$, so it converges (staircase).

$x_2 = \sqrt[3]{7} = 1.9129$, $x_3 = 1.8888$, $x_4 = 1.8821$ — decreasing towards $1.879$.

Question 8

The equation $x^2 - 5x + 3 = 0$ has a root $\beta \approx 4.30$. Use $x_{n+1} = \sqrt{5x_n - 3}$ with $x_1 = 4$ to find $x_2$, $x_3$, $x_4$, and sketch the type of diagram you would get.

▶ Show solution

$x_2 = \sqrt{17} = 4.1231$, $x_3 = 4.1971$, $x_4 = 4.2409$.

The terms increase steadily towards $4.30$ from below: a staircase going up towards the intersection of $y = \sqrt{5x - 3}$ and $y = x$.

(Consistent with $\mathrm{g}'(\beta) = \dfrac{5}{2\sqrt{5\beta - 3}} \approx 0.581$, which is positive and less than $1$.)

Question 9

A student uses $x_{n+1} = x_n^3 - 4$ starting from $x_1 = 1.79$, very close to the root $1.796$ of $x^3 - x - 4 = 0$. Find $x_2$, $x_3$ and $x_4$, and explain what happens.

▶ Show solution

$x_2 = 1.79^3 - 4 = 1.7353$, $x_3 = 1.2258$, $x_4 = -2.158$.

Starting just below the root, the terms run away downwards. $\mathrm{g}'(\alpha) = 3\alpha^2 \approx 9.68 > 1$, so every step multiplies the distance from $\alpha$ by about ten: the iteration diverges whichever side you start.

Question 10

A chord cuts a circle of radius $r$ so that the minor segment has area one quarter of the circle. The chord subtends angle $\theta$ radians at the centre, and the segment area is $\tfrac12 r^2(\theta - \sin\theta)$.

(a) Show that $\theta = \dfrac{\pi}{2} + \sin\theta$.
(b) Use $\theta_{n+1} = \dfrac{\pi}{2} + \sin\theta_n$ with $\theta_1 = 2$ to find $\theta_2$, $\theta_3$, $\theta_4$ to $4$ d.p.
(c) Show that the root is $2.310$ to $3$ d.p.
(d) State, with a reason, whether the iteration gives a staircase or a cobweb diagram.

▶ Show solution

(a) $\tfrac12 r^2(\theta - \sin\theta) = \tfrac14 \pi r^2 \Rightarrow \theta - \sin\theta = \dfrac{\pi}{2} \Rightarrow \theta = \dfrac{\pi}{2} + \sin\theta$.

(b) $\theta_2 = \dfrac{\pi}{2} + \sin 2 = 2.4801$, $\theta_3 = 2.1851$, $\theta_4 = 2.3880$.

(c) Let $\mathrm{h}(\theta) = \theta - \sin\theta - \dfrac{\pi}{2}$. $\mathrm{h}(2.3095) = -0.000638\ldots < 0$ and $\mathrm{h}(2.3105) = 0.00104\ldots > 0$. Change of sign and $\mathrm{h}$ continuous, so $\theta = 2.310$ to $3$ d.p.

(d) $\mathrm{g}'(\theta) = \cos\theta$ and $\cos 2.310 \approx -0.674$, which lies between $-1$ and $0$. So the iteration converges with terms alternating either side of the root: a cobweb diagram, as the values in (b) show.

Iteration · A Level Maths Year 2 · Created with MathJax