Iteration and Numerical Methods

1. What is Iteration?

Iteration means repeating a process over and over again. In Maths, we take an answer, feed it back into the formula to get a better answer, and repeat. Each time we go through the loop, we get closer to the true solution of an equation.

The Notation:
Iteration formulas look like this: $x_{n+1} = 2x_n + 3$
To find $x_1$, you put $x_0$ into the formula. To find $x_2$, you put $x_1$ into the formula, and so on.

2. The Ultimate Calculator Trick

In a GCSE exam, writing out the calculation every time takes too long and causes errors. Use your calculator's ANS button.

For the formula $x_{n+1} = \frac{x_n}{2} + 3$ starting with $x_0 = 4$:

1. Type your starting number 4 and press =.
2. Now type the formula using the ANS button instead of $x_n$: ANS รท 2 + 3
3. Press = to get $x_1$.
4. Just press = again to get $x_2$. Press = again to get $x_3$!

3. Rearranging to Create an Iterative Formula

Sometimes, the exam asks you to "Show that $x^3 + 2x - 5 = 0$ can be arranged into $x = \sqrt[3]{5 - 2x}$".

To do this, you treat it like a normal equation and make $x$ the subject. Once you have $x = \dots$, you just add the little $n+1$ and $n$ subscripts.

Example 1: Rearranging an equation
Show that $x^3 + 5x - 4 = 0$ can be rearranged into $x_{n+1} = \frac{4 - x_n^3}{5}$
Step 1: Look at the target. The target has division by 5, meaning $5x$ was left on its own.
Step 2: Move everything else to the other side. $5x = 4 - x^3$
Step 3: Divide by 5. $x = \frac{4 - x^3}{5}$
Step 4: Add the subscripts. $x_{n+1} = \frac{4 - x_n^3}{5}$ (Done!)

4. Solving by Iteration

Example 2: Finding the root
Using the formula $x_{n+1} = \sqrt[3]{10 - x_n}$, start with $x_0 = 2$ and find the root to 2 decimal places.
Step 1: Calculate the first few iterations. $x_0 = 2$
$x_1 = \sqrt[3]{10 - 2} = 2$
$x_2 = \sqrt[3]{10 - 2} = 2$
Wait, if $x_1$ and $x_2$ are exactly the same, we have found the exact root! The answer is exactly 2.
When do I stop pressing equals?
If the question asks for the answer to 2 decimal places, keep pressing `=` until the first two decimal places stop changing.

Practice Questions & Solutions

Try these using the ANS button trick on your calculator!

