Numerical methods: A-level Maths OCR revision notes

1.09

Locating roots by change of sign

Locating roots by a change of sign 1.09

Definitions

Root of $f (x) = 0$ : a value $α$ with $f (α) = 0$ ; graphically, a point where $y = f (x)$ meets the $x$ -axis.
Continuous on an interval: the graph of $f$ can be drawn across that interval without lifting the pen — no jumps, gaps or vertical asymptotes.

Key results

Intermediate Value Theorem: if $f$ is continuous on $[a, b]$ and $f (a)$ and $f (b)$ have opposite signs, then $f (x) = 0$ has at least one root between $a$ and $b$ .
In practice the test is simply the sign of the product: $f (a) f (b) < 0$ guarantees a sign change, and hence a root, in the interval $(a, b)$ .
Evaluating $f$ at successive values inside the interval narrows the interval containing the root to any required degree of accuracy.

Notes

Continuity is not an optional detail. $f (x) = \frac{1}{x}$ satisfies $f (- 1) = - 1$ and $f (1) = 1$ , an apparent sign change, yet has no root at all — the sign changes across a vertical asymptote rather than across the $x$ -axis.
Always state the two function values, the fact that they have opposite signs, and the fact that $f$ is continuous on the interval. A sign-change answer with any of the three missing is an incomplete argument.
State the theorem's conclusion as 'a root', not 'the root' — the theorem only guarantees existence, and says nothing by itself about how many roots lie in the interval.

Narrowing the interval: decimal search 1.09

Key results

Interval bisection is the same idea with the interval halved each time: test the midpoint, keep whichever half still shows a sign change.
To justify a root as $α = 2.1$ correct to 1 decimal place, show a sign change across the whole rounding interval $[2.05, 2.15]$ — any narrower interval lying inside it will do.

Method

Confirm a sign change over a starting interval $[a, b]$ by evaluating $f (a)$ and $f (b)$ .
Subdivide the interval into equal steps (usually tenths) and evaluate $f$ at each step, tabulating the signs.
Identify the consecutive pair of values between which the sign changes; the root lies in that narrower interval.
Repeat on the new interval until it is short enough to pin the root down to the required accuracy.

In practiceShow that $f (x) = x^{3} - 2 x - 5$ has a root between 2 and 3, and find it to 1 decimal place.

$f (2) = - 1 < 0, f (3) = 16 > 0$ a sign change, and $f$ is continuous
$f (2.1) = 0.061 > 0$ the first tenth where the sign changes
$f (2.05) = - 0.485 < 0$ test the boundary of the rounding interval
The root lies between 2.05 and 2.1, so it is 2.1 to 1 decimal place.

Notes

Rounding is a claim about an interval, not about a single evaluation: showing $f (2.1)$ is small does not prove the root rounds to $2.1$ .
Bisection always works given a sign change but is slow: each step gains only about one third of a decimal digit, so around ten steps are needed per three digits.
Tabulate values neatly (x, f(x), sign) as you go — losing track of which sign belongs to which x-value is the most common source of an incorrectly narrowed interval.

Limitations of the sign-change method 1.09

Key results

A sign change proves at least one root exists, but never proves the root is unique — an odd number of roots in the interval produces exactly the same single sign change.
An even number of roots in the interval produces no sign change at all, even though roots are present.
A repeated root touches the axis without crossing it, so it never produces a sign change: $f (x) = (x - 2)^{2}$ has a root at $x = 2$ , yet $f (1) = 1$ and $f (3) = 1$ are both positive.

Notes

A sketch of $y = f (x)$ , or knowledge of how many turning points $f$ has, is the standard safeguard against missing or double-counting roots.
Choose the search interval short enough that the graph is plausibly monotonic across it; a long interval hides pairs of roots.
The number of stationary points of $f$ bounds the number of roots it can have — a cubic has at most two turning points, so at most three roots, which narrows how many a sign-change search needs to find.

Worked examples

Worked example

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

Show worked solution

Let:

f (x) = x^{3} - 2 x - 5

Then:

f (2) = 8 - 4 - 5 = - 1

and:

f (3) = 27 - 6 - 5 = 16

Since $f (2) < 0$ and $f (3) > 0$ , there is a change of sign, and $f$ is a polynomial and therefore continuous on $[2, 3]$ .

By the Intermediate Value Theorem there is at least one root of $f (x) = 0$ in the interval $(2, 3)$ .

Worked example

