Numerical Methods with Programming

Section 8.1 Classification of fixed points

A fixed point of a function \(g\) is a number \(x^*\) such that \(g(x^*)=x^*\text{.}\) This is the same as a root of \(g(x)-x=0\) but we will see that writing an equation with \(x\) on the right provides a new approach to solving it.

The process of iterating some function \(g\) consists of the following: start from some initial value \(x_0\text{,}\) let \(x_1=g(x_0)\text{,}\) \(x_2 = g(x_1)\text{,}\) and generally \(x_{n+1} = g(x_n)\text{.}\) If the sequence \(x_n\) has a limit \(x^* \text{,}\) and \(g\) is a continuous function, it follows that \(g(x^*)=x^*\text{.}\)

However, can we expect the iteration to converge to a fixed point \(x^* \text{?}\) The answer depends on the value of \(g'(x^*)\text{.}\) Indeed, when \(x\approx x^*\text{,}\) the difference \(g(x)-x^*\) is approximately \(g'(x^*)(x-x^*)\) because the graph of a differential function is close to its tangent line. When \(|g'(x^*)|\lt 1\text{,}\) the distance to fixed point is decreasing but if \(|g'(x^*)| > 1\) it is increasing. This leads us to introduce the following concept.

Classification of fixed points. A fixed point \(x^*\) is called

• repelling if \(|g'(x^*)| > 1\)
• attracting if \(|g'(x^*)| \lt 1\)
• super-attracting if \(g'(x^*) = 0 \) (a special case of attracting fixed points)
• neutral if \(|g'(x^*)| = 1 \)

According to the above, iteration of \(g\) may converge to an attracting point but will not converge to a repelling one. The neutral points are a borderline case: some of them are limits of iterative process, some are not.