Mathematics guide, Beyond AP, step 31 of 33Previous step Next step

Step 31: Numerical Methods: Roots and Iteration

By the EconTutorials team. 13-minute read with 6 practice questions.

Syllabus9709 P2/P3 2.6, 3.6

In 30 seconds

Most equations, such as $ x^3 + 2x-8 = 0 $ or $ \ln x = 3-x $, have no tidy algebraic solution. Numerical methods trap a root first, then close in on it step by step.
If $ f $ is continuous and $ f(a) $, $ f(b) $ have opposite signs, there is a root between $ a $ and $ b $. Asymptotes can fake a sign change, and touching or paired roots can hide one.
Rearrange $ f(x) = 0 $ as $ x = F(x) $ and iterate $ x_{n+1} = F(x_n) $. If the sequence settles, its limit is a root. Staircase and cobweb diagrams show why some rearrangements work and others run away.
Exam point: to prove a root is, say, $ 1.670 $ correct to 3 d.p., show a sign change between $ 1.6695 $ and $ 1.6705 $. Iterates that “look settled” are evidence, not proof.

Video lesson coming soonA short animated lesson for this step will appear here.

Locating roots with graphs

This step covers Cambridge 9709 topic 2.6 (Paper 2) and 3.6 (Paper 3), which are the same content. IB Analysis and Approaches expects you to solve such equations with your graphic display calculator, and AP Calculus meets the key idea as the Intermediate Value Theorem. The section on Newton–Raphson is an extension that none of these syllabuses examine.

Before hunting for a root, find out how many there are and roughly where they sit. The quickest tool is a sketch. Split the equation into two sides you already know how to draw, put both graphs on one set of axes, and count the crossings.

Key termRoot: a number $ \alpha $ with $ f(\alpha) = 0 $. The real roots of $ g(x) = h(x) $ are the $ x $-coordinates of the points where $ y = g(x) $ and $ y = h(x) $ meet.

Choose the split so that both graphs are familiar: a power, an exponential, a logarithm, a trig curve or a straight line. One argument is especially useful. A graph that is increasing everywhere and a graph that is decreasing everywhere can cross at most once.

Worked example

By sketching suitable graphs, show that $ \ln x = 3-x $ has exactly one real root, and find the two consecutive integers between which it lies.

Step 1Sketch $ y = \ln x $ and $ y = 3-x $. The log curve rises for all $ x > 0 $; the line falls. So they meet at most once.

Step 2At $ x = 2 $: $ \ln 2 \approx 0.693 $ and $ 3-2 = 1 $, so the curve is below the line.

Step 3At $ x = 3 $: $ \ln 3 \approx 1.099 $ and $ 3-3 = 0 $, so the curve is above the line. They must cross in between.

There is exactly one real root, and it lies between 2 and 3 (it is about 2.208).

y = ln x and y = 3 − x meet once

y = ln xy = 3 − x

Figure 1. A rising curve and a falling line cross exactly once. At x = 2 the log curve is below the line; at x = 3 it is above, so the root lies between 2 and 3.

Change of sign, and when it misleads

A sketch shows roughly where a root is. To show it, rewrite the equation as $ f(x) = 0 $ and look at the sign of $ f $. If the graph is an unbroken curve that is below the axis at one end of an interval and above it at the other, it has to cross the axis somewhere in between.

\[ f \text{ continuous},\ \ f(a)\,f(b) < 0 \;\Longrightarrow\; \text{a root in } (a, b) \]

This is the Intermediate Value Theorem from step 10: a continuous function takes every value between $ f(a) $ and $ f(b) $, and zero is one of them.

Worked example

Show that $ x^3 + 2x-8 = 0 $ has a root between 1 and 2, then find an interval of width 0.1 that contains it.

Step 1Let $ f(x) = x^3 + 2x-8 $. It is a polynomial, so it is continuous.

Step 2$ f(1) = 1 + 2-8 = -5 < 0 $ and $ f(2) = 8 + 4-8 = 4 > 0 $. There is a change of sign, so a root lies in $ (1, 2) $.

Step 3Narrow it: $ f(1.6) = 4.096 + 3.2-8 = -0.704 < 0 $ and $ f(1.7) = 4.913 + 3.4-8 = 0.313 > 0 $.

The sign changes again, so the root lies in $ (1.6, 1.7) $.

The rule has a condition and a limit, and examiners test both.

