Stability of a fixed point

Iteration of functions: Finding zeros via iterations

Stability of a fixed point

We have already seen an example of iteration of a function where fixed points were both attractive and repulsive. It would be nice if we could already know in advance whether the behaviour at the start of an iteration of a function near a fixed point is attractive or repulsive. The following statement makes a statement about this.

Suppose the function \(f\) has a continuous derivative. When iterating the function \(f\) with fixed point \(s\), the following is true:

If \(|f'(s)|<1\), then the fixed point \(s\) is attractive.

If \(|f'(s)|>1\), then the fixed point \(s\) is repulsive.

For the math enthusiast, we prove the first statement.

Suppose that \(s\) is a fixed point of \(f\) with \(|f'(s)|<1\). Because of the continuity of the derivative function, there is a number \(M<1\) and a sufficiently small interval \(I\) around \(s\) such that \(f'(x)|<M<1\) for all points in \(I\). We choose a starting point \(x_0\) in \(I\). For each \(x_k\) we can apply \ Taylor's theorem about \(s\): there exists a number \(\xi\) between \(s\) and \(x_k\) such that \[f(x_k)=f(s)+f'((\xi)(x_k-s)\] Thus: \[x_{k+1}-s=f'((\xi)(x_k-s)\] \(\xi\) When \(x_k\) is in \(I\), then \(\xi\) is also per definition within \(I\) and we have \[\frac{|x_{k+1}-s|}{|x_k-s|}=f'(\xi)<M<1\]. But then we also have: \[\frac{|x_{k+1}-s|}{|x_k-s|}=f'(\xi)<M<1\] For arbitrary \(x_n\) it follows that \[\frac{|x_{n}-s|}{|x_0-s|}=\frac{|x_{n}-s|}{|x_{n-1}-s|}\cdot \frac{|x_{n-1}-s|}{|x_{n-2}-s|}\cdots \frac{|x_1-s|}{|x_0-s|}<M^n\] But this means that \[|x_n-s| \rightarrow 0,\mathrm{\;if\;}n\rightarrow \infty\tiny.\] In other words, the fixed point is attractive under the given condition.

The proof of the second statement in the theorem is similar.

We consider the polynomial \[x^2-5x+6=(x-2)(x-3)\] with zeros \(2\) and \(3\).

We can rewrite the equation \(x^2-5x+6=0\) as \(x=x^2-4x+6\) and thus look at the iteration of the function \[f_1(x)=x^2-4x+6\] Then \(f_1'(2)=0<1\), so the fixed point \(2\) is attractive, but the starting value must be chosen between \(1\) and \(3\) for convergence. In this case, \(f_1'(3)=2>1\) and thus is \(3\) a repulsive fixed point.

We can also rewrite the equation \(x^2-5x+6=0\) as \(x=\frac{1}{5}x^2+\frac{6}{5}\) and thus look at the iteration of the function \[f_2(x)=\frac{1}{5}x^2+\frac{6}{5}\] Then \(f_2'(2)=\frac{4}{5}<1\) and so the fixed point \(2\) is again attractive, albeit with a slower convergence behaviour than with the previous iteration of a function. Again, \(f_2'(3)=\frac{6}{5}>1\) and \(3\) is a repulsive cover point.

As a third alternative, we may rewrite the equation \(x^2-5x+6=0\) as \(x=\frac{5x-6}{x}=5-\frac{6}{x}\) and thus consider the iteration of the function \[f_3(x)=5-\frac{6}{x}\] Then \(f_3'(2)=\frac{3}{2}\), so the fixed point \(2\) is repulsive. In this case \(f_3'(3)=\frac{2}{3}<1\) and \(3\) is an attractive fixed point

We notice that the behaviour of the iteration near the fixed points depends on the chosen function.

But there are many more functions to think of for iteration. For a random number \(k\) we can rewrite the equation \(x^2-5x+6=0\) as \(x+k\cdot(x^2-5x+6) = x\) and thus consider the iteration of the function \[f(x)=x+k\cdot(x^2-5x+6)\] for different values of \(k\). Then we have \(f'(x)=1+2kx-5k\). For optimal convergence in the fixed points, we prefer a choice of \(k\) such that \(f'(s)=0\). When we are interested in the fixed point \(2\), then the best choice is \(k=1\) and we are back to the function \(f_1\). In case of fixed point \(3\), the best choice is \(k=-1\). Then the iteration function is equal to \(f_4(x)=-x^2+6x-6\), but then you have to take a starting value between \(2\) and \(4\) for convergence to the fixed point \(3\).