Use a decimal search to find, to 1 decimal place, the root of $x^{3} - 2 x - 5 = 0$ that lies between $2$ and $3$ .

Show worked solution

With:

f (x) = x^{3} - 2 x - 5

$f (2) = - 1$ and:

f (2.1) = 9.261 - 4.2 - 5 = 0.061

so the sign changes and the root lies in $(2, 2.1)$ .

To decide the first decimal place, test the midpoint of the rounding interval:

f (2.05) = 8.615125 - 4.1 - 5 = - 0.484875 < 0

So the root lies in $(2.05, 2.1)$ , which is contained in $[2.05, 2.15)$ , and every value in that interval rounds to $2.1$ .

Hence the root is $x = 2.1$ to 1 decimal place.

Continuing,

f (2.09) = - 0.050671 < 0

and:

f (2.095) = 0.005007 > 0

so the root lies in:

(2.09, 2.095)

and is $x = 2.09$ to 2 decimal places.

1.09

Iteration and fixed-point methods

Fixed-point iteration 1.09

Definitions

Rearrangement: writing $f (x) = 0$ in the equivalent form $x = g (x)$ , so that a root of $f$ is a fixed point of $g$ .
Fixed point of $g$ : a value $α$ with $g (α) = α$ .

Key results

Iterating $x_{n + 1} = g (x_{n})$ from a starting value $x_{0}$ generates a sequence; if that sequence converges to a limit $L$ , then $L = g (L)$ , so $L$ is a root of the original equation $f (x) = 0$ .
The same equation has many valid rearrangements. From $x^{3} - 2 x - 5 = 0$ one can obtain $x = 3 2 x + 5$ , or $x = \frac{x ^{3} - 5}{2}$ , or $x = \frac{5}{x ^{2} - 2}$ , all with the same roots.

Method

Rearrange $f (x) = 0$ into the form $x = g (x)$ .
Choose a starting value $x_{0}$ near the root, guided by a sign-change search or a sketch.
Compute $x_{1} = g (x_{0})$ , $x_{2} = g (x_{1})$ , and so on, keeping full calculator accuracy between steps and rounding only at the end.
Stop when successive iterates agree to the accuracy required, then confirm the answer by a sign change over its rounding interval.

In practiceUse $x_{n + 1} = 3 2 x_{n} + 5$ with $x_{0} = 2$ to find the root of $x^{3} - 2 x - 5 = 0$ to 3 decimal places.

$x^{3} = 2 x + 5 ⟹ x = 3 2 x + 5$ a rearrangement $x = g (x)$
$x_{1} = 2.08008, x_{2} = 2.09235, x_{3} = 2.09422, x_{4} = 2.09450, x_{5} = 2.09454$ full accuracy between steps
$f (2.0945) = - 0.0006 < 0, f (2.0955) = 0.0106 > 0$ sign change over the rounding interval
So the root is $2.095$ to 3 decimal places.

Notes

Rounding intermediate iterates and feeding the rounded value back in is the most common source of a wrong final digit — use the calculator's answer key to iterate.
Convergence of the iteration is evidence, not proof: the formal check that the limit really is the root to the stated accuracy is still a sign change.
If the iterates start moving further from the intended root, or oscillate wildly instead of settling, stop and try a different rearrangement rather than continuing in the hope it corrects itself.

Convergence, divergence and cobweb diagrams 1.09

Key results

Whether $x_{n + 1} = g (x_{n})$ converges near a root $α$ depends on the gradient of $g$ there: the iteration converges when $|g'(\alpha)|<1$ and diverges when $|g'(\alpha)|>1$ .
Staircase diagram: when $0<g'(\alpha)<1$ , the iterates approach the root from one side in steps.
Cobweb diagram: when $-1<g'(\alpha)<0$ , the iterates alternate either side of the root while closing in on it.
The smaller $|g'(\alpha)|$ is, the faster the convergence.

Method

Sketch $y = g (x)$ and the line $y = x$ on the same axes; their intersection is the root.
From $x_{0}$ on the $x$ -axis, move vertically to the curve $y = g (x)$ — that height is $x_{1}$ .
Move horizontally to the line $y = x$ , which carries the value $x_{1}$ back onto the $x$ -axis.
Repeat; the picture staircases inward or cobwebs inward if the iteration converges, and spirals or steps away if it diverges.

In practiceWill $x_{n + 1} = 3 2 x_{n} + 5$ converge to the root $α \approx 2.095$ ? Compare $x_{n + 1} = \frac{1}{2} (x_{n}^{3} - 5)$ .

