Numerical Methods

A2 · P3 · 5 min

Most equations cannot be solved exactly. Numerical methods find a root to any required accuracy: first locate it between two values by a sign change, then home in with an iteration $x_{n + 1} = F(x_n)$ built from a rearrangement of the equation.

Locating a root

Key result

If $f$ is continuous and $f(a)$ and $f(b)$ have opposite signs, then $f(x) = 0$ has a root between $a$ and $b$ .

To show a root lies between $1$ and $2$ , evaluate $f(1)$ and $f(2)$ , state their signs, and say "change of sign, so a root lies in $(1, 2)$ ". Graphically, a root of $g(x) = h(x)$ is where the two graphs cross; sketching them shows how many roots there are and roughly where.

Sign change

Show that the equation $x^3 = 5 - x$ has a root between $1$ and $2$ .

Solution

Let $f(x) = x^3 + x - 5$ . $f(1) = -3 < 0$ and $f(2) = 5 > 0$ . There is a change of sign, and $f$ is continuous, so a root lies between $1$ and $2$ .

Counting roots from a sketch

By sketching $y = e^{-x}$ and $y = x - 1$ on the same axes, show that $e^{-x} = x - 1$ has exactly one real root, and find two consecutive integers between which it lies.

Solution

$e^{-x}$ decreases from $+\infty$ toward $0$ ; $x - 1$ increases without bound. They cross exactly once. With $f(x) = e^{-x} - x + 1$ : $f(1) = e^{-1} > 0$ , $f(2) = e^{-2} - 1 < 0$ . The root lies between $1$ and $2$ .

Iteration

Key result

Rearrange $f(x) = 0$ into the form $x = F(x)$ . Starting from $x_1$ near the root, compute

x_{n + 1} = F(x_n).

If the sequence settles to a fixed value $\alpha$ , then $\alpha = F(\alpha)$ , so $\alpha$ is a root of the original equation.

Method

Show that the given iterative formula is a rearrangement of the equation (or derive it from the given rearrangement).
Substitute $x_1$ and compute $x_2, x_3, \ldots$ using the calculator's ANS key, writing each to at least one more decimal place than required.
Stop when two successive values agree to the required accuracy, and state the root to that accuracy.

Using a given iteration

Use the iterative formula $x_{n + 1} = \sqrt[3]{5 - x_n}$ with $x_1 = 1.5$ to find the root of $x^3 = 5 - x$ correct to 3 decimal places.

Solution

$x_2 = \sqrt[3]{3.5} = 1.5183$ , $x_3 = \sqrt[3]{3.4817} = 1.5156$ , $x_4 = 1.5160$ , $x_5 = 1.5160$ .

The root is $1.516$ (3 d.p.).

Showing a formula is a rearrangement

Show that the equation $\ln x = 4 - x$ can be written in the form $x = 4 - \ln x$ , and use $x_{n + 1} = 4 - \ln x_n$ with $x_1 = 3$ to find the root correct to 2 decimal places.

Solution

$\ln x = 4 - x \iff x = 4 - \ln x$ directly. Iterating from $x_1 = 3$ : $x_2 = 4 - \ln 3 = 2.9014$ , $x_3 = 2.9348$ , $x_4 = 2.9234$ , $x_5 = 2.9273$ , $x_6 = 2.9259$ , $x_7 = 2.9264$ , $x_8 = 2.9262$ , $x_9 = 2.9263$ .

The values settle at $2.93$ (2 d.p.).

Iteration that fails

The equation $x^3 - 3x + 1 = 0$ has a root near $1.5$ . Show that the iteration $x_{n + 1} = x_n^3 - 2x_n + 1$ starting from $x_1 = 1.5$ does not converge to it.

Solution

$x_2 = 3.375 - 3 + 1 = 1.375$ , $x_3 = 2.600 - 2.750 + 1 = 0.850$ , $x_4 = 0.614 - 1.700 + 1 = -0.086$ , $x_5 = -0.001 + 0.172 + 1 = 1.171$ , $x_6 = 0.264$ . The values jump around and do not settle near $1.5$ .

A different rearrangement, $x_{n + 1} = \sqrt[3]{3x_n - 1}$ , gives $1.5 \to 1.5183 \to 1.5262 \to 1.5296 \to 1.5310 \to \ldots \to 1.5321$ , which converges.

Why some rearrangements work

An iteration $x = F(x)$ converges near a root when $|F'(x)| < 1$ there; the closer to $0$ , the faster. You are not required to know this condition, but you are expected to understand that a rearrangement can fail, and to use the one the question provides.

Watch out

Do not round intermediate values. Keep the full calculator value in ANS and only round when you report the answer. Rounding each step can make the sequence appear to converge to the wrong digits.

Exam tip

"Correct to 3 decimal places" is checked by seeing that consecutive iterates agree when rounded to 3 d.p.; write at least $x_n$ to 4 d.p. so the examiner can see the agreement. When asked to "verify" the root to a given accuracy, show a sign change on $f$ at the two ends of the rounding interval, e.g. $f(1.5155)$ and $f(1.5165)$ .

Practice

Question

Show that $x^3 - x - 4 = 0$ has a root between $1$ and $2$ .
Show that this equation can be written as $x = \sqrt[3]{x + 4}$ and use the iteration with $x_1 = 1.5$ to find the root to 3 d.p.
Show that $2\cos x = x$ has a root in $(1, 1.5)$ and find it to 2 d.p. using $x_{n + 1} = \cos^{-1}\left(\tfrac{x_n}{2}\right)$ with $x_1 = 1$ .
Verify that $1.796$ is a root of $x^3 - x - 4 = 0$ correct to 3 d.p. by considering $f(1.7955)$ and $f(1.7965)$ .

Answers

$f(1) = -4$ , $f(2) = 2$ : sign change.
$x_2 = \sqrt[3]{5.5} = 1.7652$ , $x_3 = 1.7931$ , $x_4 = 1.7960$ , $x_5 = 1.7963$ , $x_6 = 1.7963$ : root $1.796$ .
$f(x) = 2\cos x - x$ : $f(1) = 0.081 > 0$ , $f(1.5) = -1.36 < 0$ . Iteration: $1 \to 1.0472 \to 1.0197 \to 1.0358 \to 1.0264 \to 1.0319 \to 1.0287 \to 1.0306 \to 1.0295 \to 1.0301$ ; root $1.03$ .
$f(1.7955) = -0.0071 < 0$ , $f(1.7965) = 0.0015 > 0$ : sign change, so the root is $1.796$ to 3 d.p.

Locating a root

Iteration

Why some rearrangements work

Practice

Console