Contraction Mapping Theorem

This is a workhorse for establishing existence and uniqueness of a fixpoint of an operator $F: X\rightarrow X$ on a complete metric space $(X,d)$ where $d : X\times X \rightarrow \mathbb{R}$ is the metric associated with the set $X$ . It requires that $F$ be a global contraction, that is, there is a $\rho < 1$ such that for all $x,y \in X, d(Fx,Fy) \le \rho d(x,y)$

Given $x_0 \in X$ , consider the sequence $x$ defined by $x_i = F(x_{i-1})$ for $i \ge 1$ . Note that $x$ is a Cauchy sequence since for $n \ge m \ge M$ ,

$d(x_n,x_m) \le \rho d(x_{n-1},x_{m-1}) \le \rho^m d(x_{n-m},x_0) \le \rho^M d(x_{n-m},x_0)$

$d(x_n,x_0) \le d(x_n,x_{n-1}) + d(x_{n-1},x_{n-2}) + \ldots + d(x_1,x_0)$

$d(x_n,x_0) \le \sum_{i = 1}^n d(x_i,x_{i-1}) \le \sum_{i=1}^n \rho^{i-1} d(x_1,x_0) = \frac{1 - \rho^{n}}{1 - \rho} d(x_1,x_0) \le \frac{d(x_1,x_0)}{1 - \rho}$

and so

$d(x_n,x_m) \le \rho^M \frac{1}{1 - \rho} d(x_1,x_0)$

Hence $\limsup_{n,m\rightarrow \infty} d(x_n,x_m) = \inf_M \sup_{n,m \ge M} d(x_n,x_m) = 0$ .

Since $X$ is complete, every Cauchy sequence is convergent. Hence there is a $p \in X$ such that $\lim_{n \rightarrow \infty} d(x_n,p) = 0$

Since $d(p,Fp) \le d(p,x_n) + d(x_n,Fp) \le d(p,x_n) + d(x_{n-1},p)$ it follows on taking limits that $d(p,Fp) = 0$ and so $p = Fp$ . hence $p$ is a fixpoint of $F$ .

For uniqueness, suppose $p,q$ are fixpoints of $F$ . Then

$d(p,q) = d(Fp,Fq) \le \rho d(p,q)$ . Since $\rho < 1$ , it follows that $d(p,q) = 0$ and so $p = q$ . Hence the fixpoints are identical, that is there is one fixpoint.

Navigation

About

Raedwulf ….