Numerical solution of equations

Why numerical methods? Paper 2

Many equations cannot be solved exactly. $x^3+5x-3=0$ has no rational root, and an equation such as ${\mathrm{e}}^x=x+4$ or $x=2\cos x$ mixes different kinds of function, so no algebra isolates $x$. Such equations still have roots, and a numerical method pins a root down to any accuracy you want.

Paper 2 uses two stages: first locate a root roughly, from a sketch or a change of sign; then refine it with an iterative formula until it is correct to the accuracy asked for.

Locating a root from a graph Paper 2

Rearrange the equation into the form $\mathrm{g}(x)=\mathrm{h}(x)$, where both sides are graphs you can sketch. The roots of the equation are the $x$-coordinates of the points where the two graphs meet, so the number of intersections is the number of roots.

For example, ${\mathrm{e}}^x+x-4=0$ can be written ${\mathrm{e}}^x=4-x$. The curve $y={\mathrm{e}}^x$ rises from just above the $x$-axis; the line $y=4-x$ falls. They cross exactly once, so the equation has exactly one root, and the sketch shows it lies between 1 and 2.

A sketch earns its marks for correct shapes in the right places (intercepts, asymptotes, which graph is above the other) and for a sentence linking the intersections to the roots.

One intersection, so ${\mathrm{e}}^x=4-x$ has exactly one root.

Searching for a sign change Paper 2

If $\mathrm{f}$ is continuous from $x=a$ to $x=b$, and $\mathrm{f}(a)$ and $\mathrm{f}(b)$ have opposite signs, the graph of $y=\mathrm{f}(x)$ must cross the $x$-axis somewhere between, so $\mathrm{f}(x)=0$ has a root between $a$ and $b$.

To show that a root lies in an interval:

1. Write the equation as $\mathrm{f}(x)=0$.
2. Work out $\mathrm{f}(a)$ and $\mathrm{f}(b)$, and write the values down (2 or 3 significant figures is enough).
3. State that the sign changes and $\mathrm{f}$ is continuous, so there is a root between $a$ and $b$.

To find a pair of consecutive integers between which a root lies, work out $\mathrm{f}(0)$, $\mathrm{f}(1)$, $\mathrm{f}(2)$, and so on, until the sign changes.

Two warnings. A sign change without continuity proves nothing: $\tan x$ changes sign between $x=1$ and $x=2$ but $\tan x=0$ has no root there, because the graph jumps at the asymptote $x=\frac{1}{2}\pi$. And no sign change does not mean no root: if the curve dips below the axis and comes back up, there are two roots and the end values have the same sign.

Iteration Paper 2

An iterative formula $x_{n+1}=\mathrm{F}(x_n)$ turns one approximation into the next. Start from a value $x_1$ near the root, often taken from the sign-change interval, and work out $x_2=\mathrm{F}(x_1)$, then $x_3=\mathrm{F}(x_2)$, and so on. If the sequence of approximations $x_1,x_2,x_3,\dots$ converges, it settles down to a limit $\alpha$.

How the formula relates to the equation. If $x_n\to \alpha$, then $x_{n+1}\to \alpha$ too, so in the limit both sides of the formula become $\alpha$: $\alpha =\mathrm{F}(\alpha )$. The limit is a root of the equation $x=\mathrm{F}(x)$. An iterative formula is just the equation rearranged with $x$ alone on one side. For example $x^3+5x-3=0$ rearranges to $x=\frac{3-x^3}{5}$, which gives $x_{n+1}=\frac{3-x_n^3}{5}$. It also rearranges to $x=\sqrt[3]{3-5x}$, a different iteration for the same equation.

Questions run both ways:

• given the equation, show that it can be rearranged into the form $x=\mathrm{F}(x)$;
• given the iteration, replace $x_{n+1}$ and $x_n$ by $x$ to find the equation the limit satisfies, and sometimes solve it exactly.

To a stated accuracy. Keep each iterate in your calculator (use the answer key) and write each one down to more figures than you need, usually 4 decimal places when the answer is wanted to 2. Stop when two successive iterates agree to the accuracy required, and give that value.

Working back from an iteration Paper 2

Because the limit satisfies $\alpha =\mathrm{F}(\alpha )$, you can sometimes find it exactly. Suppose $x_{n+1}=\frac{1}{3}(2x_n+\frac{9}{x_n^2})$ converges to $\alpha$. Then
$$\alpha =\frac{1}{3}(2\alpha +\frac{9}{{\alpha }^2})$$
so $3\alpha =2\alpha +\frac{9}{{\alpha }^2}$, $\alpha =\frac{9}{{\alpha }^2}$ and ${\alpha }^3=9$. The iteration is homing in on $\sqrt[3]{9}$.

This is also how a 'show that' part works: write the limit into the formula, and rearrange until you reach the equation given in the question.

When an iteration fails Paper 2

Not every rearrangement works. The same equation can give one iteration that converges to a root and another that moves away from it, however close the starting value. The condition that decides which is not in this syllabus, but you are expected to recognise failure when you see it.

For ${\mathrm{e}}^x=x+4$, the iteration $x_{n+1}=\ln (x_n+4)$ with $x_1=2$ gives $x_2=1.7918$, $x_3=1.7564$, $x_4=1.7503$: it converges to the root $1.749$. The rearrangement $x_{n+1}={\mathrm{e}}^{x_n}-4$, with the same start, gives $x_2=3.3891$, $x_3=25.64$: the values run away, and the iteration diverges.

On a graph, an iteration traces a path between the curve $y=\mathrm{F}(x)$ and the line $y=x$: up to the curve, across to the line, up to the curve again. Where the curve is shallow at the crossing point, the path closes in on it, as below. Where it is steep, the path steps or spirals away.

If an iteration diverges, or converges to a different root from the one you want, use a different rearrangement or a different starting value.

Starting from $x_1=0$, each step up to the curve and across to the line gives the next iterate, closing in on the root.