Iteration

An iterative sequence is one generated by the recurrence relation

\[ x_{n+1} = F(x_n). \]

The starting value is $x_0$ and each term is called an iterate.

A fixed point, or convergent, occurs when

\[ x_n = F(x_n). \]

Example

Given $x_{n+1} = 4 - 3x_n$ and starting point $x_0 = 5$,

a) calculate the first five iterates.
b) find any fixed points which exist.

\[ x_{0} = 5 \] \[ x_{1} = 4 - 3x_{0} = 4 - 15 = -11 \] \[ x_{2} = 4 - 3x_{1} = 4 + 33 = 37 \] \[ x_{3} = 4 - 3x_{2} = 4 - 111 = -107 \] \[ x_{4} = 4 - 3x_{3} = 4 + 321 = 325 \] \[ x_{5} = 4 - 3x_{4} = 4 - 975 = -971 \]

b) For fixed points, $x_n = F(x_n)$:

\[ x = 4 - 3x \]

\[ 4x = 4 \quad \Rightarrow \quad x = 1. \]

So $x = 1$ is a fixed point.

Graphical methods

Consider the function

\[ f(x) = x^2 + x - 2 \]

which is graphed below:

Graph of f(x) = x^2 + x - 2 showing roots at -2 and 1

From the graph, $f(x) = 0$ at the points $(-2,0)$ and $(1,0)$.

Now rearrange

\[ x^2 + x - 2 = 0 \]

\[ x = 2 - x^2. \]

This is of the form $x = F(x)$, where $F(x) = 2 - x^2$.

Plotting $y = 2 - x^2$ gives:

Graph of y = 2 - x^2

But \[ y = 2 - x^{2} \qquad\text{and}\qquad x = 2 - x^{2} \]

So \[ y = x = 2 - x^{2} \quad\text{i.e.}\quad y = x = F(x) \]

The intersection of \[ y = x \quad\text{and}\quad y = 2 - x^{2} \]

gives the points \[ (-2,\,0) \quad\text{and}\quad (1,\,0). \]

We also have the line $y = x$. Fixed points satisfy

\[ y = x = 2 - x^2. \]

The intersection of $y = x$ and $y = 2 - x^2$ gives the points $(-2,-2)$ and $(1,1)$, which are the same x values as the roots of $f(x) = 0$.

Intersection of y = x and y = 2 - x^2

Comparison with graph of f(x) = x^2 + x - 2

An iterative sequence for $x = 2 - x^2$ would be of the form

\[ x_{n+1} = 2 - x_n^2. \]

For fixed points, $x_n = F(x_n)$, so

\[ x = 2 - x^2. \]

Solving

\[ x^2 + x - 2 = 0 \]

\[ (x+2)(x-1) = 0 \quad \Rightarrow \quad x = -2,\; x = 1. \]

These are the intersections found above.

So, if an equation $f(x) = 0$ can be rearranged to the form $x = F(x)$, finding any fixed points of the iterative sequence \[ x_{n+1} = F(x_n) \] may lead to solutions for $f(x) = 0$.

Example

Given that $x^3 - 4x - 5 = 0$ can be written as

\[ x = (4x + 5)^{1/3}, \]

and using a starting value of $x_0 = 2$:

a) Write down a simple iterative formula $x_{n+1} = F(x_n)$.
b) Find, correct to 4 d.p., a root between 1 and 3.

\[ x = (4x + 5)^{1/3} \quad \Rightarrow \quad x_{n+1} = (4x_n + 5)^{1/3}. \]

$Table of iterates for x_{n+1} = (4x_n + 5)^{1/3}$

The equation $x^3 - 4x - 5 = 0$ has a root

\[ x \approx 2.4567 \quad (4\text{ d.p.}) \]

Below is a graph showing the same iterative formula, this time with a starting value of $x_0 = -4$.

Graphical iteration with starting value x0 = -4

Convergence of iteration to the same root

Again, the system converges at $x \approx 2.4567$ (4 d.p.).

First order process

If rearranging an equation $f(x)=0$ to the form $x = F(x)$ leads to $x = a$ as a solution for the iterative sequence \[ x_{n+1} = F(x_n), \] then $f(a) = 0$.

