Numerical solution of equations

Why numerical methods Paper 3

Many equations that arise naturally cannot be solved by algebra. There is no rearrangement that gives $x$ exactly from $x=2\sin x$, from ${\mathrm{e}}^x=4-x^2$, or from $x{\mathrm{e}}^x=4$. A numerical method finds a root to whatever accuracy is needed, in two stages:

1. locate the root roughly, from a sketch or by a change of sign;
2. improve the estimate with an iterative formula until it is accurate enough.

Exam questions on this topic are usually structured in exactly that order, and often begin with a problem from elsewhere in the course (a stationary point, an area, a sector) that leads to the equation. All the work is done with a calculator, in radians for any trigonometry.

Locating a root from a graph Paper 3

Rearrange the equation as $\mathrm{g}(x)=\mathrm{h}(x)$, where both sides have graphs you can sketch. Each point where the two graphs cross gives a root, so the sketch shows how many roots there are and roughly where they are.

For ${\mathrm{e}}^x=4-x^2$, sketch $y={\mathrm{e}}^x$ and $y=4-x^2$. The exponential curve is always positive and increasing; the parabola has its vertex at $(0,4)$ and crosses the $x$-axis at $\pm 2$. They cross twice, once for negative $x$ and once for positive $x$, so the equation has exactly two roots.

A sketch for this purpose needs the right shapes, the key intercepts, and the intersections clearly visible. It does not need to be drawn to scale, but your reasoning about how many times the graphs cross must be convincing.

Two intersections: the equation ${\mathrm{e}}^x=4-x^2$ has two roots.

Locating a root by a change of sign Paper 3

Write the equation as $\mathrm{f}(x)=0$. If $\mathrm{f}$ is continuous between $a$ and $b$, and $\mathrm{f}(a)$ and $\mathrm{f}(b)$ have opposite signs, then the graph of $y=\mathrm{f}(x)$ must cross the $x$-axis somewhere between them, so there is a root between $a$ and $b$.

Show the working the examiner wants: the two values, a statement of the change of sign, and the conclusion. For example: $\mathrm{f}(1)=-0.282<0$ and $\mathrm{f}(1.5)=2.73>0$; there is a change of sign and $\mathrm{f}$ is continuous, so the root lies between 1 and 1.5. Give each value to 2 or 3 significant figures, enough to make the sign clear.

To find a pair of consecutive integers between which a root lies, evaluate $\mathrm{f}$ at $0,1,2,\dots$ (or $-1,-2,\dots$) until the sign changes.

The test can mislead in two ways:

• A sign change with no root. $\mathrm{f}(x)=\frac{1}{x-2}$ changes sign between 1 and 3, but has no root: it is not continuous at $x=2$.
• A root with no sign change. If the curve only touches the axis, as $(x-3{)}^2$ does at 3, or crosses twice between $a$ and $b$, then $\mathrm{f}(a)$ and $\mathrm{f}(b)$ have the same sign.

Iterative formulae Paper 3

An iterative formula $x_{n+1}=\mathrm{F}(x_n)$ builds a sequence of approximations $x_1,x_2,x_3,\dots$ from a starting value $x_1$: put $x_1$ into $\mathrm{F}$ to get $x_2$, put $x_2$ in to get $x_3$, and so on. If the terms get closer and closer to a number $\alpha$, the sequence converges to $\alpha$.

Why the limit is a root. When the sequence has settled, $x_n$ and $x_{n+1}$ are both essentially $\alpha$, so the formula becomes $\alpha =\mathrm{F}(\alpha )$. The limit is a root of the equation $x=\mathrm{F}(x)$. So:

• given an iterative formula, the equation it solves is found by replacing $x_{n+1}$ and $x_n$ by $x$;
• given an equation, rearrange it into the form $x=\mathrm{F}(x)$ to make a formula.

For example, $x^3+5x-20=0$ can be rearranged as $x=\sqrt[3]{20-5x}$, or as $x=\frac{20-x^3}{5}$. Each gives an iterative formula, and they behave very differently, as the section on failure shows.

On a calculator, type the starting value and press equals, then type the formula using the answer key in place of $x_n$. Each press of equals gives the next term.

Finding a root to a given accuracy Paper 3

To find a root correct to a stated number of decimal places:

1. start from the given $x_1$, or a value from your sign-change work;
2. write down each iterate to at least two more decimal places than the answer needs (questions often ask you to show the result of each iteration to 4 decimal places);
3. stop when successive iterates agree when rounded to the required accuracy, and state the root to that accuracy.

Do not round between steps: carry the full calculator value forward and only round what you write down. If the iterates are still changing in the deciding digit, keep going. To be certain of a 2 decimal place answer such as 1.90, you can also check that $\mathrm{f}(1.895)$ and $\mathrm{f}(1.905)$ have opposite signs, which shows the root lies in the interval that rounds to 1.90.

Give the answer to exactly the accuracy asked: 2.310, not 2.31, when 3 decimal places are required.

When an iteration fails Paper 3

An iteration does not always converge, and you are expected to recognise this. You are not expected to know a test for convergence.

Picture it on a graph of $y=\mathrm{F}(x)$ and $y=x$. From $x_1$, go vertically to the curve: the height is $x_2$. Go horizontally to the line $y=x$, which moves you to $x=x_2$, then vertically to the curve again for $x_3$. The root is where the curve meets the line. If the curve is fairly flat where it crosses the line, the path closes in on the root in a staircase or a cobweb. If the curve is steep there, the path moves away.

For example, $x^2-3x+1=0$ has roots near 0.382 and 2.618. The formula $x_{n+1}=3-\frac{1}{x_n}$ with $x_1=1$ gives $2,2.5,2.6,2.615,\dots$, converging to 2.618. The rearrangement $x_{n+1}=\frac{x_n^2+1}{3}$ started at $x_1=2.5$, very close to 2.618, gives $2.4167,2.2801,2.0663,\dots$: it moves away from 2.618 and drifts to the other root, 0.382.

Signs that an iteration is failing: the terms move steadily away from the root, oscillate with growing size, repeat in a cycle without settling, or settle on a different root. The cure is a different rearrangement.

The staircase from $x_1=1$ closes in on the root near 2.618.