# 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$. Commented May 5, 2016 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? Commented May 5, 2016 at 17:37

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? Commented May 5, 2016 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. Commented May 5, 2016 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$. Commented May 5, 2016 at 20:13
• (Assuming the inverse exists of course.) Commented May 5, 2016 at 20:20