Iterative methodsEdexcel International A Level Maths: Revision notes

A recurrence relation of the form $x_{n+1}=f(x_n)$ defines a sequence from a starting value $x_0$: each term is found by putting the previous term into $f$. For example $x_{n+1}=\sqrt[3]{4x_n+3}$ with $x_0=2$ gives $x_1=\sqrt[3]{11}=2.224$, then $x_2=2.2828$, $x_3=2.2977$, and so on. If the terms settle towards a value, the sequence converges to a limit $L$. Iteration is used to find approximate solutions of equations that cannot be solved algebraically.

To solve $f(x)=0$ by iteration, rearrange it into the form $x=g(x)$ and use $x_{n+1}=g(x_n)$. There are many possible rearrangements. For $x^3-4x-3=0$ you can write $x^3=4x+3$ and so $x=\sqrt[3]{4x+3}$, or $x=\frac{x^3-3}{4}$. In an exam the rearrangement is usually given (a lead), and you are asked to show it: write each algebraic step, isolate the required term and finish on exactly the printed form. Take care with signs and with dividing every term.

Work with full calculator values and round only when the question asks, usually to a stated number of decimal places. If the sequence converges to $\alpha$, then for large $n$ both $x_n$ and $x_{n+1}$ are approximately $\alpha$, so $\alpha=g(\alpha)$: the limit satisfies the equation $x=g(x)$, and so the original equation. For $x_{n+1}=\sqrt[3]{4x_n+3}$ the limit satisfies $\alpha=\sqrt[3]{4\alpha+3}$, which cubes to $\alpha^3-4\alpha-3=0$. To quote $\alpha$ to $k$ decimal places, continue until consecutive terms agree to $k$ decimal places and then confirm with a sign change (next section).

Let $f$ be continuous. If $f(a)$ and $f(b)$ have opposite signs, then $f(x)=0$ has a root between $a$ and $b$. To show $2<\alpha<2.5$ for $f(x)=\ln x+x-3$: $f(2)=-0.307<0$ and $f(2.5)=0.416>0$; $f$ is continuous, so a root lies in $(2,2.5)$. A full answer gives both values (or their signs), states that $f$ is continuous, and states the conclusion. To confirm a value to $k$ decimal places, test $f$ at the two values half a unit in the last place either side. For $\alpha=3.196$ (3 d.p.) test $f(3.1955)$ and $f(3.1965)$: opposite signs show $3.1955<\alpha<3.1965$.

The equation $x^3-3x^2-2=0$ has a root $\alpha$ between 3 and 3.5, since $f(3)=-2$ and $f(3.5)=4.125$. Show that $x=3+\frac{2}{x^2}$: $x^3-3x^2=2$, so $x^2(x-3)=2$, so $x-3=\frac{2}{x^2}$. With $x_0=3.2$: $x_1=3.1953$, $x_2=3.1959$, $x_3=3.1958$. Check $\alpha=3.196$ (3 d.p.): $f(3.1955)=-0.0037<0$ and $f(3.1965)=0.0078>0$, so $3.1955<\alpha<3.1965$.

Not every rearrangement works. A sequence may diverge (terms grow without limit), oscillate between values, or converge to a different root from the one you want. Different rearrangements of the same equation behave differently, and a poor starting value can also cause failure. In examination questions a suitable rearrangement is supplied, but if the terms do not settle, say so and use the alternative form you are given. A converging sequence that oscillates, such as $x_{n+1}=3-\ln x_n$ (2.307, 2.164, 2.228, ...), alternates about the root while closing in on it.