A sign change with no root. If $ f $ is not continuous it can jump from negative to positive without passing through zero. The usual culprit is a vertical asymptote, as in Figure 2.
A root with no sign change. At a repeated root, such as $ (x-1)^2 = 0 $, the graph touches the axis and turns back, so $ f $ has the same sign on both sides. An interval can also hide two close roots: both ends then have the same sign.
At least one, not exactly one. A sign change promises at least one root in the interval. It could be three.

y = 1/(x − 2): a sign change with no root

y = 1/(x − 2)

Figure 2. f(1) is negative and f(3) is positive, but the curve never crosses the x-axis. It jumps across the vertical asymptote at x = 2, so the change-of-sign rule does not apply.

Common mistakeWriting “$ f(1) < 0 $ and $ f(2) > 0 $, so there is a root” and stopping. A full answer states $ f $, shows both values with their signs, says change of sign, and gives the reason the rule applies: $ f $ is continuous on the interval. Without that last phrase, Figure 2 would “prove” a root that does not exist.

Iteration: $ x_{n+1} = F(x_n) $

Each extra decimal place found by sign changes costs more and more evaluations. An iterative formula does better: it turns one estimate into a better one, automatically. Rearrange $ f(x) = 0 $ into the form $ x = F(x) $. A root then satisfies $ \alpha = F(\alpha) $. Choose a starting value $ x_1 $ and keep feeding each output back in.

Key termFixed point: a number $ \alpha $ with $ F(\alpha) = \alpha $. It is where $ y = F(x) $ meets the line $ y = x $. If the sequence $ x_{n+1} = F(x_n) $ converges and $ F $ is continuous, its limit is a fixed point, and so a root of the original equation.

Why must the limit be a root? If $ x_n \to \alpha $, then $ x_{n+1} \to \alpha $ as well (it is the same sequence, one step later), while $ F(x_n) \to F(\alpha) $ by continuity. Both sides of $ x_{n+1} = F(x_n) $ have the same limit, so $ \alpha = F(\alpha) $.

Worked example

(a) Show that $ x^3 + 2x-8 = 0 $ can be written as $ x = \sqrt[3]{8-2x} $. (b) Use $ x_{n+1} = \sqrt[3]{8-2x_n} $ with $ x_1 = 1.6 $ to find the root correct to 2 decimal places, giving each iterate to 4 decimal places.

Step 1$ x^3 + 2x-8 = 0 \iff x^3 = 8-2x \iff x = \sqrt[3]{8-2x} $. Each step is reversible.

Step 2Iterate, keeping the full calculator value each time (use the ANS key): $ x_2 = 1.6869 $, $ x_3 = 1.6663 $, $ x_4 = 1.6712 $, $ x_5 = 1.6700 $, $ x_6 = 1.6703 $, $ x_7 = 1.6702 $.

Step 3From $ x_4 $ onwards every iterate rounds to 1.67, and the values are now changing only in the fourth decimal place.

The root is 1.67 correct to 2 decimal places. Quote it to exactly that accuracy, not as 1.6702.

Exam tipWrite each iterate to the number of places the question asks for, but never re-type a rounded value into the next step. Stop once two consecutive iterates agree to the accuracy required, and give the final answer to exactly that accuracy. Cambridge awards a separate mark for the final answer.

Proving the accuracy. Settled iterates are strong evidence, but they are not a proof. A sign change turns them into one. A number rounds to 1.670 (to 3 d.p.) exactly when it lies in the interval $ [1.6695, 1.6705) $. So test $ f $ at the two ends of that interval: the answer plus or minus 0.0005. In general, to show $ \alpha = X $ correct to $ n $ decimal places:

\[ \text{test } f\big(X-0.5 \times 10^{-n}\big) \text{ and } f\big(X + 0.5 \times 10^{-n}\big) \]

If $ f $ is continuous and the two values have opposite signs, the root lies between them, so it rounds to $ X $.

Worked example

Show that the root of $ x^3 + 2x-8 = 0 $ is 1.670 correct to 3 decimal places.

Step 1Numbers that round to 1.670 lie between 1.6695 and 1.6705.

Step 2$ f(1.6695) \approx -0.0077 < 0 $ and $ f(1.6705) \approx 0.0026 > 0 $.

Step 3$ f $ is continuous and changes sign, so $ 1.6695 < \alpha < 1.6705 $.

Hence $ \alpha = 1.670 $ correct to 3 decimal places. Testing 1.669 and 1.671 instead would prove nothing about the third decimal place.

Staircases, cobwebs and convergence

