Iteration

What you'll learn

Read notation like $x_0$ , $x_n$ and $x_{n+1}$ .
Use an iterative formula to generate values such as $x_1$ , $x_2$ , $x_3$ .
Use iteration to estimate solutions to equations.
Show a solution lies in an interval and explain the link between an iteration and an equation.

1. Reading the notation

A sequence is a list of numbers in order. Each number in the list is called a term.

A subscript is the small lower number on a letter. For example, $x_3$ means “the term with subscript 3”. It does not mean $x^3$ .

A starting value is the value you are given before any formula is used, usually $x_0$ or $P_0$ .

Definition

Iteration

Iteration means repeatedly applying the same rule. A recurrence formula is a rule that tells you how to get the next term from the current term, such as $P_{t+1}=1.10(P_t-12)$ .

Iteration uses the output from one step as the input for the next step.

Worked example: a changing population

Example

Finding a future population

The number of birds in a park after $t$ weeks is $P_t$ , where $P_0=180$ and $P_{t+1}=1.10(P_t-12)$ . Find $P_3$ .

Each week’s population is found from the previous week’s value, not by reusing the starting value each time.

Start with the given value $P_0=180$ .
Substitute $P_0$ into the rule to find $P_1$ .
$P1=1.10(180−12)=1.10×168=184.8P_1=1.10(180-12)=1.10 \times 168=184.8$
Use $P_1$ , not $P_0$ , to find $P_2$ .
$P2=1.10(184.8−12)=1.10×172.8=190.08P_2=1.10(184.8-12)=1.10 \times 172.8=190.08$
Use $P_2$ to find $P_3$ .
$P3=1.10(190.08−12)=1.10×178.08=195.888P_3=1.10(190.08-12)=1.10 \times 178.08=195.888$
So the formula gives $P_3=195.888$ , which is about 196 birds if a whole number is required.

Common Mistake

Reusing the starting value

Do not put $P_0$ into every line. $P_1$ uses $P_0$ , then $P_2$ uses $P_1$ , then $P_3$ uses $P_2$ .

2. Iterating algebraic formulae

Many questions use a rule like:

xn+1=2+6xn2x_{n+1}=2+\frac{6}{x_n^2}

Here, $x_n$ means the current value, and $x_{n+1}$ means the next value.

The subscript n marks the current term, while n+1 marks the term produced by the formula.

Key Idea

Current value to next value

To find the next term, substitute the current term into the formula. After one use of the formula you get $x_1$ ; after two uses you get $x_2$ ; after three uses you get $x_3$ .

Worked example: finding $x_1$ , $x_2$ and $x_3$

Example

Using an iteration formula three times

Use $xn+1=2+6xn2x_{n+1}=2+\frac{6}{x_n^2}$ , with $x_0=2$ , to find $x_1$ , $x_2$ and $x_3$ .

The formula is applied three times, feeding each answer into the next step.

Find the first new value, $x_1$ , by using $x_0=2$ .
$x1=2+622=2+64=3.5x_1=2+\frac{6}{2^2}=2+\frac{6}{4}=3.5$
Find $x_2$ by using $x_1=3.5$ .
$x2=2+63.52=2.489795918…x_2=2+\frac{6}{3.5^2}=2.489795918\ldots$
Find $x_3$ by using the full calculator value for $x_2$ .
$x3=2+62.489795918…2=2.967884977…x_3=2+\frac{6}{2.489795918\ldots^2}=2.967884977\ldots$
To 3 d.p., the values are $x_1=3.500$ , $x_2=2.490$ and $x_3=2.968$ .

Tip

Calculator shortcut

Use the calculator’s Ans key carefully: enter the starting value first, then type the formula using Ans wherever $x_n$ appears, and press equals repeatedly.

3. Using iteration to estimate solutions

Some equations are difficult to solve exactly. Instead, you may be given an iteration formula that produces better and better estimates.

If the terms get closer and closer to one value, we say the sequence converges.

Definition

Root and fixed point

A root is a value of $x$ that makes an equation true. A fixed point is a value that stays unchanged by an iteration, so the current value and next value are equal.

At a fixed point, applying the iteration rule leaves the value unchanged.

Worked example: estimating a solution

Example

Three iterations for an estimate

Starting with $x_0=0$ , use $xn+1=2xn2+4x_{n+1}=\frac{2}{x_n^2+4}$ three times to estimate the solution of $x^3+4x=2$ .

The sequence of estimates moves towards a stable fixed point where the current and next values are nearly equal.

Start with $x_0=0$ .
First iteration:
$x1=202+4=0.5x_1=\frac{2}{0^2+4}=0.5$
Second iteration:
$x2=20.52+4=0.470588235…x_2=\frac{2}{0.5^2+4}=0.470588235\ldots$
Third iteration:
$x3=20.470588235…2+4=0.473770491…x_3=\frac{2}{0.470588235\ldots^2+4}=0.473770491\ldots$
After three iterations, the estimate is $x≈0.474x\approx0.474$ .

Common Mistake

Stopping too early

If a question says use the formula three times from $x_0$ , calculate $x_1$ , $x_2$ and $x_3$ . Do not stop at $x_2$ .

4. Explaining the relationship to an equation

