Let $f(x)$ be a strictly decreasing function on $\mathbb{R}$ with $|f(x)-f(y)|<|x-y|$ whenever $x\neq y$. Set $x_{n+1}=f(x_n)$. Show that the sequence $\{x_n\}$ converges to the root of $x=f(x)$.

Note that the condition is weaker than what is required in the contracting mapping principle.


Firstly, here's a picture of what's going on:

enter image description here

Formally, we start by observing that because $f$ is strictly decreasing and continuous, $f(x) = x$ must have a unique solution. Call this fixed point $r$; then defining \begin{align*} A &= \{x \in \mathbb{R} : x < r \} \\ B &= \{r\} \\ C &= \{x \in \mathbb{R} : x > r \}. \end{align*} we have \begin{align*} f(x) &> x \text{ for all } x \in A \\ f(r) &= r \\ f(x) &< x \text{ for all } x \in C. \end{align*}

We can say more:

  • $\boldsymbol{f}$ maps $\boldsymbol{A}$ into $\boldsymbol{C}$ and vice versa: For $a \in A$, $f(a) > a$, so by decreasing $f(f(a)) < f(a)$. So $f(a) \in C$. Similarly for $C$.

  • $\boldsymbol{f(f(x)) > x}$ on $\boldsymbol{A}$ and $\boldsymbol{f(f(x)) < x}$ on $\boldsymbol{C}$: For $a \in A$, $|f(f(a)) - f(a)| < |f(a) - a|$. So $f(f(a))$ is closer to $f(a)$ than $a$ is, and since $a, f(f(a)) \in A$ and $f(a) \in C$, "closer to $f(a)$" implies larger.

So now fix any $x_1 \in \mathbb{R}$. We may assume that $x_1 \in A$. By the above facts, it follows that $x_1, x_3, x_5, \ldots$ is an increasing sequence in $A$, and $x_2, x_4, x_6, \ldots$ is a decreasing sequence in $C$. It follows that both of them converge, say to $x$ and to $y$ respectively, where $x \le r \le y$. But by continuity, $f(x_{2k})$ must converge to the same thing as $f(x_{2k+1})$, so $x = y = r$, and therefore $x_n \to r$.

  • $\begingroup$ I rehashed my answer to remove a lot of unnecessary details and clarify the main point. $\endgroup$ – 6005 Sep 7 '16 at 10:01
  • 1
    $\begingroup$ Thanks! Great answer, and the intuition too. It's called a cobweb plot, as I recall. $\endgroup$ – Zhang Edison Sep 7 '16 at 10:08
  • $\begingroup$ @ZhangEdison yeah kinda reminded me of the microeco lesson I had. $\endgroup$ – Vim Sep 9 '16 at 1:02

Uniqueness. If $x$ and $y$ are distinct fixed points then $0<|x-y|=|f(x)-f(y)|<|x-y|$. Contradiction.

Existence. $|f(x)-f(y)|<|x-y|$ implies that $f$ is continuous. If $f$ has not fixed point then i) $f(x)>x$ for all $x$ or ii) $f(x)<x$ for all $x$. If i) holds then for $x_0\in \mathbb{R}$, $x_1=f(x_0)>x_0$ and since $f$ is decreasing $x_2=f(x_1)<f(x_0)=x_1$. Hence if $h(x)=f(x)-x$ we have that $h(x_0)>0$ and $h(x_1)<0$ and by the IVT, we have a root of $h(x)=0$, i.e. a fixed point for $f$. The case ii) is similar.

Convergence of iterates. Let $z$ be the fixed point. And let $x_0\in\mathbb{R}$, then $$|x_n-z|=|f(x_{n-1})-z|<|x_{n-1}-z|<\dots<|x_{0}-z|$$ which means that $f$ send the compact $K=[z-|z-x_0|,z+|z-x_0|]$ in itself. Moreover $d_n=|x_n-z|$ is strictly decreasing, and admits a limit $r\geq 0$. Let $x_{n_k}$ be a subsequence which converges to some $y\in K$. If $y\not=z$ then $$r=|y-z|=\lim_{k\to\infty} d_{n_k}=\lim_{k\to\infty} d_{n_{k}+1}=\lim_{k\to\infty}|f(x_{n_k})-z| =|f(y)-z|=|f(y)-f(z)|<|y-z|$$ which is a contradiction. Therefore any convergent subsequence of $\{x_n\}_n$ has limit $z$, which, along with the compactness of $K$, implies that $\{x_n\}_n$ converges to $z$.

P.S. Once we have established the existence of the fixed point the decreasing hypothesis is not needed anymore.

Note:$f(x)=x-\arctan(x)+\pi/2$ is a strictly increasing function which is a weak contraction in $\mathbb{R}$, but it has no fixed points.

  • 1
    $\begingroup$ +1: for a great use of compactness, and for the note that the existence of a fixed point is sufficient (decreasing is not needed). $\endgroup$ – 6005 Sep 7 '16 at 10:14

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.