Iteration

Description

Iteration is a method for finding approximate solutions to equations that can't be solved algebraically. You start with an estimate and feed it into a formula repeatedly, getting closer to the answer each time.

Iterative formula

You'll usually be given a formula in the form $x_{n+1} = f(x_n)$. Substitute your starting value $x_0$, compute $x_1$, then feed $x_1$ back in to get $x_2$, and so on until the answer stabilises.

Example: Use $x_{n+1} = \sqrt{x_n + 5}$ with $x_0 = 2$ to find a root to 3 decimal places.

• $x_1 = \sqrt{2 + 5} = \sqrt{7} \approx 2.646$
• $x_2 = \sqrt{2.646 + 5} \approx 2.765$
• $x_3 \approx 2.796$
• Continue until the digits settle...

Change of sign to verify a root

Before iterating, you may be asked to show a root lies in a given interval, say between $x = 2$ and $x = 3$.

Substitute both values into $f(x)$:

• If $f(2)$ is negative and $f(3)$ is positive (or vice versa), there must be a root in between — the function has changed sign and must have crossed zero.

Example: Show that $f(x) = x^3 - x - 4$ has a root between 1 and 2.

$f(1) = 1 - 1 - 4 = -4$ (negative)

$f(2) = 8 - 2 - 4 = 2$ (positive)

Change of sign, so there is a root in the interval $1 < x < 2$. ✓

Links

Changing the subject