29: Contraction Mapping Principle

<The previous article in this series | The table of contents of this series | The next article in this series>

description/proof of the contraction mapping principle

---

Topics

About: metric space

---

The table of contents of this article

• Starting Context
• Target Context
• Orientation
• Main Body
• 1: Description
• 2: Proof

---

Starting Context

• The reader knows a definition of complete metric space.
• The reader knows a definition of map.

---

Target Context

• The reader will have a description and a proof of the contraction mapping principle.

---

Orientation

There is a list of definitions discussed so far in this site.

There is a list of propositions discussed so far in this site.

---

Main Body

---

1: Description

For any complete metric space, $M$, and any map, $f:M\to M$, such that there is any $0\le r<1$ such that $dist(f(p_1),f(p_2))\le rdist(p_1,p_2)$ for any $p_1,p_2\in M$, $f$ has the unique fixed point, $p$, (which means that $f(p)=p$), and for any $p_0\in M$, $li{m}_{k\to \mathrm{\infty }}{f}^k(p_0)=p$.

---

2: Proof

$$dist(f^{k+1}(p_0),f^k(p_0))\le rdist(f^k(p_0),f^{k-1}(p_0))\le r^{2}dist(f^{k-1}(p_0),f^{k-2}(p_0))...$$ $$\le r^{k}dist(f(p_0),p_0).$$ $$dist(f^{k+m}(p_0),f^k(p_0))\le dist(f^{k+m}(p_0),f^{k+m-1}(p_0))+dist(f^{k+m-1}(p_0),f^{k+m-2}(p_0))+...+dist(f^{k+1}(p_0),f^k(p_0))$$ $$\le (r^{k+m-1}+r^{k+m-2}+...+r^k)dist(f(p_0),p_0)=r^k\frac{r^m-1}{r-1}dist(f(p_0),p_0).$$ So, $f^k(p_0)$ . . . is a Cauchy sequence, and as $M$ is complete, the sequence converges to a $p$. As $dist(f(p_1),f(p_2))\le rdist(p_1,p_2)$, $f$ is continuous, and so, $$\underset{k\to \mathrm{\infty }}{lim}f(f^k(p_0))=\underset{k\to \mathrm{\infty }}{lim}{f}^{k+1}(p_0)=f(p)=p$$. $p$ is unique, because for fixed points, $p_1$ and $p_2$, $dist(p_1,p_2)=dist(f(p_1),f(p_2))\le rdist(p_1,p_2)$, which is possible only if $dist(p_1,p_2)=0$.

---

References

<The previous article in this series | The table of contents of this series | The next article in this series>