Notes · MathematicsUK · A-Levels

Numerical methods

Numerical methods find approximate solutions where exact algebra is impossible: locating roots by change of sign, refining them by iteration and by the Newton-Raphson method, and estimating definite integrals with the trapezium rule. Each method comes with conditions for success and characteristic ways of failing, which are examined as carefully as the calculations themselves.

4 sections~10 min reading time3 competenciesLevel Standard 2 · Advanced 2

T·101010 / 20

Exam profile

AO1 · Apply iterative and numerical procedures accuratelyAO2 · Justify convergence, the direction of an error, and conditions for failureAO3 · Use numerical methods where analytic solutions are unavailable

Operators:show thatfindusededuceexplainestimate

basic level

AS-Level covers locating roots by change of sign and the trapezium rule.

higher level

The full A-Level adds fixed-point iteration $x_{n+1} = g(x_n)$ and the Newton-Raphson method, together with their conditions for failure.

Depth

Text

Contents · 4 sections

Numerical methods

Locating roots by change of sign#

StandardDfE GCE Mathematics I1AQA 7357 I

A sign change traps a root

Fig. 1

f(1) = -3 < 0

and

f(2) = 3 > 0

, so

x^3 - x - 3 = 0

has a root between 1 and 2.

If a continuous function

f

satisfies

f(a)

and

f(b)

having opposite signs, then

f

must take the value zero somewhere between

a

and

b

; that is, there is a root in the interval

(a, b)

. This change-of-sign test is the simplest way to establish that a root exists and to trap it in an interval, and it relies on continuity — the graph cannot jump from below the axis to above without crossing it.

The method is used both to demonstrate a root exists ('show that

f(x) = 0

has a root between 1 and 2') and to refine its location by interval bisection: evaluate

f

at the midpoint, keep whichever half still shows a sign change, and repeat. Each step halves the interval, steadily squeezing the root between ever-closer bounds.

Two cautions are essential. First, the function must be continuous on the interval; a sign change across a discontinuity (as with

\tfrac{1}{x}

across

x = 0

) does not indicate a root. Second, a repeated (even-order) root touches the axis without crossing, so there is no sign change even though a root is present — the test can miss such roots.

Conversely, no sign change in an interval does not prove there is no root: two roots close together give the same sign at the ends. The sign-change test is a sufficient condition for a root, not a necessary one, and stating this correctly is a common exam requirement.

f(a)\,f(b) < 0 \ \text{and } f \text{ continuous} \ \Rightarrow\ \exists\, \text{root in } (a, b)

Change-of-sign criterion

Opposite signs at the ends of an interval guarantee a root, provided $f$ is continuous there.

Worked example

Establishing a root by change of sign

Show that $x^3 - 5x + 1 = 0$ has a root in the interval $[0, 1]$ .

Evaluate at the ends
$f(0) = 0 - 0 + 1 = 1 > 0$ ; $f(1) = 1 - 5 + 1 = -3 < 0$ .
Apply the criterion
$f$ is a polynomial, hence continuous, and $f(0)$ and $f(1)$ have opposite signs.
Conclude
By the change-of-sign rule there is a root of $x^3 - 5x + 1 = 0$ in $(0, 1)$ .

Result: Since $f(0) > 0$ , $f(1) < 0$ and $f$ is continuous, a root lies in $(0, 1)$ .

Typical mistakes

Claiming a root from a sign change across a discontinuity such as an asymptote.
Asserting there is no root simply because there is no sign change (two roots may hide there).

Active revision

Show that $f(x) = e^{x} - 3x$ has a root between $1.5$ and $2$ , and use bisection once to give a smaller interval containing it.

Active recall

Recall the key points — then reveal.

Sources: Mathematics: AS and A level content (GCE subject content) (Department for Education) · AQA A-level Mathematics 7357 specification (AQA)

Fixed-point iteration#

AdvancedDfE GCE Mathematics I2AQA 7357 I

The fixed point of an iteration

Fig. 2The iteration

x_{n+1} = \sqrt[3]{x_n + 3}

converges to the point where

y = \sqrt[3]{x + 3}

meets

y = x

To solve

f(x) = 0

by iteration, you first rearrange it into the form

x = g(x)

, then generate a sequence by the recurrence

x_{n+1} = g(x_n)

from a starting value

x_0

. If the sequence converges, its limit

L

satisfies

L = g(L)

, which is exactly the equation you rearranged, so

L

is a root. A single equation can be rearranged into several different iterations, and they do not all behave the same way.

Convergence depends on the rearrangement. The iteration converges to a root near

\alpha

when

|g'(\alpha)| < 1

and diverges when

|g'(\alpha)| > 1

; the smaller

|g'(\alpha)|

, the faster the convergence. This is why one rearrangement of an equation may home in on the root while another, algebraically equivalent, rearrangement flies away from it.

The behaviour of a convergent iteration is pictured with a staircase or cobweb diagram drawn between the curve

y = g(x)

and the line

y = x

: successive iterates step towards the intersection point, which is the root. Reading off from such a diagram whether an iteration converges, and to which root, is an examinable skill.

In practice you show a chosen iteration works by demonstrating a sign change of

f

around the limit (to prove a genuine root is found) and by computing successive iterates until they agree to the required accuracy. Stating the root to the requested number of decimal places, and confirming it with a sign change, is the standard write-up.

x_{n+1} = g(x_n), \qquad \text{converges near } \alpha \text{ if } |g'(\alpha)| < 1

Fixed-point iteration

The limit satisfies $x = g(x)$ ; convergence requires the gradient of $g$ to be less than 1 in size at the root.

Worked example

Iterating to a root

Use $x_{n+1} = \sqrt[3]{x_n + 3}$ with $x_0 = 1$ to find the root of $x^3 - x - 3 = 0$ to 2 decimal places.

Iterate
$x_1 = \sqrt[3]{4} = 1.5874$ ; $x_2 = \sqrt[3]{4.5874} = 1.6621$ ; $x_3 = \sqrt[3]{4.6621} = 1.6710$ .
Continue
$x_4 = \sqrt[3]{4.6710} = 1.6720$ ; the iterates have settled to $1.67$ (2 d.p.).
Confirm the root
$f(1.665) = -0.03 < 0$ and $f(1.675) = 0.02 > 0$ , a sign change, so the root is $1.67$ to 2 d.p.

Result: The root is $x \approx 1.67$ .

Typical mistakes

Assuming every rearrangement converges; some diverge because $|g'| > 1$ at the root.
Rounding intermediate iterates too early, so later iterates are corrupted.

Active revision

The equation $x^3 - 5x + 1 = 0$ is rearranged as $x_{n+1} = \dfrac{x_n^3 + 1}{5}$ . Starting from $x_0 = 0$ , find $x_1$ , $x_2$ and $x_3$ , and state the root to 3 decimal places.

Active recall

Recall the key points — then reveal.

Sources: Mathematics: AS and A level content (GCE subject content) (Department for Education) · AQA A-level Mathematics 7357 specification (AQA)

The Newton-Raphson method#

AdvancedDfE GCE Mathematics I3AQA 7357 I

Newton-Raphson uses the tangent

Fig. 3For

f(x) = x^2 - 2

from

x_0 = 2

, the tangent meets the axis at

x_1 = 1.5

, closer to

\sqrt{2}

The Newton-Raphson method is a fast iteration that uses the tangent to a curve to refine an estimate of a root. From an estimate

x_n

, you follow the tangent to the curve down to where it meets the

x

-axis, and that crossing is the next estimate. Algebraically this gives

x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}

