I have the following implicit equation

$$ x= f(x) $$

which I solve by starting with some value for $x$, then setting $x$ to the new value $f(x)$ and so forth until convergence.

How is that method called? What are its convergence properties, what are caveats one should be aware of, especially wrt the convexity of $f$? In my case $f$ is infinitely derivable.

  • $\begingroup$ This is called fixed point iteration. You'll find there have been a number of Questions at Math.SE about its convergence properties, esp. for smooth (differentiable) $f$. $\endgroup$ – hardmath Mar 15 '14 at 17:47
  • $\begingroup$ AFAIK, this method is not really used in numerical analysis, because its convergence is rather slow. One usually goes for the Newton method, which requires a lot more assumptions on $f$ (namely, differentiability and some control over derivatives), but converges much faster. $\endgroup$ – Giuseppe Negro Mar 15 '14 at 17:56
  • 1
    $\begingroup$ @GiuseppeNegro: Newton's method for root-finding $f(x)=0$ is a fixed point iteration for $x = x - f(x)/f'(x)$. $\endgroup$ – hardmath Mar 15 '14 at 18:05

It is called the fixed point method. There is a whole theory, called Fixed Point Theory, part of an nonlinear analysis, but it's results are applied in many other fields such as numerical analysis (your question is about that I suppose).

The most known result about this theory is called Banach's contraction principle, and states: In a complete space, for a contractive mapping, there exist a unique fixed point.

So your method is convergent if the space you're working in is complete and if the function is contractive.


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.