Iteration and Newton-RaphsonAQA A-Level Maths: Revision notes

An iteration (recurrence relation) $x_{n+1}=g(x_n)$ generates a sequence $x_0,x_1,x_2,\ldots$ from a starting value. To solve $f(x)=0$, rearrange it into the form $x=g(x)$. For $x^3+x-3=0$: $x^3=3-x$, so $x_{n+1}=\sqrt[3]{3-x_n}$. With $x_0=1$: $x_1=1.2599$, $x_2=1.2028$, $x_3=1.2158$, $x_4=1.2129$. If the sequence converges to $\alpha$, then $\alpha=g(\alpha)$, so $\alpha$ is a root of the original equation. Keep full calculator values (use the ANS key) and stop when successive terms agree to the required accuracy.

Draw $y=x$ and $y=g(x)$. From $x_0$ go vertically to the curve, horizontally to the line $y=x$, and repeat. If $0<g'(\alpha)<1$ the path is a staircase that converges from one side. If $-1<g'(\alpha)<0$ it is a cobweb spiralling inwards, with terms alternating either side of $\alpha$. If $|g'(\alpha)|>1$ the path moves away from $\alpha$ and the iteration diverges. For $g(x)=\sqrt[3]{3-x}$, $g'(x)=-\frac13(3-x)^{-2/3}$, which is about $-0.23$ at $\alpha=1.213$, so it converges in a cobweb.

The Newton-Raphson method uses tangents. The tangent at $x_n$ meets the $x$-axis at $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.$ For $f(x)=x^2-7$, $f'(x)=2x$, so $x_{n+1}=x_n-\frac{x_n^2-7}{2x_n}$. With $x_0=3$: $x_1=\frac83=2.6667$, $x_2=2.6458$, close to $\sqrt7=2.64575$. For $f(x)=x^3-2x-5$ with $x_0=2$: $x_1=2.1$, $x_2=2.094568$, $x_3=2.094551$, so $\alpha=2.0946$ (4 d.p.). The method usually converges very quickly when $x_0$ is close to the root.

Iteration: the sequence diverges if $|g'|>1$ near the root. The rearrangement $x_{n+1}=\frac{x_n^3+1}{3}$ for $x^3-3x+1=0$ has $g'(x)=x^2$, which is greater than 1 at the root $1.532$, so starting at $1.6$ gives $1.699$, $1.967$, moving away. Newton-Raphson: it fails if $f'(x_n)=0$ (a horizontal tangent never meets the axis and the formula divides by zero). It can also converge to a different root, or oscillate, if $x_0$ is near a stationary point or far from the root. For $f(x)=x^3-3x+1$, $f'(1)=0$, so $x_0=1$ fails.