$\displaystyle g(x)=(2x+5)^{1/3}:\ \ g'(\alpha)=\tfrac23(2\alpha+5)^{-2/3}\approx0.15$ $0<g'(\alpha)<1$ : a staircase that converges
$\displaystyle g(x)=\tfrac12\left(x^3-5\right):\ \ g'(\alpha)=\tfrac32\alpha^2\approx6.6$ $|g'(\alpha)|>1$ : the steps move away from the root
With $-1<g'(\alpha)<0$ the diagram would be a cobweb spiralling inwards.

Notes

A diverging rearrangement is not a mistake in the algebra — it is simply unusable, and a different rearrangement must be tried.
One rearrangement can converge to one root of the equation while a different rearrangement, or a different $x_{0}$ , converges to another.
$g'(\alpha)$ can be estimated in practice from the equation without knowing $α$ exactly, by differentiating $g (x)$ and evaluating near the approximate root already found from a sign-change search.

Worked example

The equation $x^{3} - 2 x - 5 = 0$ can be rearranged as:

x = 3 2 x + 5

Starting with $x_{0} = 2$ , find $x_{1}$ , $x_{2}$ , $x_{3}$ and $x_{4}$ to 4 decimal places, and comment on the convergence.

Show worked solution

The rearrangement is valid because:

x = 3 2 x + 5 ⟺ x^{3} = 2 x + 5 ⟺ x^{3} - 2 x - 5 = 0

so any limit of the iteration is a root of the original equation.

Iterating:

x_{n + 1} = 3 2 x_{n} + 5

from $x_{0} = 2$ :

x_{1} = 39 = 2.0801

x_{2} = 3 2 (2.0800838) + 5 = 3 9.1601676 = 2.0924

$x_{3} = 2.0942$ ; $x_{4} = 2.0945$ (all to 4 d.p., with full accuracy carried between steps).

The iterates increase steadily towards the root and each new estimate changes by roughly a fifth of the previous change, which is the staircase behaviour expected when:

0<g&#039;(\alpha)<1

Convergence is reliable but noticeably slower than Newton-Raphson on the same equation.

1.09

The Newton–Raphson method

The Newton-Raphson method 1.09

Key results

Newton-Raphson iteration: $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$ .
Geometrically, the tangent to $y = f (x)$ at the point $(x_{n}, f (x_{n}))$ is followed down to the $x$ -axis, and the crossing point is taken as the next estimate.
The formula is derived directly from that tangent: the tangent has equation $y-f(x_n)=f'(x_n)(x-x_n)$ , and setting $y = 0$ gives $x=x_n-\dfrac{f(x_n)}{f'(x_n)}$ .
Near a simple root with a well-behaved curve, convergence is very fast — roughly doubling the number of correct digits at each step, far quicker than a typical fixed-point rearrangement.

Method

Differentiate to obtain $f'(x)$ .
Choose a sensible $x_{0}$ close to the root, informed by a sign-change search or a sketch.
Apply $x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}$ , keeping full accuracy between iterations.
Stop when successive iterates agree to the required accuracy, and verify with a sign change over the rounding interval.

In practiceApply Newton-Raphson to $f (x) = x^{3} - 2 x - 5$ from $x_{0} = 2$ .

