# What can we say about the convergence of these fixed-point iterations for $\phi:\mathbb{R}\to \mathbb{R}$

Let $\phi: \mathbb{R}\to \mathbb{R} \in C^2(\mathbb{R})$ and let $x^{*}$ be a fixed-point of this function. Further assume that $|\phi'(x^{*})| \neq 1$. We define two sequences

\begin{align} &1.) &x_{k+1} &:= \phi(x_k)\\ &2.) &y_{k+1} &:= \phi^{-1}(y_k)\\ \end{align}

Prove that at least one of these converges locally to $x^{*}$.

I was trying to solve this by considering two separate cases. First assume that $|\phi'(x^{*})| < 1$. We can then find an $\epsilon > 0$, such that

\begin{align} L := \max_{x \in I} |\phi'(x)|\end{align} is $< 1$,

where $I := [x^{*} - \epsilon, x^{*} + \epsilon]$. It follows that $\phi$ is lipschitz on $I$. Further we get $\phi(I) \subseteq I$, since

\begin{align}|\phi(x) - x^{*}| = |\phi(x) - \phi(x^{*})| \leq L|x - x^{*}| < \epsilon\end{align}.

Now, according to the Banach fixed-point theorem the sequence defined by $1.)$ converges for all $x_0 \in I$ to $x^{*}$. But what about the second sequence? Will it converge too? I don't know!

In the case that $|\phi'(x^{*})| > 1$, I think we can use the same argument as above, but this time for the second sequence, since

\begin{align}|(\phi^{-1})'(x^{*})| = \left|\frac{1}{\phi'(\phi^{-1}(x^{*}))}\right| = \left|\frac{1}{\phi'(x^{*})}\right| < 1\end{align}.

But again, I'm at a loss about what to say of the convergence of the first sequence. What is a good way to tackle this problem?

• You need some conditions on $x_1$, $y_1$. – Martin Argerami May 5 '16 at 17:15
• Yes, I guess there probably need to be some conditions on the start values. But can we maybe show in an easy way that without these additional constraints the sequences will diverge? – jazzinsilhouette May 5 '16 at 17:37

## 1 Answer

As stated, the statement is not true, even with the unspoken requirement that $\phi$ is invertible. Let $$\phi(x)=1-x^3, \ \ \ \ \ \ \ \ \ \ x_1=y_1=1.$$

Then $$x_2=\phi(x_1)=1-1^2=0$$ $$x_3=\phi(x_2)=1-0^2=1,$$ and so the sequence $\{x_k\}$ alternates between $0$ and $1$.

Similarly, from $\phi(1)=0$ and $\phi(0)=1$ we get $\phi^{-1}(1)=0$ and $\phi^{-1}(0)=1$, so the sequence $\{y_k\}$ will also alternate between $0$ and $1$.

And we can take $$x^*= \frac1{2^{1/3}}\,\left( \displaystyle1+\frac{\sqrt{93}}{9}\right)^{1/3}-\left(\frac2{3 (9+\sqrt{93})})\right)^{1/3}\approx0.6823278$$ which is a fixed point: $1-(x^*)^3=x^*$ (I'm trusting here that Wolfram Alpha gave me the right solution, but in any case there is a fixed point in the area, as the graph of $1-x^3$ has to cross the line $y=x$).

One can also check that $|\phi'(x^*)|=|-3(x^*)^2|\approx 1.39671\ne1.$

• Thanks for you answer. If I understand you correctly you're referring to the second part of my "proof", where I assumed that $|\phi'(x^*)| > 1$ However, I think that taking $x_1 = 1$ and showing that neither sequence converges is not enough, since $\phi$ is not a contraction mapping; $x_1$ must be in a small enough neighbourhood of $x^{*}$. Or what am I missing here? – jazzinsilhouette May 5 '16 at 19:22
• But you never said that $\phi$ has to be a contraction! Nor that $x_1$ and $y_1$ had to be close to $x^*$. If you restrict your problem to $x_1$ and $y_1$ close enough to $x^*$, then the argument works as you mention in the first part of your argument. In that case, I don't understand what your question is. – Martin Argerami May 5 '16 at 19:49
• I'm sorry that my question isn't clear enough. $\phi$ need not be a contraction, but as far as I understand your counterexample only works because $x_1$ and $x^{*}$ are too far apart. The exercise asked to show that at least one of the sequences above converge locally to the fixed-point. In my argument I was using the fact we can always find a neighbourhood of $x^{*}$ in which $\phi$ is a contraction (if $|\phi'(x^{*})| < 1$). My question is, whether we maybe can say anything about the behaviour of sequence $2$ in the case that $|\phi'(x^{*})| < 1$. – jazzinsilhouette May 5 '16 at 20:13
• (Assuming the inverse exists of course.) – jazzinsilhouette May 5 '16 at 20:20