4
$\begingroup$

Prove the Contraction Mapping Theorem.

Let $(X,d)$ be a complete metric space and $g : X \rightarrow X$ be a map such that $\forall x,y \in X, d(g(x), g(y)) \le \lambda d(x,y)$ for some $0<\lambda < 1$. Then $g$ has a unique fixed point $x^* \in X $, and it attracts everything, i.e. for any $x_0 \in X$ , the sequence of iterates $x_0, g(x_0), g(g(x_0))$, ... converges to the fixed point $x^* \in X$.

The hint I am given are for existence and convergence - prove that the sequence is Cauchy. For uniqueness, choose two fixed points of $g$ and apply the map to both.

Still a bit do not know how to proceed after looking at the hint. Could anyone help me based on those hints?

$\endgroup$
  • 2
    $\begingroup$ Hint: $d(x_{n+1},x_n)=d(g(x_n),x_n)=d(g(g(x_{n-1})),g(x_{n-1}))\le \lambda d(g(x_{n-1}),x_{n-1})=d(x_n,x_{n-1})$ $\endgroup$ – J.R. Feb 8 '14 at 19:17
  • $\begingroup$ @TooOldForMath: what are you trying to achieve here? $\endgroup$ – afsdf dfsaf Feb 8 '14 at 19:19
  • 1
    $\begingroup$ I am giving you a hint so you can solve it. This is how it goes. Repeating what I wrote gives you $d(x_{n+1},x_n)\le \lambda^n d(x_1,x_0)$. Now $\lambda$ is between $0$ and $1$, so what happens when $n\rightarrow\infty$...? $\endgroup$ – J.R. Feb 8 '14 at 19:26
  • $\begingroup$ why $\lambda d(g(x_{n-1}), x_{n-1}) = d(x_n, x_{n-1})$? $\endgroup$ – afsdf dfsaf Feb 8 '14 at 19:52
  • 1
    $\begingroup$ $d(x_{n+1},x_n)\le \lambda d(x_n,x_{n-1}) \le \lambda^2 d(x_{n-1},x_{n-2})\le\cdots\le \lambda^n d(x_1,x_0)$ $\endgroup$ – J.R. Feb 9 '14 at 0:13
2
$\begingroup$

From

$$d(x_{n+1},x_n)=d(g(g(x_{n-1})),g(x_{n-1}))\le \lambda d(g(x_{n-1}), x_{n-1})=d(x_n,x_{n-1})$$

we get after $n$ applications of that inequality

$$d(x_{n+1},x_n)\le \lambda d(x_n,x_{n-1}) \le \lambda^2 d(x_{n-1},x_{n-2}) \le \cdots\le \lambda^n d(x_1,x_0)\tag{1}$$

Now we want to show that $(x_n)_n$ is a Cauchy sequence. So let $\epsilon>0$.

We assume $x_1\not=x_0$ (otherwise $x_0$ is already a fixed point). Set $c=d(x_1,x_0)>0$.

Since $0<\lambda<1$, the sum $\sum_{n=0}^\infty \lambda^n$ converges (to $1/(1-\lambda)$). Therefore we can pick $N$ large enough such that

$$\sum_{k=n}^\infty \lambda^k<\frac{\epsilon}{c}$$

for all $n\ge N$.

Then for $m>n\ge N$ we have by the triangle inequality

$$d(x_m,x_n)\le \sum_{k=n}^{m-1} d(x_{k},x_{k+1})$$

Applying $(1)$ we obtain

$$d(x_m,x_n)\le c\sum_{k=n}^{m-1} \lambda^k\le c\sum_{k=n}^\infty \lambda^k<c\cdot\frac{\epsilon}{c}=\epsilon$$

So $(x_n)_n$ really is a Cauchy sequence. Since $(X,d)$ is complete, it converges to a limit $x\in X$.

By the equation $x_{n+1}=g(x_n)$, the limit satisfies $x=g(x)$, so it is a fixed point.

Uniqueness is trivial, let $y$ be another fixed point of $g$. Then

$$d(x,y)=d(g(x),g(y))\le \lambda d(x,y)$$

If now $x\not=y$, then $d(x,y)>0$, so we can divide by $d(x,y)$ to obtain $\lambda\ge 1$, a contradiction. Therefore, $x=y$.

