description/proof of the contraction mapping principle
Topics
About: metric space
The table of contents of this article
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 \lt 1\) such that \(dist (f (p_1), f (p_2)) \le r dist (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\), \(lim_{k \to \infty} f^k (p_0) = p\).
2: Proof
$$dist (f^{k + 1} (p_0), f^k (p_0)) \le r dist (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 r dist (p_1, p_2)\), \(f\) is continuous, and so, $$\lim_{k \to \infty} f (f^k (p_0)) = \lim_{k \to \infty} 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 r dist (p_1, p_2)\), which is possible only if \(dist (p_1, p_2) = 0\).