Not every rearrangement works. The same cubic can be written $ x = \tfrac{1}{2}(8-x^3) $. From the same start, $ x_1 = 1.6 $, it gives $ 1.952 $, $ 0.2811 $, $ 3.9889 $, $ -27.7341 $, and runs away, even though it started very near the root. A picture explains the difference.

Draw $ y = F(x) $ and the line $ y = x $; they meet at the fixed point. Start at $ x_1 $ on the $ x $-axis and repeat two moves: go vertically to the curve (height $ F(x_n) = x_{n+1} $), then horizontally to the line $ y = x $, which puts you directly above $ x_{n+1} $. When $ F $ is decreasing near the root the path spirals: a cobweb. When $ F $ is increasing it climbs or falls in steps: a staircase.

Cobweb for x(n+1) = ∛(8 − 2x(n)), starting at x₁ = 0.5

y = xy = ∛(8 − 2x)

Figure 3. Up to the curve, across to y = x, and repeat. Because F is decreasing, the path spirals inwards, landing on alternate sides of the root: 0.5, 1.9129, 1.6101, 1.6845, 1.6668, …

A cobweb has a bonus. A decreasing $ F $ sends a point below the root to one above it, so the root always lies between two consecutive iterates. In the worked example, $ x_6 = 1.6703 $ and $ x_7 = 1.6702 $ already trap the root. A staircase approaches from one side only, as Figure 4 shows for $ x_{n+1} = \sqrt{x_n + 3} $, a rearrangement of $ x^2-x-3 = 0 $.

Staircase for x(n+1) = √(x(n) + 3), starting at x₁ = 0

y = xy = √(x + 3)

Figure 4. F is increasing, so the path climbs in steps and every iterate is below the root: 0, 1.7321, 2.1753, 2.2749, 2.2967, …

What decides whether the path closes in or spirals out is how steep $ y = F(x) $ is where it crosses $ y = x $. Near the root each step multiplies the error by about $ F'(\alpha) $. If that factor is smaller than 1 in size, the errors shrink like a geometric sequence. Cambridge does not require this condition, but it tells you which rearrangement to try.

Iteration	$ F'(\alpha) $	Diagram	Behaviour
$ x_{n+1} = \sqrt[3]{8-2x_n} $	$ -\dfrac{2}{3\alpha^2} \approx -0.24 $	cobweb	converges
$ x_{n+1} = \tfrac{1}{2}(8-x_n^3) $	$ -\tfrac{3}{2}\alpha^2 \approx -4.18 $	cobweb	spirals out
$ x_{n+1} = \sqrt{x_n + 3} $	$ \dfrac{1}{2\alpha} \approx 0.22 $	staircase	converges

Extension: the Newton–Raphson method

This section is an extension. Newton–Raphson is not in Cambridge 9709, AP Calculus or IB Analysis and Approaches, so no exam question will require it. It is taught in first-year university courses, and a version of it runs inside calculator equation solvers and spreadsheet functions.

The idea is the tangent line from step 16, used again and again. Stand at $ (x_n, f(x_n)) $, draw the tangent, and see where it meets the $ x $-axis. Setting $ 0 = f(x_n) + f'(x_n)(x-x_n) $ gives the next estimate.

