# Contraction mapping theorem

• Nov 28th 2010, 05:57 PM
kathrynmath
Contraction mapping theorem
0<c<1 and |f(x)-f(y)<c|c-y|
a) Show f is continuous on all of R
b)Pick some point y1 in R and construct the sequence (y1,f(y1),f(f(y1)),....)
In general if y_(n+1)=f(yn) show that the resulting sequence yn is a Cauchy sequence. hence we may let y=limyn
c)Prove that y is a fixed point of f and that is unique in this regard.
d) Finally prove that if x is any arbitrary point in R then the sequence (x,f(x),f(f(x)),...) converges to y defined in (b).

a) want to show if |x-c|<delta then |f(x)-f(c)|<epsilon
b) A sequence is Cauchy if |an-am|<epsilon
c)want to show f(y)=y
• Nov 28th 2010, 06:56 PM
Drexel28
Quote:

Originally Posted by kathrynmath
0<c<1 and |f(x)-f(y)<c|c-y|
a) Show f is continuous on all of R

It's much, much stronger than continuous. If you're allowed to use the limit definition of continuity just note that $\displaystyle \displaystyle 0\leqslant \lim_{x\to y}|f(x)-f(y)|\leqslant \lim_{x\to y}c|x-y|=0$
Quote:

b)Pick some point y1 in R and construct the sequence (y1,f(y1),f(f(y1)),....)
In general if y_(n+1)=f(yn) show that the resulting sequence yn is a Cauchy sequence. hence we may let y=limyn
Note that by induction $\displaystyle d\left(f^{m+1}(y_1),f^{m}(y_1)\right)<c^m d\left(f(y_1),y_1\right)$. Thus, we see that

\displaystyle \begin{aligned}d\left(f^{n+k}(y_1),f^n(y_1)\right) &\leqslant \sum_{j=0}^{k-1}d\left(f^{n+j+1}(y_1),f^{n+j}(y_1)\right)\\ &< \sum_{j=0}^{k-1}c^{n+j}d\left(f(y_1),y_1\right)\\ &< \frac{c^n}{1-c}d\left(f(y_1),y_1\right)\end{aligned}

From where it evidently follows, letting $\displaystyle n\to\infty$ that $\displaystyle \left\{f^{n}(y_1)\right\}_{n\in\mathbb{N}}$ is Cauchy, and thus by the completeness of $\displaystyle \mathbb{R}$ it follows that $\displaystyle y=\lim f^{n}(y_1)$ exists.
Quote:

c)Prove that y is a fixed point of f and that is unique in this regard.
Uniqueness is clear in general since if $\displaystyle x\ne y$ but $\displaystyle f(x)=x,f(y)=y$ then we see our conditions state that $\displaystyle d(x,y)=d\left(f(x),f(y)\right)<cd(x,y)<d(x,y)$

Now, to see that $\displaystyle y$ is a fixed point we merely note that since $\displaystyle \lim f^n(y_1)=y$ that $\displaystyle \lim f^{n+1}(y_1)=y$ and so by the continuity of $\displaystyle f$ we have that $\displaystyle f(y)=f\left( \lim f^n(y_1)\right)=\lim f^{n+1}(y_1)=y$

Quote:

d) Finally prove that if x is any arbitrary point in R then the sequence (x,f(x),f(f(x)),...) converges to y defined in (b).
Merely note that $\displaystyle y_1$ was arbitrary to begin with.

Remark: There is a much more elegant way of proving that a contractive map from a complete metric space to itself has a fixed point.
• Nov 28th 2010, 07:24 PM
kathrynmath
What are all the d's? If they are derivatives, we haven't gotten to derivatives yet.
• Nov 28th 2010, 07:25 PM
Drexel28
Quote:

Originally Posted by kathrynmath
What are all the d's? If they are derivatives, we haven't gotten to derivatives yet.

Distance function...absolute value.
• Nov 28th 2010, 07:45 PM
kathrynmath
ok what about the lim f^n and lim f^(n+1). I guess I'm not seeing what f^n is
• Nov 28th 2010, 07:46 PM
Drexel28
Quote:

Originally Posted by kathrynmath
ok what about the lim f^n and lim f^(n+1). I guess I'm not seeing what f^n is

Look here.
• Nov 28th 2010, 08:20 PM
kathrynmath
I'm not sure how d follows from y1 being arbitrary in b. I do notice we have similar sequences.