Iteration of functions: Iteration of functions and fixed points
Iteration of a function and fixed points
Iteration of a function 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\).
Difference equation 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\).
Fixed point 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.
