Contraction mapping principle

The contraction mapping principle, also known as Banach's fixed-point theorem, is a very interesting and useful theorem. It says: Given a "contraction" map $F:S\to S$ where $S$ is a closed set, we have a unique solution $x\in S$ to the equation $$x=F(x).$$

Let's prove it. But before that, we need some preparation.

Accompanying video:

Definition (Norm)

Let $X$ be a vector space over the field $K$. The function $\Vert \cdot \Vert :X\to \mathbb{R}$ is said to be a norm if it satisfies the following axioms:

1. For all $u\in X$, $\Vert u\Vert \ge 0$. In particular, $$\Vert u\Vert =0⟺u=0.$$
2. For all $\alpha \in K$ and $u\in X$, $$\Vert \alpha u\Vert =|\alpha |\Vert u\Vert .$$
3. (Triangle inequality) For all $u,v\in X$, $$\Vert u+v\Vert \le \Vert u\Vert +\Vert v\Vert .$$

Example. For $x=(x_1,x_2,\cdots ,x_n)\in {\mathbb{R}}^n$, 

$$\Vert x\Vert =\sqrt{x_1^2+x_2^2+\cdots +x_n^2}$$

is a norm. This norm is called the Euclidean norm or $L^2$ norm.□

Example. For $x=(x_1,x_2,\cdots ,x_n)\in {\mathbb{R}}^n$, 

$$\Vert x{\Vert }_1=|x_1|+|x_2|+\cdots +|x_n|$$

is a norm (the $L^1$ norm). □

Definition (Normed space)

A set on which a norm is defined is called a normed space.

Example. ${\mathbb{R}}^n$ with the Euclidean norm is a normed space called the ($n$-dimensional) Euclidean space. (Actually, we also need to define the Euclidean distance induced by the Euclidean norm: $d(x,y)=\Vert x-y\Vert$.) □

See also: Euclidean spaces

Definition (Complete space)

A space $X$ in which every Cauchy sequence converges is said to be complete.

Example. The Euclidean space is complete.

Definition (Banach space)

A complete normed space is called a Banach space.

Lemma 1 [Absolutely converging series and completeness]

Let $X$ be a Banach space. The series

$$\sum _{n=1}^{\mathrm{\infty }}{x}_n=x_1+x_2+\cdots +x_n+\cdots$$

converges in $X$ if

$$\begin{array}{}\text{(Eq:AbsConv)}& \sum _{n=1}^{\mathrm{\infty }}\Vert x_n\Vert <+\mathrm{\infty }.\end{array}$$

Proof. Let

$$S_n=x_1+x_2+\cdots +x_n.$$

Suppose $m>n$, then, by the triangle inequality and the above assumption (Eq:AbsConv),

$$\Vert S_m-S_n\Vert =\Vert \sum _{k=n+1}^m{x}_k\Vert \le \sum _{k=n+1}^m\Vert x_k\Vert \to 0$$

as $m,n\to \mathrm{\infty }$. Thus, $S_n$ is a Cauchy sequence. Since $X$ is complete, $S_n$ converges in $X$. ■

Definition (Fixed point)

Let $F$ be a mapping with its domain and codomain being subsets of $X$ (i.e., $\text{dom}F,\text{cod}F\subset X$). A point $x\in X$ is said to be a fixed point of $F$ if

$$x=F(x).$$

Definition (Contraction)

Let $X$ be a normed space. A mapping $F:\text{dom}F\to \text{cod}F$ ($\text{dom}F,\text{cod}F\subset X$) is said to be a contraction mapping or contraction if there exists a constant $r\in [0,1)$ such that, for all $x_1,x_2\in \text{dom}F$,

$$\Vert F(x_1)-F(x_2)\Vert \le r\Vert x_1-x_2\Vert .$$

Lemma 2

A contraction is continuous.

Proof. For any $\epsilon >0$, if $\Vert x-x^{\prime }\Vert <\epsilon$, then

$$\Vert F(x)-F(x^{\prime })\Vert \le r\Vert x-x^{\prime }\Vert <r\epsilon <\epsilon$$

since $0\le r<1$. ■

Theorem (Contraction mapping principle)

Let $X$ be a Banach space and $S$ be a nonempty closed subset of $X$. If a mapping $F:S\to S$ is a contraction mapping, then there exists a unique fixed point of $F$ in $S$.

Proof. First, we prove the uniqueness of the fixed point. Let $x,x^{\prime }\in S$ be fixed points of $F$. That is, $x=F(x)$ and $x^{\prime }=F(x^{\prime })$. Thus,

$$\Vert x-x^{\prime }\Vert =\Vert F(x)-F(x^{\prime })\Vert .$$

Since $F$ is a contraction, there exists an $r\in [0,1)$ such that

$$\Vert F(x)-F(x^{\prime })\Vert \le r\Vert x-x^{\prime }\Vert .$$

Therefore, we have

$$\Vert x-x^{\prime }\Vert \le r\Vert x-x^{\prime }\Vert ,$$

and hence,

$$0\le (1-r)\Vert x-x^{\prime }\Vert \le 0.$$

Since $1-r>0$, we have $\Vert x-x^{\prime }\Vert =0$. Thus, $x=x^{\prime }$.

Next, we prove the existence of the fixed point.  We construct the solution iteratively. First, take an arbitrary $x_0\in S$, and define $x_n(n=1,2,\cdots )$ by the following recurrence equation:

$$\begin{array}{}\text{(Eq:rec)}& x_n=F(x_{n-1})\end{array}$$

for $n=1,2,\cdots$. Clearly, $x_n\in S$ for all $n\in \mathbb{N}$. Next, we have

$$\begin{array}{rcl}\Vert x_{n+1}-x_n\Vert & \le & r\Vert F(x_n)-F(x_{n-1})\Vert =r\Vert x_n-x_{n-1}\Vert \\ & \le & r^2\Vert x_{n-1}-x_{n-2}\Vert \\ & ⋮& \\ \text{(Eq:xs)}& & \le & r^n\Vert x_1-x_0\Vert .\end{array}$$

Note that 

$$\begin{array}{rcl}{x}_{n+1}& =& (x_{n+1}-x_n)+(x_n-x_{n-1})+\cdots +(x_1-x_0)+x_0\\ \text{(Eq:XSeries)}& & =& x_0+\sum _{i=0}^n(x_{i+1}-x_i).\end{array}$$

From (Eq:xs), we have

$$\begin{array}{rcl}\Vert x_0\Vert +\sum _{n=0}^{\mathrm{\infty }}\Vert x_{n+1}-x_n\Vert & \le & \Vert x_0\Vert +\sum _{n=0}^{\mathrm{\infty }}{r}^n\Vert x_1-x_0\Vert \\ & =& \Vert x_0\Vert +\frac{\Vert x_1-x_0\Vert }{1-r}<\mathrm{\infty }\end{array}$$

as $0\le r<1$. Thus, the series on the right-hand side of (Eq:XSeries) is absolutely converging; hence it converges by the above Lemma 1. But, by the definition of the series (Eq:XSeries), this means that the sequence $\{x_n\}$ converges, that is, $x^{\ast }=\underset{n\to \mathrm{\infty }}{lim}{x}_n$ exists. Finally, note that a contraction is continuous. Thus, both sides of (Eq:rec) converge to $x^{\ast }$ so that

$$x^{\ast }=F(x^{\ast })$$

as $n\to \mathrm{\infty }$. ■