$\displaystyle f'(x)=3x^2-2$
$\displaystyle x_1=2-\dfrac{f(2)}{f'(2)}=2-\dfrac{-1}{10}=2.1$
$x_{2} = 2.1 - \frac{0.061}{11.23} = 2.094568, x_{3} = 2.094551$ converging fast
$x_{3}$ and $x_{4}$ agree to 6 decimal places: $α = 2.09455$ .

Notes

Newton-Raphson is itself a fixed-point iteration, with $g(x)=x-\dfrac{f(x)}{f'(x)}$ — it is just an unusually well-chosen one.
Newton-Raphson needs BOTH $f (x)$ and $f'(x)$ evaluated at each step, unlike simple fixed-point iteration — forgetting to differentiate first, and instead reusing $f (x)$ in place of $f'(x)$ , is a common setup error.

When Newton-Raphson fails 1.09

Key results

If $f'(x_n)=0$ the iteration is undefined: the tangent is horizontal and never meets the $x$ -axis.
If $f'(x_n)$ is merely close to zero — that is, $x_{n}$ is near a stationary point — the correction term $\dfrac{f(x_n)}{f'(x_n)}$ is enormous, and the next estimate is thrown far away, possibly converging to a completely different root or diverging.
The method can also fail if the interval between $x_{n}$ and the root contains a discontinuity or vertical asymptote of $f$ .

Notes

This is why a sensible initial estimate matters: locate the root by a sign change first, then start Newton-Raphson inside that interval.
If asked to explain a failure, name the specific cause at the given $x_{0}$ (for example 'the initial estimate is a stationary point, so $f'(x_0)=0$ and the tangent never meets the $x$ -axis'), rather than saying only that the method 'does not work'.
A quick sketch showing the tangent at the given $x_{0}$ is often the fastest way to see and explain why it shoots off towards the wrong root or fails to converge at all.

Worked examples

Worked example

Use the Newton-Raphson method with $x_{0} = 2$ to find $x_{1}$ , $x_{2}$ and $x_{3}$ for:

f (x) = x^{3} - 2 x - 5

Show worked solution

f&#039;(x)=3x^2-2

At $x_{0} = 2$ :

f (2) = 8 - 4 - 5 = - 1

and:

f&#039;(2)=3(4)-2=10

so:

x_{1} = 2 - \frac{- 1}{10} = 2.1

At $x_{1} = 2.1$ :

f (2.1) = 9.261 - 4.2 - 5 = 0.061

and:

f&#039;(2.1)=3(4.41)-2=11.23

so:

x_{2} = 2.1 - \frac{0.061}{11.23} = 2.0945681 = 2.0946

(4 d.p.).

At:

x_{2} = 2.0945681

f (x_{2}) = 0.00018572

and:

f&#039;(x_2)=11.161647

so:

x_{3} = 2.0945681 - \frac{0.00018572}{11.161647} = 2.0945515

The estimates have already stabilised to 6 decimal places after three steps, illustrating how quickly Newton-Raphson converges near a simple root; the root is $2.094551$ to 6 d.p.

Worked example

Explain why the Newton-Raphson method cannot be applied to:

f (x) = x^{3} - 3 x + 1

with $x_{0} = 1$ , and use a better starting value to find the largest root to 4 decimal places.

Show worked solution

f&#039;(x)=3x^2-3

so:

f&#039;(1)=3-3=0

The Newton-Raphson formula requires division by $f'(x_0)$ , which is undefined here: geometrically, $x = 1$ is a stationary point, the tangent there is horizontal, and it never meets the $x$ -axis.

Choose instead $x_{0} = 1.5$ , which is a sensible estimate since:

f (1.5) = 3.375 - 4.5 + 1 = - 0.125 < 0

and:

f (2) = 8 - 6 + 1 = 3 > 0

give a sign change in $(1.5, 2)$ .

Then:

f&#039;(1.5)=3(2.25)-3=3.75

so:

x_{1} = 1.5 - \frac{- 0.125}{3.75} = 1.5333333

Next,

f (1.5333333) = 0.0050370

and:

f&#039;(1.5333333)=4.0533333

so:

x_{2} = 1.5333333 - \frac{0.0050370}{4.0533333} = 1.5320906

A further step gives:

x_{3} = 1.5320889

so the root is $1.5321$ to 4 d.p.

As a check,

f (1.53205) = - 0.000157 < 0

and:

f (1.53215) = 0.000247 > 0

confirming a sign change across the rounding interval.

1.09

Numerical integration: the trapezium rule

Numerical integration: the trapezium rule 1.09

Definitions

Strip: one of the $n$ equal-width slices the interval $[a, b]$ is divided into, each of width $h = \frac{b - a}{n}$ .
Ordinate: one of the $n + 1$ function values $y_{0}, y_{1}, \dots, y_{n}$ at the strip boundaries $x = a, a + h, \dots, b$ .

Key results

Trapezium rule: $\int_{a}^{b} y d x \approx \frac{h}{2} [y_{0} + y_{n} + 2 (y_{1} + y_{2} + \dots + y_{n - 1})]$ , with $h = \frac{b - a}{n}$ .
The rule treats each strip as a trapezium rather than a rectangle, replacing the curve across each strip by the straight chord joining its two ordinates.
The two outer ordinates $y_{0}$ and $y_{n}$ are counted once each; every interior ordinate is counted twice, because it is a side shared by two adjacent trapezia.

Method

Compute $h = \frac{b - a}{n}$ and list the $n + 1$ values of $x$ .
Tabulate the corresponding ordinates $y_{0}, y_{1}, \dots, y_{n}$ , keeping more decimal places than the final answer needs.
Add the two end ordinates, add twice the sum of all the interior ordinates.
Multiply the total by $\frac{h}{2}$ and round the final answer only at this stage.

In practiceEstimate $\int_{0}^{2} 1 + x^{2} d x$ using 4 strips.

$h = \frac{2 - 0}{4} = 0.5 : x = 0, 0.5, 1, 1.5, 2$
$y = 1, 1.11803, 1.41421, 1.80278, 2.23607$ 5 ordinates, 5 decimal places
$\approx \frac{0.5}{2} [(1 + 2.23607) + 2 (1.11803 + 1.41421 + 1.80278)]$ ends once, interior twice
$= 0.25 \times 11.90612 = 2.977$ an overestimate: the curve is convex (true value 2.958)

Notes

Confusing strips with ordinates is the classic error: $n$ strips means $n + 1$ ordinates, so '5 ordinates' means 4 strips.
For a trigonometric integrand, the calculator must be in radians, since $\int y d x$ in calculus always uses radian measure.
More strips always give a better approximation, but the trapezium rule can never give the exact area under a genuinely curved (non-straight) function, however many strips are used — it is an approximation method by design.

Accuracy of the trapezium rule 1.09

Key results

The rule overestimates the area under a convex (concave-up, $f''>0$ ) curve, because each straight chord lies above the curve.
The rule underestimates the area under a concave (concave-down, $f''<0$ ) curve, because each straight chord lies below the curve.
The error is approximately proportional to $h^{2}$ , so doubling the number of strips reduces the error by a factor of about 4.

Notes

This reasoning gives the direction of the error without ever computing the integral exactly — a sketch, or the sign of $f''$ , is enough.
If the curve changes concavity inside $[a, b]$ , no direction can be claimed: the over- and under-estimates in different parts of the interval partly cancel.
Increasing $n$ improves accuracy but never makes the answer exact for a genuinely curved graph; the trapezium rule is exact only for a straight line.
Whether an approximation is an over- or under-estimate can be stated with certainty from the concavity alone — no numerical comparison against the true value is needed to answer that part of a question.

Worked examples

Worked example

Use the trapezium rule with 4 strips to estimate:

\int_{0}^{2} x^{2} d x

and compare with the exact value.

Show worked solution

With $n = 4$ strips over $[0, 2]$ , $h = 0.5$ , so:

x = 0, 0.5, 1, 1.5, 2

giving:

y = 0, 0.25, 1, 2.25, 4

The trapezium rule gives:

\frac{0.5}{2} [0 + 4 + 2 (0.25 + 1 + 2.25)] = 0.25 [4 + 2 (3.5)] = 0.25 (4 + 7) = 0.25 (11) = 2.75

The exact value is:

\int_{0}^{2} x^{2} d x = [\frac{x ^{3}}{3}]_{0}^{2} = \frac{8}{3} \approx 2.667

so the trapezium rule overestimates here — as expected, since $y = x^{2}$ is convex (:

y&#039;&#039;=2>0

Doubling to 8 strips gives $2.6875$ , and the error falls from $0.0833$ to $0.0208$ , a factor of about 4, matching the $h^{2}$ behaviour of the error.

Worked example

Use the trapezium rule with 5 ordinates to estimate:

\int_{1}^{3} ln x d x

giving your answer to 4 decimal places.

State, with a reason, whether this is an overestimate or an underestimate, and confirm by evaluating the integral exactly.

Show worked solution

Five ordinates means 4 strips, so:

h = \frac{3 - 1}{4} = 0.5

and:

x = 1, 1.5, 2, 2.5, 3

The ordinates are $y_{0} = ln 1 = 0$ ,

y_{1} = ln 1.5 = 0.4054651

y_{2} = ln 2 = 0.6931472

y_{3} = ln 2.5 = 0.9162907

y_{4} = ln 3 = 1.0986123

The interior ordinates sum to $2.0149030$ , so the estimate is:

\frac{0.5}{2} [0 + 1.0986123 + 2 (2.0149030)] = 0.25 (5.1284183) = 1.2821

(4 d.p.).

Since $y = ln x$ has:

y&#039;&#039;=-\dfrac{1}{x^2}<0

the curve is concave throughout $[1, 3]$ , so each chord lies below the curve and the rule underestimates.

Exactly, integrating by parts,

\int ln x d x = x ln x - x + c

so:

\int_{1}^{3} ln x d x = (3 ln 3 - 3) - (0 - 1) = 3 ln 3 - 2 = 1.2958

(4 d.p.).

The estimate is indeed smaller, by about $1.1%$ .