10 - Contraction Mapping Theorem

Contraction Mapping Theorem

Let $X$ be a non-empty complete metric space
Suppose that $f:X\to X$ is a contraction then

$f$ has a unique fixed point so there exists unique $x\in X$ such that

$$f(x)=x$$

Proof

Need to show that it is unique

Suppose we have $f(x_1)=x_1$ and $f(x_2)=x_2$ then

$$d(x_1,x_2)=d(f(x_1),f(x_2))\le Kd(x_1,x_2)$$

Since $d(x_1,x_2)\ge 0$ and $0\le K<1$ then

$$d(x_1,x_2)=0$$

Hence

$$x_1=x_2$$

Showing there is a fixed point
Proof is constructive and may be used in practical situations to find fixed point numerically
Pick an arbitrary $x_0\in X$and form iterates

$$\begin{array}{rl}{x}_1& :=f(x_0)\\ x_2& :=f(x_1)\\ & \text{etc...}\end{array}$$

Claim that $(x_n{)}_{n=1}^{\infty }$ converges to some limit $x$ and $f(x)=x$
Using contraction property then

$$d(x_n,x_{n-1})\le Kd(x_{n-1},x_{n-2})\le K^{2}d(x_{n-2},x_{n-3})\le \cdots \le K^{n-1}d(x_0,x_1)$$

Hence for $n>m$ then

$$\begin{array}{rl}d(x_n,x_m)& \le d(x_n,,x_{n-1})+\cdots +d(x_{m+1},x_m)\\ & \le (K^{n-1}+K^{n-2}+\cdots +K^m)d(x_0,x_1)\\ & =K^m(1+K+K^2+\cdots K^{n-1-m})d(x_0,x_1)\\ & \le K^m(1+K+K^2+\cdots )d(x_0,x_1)\\ & =K^m\cdot \frac{d(x_0,x_1)}{1-K}=C{K}^m\end{array}$$

where $C=\frac{d(x_0,x_1)}{1-K}$
Since $K<1$ for any $ϵ>0$ there exists $N$ such that $C{K}^N<ϵ$
Thus $(x_n{)}_{n=1}^{\infty }$ is a Cauchy Sequence

As $X$ is complete then $x_n\to x$ for some $x\in X$
Since $f$ is continuous then

$$f(x)=\underset{n\to \infty }{\lim }f(x_n)=\underset{n\to \infty }{\lim }{x}_{n+1}=x$$