, which typically converges much faster than a simple rearrangement iteration.

The formula comes directly from the tangent line. The tangent at

(x_n, f(x_n))

has gradient

f'(x_n)

and reaches the axis when its height has fallen by

f(x_n)

, i.e. after a horizontal step of

\dfrac{f(x_n)}{f'(x_n)}

. Subtracting this step gives the next estimate. When the method works, the number of correct decimal places roughly doubles each step.

Newton-Raphson can fail in characteristic ways. If

f'(x_n) = 0

the tangent is horizontal and never meets the axis, so the method breaks down. A poor starting value can send an iterate far from the intended root or into a different one, and near a turning point the tangent can overshoot wildly. Being able to explain, with a sketch, why a given start fails is an examined point.

The reliable write-up quotes the iteration formula, states the derivative, computes successive estimates keeping enough figures, and confirms the root with a sign change. Because the method needs

f'

, you must be able to differentiate the function — Newton-Raphson ties the numerical topic back to calculus.

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

The Newton-Raphson iteration

Follow the tangent at $x_n$ down to the axis to get the next estimate; fails where $f'(x_n) = 0$ .

Worked example

A Newton-Raphson iteration

Use Newton-Raphson on $f(x) = x^2 - 2$ with $x_0 = 2$ to estimate $\sqrt{2}$ (two iterations).

Set up the formula
$f'(x) = 2x$ , so $x_{n+1} = x_n - \dfrac{x_n^2 - 2}{2x_n}$ .
First iteration
$x_1 = 2 - \dfrac{4 - 2}{4} = 2 - 0.5 = 1.5$ .
$x_1 = 2 - \frac{2}{4} = 1.5$
Second iteration
$x_2 = 1.5 - \dfrac{2.25 - 2}{3} = 1.5 - 0.08333 = 1.41667$ .

Result: $x_2 \approx 1.4167$ , already close to $\sqrt{2} = 1.41421\ldots$

Typical mistakes

Using $f(x_n)/f'(x_n)$ with the wrong sign, or adding instead of subtracting.
Not recognising that $f'(x_n) = 0$ causes the method to fail.

Active revision

Apply the Newton-Raphson method to $f(x) = x^3 - 2x - 5$ with $x_0 = 2$ to find the root to 4 decimal places.

Active recall

Recall the key points — then reveal.

Sources: Mathematics: AS and A level content (GCE subject content) (Department for Education) · AQA A-level Mathematics 7357 specification (AQA)

The trapezium rule#

StandardDfE GCE Mathematics I4AQA 7357 I

Trapezium strips under a curve

Fig. 4Four trapezia approximate the area under

y = \sqrt{x}

; each chord top slightly underestimates the concave curve.

The trapezium rule estimates a definite integral (an area) when the integrand cannot be integrated exactly. The interval

[a, b]

is divided into

n

equal strips of width

h = \dfrac{b - a}{n}

, the ordinates

y_0, y_1, \ldots, y_n

are evaluated at the strip boundaries, and each strip is approximated by a trapezium whose parallel sides are consecutive ordinates. Summing the trapezium areas gives the estimate.

Adding the areas

\tfrac{h}{2}(y_i + y_{i+1})

and collecting terms gives the rule

\displaystyle\int_a^b y\,dx \approx \dfrac{h}{2}\big(y_0 + y_n + 2(y_1 + y_2 + \cdots + y_{n-1})\big)

. The end ordinates appear once and every interior ordinate appears twice — a structure worth memorising as 'first plus last, plus twice the middle, all times

\tfrac{h}{2}

The accuracy improves as the number of strips increases (and

h

decreases), because straight-topped trapezia fit a curve better over narrower strips. The error also has a predictable direction: where the curve is concave (bending downwards) the trapezia lie below the curve and the rule underestimates; where it is convex (bending upwards) the trapezia lie above and the rule overestimates.

Being able to state whether a particular estimate is an over- or under-estimate, by considering the concavity of the curve over the interval, is a favourite follow-up question. It rewards understanding the geometry of the method rather than just the arithmetic of the formula.

\int_a^b y\,dx \approx \frac{h}{2}\Big(y_0 + y_n + 2\big(y_1 + \cdots + y_{n-1}\big)\Big), \quad h = \frac{b - a}{n}

The trapezium rule

End ordinates once, interior ordinates twice, all scaled by half the strip width.

Worked example

Applying the trapezium rule

Use the trapezium rule with 4 strips to estimate $\displaystyle\int_0^4 \sqrt{x}\,dx$ .

Find h and the ordinates
$h = \dfrac{4 - 0}{4} = 1$ ; ordinates at $x = 0,1,2,3,4$ are $0, 1, 1.4142, 1.7321, 2$ .
Apply the rule
$\dfrac{1}{2}\big(0 + 2 + 2(1 + 1.4142 + 1.7321)\big) = \dfrac{1}{2}(2 + 2 \times 4.1463)$ .
$\frac{1}{2}\big(2 + 2(4.1463)\big)$
Evaluate
$= \dfrac{1}{2}(2 + 8.2926) = 5.146$ (3 d.p.). The exact value is $\tfrac{2}{3}(4^{3/2}) = 5.333$ , so this underestimates, as expected for a concave curve.

Result: Estimate $\approx 5.15$ , an under-estimate of the true $5.33$ .

Typical mistakes

Using the wrong number of ordinates ( $n$ strips need $n + 1$ ordinates).
Doubling the end ordinates, or failing to double the interior ones.

Active revision

Use the trapezium rule with 4 strips to estimate $\displaystyle\int_0^2 \sqrt{1 + x^3}\,dx$ , and state whether it over- or under-estimates the true value.

Active recall

Recall the key points — then reveal.

Sources: Mathematics: AS and A level content (GCE subject content) (Department for Education) · AQA A-level Mathematics 7357 specification (AQA)

References & sources

Sources

Department for Education

Mathematics: AS and A level content (GCE subject content)

AQA

AQA A-level Mathematics 7357 specification

Numerical methods

4 sections~10 min reading time3 competenciesLevel Standard 2 · Advanced 2

Numerical methods

Key points

Establishing a root by change of sign

Key points

Iterating to a root

Key points

A Newton-Raphson iteration

Key points

Applying the trapezium rule

Sources

Numerical methods

Key points

Establishing a root by change of sign

Key points

Iterating to a root

Key points

A Newton-Raphson iteration

Key points

Applying the trapezium rule

Sources