Iteration in maths

Iteration in maths means repeating the same step, feeding each answer back in to get the next one. At GCSE and A-level it is used to find approximate solutions to equations you cannot solve exactly: rearrange the equation into the form x = g(x), turn it into an iterative formula, start from a first guess x₀, and keep substituting until the answers stop changing to the accuracy you need.

What is iteration?

An iterative formula tells you how to get the next value from the one before. It uses suffix notation: x₀ is the starting value, x₁ the first answer, x₂ the second, and so on. A typical formula looks like this:

Put x₀ into the right-hand side to get x₁, put x₁ in to get x₂, and keep going. If the values settle down towards a single number, the iteration converges, and that number is a solution of the equation x = ∛(5x − 1). If they wander off, it diverges.

How to solve an equation by iteration

1. Show there is a solution in an interval, by a change of sign.
2. Rearrange the equation into the form x = g(x).
3. Write the iterative formula x_n+1 = g(x_n) and choose x₀ (usually given).
4. Iterate, writing down each value, until two in a row agree to the accuracy asked for.
5. Check with a change of sign either side of your rounded answer, if the question asks you to.

Step 1: the change of sign

Write the equation as f(x) = 0. If f(x) is negative at one value and positive at another, and the graph has no gaps in between, it must cross zero somewhere between them. For x³ − 5x + 1 = 0:

The sign changes, so there is a solution between x = 2 and x = 3.

Step 2: rearranging to x = g(x)

Make x the subject on one side, leaving x inside the other side as well. Here, add 5x and subtract 1 from both sides, then take the cube root:

Exam questions usually give you the rearrangement and ask you to show it, so work forwards from the equation they start with. Practise rearranging in this question from the Algebra course.

Worked examples

Example 1: iterating to 2 decimal places

Use x_n+1 = ∛(5x_n − 1) with x₀ = 2 to find the solution of x³ − 5x + 1 = 0 between 2 and 3, to 2 decimal places.

x₄ and x₅ both round to 2.13, so the solution is x = 2.13 to 2 decimal places. To prove it, check the sign either side of the rounding boundaries: f(2.125) = −0.029 and f(2.135) = 0.057. The sign changes, so the root lies between 2.125 and 2.135 and rounds to 2.13.

Example 2: finding the limit exactly

The formula x_n+1 = √(x_n + 6) with x₀ = 1 gives 2.6458, 2.9404, 2.9900, 2.9983, ... What do the values converge to?

When the values settle at a limit L, both x_n+1 and x_n equal L:

A square root is never negative, so L = 3. This is how you find the equation that a limit satisfies: replace both x_n and x_n+1 with the same letter.

Check your understanding.

Staircase and cobweb diagrams (A-level)

Iteration has a picture. A solution of x = g(x) is where the graph of y = g(x) meets the line y = x. From x₀, go vertically to the curve, then horizontally to the line, which gives x₁ underneath. Repeat. When the arrows step steadily towards the crossing, it is a staircase diagram. Here x_n+1 = (x_n² + 4) ÷ 5 starting from x₀ = 3 gives 2.6, 2.152, 1.726, 1.396, ... stepping down towards x = 1, a root of x² − 5x + 4 = 0.

When g(x) is a decreasing function, the values jump from one side of the root to the other, and the path spirals inwards. This is a cobweb diagram. Here x_n+1 = 3 ÷ (x_n + 1) starting from x₀ = 0.5 gives 2, 1, 1.5, 1.2, 1.364, ... closing in on 1.303.

When iteration fails

The same equation can be rearranged in more than one way, and not every rearrangement works. x³ − 5x + 1 = 0 can also be written as x = (x³ + 1) ÷ 5. Starting at x = 2.2, near the root at 2.128, this gives 2.330, 2.729, 4.263, 15.69, ... and runs away.

The rule is the gradient of g at the root. The iteration converges if the curve is shallower than the line y = x there:

For g(x) = ∛(5x − 1), g'(2.128) = 0.37, so it converges. For g(x) = (x³ + 1) ÷ 5, g'(2.128) = 2.72, so it diverges from that root. Started at x = 2, it slides away to the other root, near 0.2016, where its gradient is small. Change of sign checks can fail too: if the curve touches the axis without crossing, or there are two roots close together, the sign may not change at all.

The Newton-Raphson method (A-level)

Newton-Raphson is an iteration that uses the tangent to the curve. Starting from a guess, follow the tangent down to the x axis and use that as the next guess:

For f(x) = x³ − 5x + 1, f'(x) = 3x² − 5. From x₀ = 2: x₁ = 2 − (−1) ÷ 7 = 2.142857, x₂ = 2.128571, x₃ = 2.128419. Three steps give six decimal places, where the cube root formula needed five steps for two. It fails if f'(x_n) is zero or close to zero, because the tangent is flat and the next guess shoots far away. The Derivative Calculator can find f'(x) for you, and the Newton-Raphson method guide goes further.

Common mistakes

• Rounding as you go. Keep full calculator values and only round the answers you write down.
• Stopping too early. Keep going until two values in a row round to the same answer.
• Leaving the calculator in degrees at A-level. Formulas with sin or cos need radians unless the question says otherwise.
• Losing the x on the right-hand side when rearranging. x = g(x) still has x inside g.
• Not giving the conclusion for a change of sign: say the sign changes and the function is continuous, so there is a root.
• Writing x₀ as the first iterate. x₀ is the start; x₁ is the first answer.

Practise with a short timed paper

Algebra comes up in every GCSE and A-level Maths paper. The daily GCSE Maths Higher and A-level Maths: Algebra & Functions papers are short timed papers of 8 questions, with a new one every day.

Read next

Maths · CalculusNewton-Raphson method: formula, examples and when it failsThe Newton-Raphson method for solving f(x) = 0: the formula, why it works, worked examples, proving a root to a given accuracy and when the method fails.