# Convergence of fixed-point iteration for convex function

Let $f:[0,1]\to[0,1]$ be a smooth, convex (downward) function satisfying $$f(0)=f(1)=1,\quad \lim_{x\to 0}f'(x)=-\infty,\quad \lim_{x\to 1}f'(x)=+\infty.$$

I am confident to be able to argue that $f$ has exactly two fixed points in $[0,1]$ (one of them being $1$, of course.)

I would like to show that for any starting value $x\in (0,1)$, the sequence of function iterates $f(x), f(f(x)),\ldots$ converges to the fixed point which is not $1$.

I know from the convexity of $f$ that there exist $0<x_-<x_+<1$ such that $f'(x_\pm)=\pm1$ and that $f$ on the interval $(x_-,x_+)$ is non-expansive.

I was thinking to try and argue that for any starting value the iterates $f^i(x)$ would eventually lie in $(x_-,x_+)$ and to then apply Banach's fixed point theorem.

My questions are:

• Is it clear that the fixed point lies in the interval $(x_-,x_+)$? (I doubt it)
• In order to apply Banach's fixed-point theorem, would I have to show that $f((x_-,x_+))\subset (x_-,x_+)$?
• Is there a different approach that would guarantee convergence of the function iterates without checking additional conditions?

Thank you.

Edit:

Thanks to the efforts of richard and froggie it now seems that convergence of the iterates cannot be guaranteed under the conditions specified above.

I would therefore like to add the following assumptions: ($p$ denotes the fixed point which is not $1$)

• $-1<f'(p)<1$.
• If $c=\min_x f(x)$, then $-1<f'(c)<1$.

I think that with these additional assumptions it should be possible to prove convergence of the function iterates from every starting point.

• Do functions with these properties exist? – user108903 Dec 16 '12 at 15:30
• Yes, the maybe easiest example would be $f(x)=2-\sqrt{x}-\sqrt{1-x}$. – Eckhard Dec 16 '12 at 15:35
• Oops, I misread your question. Thanks for the example. – user108903 Dec 16 '12 at 15:41
• Do you assume that $f$ is differentiable on $(0,1)$? – 23rd Dec 16 '12 at 15:52
• Yes. In fact, I'm happy to assume the existence of as many derivatives as necessary. I added smoothness to the original question. – Eckhard Dec 16 '12 at 15:57

## 1 Answer

Since $f(1)=1$ and $\lim_{x\to 1}f'(x)=+\infty$, it is easy to see that there exists $a\in(0,1)$, such that $f(a)<a$. Define $g(x)=f(x)-x$ on $[0,1]$. Since $g(0)=1>0$ and $g(a)<0$, there exists $p\in[0,a]$, such that $g(p)=0$, i.e. $f(p)=p$. Since $g(p)=g(1)=0$ and $g$ is convex on $[p,1]$, either $g\equiv 0$ on $[p,1]$ or $g(x)<0$ on $(p,1)$. The former case cannot happen, because $\lim_{x\to 1}g'(x)=+\infty$. Therefore, $f$ has a unique fixed point $p$ in $[0,1)$.

Unfortunately, it could happen that $f'(p)<-1$. In this situation, the iteration of $f$ cannot converge to $p$.

When $-1<f'(p)<1$, note that the iteration of $f$ on $(p-\delta,p+\delta)$ converges to $p$ for some $\delta>0$. Then we can define $I=(l,r)$ to be the maximal interval containing $p$ such that the iteration of $f$ on $I$ converges to $p$. By definition, $f(I)\subset I$. Since $I$ is maximal, $f(l),f(r)\notin I$, i.e. $f(l),f(r)\in\{l,r\}$. Then there are two cases: $l=0$ and $r=1$ or $f(l)=r$ and $f(r)=l$. For the latter case, by the maximality of $I$, we can conclude that $f'(r)< 0$, and hence $f'(p)<0$. Moreover, due to $f(I)\subset I$, we know that $f'(l)f'(r)\ge 1$.

• Thank you for your answer, Richard. Would the condition $-1<f'(p)<1$ be sufficient for the iteration of $f$ to converge to $p$ for any starting value? In the notation of my original question this would mean $x_-<p<x_+$. – Eckhard Dec 16 '12 at 16:32
• @Eckhard: I have updated my answer for $-1<f'(p)<1$. I avoid to use your notations $x_\pm$, because the point $x$ for $f'(x)=\pm 1$ may not be unique. – 23rd Dec 16 '12 at 17:20
• Thanks again. I don't quite see yet why the maximal interval $I$ must be open, but otherwise the argument seems compelling. – Eckhard Dec 16 '12 at 17:28
• @Eckhard: It is because if $f^n(x)\to p$, then there exists a neighborhood of $x$ converging to $p$ under the iteration of $f$. – 23rd Dec 16 '12 at 17:33
• @Eckhard: I agree with you. Moreover, I think only $f'(c)\ge -1$ is sufficient to exclude the situation $f(l)=r,f(r)=l$. The reason is as follows. Letting $f(x)=c$, then $f'(x)=0$ and $f$ is decreasing on $[0,x]$. Therefore, $f'(x)>f'(r)\Rightarrow r\le x\Rightarrow l=f(r)\ge f(x)=c\Rightarrow f'(c)\le f'(l)<-1$. – 23rd Dec 17 '12 at 8:15