4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I kinda suspected that would be the case... I tried searching the web to see if there was a global convergence strategy for general fixed point iterations and found no papers on the topic. I suppose the only thing I can do (if possible) is obtain a different $f$ for the same equation such that we get a contraction. $\endgroup$ – Paul May 6 '13 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.