Iteration and numerical methods

Lesson overview

Algebra — numerical methods

**Iteration** is a method for finding approximate solutions to equations that cannot be solved exactly. We rearrange the equation into the form $x = f(x)$ , then use the iterative formula $x_{n+1} = f(x_n)$ . Starting with an initial guess $x_0$ , we repeatedly substitute to get closer to the solution: $x_1 = f(x_0), \quad x_2 = f(x_1), \quad x_3 = f(x_2), \quad \ldots$ The iteration **converges** when successive values agree to the required degree of accuracy. Not all rearrangements converge — it depends on the gradient of $f(x)$ near the solution. **Sign change method**: if $f(a)$ and $f(b)$ have opposite signs, there is a root between $a$ and $b$ (provided $f$ is continuous).

Using an iterative formula

Use the iteration $x_{n+1} = \sqrt{2x_n + 3}$ with $x_0 = 4$ to find the solution to $x^2 - 2x - 3 = 0$ correct to $3$ decimal places.

Keep iterating until consecutive values agree to the required accuracy.

Rearranging to find an iteration formula

To solve $x^3 + 2x - 5 = 0$ , rearrange: $x^3 = 5 - 2x$ , so $x = \sqrt[3]{5 - 2x}$ , giving $x_{n+1} = \sqrt[3]{5 - 2x_n}$ .

Different rearrangements may or may not converge.

Sign change method to locate a root

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

f(1)

$1 - 1 - 1 = -1$

negative

f(2)

$8 - 2 - 1 = 5$

positive

If $f(a) < 0$ and $f(b) > 0$ , there is a root in $(a, b)$ .

Worked example

Show that the equation $x^3 - 4x + 1 = 0$ has a root between $0$ and $1$ , then use the iteration $x_{n+1} = \dfrac{x_n^3 + 1}{4}$ with $x_0 = 0.5$ to find the root correct to $2$ decimal places.

Check sign change: $f(0) = 1$ (positive), $f(1) = -2$ (negative). Sign change, so root exists in $(0, 1)$ .
Start with $x_0 = 0.5$ : $x_1 = \dfrac{0.5^3 + 1}{4} = \dfrac{1.125}{4} = 0.28125$ .
$x_2 = \dfrac{0.28125^3 + 1}{4} \approx 0.25552$ , $x_3 \approx 0.25417$ , $x_4 \approx 0.25410$ .
The values agree to 2 d.p. at $0.25$ . So the root is $0.25$ (to 2 d.p.).

Try it

Check for a sign change first, then iterate until consecutive values agree to the required accuracy.

Question 1

The iteration $x_{n+1} = \sqrt{5 + x_n}$ with $x_0 = 2$ gives $x_1 =$ ?

Question 2

If $f(1) = -3$ and $f(2) = 5$ , what can we conclude?

Question 3

Rearrange $x^2 + 3x - 7 = 0$ to give an iteration formula.

Question 4

An iteration converges when:

Question 5

Using $x_{n+1} = \dfrac{x_n^2 + 2}{5}$ with $x_0 = 1$ , what is $x_2$ ?

Common mistakes

Watch for these when working through the lesson.

Not checking whether the iteration actually converges — some rearrangements diverge.
Rounding too early in the iteration, which accumulates errors.
Stopping the iteration before consecutive values agree to the required number of decimal places.

Iteration and numerical methods

Lesson overview

Worked example

Try it

Common mistakes

Related topics

Independent practice will plug in here