Banach Fixed-Point Theorem

Theorem

Suppose $(M, d)$ is a complete metric space, and suppose $f:M\to M$ is a contraction, i.e.

$d(f(x), f(y)) \le q d(x, y)$

for some $q \in [0 .. 1)$ and each $x, y\in M$.

Then there exists a unique fixed point of $f$.

Also known as the Contraction Mapping Theorem.

Proof

Uniqueness

Suppose $f$ has two distinct fixed points $p_1, p_2\in M$. Then

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle qd(f(p_1), f(p_2))\)	\(=\)	\(\displaystyle qd(p_1, p_2)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition of fixed point
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\ge\)	\(\displaystyle d(f(p_1), f(p_2))\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by the condition on $f$

which is only possible if $d(f(p_1), f(p_2)) = 0$ since $q < 1$.

But since $d$ is a metric, this means that $f(p_1) = f(p_2)$ and so $p_1 = p_2$.

Existence

We find a fixed point by selecting an arbitrary member of $M$ and repeatedly taking the image under $f$.

Take any $a\in M$ and define $a_0 = a, a_{n+1} = f(a_n)$ for $n \in \N$. Then by assumption, $d(a_{n+2}, a_{n+1}) \leq qd(a_{n+1}, a_n)$.

Therefore

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle d(a_{n+k}, a_n)\)	\(\le\)	\(\displaystyle qd(a_{n+k-1}, a_{n-1})\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle q^2d(a_{n+k-2}, a_{n-2})\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\vdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle q^nd(a_{n+k-n}, a_{n-n})\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle q^nd(a_k, a_0)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

for each $n, k\in\N$, from which it follows that $d(a_{n+1}, a_n) \leq q^nd(a_1, a_0)$.

So for any $n > m$:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle d(a_n, a_m)\)	\(\le\)	\(\displaystyle \sum_{i=m}^{n-1}d(a_{i+1}, a_i)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	since $d$ is a metric
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle \sum_{i=m}^{n-1}q^id(a_1, a_0)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by the above
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle q^md(a_1, a_0)\cdot\sum_{i=0}^{n-m-1}q^i\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle q^md(a_1, a_0)\cdot\sum_{i=0}^\infty q^i\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	since $q > 0$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{q^md(a_1, a_0)}{1 - q}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by Sum of Infinite Geometric Progression

This last quantity can be made arbitrarily small for all sufficiently large choices of $m$, so the sequence $(a_n)_{n\in\N}$ is Cauchy.

Therefore, by assumption that the metric space is complete, $\exists a\in M : d(a, a_n)\to 0$.

Finally:

$d(a, f(a)) \leq d(a, a_{n+1}) + d(a_{n+1}, f(a)) \leq d(a, a_{n+1}) + qd(a, a_n) \to 0 + q\cdot 0 = 0$

So $a = f(a)\ $.

$\blacksquare$

Source of Name

This entry was named for Stefan Banach.