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 qd(f(p_1), f(p_2))\)	\(=\)	\(\displaystyle qd(p_1, p_2)\)	\(\displaystyle \)	by definition of fixed point
	\(\displaystyle \)	\(\displaystyle \)	\(\ge\)	\(\displaystyle d(f(p_1), f(p_2))\)	\(\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 d(a_{n+k}, a_n)\)	\(\le\)	\(\displaystyle qd(a_{n+k-1}, a_{n-1})\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle q^2d(a_{n+k-2}, a_{n-2})\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\vdots\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle q^nd(a_{n+k-n}, a_{n-n})\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle q^nd(a_k, a_0)\)	\(\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 d(a_n, a_m)\)	\(\le\)	\(\displaystyle \sum_{i=m}^{n-1}d(a_{i+1}, a_i)\)	\(\displaystyle \)	since $d$ is a metric
	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle \sum_{i=m}^{n-1}q^id(a_1, a_0)\)	\(\displaystyle \)	by the above
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle q^md(a_1, a_0)\cdot\sum_{i=0}^{n-m-1}q^i\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle q^md(a_1, a_0)\cdot\sum_{i=0}^\infty q^i\)	\(\displaystyle \)	since $q > 0$
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{q^md(a_1, a_0)}{1 - q}\)	\(\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.