Iteration

​​In a nutshell

Iteration is a method of re-inputting an output into a function to get closer and closer to the root. To find the root of $$f(x)$$, you let $$f(x)=0$$ and rearrange into the format $$x=g(x)$$, then iterate as follows, $$x_n=g(x_{n-1})$$. The result will either converge closer to a root or diverge further from the root.

Iterative function

To make an iterative function, the formula must be in the format $$x=g(x)$$. To begin, let $$f(x)=0$$ and rearrange.

Example 1

Find three iterative functions for $$f(x)=x^2 -2x-1$$.

First, let $$f(x)=0$$

​$$\begin{aligned}f(x)&=x^2 -2x-1\\0&=x^2 -2x-1\end{aligned}$$

​

Then rearrange as you wish to. There are two functions you can make by moving $$x^2$$.

​$$\begin{aligned}x^2&=2x+1\\\end{aligned}$$​​

Another can be made by moving $$-2x$$.

$$\begin{aligned}2x&=x^2-1\\x&=\underline{\dfrac{x^2-1}{2}}\end{aligned}$$​​

Iteration: $$x_n=g(x_{n-1})$$

With an iterative function in the form $$x=g(x)$$​, you will find subsequent $$x$$ values with the aim of getting closer to the root. You use an $$x_0$$ value to find $$x_1$$, use $$x_1$$ to find $$x_2$$ and so on.

$$\begin{aligned}x_n&=g(x_{n-1})\\x_1&=g(x_0)\\x_2&=g(x_1)\\x_3&=g(x_2)\\.\\.\\.\\\end{aligned}$$​​

Example 2

Use $$x=\dfrac{x^2-1}{2}$$ and $$x_0=5$$ to find $$x_1,x_2,x_3$$​

​​$$\begin{aligned}x_0&=5\\\\x_1&=\dfrac{5^2-1}{2}=\underline{12}\\\\x_2&=\dfrac{12^2-1}{2}=\underline{71.5}\\\\x_3&=\dfrac{71.5^2-1}{2}=\underline{2555.625}\\\end{aligned}$$​​

Diverging and converging iteration

The previous example showed a diverging iteration: $$x_n$$ grew increasingly larger and diverged from the root. The opposite of this is a converging iteration, where $$x_n$$ gets closer to the root.

Example 3

Use $$x=2+\dfrac1x$$ and $$x_0=2$$ to find a root rounded to $$3\space d.p$$.

$$\begin{aligned}x_0&=2\\x_1&=2+\dfrac12=2.5\\\\x_2&=2+\dfrac1{2.5}=2.4\\\\x_3&=2+\dfrac1{2.4}=2.4167\\\\x_4&=2+\dfrac1{2.4167}=2.4138\\\\x_5&=2+\dfrac1{2.4138}=2.4143\\\\x_6&=2+\dfrac1{2.4143}=2.4142\\\\x_7&=2+\dfrac1{2.4142}=2.4142\\\\\end{aligned}$$

As $$2.414$$ is repeating, you know that you have converged onto a root.

$$f(x)=0$$ when $$\underline{x=2.414}$$​​

​​