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?

  • $\begingroup$ You need some conditions on $x_1$, $y_1$. $\endgroup$ – Martin Argerami May 5 '16 at 17:15
  • $\begingroup$ 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? $\endgroup$ – jazzinsilhouette May 5 '16 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.$

  • $\begingroup$ 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? $\endgroup$ – jazzinsilhouette May 5 '16 at 19:22
  • $\begingroup$ 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. $\endgroup$ – Martin Argerami May 5 '16 at 19:49
  • $\begingroup$ 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$. $\endgroup$ – jazzinsilhouette May 5 '16 at 20:13
  • $\begingroup$ (Assuming the inverse exists of course.) $\endgroup$ – jazzinsilhouette May 5 '16 at 20:20

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.