# fixed-point iteration

Are there functions $f$ of one real variable $x\in X$ that are not contracting maps on the set $X$ but for which, given the starting point $x_0$, the fixed-point iteration $x_n=f(x_{n-1})$, for $n=1,2,3,\dots$ will still converge to a fixed-point?

-
Not if the fixed point, call it $a,$ so $f(a) = a,$ has also $|f'(a)| > 1.$ –  Will Jagy Jan 14 '13 at 3:56
So at some point we have: if the fixed-point iteration $x_n=f(x_{n−1})$ converges in the vicinity of the fixed point $a$, then $f$ is a contracting map in a neighbourhood of $a$? –  pluton Jan 14 '13 at 4:06
Consider $f(x)=x^2$ on the set $[0,1]$: it is not a contraction, but the iterates do converge to a fixed point. –  user53153 Jan 14 '13 at 4:22
@5PM I was commenting, because pluton had added that question in a comment right before yours. –  JSchlather Jan 14 '13 at 5:06
@Jacob Oh, I see. Well, how about $f=\chi_{\mathbb Q}$ then. –  user53153 Jan 14 '13 at 5:10
Consider the function $f=\chi_{\mathbb Q}$ (i.e., $f(x)=1$ if $x$ is rational and $0$ otherwise). It is nowhere continuous, let alone contracting. On the other hand, $f(f(x))=1$ for all $x$.
This is a quite problematic function but the answer is helpful. Then, for which class of functions the most basic fixed-point theorem ($f$ continuous, $f(X)\subset X$ and $|f'|<1$ on $X$) provides necessary and sufficient conditions instead of the usual sufficient conditions only? –  pluton Jan 14 '13 at 14:15
@pluton Seeing that such a class must exclude the quadratic polynomial $x\mapsto x^2$, I'm not optimistic that you'll find anything more interesting than degree $1$ polynomials. –  user53153 Jan 14 '13 at 14:44