Each iterate differs from $a$ by an error $e_n$, so

\[ x_n = a + e_n. \]

Then

\[ x_{n+1} = F(x_n) \quad \Rightarrow \quad a + e_{n+1} = F(a + e_n). \]

Using Taylor’s series about $x = a$:

\[ F(a + e_n) = F(a) + e_n F'(a) + \frac{e_n^2}{2}F''(a) + \cdots \]

Since $a$ is a fixed point, $F(a) = a$, so

\[ a + e_{n+1} = a + e_n F'(a) + \frac{e_n^2}{2}F''(a) + \cdots \]

\[ e_{n+1} = e_n F'(a) + \frac{e_n^2}{2}F''(a) + \cdots \]

For convergence, we require

\[ |F'(a)| \lt 1. \]

If $F'(a)$ is a constant and dominates the higher-order terms, this is called a first order process.

To estimate $F'(a)$ from consecutive iterates, note that for small errors

\[ \frac{e_{n+1}}{e_n} \approx F'(a). \]

\[ F'(a) = \frac{x_{n+1} - x_n}{\,x_n - x_{n+1}\,} \] \[ = \frac{e_n F'(a) - e_n}{\,e_n - \dfrac{e_n}{F'(a)}\,} \] \[ = \frac{F'(a)\,\big(F'(a)-1\big)} {\;F'(a)-1\;} \]

Since $e_n = x_n - a$, eliminating $a$ using three consecutive iterates gives an approximate value for $F'(a)$.

Second order process

If, in the Taylor expansion,

\[ F(a + e_n) = F(a) + e_n F'(a) + \frac{e_n^2}{2}F''(a) + \cdots, \]

we have $F'(a) = 0$, then

\[ e_{n+1} \approx \frac{e_n^2}{2}F''(a). \]

Here $F''(a)$ is a constant, and the error is proportional to $e_n^2$. This is called a second order process.

Rule of false position

The rule of false position is used to find approximate roots of the equation $f(x) = 0$.

Take two points on the graph on either side of the x-axis. Let $A(a, f(a))$ be a fixed point and $P_0(x_0, f(x_0))$ be a varying point.

An iterative equation can then be formed by taking the x-intercept of the secant line through $A$ and $P_n$:

\[ x_{n+1} = a - f(a)\, \frac{\,a - x_n\,}{\,f(a) - f(x_n)\,} \]

Example

Use the rule of false position to solve the equation

\[ x^4 - 2x = 0,\quad x > 0 \]

to two decimal places.

Let $f(x) = x^4 - 2x$.

\[ f(1) = 1 - 2 = -1 \quad \Rightarrow \quad (1, -1) \]

\[ f(2) = 16 - 4 = 12 \quad \Rightarrow \quad (2, 12). \]

\[ x_{n+1} = 2 - 12\left( \frac{\,2 - x_n\,}{\,12 - f(x_n)\,} \right) \] \[ = 2 - 12\left( \frac{\,2 - x_n\,}{\,12 - x_n^{4} + 2x_n\,} \right) \]

Take $A(2, 12)$ and $P_0(1, -1)$. Using the false position formula with $a = 2$ and $x_0 = 1$, generates iterates:

Starting with x₀ = 1 and f(x₀) = -1

\[ x_{1} = a - f(a)\, \frac{\,a - x_0\,}{\,f(a) - f(x_0)\,} \]

\[ x_{1} = 2 - 12\left(\frac{2 - 1}{12 - (-1)}\right) \] \[ = 2 - \frac{12}{13} \] \[ = 1.0769231 \]

\[ x_{2} = 2 - 12\left( \frac{\,2 - x_{1}\,}{\,12 - x_{1}^{4} + 2x_{1}\,} \right) \] \[ = 2 - 12\left( \frac{\,2 - 1.0769231\,}{\,12 - (1.0769231)^{4} + 2(1.0769231)\,} \right) \] \[ = 1.13521 \]

Continuing, we obtain

\[ x \approx 1.26 \quad (2\text{ d.p.}) \]

Convergence of false position method

Graphical illustration of false position method

Newton Raphson Iteration

The Newton–Raphson iteration for solving $f(x) = 0$ is

\[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}. \]