Iteration of a function and fixed points

Iteration of functions: Iteration of functions and fixed points

Iteration of a function and fixed points

For a given 'neat' function $f$ and number $x_0$ , consider the rule

$x_{k+1} = f(x_k),\quad k = 0, 1, 2, 3, \ldots\tiny.$ According to this rule, a sequence $x_0, x_1, x_2, x_3, \ldots$ is constructed; we say that this sequence arises from iteration of a function, with the function $f$ , and starting value $x_0$ .

The sequence $x_0, x_1, x_2, x_3 \ldots$ is also denoted by

$x_0, f(x_0), f(f(x_0)), f(f(f(x_0))), \ldots$ Tnen we write $f^n(x_0)=x_n$ where $f^n$ indicates that we $f$ apply $n$ times. Such repeated application of a function naturally requires that the image of the function $f$ be within the domain of $f$ ; this is part of the 'neatness' of the $f$ function. A relation described as in equation $x_{n+1}=f(x_n)$ is called a first-order difference equation, because $x_{n+1}$ only depends on its first predecessor $x_n$ .

Of great importance are possible points for which $x_{n+1}=x_n$ . Such values can arise if the function $f$ has an argument, say $s$ , for which $f(s)=s$ . Such a point $s$ with a given function $f$ is called a fixed point, or also stationary point of the function $f$ . Of interest are rows of $x_0, x_1, x_2,\ldots$ for which $x_n$ gets arbitrarily close to such a fixed point for sufficiently large $n$ , that is, rows that converge to a fixed point. We then speak of an attractive fixed point. Conversely, a fixed point is said to be repulsive if a sequence with starting value $x_0$ close to the fixed point, but not equal to it, yields a sequence $x_0, x_1, x_2,\ldots$ whose values move further and further away from the fixed point.

Consider the iteration

$f(x)=x-\frac{1}{3}(x^2-2),\quad \mathrm{with\;} x_0=2$ The first steps in the iteration yield the following results (exactly and rounded to 6 digits) in the table below:

$\begin{array} {c|c|c} n & x_n\;(\mathrm{exact}) & x_n\;(\mathrm{rounded})\\ \hline 0 & 2 & 2.00000 \\[3pt]1 & \frac{4}{3} & 1.33333 \\[3pt] 2 & \frac{38}{27} & 1.40741 \\[3pt] 3 & \frac{3092}{2187} & 1.41381 \\[3pt] 4 & \frac{20\,292\,086}{14\,348\,907} & 1.41419 \\[3pt] 5 & \frac{873\,521\,274\,507\,908}{617\,673\,396\,283\,947} & 1.41421 \end{array}$ Hereafter the 5 decimals do not change anymore and that could therefore be an approximation of a fixed point of this function. In this case it is easy to see that this is so because $x=\sqrt{2}$ is indeed a fixed point. So it seems that iteration of this function for initial value $x_0=2$ converges to this fixed point.

It is also clear that the function $f$ has a fixed point in $-\sqrt{2}$ , but if you start with $x_0=-2$ , for example, assuming that you then converge to the fixed point, you will be disappointed. The results are shown in the table below.

$\begin{array} {c|c|c} n & x_n\;(\mathrm{exact}) & x_n\;(\mathrm{rounded})\\ \hline 0 & -2 & -2.00000 \\[3pt]1 & -\frac{8}{3} & -2.66667 \\[3pt] 2 & -\frac{118}{27} & -4.37037 \\[3pt] 3 & -\frac{22\,024}{2187} & -10.0704 \\[3pt] 4 & -\frac{619\,990\,102}{14\,348\,907} & -43.2082 \\[3pt] 5 & -\frac{410\,664\,274\,485\,257\,336\,648}{617\,673\,396\,283\,947} & -664.857 \end{array}$ Even if you start at $x_0=-1$ it doesn't get any better:

$\begin{array} {c|c|c} n & x_n\;(\mathrm{rounded})\\ \hline 0 & -1.00000 \\[3pt]1 & -0.666667 \\[3pt] 2 & -0.148148 \\[3pt] 3 & 0.511203 \\[3pt] 4 & 1.09076 \\[3pt] 5 & 1.36084 \\[3pt] 6 & 1.41021 \\[3pt] 7 & 1.41398 \\[3pt] 8 & 1.41020 \\[3pt] 9 & 1.41021 \end{array}$ We now come back to an approximation of $\sqrt{2}$ . No matter how close you start to $-\sqrt{2}$ , the iterands get further and further away from the deck point. In other words, $-\sqrt{2}$ is a repulsive fixed point.