$\endgroup$
  • $\begingroup$ "Therefore we can pick $N$ large enough such that $$\sum_{k=n}^\infty \lambda^k<\frac{\epsilon}{c}$$ for all $n\ge N$." For this part, do you backfill $$\frac{\epsilon}{c}$$ after going through the following: "Then for $m>n\ge N$ we have by the triangle inequality $$d(x_m,x_n)\le \sum_{k=n}^{m-1} d(x_{k},x_{k+1})$$ Applying $(1)$ we obtain $$d(x_m,x_n)\le c\sum_{k=n}^{m-1} \lambda^k\le c\sum_{k=n}^\infty \lambda^k<c\cdot\frac{\epsilon}{c}=\epsilon$$"? $\endgroup$ – afsdf dfsaf Feb 9 '14 at 17:18
  • $\begingroup$ Backfill? What are you talking about? This is a logically complete argument. $\endgroup$ – J.R. Feb 9 '14 at 17:25
  • $\begingroup$ I just mean whether we get to go through the following part: "Then for $m>n\ge N$ we have by the triangle inequality $$d(x_m,x_n)\le \sum_{k=n}^{m-1} d(x_{k},x_{k+1})$$ Applying $(1)$ we obtain $$d(x_m,x_n)\le c\sum_{k=n}^{m-1} \lambda^k\le c\sum_{k=n}^\infty \lambda^k<c\cdot\frac{\epsilon}{c}=\epsilon$$" before filling $$\frac{\epsilon}{c}$$ in the "Therefore we can pick $N$ large enough such that $$\sum_{k=n}^\infty \lambda^k<\frac{\epsilon}{c}$$ If not, how did you get $$\sum_{k=n}^\infty \lambda^k<\frac{\epsilon}{c}$$? $\endgroup$ – afsdf dfsaf Feb 9 '14 at 17:36
  • $\begingroup$ Please stop copying all this stuff in the comments. It makes it really unreadable. You are not "filling" $\epsilon/c$ whatever you mean by that. The logic is like this: $c$ is a constant defined as $d(x_1,x_0)$. It is fixed. Now I throw you an $\epsilon>0$ in the beginning. And now you notice, aha, the sum $\sum_{k=1}^\infty \lambda^k$ converges therefore sequence of truncated sums $\sum_{k=n}^\infty \lambda^k$ converges to $0$ for $n\rightarrow\infty$. So it will eventually be smaller than that given $\epsilon/c$. Let us say that the point when it becomes smaller is reached at $N$ $\endgroup$ – J.R. Feb 9 '14 at 17:42
  • $\begingroup$ $\sum_{k=n}^\infty \lambda^k <\epsilon/c$ for all $n$ bigger than $N$. $\endgroup$ – J.R. Feb 9 '14 at 17:43
0
$\begingroup$

One proviso: You do need that $X$ is non-empty in the statement.

To elaborate on the hints you have been given; To prove existance, pick $x_0 \in X$, and call (for convenience of writing) $g(x_0) = x_1, g(x_1) = x_2$ etcetera. Let $d(x_0,x_1) = d$. Then $d(x_1,x_2) \leq \lambda d$, and $d(x_2,x_3) \leq \lambda^2 d$...can you see how to extend this to show that the sequence is Cauchy?

For uniqueness, suppose $x$ and $y$ are both fixed points. What is $d(g(x),g(y))$?.

$\endgroup$
  • $\begingroup$ I don't think you do - if $x = y$ then both sides of the inequality are $0$, which is fine. $\endgroup$ – meta Feb 8 '14 at 19:37
  • $\begingroup$ Touche! (I'm used to strong inequalities being used, which isn't really different here, and didn't notice the difference.) $\endgroup$ – Jonathan Y. Feb 8 '14 at 19:39
  • $\begingroup$ @meta: After we got to $d(x_{n+1}, x_n) \le \lambda^n d(x_1, x_0)$, then assuming that $m > n$, $d(x_m, x_n) \le d(x_m, x_{m-1}) + d(x_{m-1}, x_{m-2}) + ... + d(x_{n+1}, x_{n})$ since each term of the right hand side is 0 ...so if we add up all the 0 terms, we get 0 on the right hand side. Therefore, $d(x_m, x_n)$ is 0. If this is right, then the question I have here is how do I guarantee that $x_{m-1} > x_n$? $\endgroup$ – afsdf dfsaf Feb 9 '14 at 3:04

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.