\[ x_{n+1} = x_n-\frac{f(x_n)}{f'(x_n)}, \qquad f'(x_n) \neq 0. \]

Newton–Raphson on y = x³ + 2x − 8, starting at x₁ = 2.5

y = x³ + 2x − 8

Figure 5. Each gold tangent is followed down to the x-axis to give the next estimate: x₂ = 1.8916, x₃ = 1.6912, already close to α = 1.6702.

Worked example

Apply Newton–Raphson to $ f(x) = x^3 + 2x-8 $ with $ x_1 = 2 $.

Step 1$ f'(x) = 3x^2 + 2 $, so $ x_{n+1} = x_n-\dfrac{x_n^3 + 2x_n-8}{3x_n^2 + 2} $.

Step 2$ x_2 = 2-\dfrac{4}{14} = 1.714286 $, then $ x_3 = 1.671159 $ and $ x_4 = 1.670245 $.

Step 3$ x_5 = 1.670245 $ agrees with $ x_4 $ to 6 decimal places.

Three steps give the root to 6 decimal places; the cube-root iteration needed six steps for four places. Newton fails when the tangent is flat ($ f'(x_n) = 0 $) or when a poor start throws it towards a different root, which is why you still locate the root with a sketch or a sign change first.

Economics: the internal rate of return

A project costs money now and pays back later. At discount rate $ r $, a payment of $ C $ dollars in $ t $ years is worth $ C/(1 + r)^t $ today. The net present value (NPV) adds these together, counting the initial cost as negative. The internal rate of return (IRR) is the rate at which the project exactly breaks even, $ \text{NPV}(r) = 0 $. With three or more years of payments there is no practical formula, so it is found numerically. This is exactly what a spreadsheet IRR function does.

Worked example

A machine costs $1000 and adds $440 to profit at the end of each of the next three years. Find its IRR to 1 decimal place as a percentage.

Step 1$ \text{NPV}(r) = -1000 + \dfrac{440}{1+r} + \dfrac{440}{(1+r)^2} + \dfrac{440}{(1+r)^3} $. Then $ \text{NPV}(0.15) \approx 4.62 > 0 $ and $ \text{NPV}(0.16) \approx -11.81 < 0 $: NPV is continuous for $ r > -1 $, so the IRR is between 15% and 16%.

Step 2Put $ x = 1 + r $ and multiply by $ x^3 $: $ -1000x^3 + 440x^2 + 440x + 440 = 0 $, so $ x = \sqrt[3]{0.44(x^2 + x + 1)} $.

Step 3Iterate from $ x_1 = 1.15 $: $ 1.1518 $, $ 1.1524 $, $ 1.1526 $, $ 1.1527 $, $ 1.1528 $, $ 1.1528 $. So $ x \approx 1.153 $ and $ r \approx 0.153 $.

Step 4Prove it: $ \text{NPV}(0.1525) \approx 0.47 > 0 $ and $ \text{NPV}(0.1535) \approx -1.18 < 0 $. A sign change, so $ 0.1525 < r < 0.1535 $.

The IRR is 15.3%. If the firm can borrow at 12% the machine is worth buying; at a cost of capital of 18% it is not. Remember to subtract 1: the iteration finds $ 1 + r $, not $ r $.

Net present value of the project ($)

NPV(r) = −1000 + 440/(1+r) + 440/(1+r)² + 440/(1+r)³

Figure 6. NPV falls as the discount rate rises and crosses zero once, at the internal rate of return.

Practise: 6 questions

Try each one on paper first, then check the worked answer.

EasyQ1. Show that $ x^3-x-3 = 0 $ has a root between 1 and 2. Show worked answer

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

EasyQ2. Use $ x_{n+1} = \sqrt[3]{10-3x_n} $ with $ x_1 = 1.5 $ to find $ x_2 $ and $ x_3 $ to 4 decimal places. State, with integer coefficients, the cubic equation that the limit satisfies. Show worked answer

$ x_2 = \sqrt[3]{10-4.5} = \sqrt[3]{5.5} = 1.7652 $.
$ x_3 = \sqrt[3]{10-3(1.76517\ldots)} = 1.6756 $.
The limit satisfies $ x = \sqrt[3]{10-3x} $, so $ x^3 = 10-3x $.
That is $ x^3 + 3x-10 = 0 $.

MediumQ3. Show that the root of $ e^x + x-4 = 0 $ is 1.074 correct to 3 decimal places. Show worked answer

Let $ f(x) = e^x + x-4 $, which is continuous.
Numbers that round to 1.074 lie between 1.0735 and 1.0745.
$ f(1.0735) \approx -0.0009 < 0 $ and $ f(1.0745) \approx 0.0030 > 0 $.
Change of sign, so $ 1.0735 < \alpha < 1.0745 $ and $ \alpha = 1.074 $ to 3 d.p.

MediumQ4. Let $ g(x) = x^2-4x + 3.9 $. A student finds $ g(1) = 0.9 $ and $ g(3) = 0.9 $, and concludes that $ g(x) = 0 $ has no root between 1 and 3. Show that the student is wrong, and find the roots exactly. Show worked answer

$ g(2) = 4-8 + 3.9 = -0.1 < 0 $.
So $ g $ changes sign on $ (1, 2) $ and again on $ (2, 3) $: there are two roots in $ (1, 3) $.
Exactly: $ (x-2)^2 = 0.1 $, so $ x = 2 \pm \sqrt{0.1} \approx 1.684 $ and $ 2.316 $.
No sign change between the ends does not mean no root: two close roots can hide inside the interval.

MediumQ5. The sequence $ x_{n+1} = 2 + \dfrac{1}{x_n} $, with $ x_1 = 2 $, converges to $ \alpha $. Find $ x_2 $, $ x_3 $ and $ x_4 $, then find the exact value of $ \alpha $. Show worked answer

$ x_2 = 2.5 $, $ x_3 = 2.4 $, $ x_4 = 2.4167 $ (to 4 d.p.).
The limit satisfies $ \alpha = 2 + \dfrac{1}{\alpha} $, so $ \alpha^2-2\alpha-1 = 0 $.
$ \alpha = 1 \pm \sqrt{2} $. All the iterates are positive, so $ \alpha = 1 + \sqrt{2} \approx 2.4142 $.

ExamQ6. (a) By sketching suitable graphs, show that the equation $ \cos x = x^2 $ has exactly one root for $ x > 0 $, where $ x $ is in radians. [2] (b) Show by calculation that this root lies between 0.8 and 0.9. [2] (c) Show that, if a sequence of values given by $ x_{n+1} = \sqrt{\cos x_n} $ converges, it converges to this root. [1] (d) Use this iterative formula with $ x_1 = 0.8 $ to find the root correct to 2 decimal places. Give the result of each iteration to 4 decimal places. [3] Show worked answer

(a) Sketch $ y = \cos x $ and $ y = x^2 $. For $ 0 < x \le 1 $, $ x^2 $ increases from 0 to 1 while $ \cos x $ decreases from 1, so they cross once; for $ x > 1 $, $ x^2 > 1 \ge \cos x $, so no more crossings. [B1 B1]
(b) Let $ f(x) = \cos x-x^2 $. $ f(0.8) = 0.0567 > 0 $, $ f(0.9) = -0.1884 < 0 $. [M1]
Change of sign and $ f $ continuous, so the root is in $ (0.8, 0.9) $. [A1]
(c) A limit $ \alpha $ satisfies $ \alpha = \sqrt{\cos \alpha} $, so $ \alpha^2 = \cos \alpha $, the given equation. [B1]
(d) $ 0.8347,\ 0.8194,\ 0.8262,\ 0.8232,\ 0.8245,\ 0.8239,\ 0.8242,\ 0.8241 $. [M1 A1]
The root is 0.82 correct to 2 d.p. [A1]
Total: 8 marks.

Check yourself

1. To show that a root of $ f(x) = 0 $ is 2.346 correct to 3 decimal places, you should evaluate $ f $ at

Numbers that round to 2.346 lie in $ [2.3455, 2.3465) $, so a sign change between these two values traps the root inside that interval.

2. An iteration has $ F'(\alpha) = -0.6 $. Near $ \alpha $, its diagram is

A negative gradient makes the iterates alternate sides (a cobweb), and $ |F'(\alpha)| < 1 $ means each error shrinks, so it converges.

3. The sequence $ x_{n+1} = \sqrt{2x_n + 8} $, with $ x_1 = 1 $, converges. What is its limit?

The limit satisfies $ \alpha = \sqrt{2\alpha + 8} $, so $ \alpha^2-2\alpha-8 = 0 $ and $ \alpha = 4 $ or $ -2 $. A square root is never negative, so the limit is 4.

Your score: 0 out of 3

The short version

Sketch two graphs to count roots and find roughly where they are; a rising graph and a falling graph meet at most once.
If $ f $ is continuous and changes sign on $ [a, b] $, there is a root in between. Asymptotes fake a sign change; repeated or paired roots hide one.
Rearrange to $ x = F(x) $ and iterate $ x_{n+1} = F(x_n) $; a limit satisfies $ \alpha = F(\alpha) $. Keep full accuracy between steps.
Prove $ \alpha = X $ to $ n $ d.p. with a sign change between $ X \pm 0.5 \times 10^{-n} $.
Cobwebs (decreasing $ F $) bracket the root; staircases (increasing $ F $) approach from one side. Steep $ F $ at the root means the iteration fails. Newton–Raphson is a fast extension beyond the syllabus.
The full chapter in Mathematics Made Simple has many more worked examples and a full set of practice questions with a complete answer key.

Step 31: Numerical Methods: Roots and Iteration

Locating roots with graphs

Change of sign, and when it misleads

Iteration: \( x_{n+1} = F(x_n) \)

Staircases, cobwebs and convergence

Extension: the Newton–Raphson method

Economics: the internal rate of return

Practise: 6 questions

Check yourself

The short version

Further reading on EconTutorials

Contact Info

Quick Links

Success!