You may be asked what the values $x_1$ , $x_2$ , $x_3$ have to do with an equation.

The key idea is: if the iteration settles down, then eventually the current value and next value are almost the same.

Worked example: linking the formula and equation

Example

Why the iteration solves the equation

An iteration is $xn+1=2xn2+4x_{n+1}=\frac{2}{x_n^2+4}$ . Explain its relationship with $x^3+4x-2=0$ .

When the iteration converges, replacing both the current and next values by the same fixed value links the formula to the equation.

If the sequence converges to a value $a$ , then both $x_n$ and $x_{n+1}$ are close to $a$ .
Replace $x_n$ and $x_{n+1}$ with $a$ .
$a=2a2+4a=\frac{2}{a^2+4}$
Multiply both sides by $a^2+4$ .
$a(a^2+4)=2$
Expand and rearrange.
$a^3+4a-2=0$
Therefore the converging values are estimates for a root of $x^3+4x-2=0$ .

Common Mistake

Not every rearrangement works

Different rearrangements of the same equation can behave differently. In an exam, use the iteration formula you are given unless you are specifically asked to rearrange it.

5. Showing a solution lies in an interval

To test an interval, write the equation as $f (x) = 0$ . Function notation $f (x)$ means “the value of the expression when the input is $x$ ”.

Definition

Sign change

A sign change means one output is negative and the other is positive. For a continuous graph, this shows the graph crosses the x-axis between the two inputs.

Equations made from powers of $x$ , such as $x^3+5x-2=0$ , have continuous graphs.

Worked example: showing a solution is between two values

Example

Using a sign change

Show that $x^3+5x-2=0$ has a solution between $x = 0$ and $x = 1$ .

A continuous graph with opposite signs at the endpoints must cross the x-axis between them.

Let $f(x)=x^3+5x-2$ .
Substitute $x = 0$ .
$f(0)=0^3+5(0)-2=-2$
Substitute $x = 1$ .
$f(1)=1^3+5(1)-2=4$
The outputs -2 and 4 have opposite signs, so there is a sign change.
Because the graph is continuous, there is a solution between $x = 0$ and $x = 1$ .

6. Rearranging into an iteration formula

Sometimes you must rearrange an equation into the form:

xx=\text{an expression involving }x

Then you turn it into an iteration formula by writing the next value on the left and the current value on the right.

Worked example: rearrange and iterate

Example

Creating and using an iteration formula

Show that $x^3+5x=2$ can be rearranged as $x=25−x35x=\frac{2}{5}-\frac{x^3}{5}$ . Then use $x_0=0$ to iterate twice.

Rearrange the equation.
$x3+5x=25x=2−x3x=2−x35=25−x35\begin{aligned} x^3+5x&=2\\ 5x&=2-x^3\\ x&=\frac{2-x^3}{5}=\frac{2}{5}-\frac{x^3}{5} \end{aligned}$
Write it as an iteration formula.
$xn+1=25−xn35x_{n+1}=\frac{2}{5}-\frac{x_n^3}{5}$
Use $x_0=0$ to find $x_1$ .
$x1=25−035=0.4x_1=\frac{2}{5}-\frac{0^3}{5}=0.4$
Use $x_1=0.4$ to find $x_2$ .
$x2=25−0.435=0.3872x_2=\frac{2}{5}-\frac{0.4^3}{5}=0.3872$
After two iterations, the estimate is $x≈0.3872x\approx0.3872$ .

Common Mistake

Mixing the symbols

Once you turn a rearrangement into an iteration formula, write the next value as $x_{n+1}$ and every current value on the right as $x_n$ .

Exam technique

In the exam

Write down the starting value clearly, then label each new value $x_1$ , $x_2$ , $x_3$ or $P_1$ , $P_2$ , $P_3$ .
Use the previous answer each time; keep full calculator accuracy and round only the final answer unless told otherwise.
For interval questions, substitute both endpoints into $f (x)$ and state that opposite signs show a root between them.
For relationship questions, set $x_{n+1}=x_n=x$ , then rearrange back to the original equation.

Self review

Check yourself

If you start with $x_0$ , what values do you find after three iterations?
How would you show that $x^3+5x-2=0$ has a root between 0 and 1?
Why does a fixed point of $xn+1=2xn2+4x_{n+1}=\frac{2}{x_n^2+4}$ solve $x^3+4x-2=0$ ?

What you'll learn

Read notation like $x_0$ , $x_n$ and $x_{n+1}$ .
Use an iterative formula to generate values such as $x_1$ , $x_2$ , $x_3$ .
Use iteration to estimate solutions to equations.
Show a solution lies in an interval and explain the link between an iteration and an equation.

1. Reading the notation

A sequence is a list of numbers in order. Each number in the list is called a term.

A subscript is the small lower number on a letter. For example, $x_3$ means “the term with subscript 3”. It does not mean $x^3$ .

A starting value is the value you are given before any formula is used, usually $x_0$ or $P_0$ .

Definition

Iteration

Iteration means repeatedly applying the same rule. A recurrence formula is a rule that tells you how to get the next term from the current term, such as $P_{t+1}=1.10(P_t-12)$ .

Iteration uses the output from one step as the input for the next step.