Advanced Analysis

Contraction Mapping Principle

Theorem (Contraction Mapping Principle)
Suppose that \(X\) is a complete metric space. Let \(f : X \rightarrow X\), and suppose there is a \(\rho \in [0,1)\) such that
\[ d(f(x), f(y)) \leq \rho d(x,y) \text{ for all } x,y \in X.\]
(Such a map \(f\) is called a contraction.) Then \(f\) has a unique fixed point, i.e., there exists a unique \(x_* \in X\) such that \(f(x_*) = x_*\).
Proof
Let \(x_0\) be any point in \(X\), and for \(n \geq 1\), let \(x_{n} := f(x_{n-1})\). The point \(x_0\) informally represents a “guess” for the location of the critical points, and the sequence \(x_n\) is constructed by iterating \(f\): \(x_1 = f(x_0), x_2 = f(f(x_0)), \ldots\). We will first show that the sequence converges to a fixed point, then show that there can be at most one fixed point.
Highlight
Key Facts: Fix a positive real \(\delta\) such that \(d(x_0,x_1) \leq \delta\).
  1. For each integer \(n \geq 0\), \(d(x_n,x_{n+1}) \leq \delta \rho^{n}\).
  2. For any integers \(k,l\) with \(k < l\),
    \[ d(x_k,x_l) \leq \frac{\delta \rho^{k}}{1-\rho.}\]
Prove the first fact by induction: \(d(x_0,x_1) \leq \delta\) by definition, and otherwise
\[{}d(x_n,x_{n+1}){}\]
\[{}= d(f(x_{n-1}), f(x_n)){}\]
\[{}\leq \rho d (x_{n-1},x_n){}\]
by definition of the sequence \(x_n\) and the fact that \(f\) is a contraction. By the induction hypothesis, \(d(x_{n-1},x_n) \leq \delta \rho^{n-1}\), so the first inequality follows.

For the second key fact, use the triangle inequality:
\[{}d(x_k,x_l) {}\]
\[{}\leq \sum_{m=k}^{l-1} d (x_m, x_{m+1}) \sum_{m=k}^{l-1} \delta \rho^{m}{}\]
\[{}\leq \sum_{m=k}^\infty \delta \rho^m{}\]
\[{}= \frac{\delta \rho^k}{1-\rho}. {}\]
  • By Key Fact 2, given any \(\epsilon > 0\), there is some positive \(N\) such that \(\delta \rho^{N} (1-\rho)^{-1} < \epsilon\) simply because \(\rho \in [0,1)\), so \(\rho^N \rightarrow 0\) as \(N \rightarrow \infty\). Thus if \(k,l \geq N\), \(d(x_{k},x_{l}) < \epsilon\). The sequence is thus Cauchy and must converge to some \(x_* \in X\).
  • Contraction maps are always continuous (prove this!), so
    \[{}x_*{}\]
    \[{}= \lim_{n \rightarrow \infty} x_n{}\]
    \[{}= \lim_{n \rightarrow \infty} f(x_{n-1}){}\]
    \[{}= f\left( \lim_{n \rightarrow \infty} x_{n-1}\right) = f(x_*) {}\]
    by continuity of \(f\). Thus \(x_*\) is a fixed point.
  • If \(x_*\) and \(y_*\) are both fixed points of \(f\), then
    \[{}d(x_*,y_*){}\]
    \[{}= d( f(x_*), f(y_*)){}\]
    \[{}\leq \rho d(x_*,y_*).{}\]
    If \(x_* \neq y_*\), then \(d(x_*,y_*) > 0\), but then \(\rho \in [0,1)\) implies \(d(x_*,y_*) < d (x_*,y_*)\), which is impossible. Thus \(x_* = y_*\).
Corollary (Stability of Fixed Points)
Suppose \(X\) is a complete metric space and let \(f,g\) map \(X\) to itself. Suppose \(f\) is a contraction with factor \(\rho\) and that \(g\) has a fixed point (\(g\) may or may not be a contraction). Suppose also that \(d(f(x),g(x)) \leq \epsilon\) for all \(x \in X\). If \(x_*\) denotes the fixed point of \(X\) and \(y_*\) denotes a fixed point of \(g\), then
\[ d(x_*,y_*) \leq \epsilon (1-\rho)^{-1}, \]
i.e., if \(f\) and \(g\) are uniformly close to one another, then fixed points of \(f\) and \(g\) must also be close to one another.
Proof
Repeat the previous proof expressing \(x_*\) as a limit of a sequence \(x_{n} = f(x_{n-1})\). This time choose \(x_0\) specifically to equal \(y_*\). Then
\[{}d(x_0,f(x_0)) = d(y_*,f(x_0)){}\]
\[{}= d(g(y_*),f(x_0)){}\]
\[{}= d(g(x_0),f(x_0)) \leq \epsilon{}\]
by virtue of the fact that \(x_0 = y_* = g(y_*)\).

To finish, observe
\[d(x_*,y_*) = \lim_{n \rightarrow \infty} d(x_n,x_0) \leq \epsilon (1 - \rho)^{-1}\]
by virtue of Key Fact 2 (because we can take \(\delta = \epsilon\) in this case).