Q1: Using $x_{n+1} = \frac{x_n + 5}{3}$ and $x_0 = 1$, find $x_1$ and $x_2$.
Find $x_1$ by plugging in $x_0 = 1$:
$x_1 = \frac{1 + 5}{3} = \frac{6}{3} = 2$
Find $x_2$ by plugging in $x_1 = 2$:
$x_2 = \frac{2 + 5}{3} = \frac{7}{3}$ (or $2.333\dots$)
Answer: $x_1 = 2$, $x_2 = 2.33$ (2 d.p)
Q2: Using $x_{n+1} = 2(x_n)^2 - 3$ and $x_0 = 2$, find $x_3$.
$x_1 = 2(2)^2 - 3 = 2(4) - 3 = 5$
$x_2 = 2(5)^2 - 3 = 2(25) - 3 = 47$
$x_3 = 2(47)^2 - 3 = 2(2209) - 3 = 4415$
Answer: $x_3 = 4415$
Q3: Show that $x^2 - 4x + 1 = 0$ can be written as $x_{n+1} = \frac{x_n^2 + 1}{4}$
Look at the target: we need $4x$ on the bottom, which means we must isolate $4x$.
Start with: $x^2 - 4x + 1 = 0$
Move $4x$ to the other side: $x^2 + 1 = 4x$
Divide by 4: $\frac{x^2 + 1}{4} = x$
Rewrite with subscripts: $x_{n+1} = \frac{x_n^2 + 1}{4}$
Proof complete.
Q4: Show that $x^3 - x - 2 = 0$ can be written as $x_{n+1} = \sqrt[3]{x_n + 2}$
Target has a cube root, so we must isolate $x^3$.
$x^3 - x - 2 = 0$
Move the $-x$ and $-2$ to the other side: $x^3 = x + 2$
Cube root both sides: $x = \sqrt[3]{x + 2}$
Rewrite with subscripts: $x_{n+1} = \sqrt[3]{x_n + 2}$
Proof complete.
Q5: Using $x_{n+1} = \sqrt{5x_n + 2}$, start with $x_0 = 2$ and find the root to 2 decimal places.
Type 2, press `=`. Then type $\sqrt{5\text{ANS} + 2}$.
$x_1 = 3.4641...$
$x_2 = 4.3955...$
$x_3 = 4.8967...$
$x_4 = 5.1462...$
$x_5 = 5.2660...$
$x_6 = 5.3226...$
Keep pressing `=`: it settles around $5.37228...$
Answer: $5.37$
Q6: Show that there is a solution to $x^3 - 3x + 1 = 0$ between $x = 1$ and $x = 2$.
This is a classic "Change of Sign" question, which always comes before iteration.
Substitute $x = 1$ into the equation: $1^3 - 3(1) + 1 = 1 - 3 + 1 = -1$
Substitute $x = 2$ into the equation: $2^3 - 3(2) + 1 = 8 - 6 + 1 = 3$
Because there is a change of sign (from -1 to 3), the graph must cross the x-axis (where $y=0$) between 1 and 2.
A change of sign proves a root exists between $x=1$ and $x=2$.
Q7: Using $x_{n+1} = \frac{7}{x_n^2 + 2}$ and $x_0 = 1$, find $x_1$ and $x_2$.
$x_1 = \frac{7}{1^2 + 2} = \frac{7}{3} = 2.333...$
$x_2 = \frac{7}{(7/3)^2 + 2} = \frac{7}{49/9 + 18/9} = \frac{7}{67/9} = \frac{63}{67}$
Decimal: $x_2 \approx 0.940$
Answer: $x_1 = 2.33$, $x_2 = 0.94$ (2 d.p)
Q8: Rearrange $x^3 + 4x - 1 = 0$ to make an iterative formula in the form $x_{n+1} = \frac{A}{x_n^2 + B}$. Find A and B.
Target has an $x^2$ on the bottom. We need to factorise to get this.
Move the 1 over: $x^3 + 4x = 1$
Factorise out an $x$: $x(x^2 + 4) = 1$
Divide by the bracket: $x = \frac{1}{x^2 + 4}$
Add subscripts: $x_{n+1} = \frac{1}{x_n^2 + 4}$
Answer: $A = 1, B = 4$
Q9: The number of bacteria in a dish is modeled by $P_{n+1} = 1.2P_n - 100$. If there are initially 500 bacteria ($P_0 = 500$), how many are there after 3 hours ($P_3$)?
This is iteration applied to a real-world scenario!
$P_0 = 500$
$P_1 = 1.2(500) - 100 = 600 - 100 = 500$
$P_2 = 1.2(500) - 100 = 500$
$P_3 = 1.2(500) - 100 = 500$
Answer: 500 bacteria. (This is a stable population!)
Q10: An iterative formula is $x_{n+1} = \frac{x_n}{3} + 4$. It approaches a limit (a final answer). Set up and solve an equation to find what this limit is.
When an iteration reaches its limit, the answers stop changing. This means $x_{n+1} = x_n$. Let's just call them both $x$.
Replace both with $x$: $x = \frac{x}{3} + 4$
Multiply everything by 3: $3x = x + 12$
Subtract $x$: $2x = 12$
Divide by 2: $x = 6$
Answer: The limit is exactly 6.