# Banach Fixed-Point Theorem

## Theorem

Let $\left({M, d}\right)$ be a complete metric space.

Let $f: M \to M$ be a contraction.

That is, there exists $q \in \left[{0 \,.\,.\, 1}\right)$ such that for all $x, y \in M$:

- $d \left({f \left({x}\right), f \left({y}\right)}\right) \le q d \left({x, y}\right)$

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

## Proof

### Uniqueness

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

Then:

\(\displaystyle q d \left({f \left({p_1}\right), f \left({p_2}\right)}\right)\) | \(=\) | \(\displaystyle q d \left({p_1, p_2}\right)\) | $\quad$ Definition of fixed point | $\quad$ | |||||||||

\(\displaystyle \) | \(\ge\) | \(\displaystyle d \left({f \left({p_1}\right), f \left({p_2}\right)}\right)\) | $\quad$ Hypothesis on $f$ | $\quad$ |

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

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

$\Box$

### Existence

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

Take any $a_0 \in M$ and define recursively:

- $a_{n+1} = f \left({a_n}\right)$

for $n \in \N$.

Then by assumption:

- $d \left({a_{n+2}, a_{n+1} }\right) \le q d \left({a_{n+1}, a_n}\right)$

Therefore, for all $k, n \in \N$, we have:

\(\displaystyle d \left({a_{n+k}, a_n}\right)\) | \(\le\) | \(\displaystyle q d \left({a_{n+k-1}, a_{n-1} }\right)\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \) | \(\le\) | \(\displaystyle q^2 d \left({a_{n+k-2}, a_{n-2} }\right)\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \) | \(\vdots\) | \(\displaystyle \) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \) | \(\le\) | \(\displaystyle q^n d \left({a_{n+k-n}, a_{n-n} }\right)\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle q^n d \left({a_k, a_0}\right)\) | $\quad$ | $\quad$ |

from which it follows that $d \left({a_{n+1}, a_n}\right) \le q^n d \left({a_1, a_0}\right)$ for all $n \in \N$.

So for any $n > m$:

\(\displaystyle d \left({a_n, a_m}\right)\) | \(\le\) | \(\displaystyle \sum_{i \mathop = m}^{n-1} d \left({a_{i+1}, a_i}\right)\) | $\quad$ since $d$ is a metric | $\quad$ | |||||||||

\(\displaystyle \) | \(\le\) | \(\displaystyle \sum_{i \mathop = m}^{n-1} q^i d \left({a_1, a_0}\right)\) | $\quad$ by the above | $\quad$ | |||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{i \mathop = 0}^{n-m-1} q^{i+m} d \left({a_1, a_0}\right)\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle q^m d \left({a_1, a_0}\right) \sum_{i \mathop = 0}^{n-m-1} q^i\) | $\quad$ Summation is Linear | $\quad$ | |||||||||

\(\displaystyle \) | \(\le\) | \(\displaystyle q^m d \left({a_1, a_0}\right) \cdot \sum_{i \mathop = 0}^\infty q^i\) | $\quad$ since $q \ge 0$ | $\quad$ | |||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \frac {q^m d \left({a_1, a_0}\right)} {1 - q}\) | $\quad$ Sum of Infinite Geometric Progression | $\quad$ |

This last quantity can be made arbitrarily small for all sufficiently large choices of $m$, so the sequence $\left\langle{a_n}\right\rangle_{n \mathop \in \N}$ is Cauchy.

Since $M$ is complete metric space:

- $\displaystyle a := \lim_{n \mathop \to \infty} a_n \in M$

Finally:

\(\displaystyle d \left({a, f \left({a}\right)}\right)\) | \(\le\) | \(\displaystyle d \left({a, a_{n+1} }\right) + d \left({a_{n+1}, f \left({a}\right)}\right)\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \) | \(\le\) | \(\displaystyle d \left({a, a_{n+1} }\right) + q d \left({a, a_n}\right)\) | $\quad$ | $\quad$ |

and the quantity on the right converges to zero since $a = \displaystyle \lim_{n \mathop \to \infty} a_n$.

Thus:

- $a = f \left({a}\right)$

$\blacksquare$

## Also known as

Also known as the **Contraction Mapping Theorem**, **Contraction Theorem** and **Contraction Lemma**.

## Source of Name

This entry was named for Stefan Banach.

## Sources

- 2003: John M. Lee:
*Introduction to Smooth Manifolds*: Appendix $C$