Is it possible to ensure global convergence of a fixed point iteration?

Question

Suppose I have a fixed point iteration of the form

$$x_{n+1}=f(x_n).$$

Suppose further that after some initial testing, I found that it does not converge to an a priori known fixed point $x^*$. I recall from optimization class that often when the standard newton's method does not converge, one can implement a global convergence strategy to ensure convergence from any initial point (e.g. line search with backtracking). Does anything similar exist for general fixed point iterations? Is there strategy that I can implement to ensure that the sequence of iterations does converge?

Answer 1

There is nothing that can guarantee converge of such a fixed point iteration, but there are criteria that if you can show that they hold, the iteration will converge. In particular, the fixed point iteration will converge if it is a contraction. I am quite sure, however, that it is not very difficult to find example of functions $f(x)$ where even with damping the iteration will not converge.

Other than that, if all you care about is finding a fixed point of $f$, then you can of course reformulate the problem. For example, you can find roots of the function $g(x)=x-f(x)$ (e.g., using Newton's method) or minima of $h(x)=\|x-f(x)\|^2$.