# 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

Let $f$ have two fixed points $p_1, p_2 \in M$.

Let's prove $p_1=p_2$:

 $\displaystyle d \left( p_1,p_2 \right)$ $=$ $\displaystyle d \left({f \left({p_1}\right), f \left({p_2}\right)}\right)$ Definition of fixed point. $\displaystyle$ $\le$ $\displaystyle q\, d \left({p_1, p_2}\right)$ Map $f$ is a contraction. $\displaystyle$ $\le$ $\displaystyle d \left({p_1, p_2}\right)$ Assumed $q\lt 1$.

Then $d \left( p_1,p_2 \right) = 0$.

Metric space property (M4) implies $p_1 = p_2$.

### Existence

The fixed point $p$ will be found from an arbitrary member $a_0$ of $M$ by iteration.

The plan is to obtain $p=\lim_{n\to\infty} a_n$ with definition $a_{n+1}=f\left(a_n\right)$.

The sequence of iterates converges in complete metric space $M$ because it is a Cauchy sequence in $M$, proof below.

Induction on $n$ applies to obtain the contractive estimate:

$d \left( a_{n+1}, a_n \right) \le q^n\, d \left( a_1, a_0\right)$

Induction details $n=1$:

 $\displaystyle d \left(a_2, a_1 \right)$ $=$ $\displaystyle d \left( f\left(a_1\right), f(\left(a_0 \right) \right)$ Definition of sequence $\sequence{a_n}$. $\displaystyle$ $\le$ $\displaystyle q\, d \left( a_1, a_0\right)$ Map $f$ is a contraction.

Assume the contractive estimate for $n=k$. Induction details for $n=k+1$:

 $\displaystyle d \left(a_{k+2}, a_{k+1} \right)$ $=$ $\displaystyle d \left( f\left(a_{k+1}\right), f(\left(a_k \right) \right)$ $\displaystyle$ $\le$ $\displaystyle q\, d \left( a_{k+1}, a_k \right)$ Map $f$ is a contraction. $\displaystyle$ $\le$ $\displaystyle q\, q^k\, d \left( a_1, a_0\right)$ Induction hypothesis applied. Induction complete.

Let's prove sequence $\sequence{a_n}$ is a Cauchy sequence in $M$ by showing that $\lim_{m\to\infty} d \left( a_{n+m}, a_n \right)=0$ for $n$ large.

 $\displaystyle d(a_{n+m},a_n)$ $\le$ $\displaystyle \sum_{j=n}^{n+m-1} d(a_{j+1},a_j)$ metric space triangle inequality (M2) and telescoping sum ideas $\displaystyle$ $\le$ $\displaystyle \sum_{j=n}^{n+m-1} q^j\, d(a_1,a_0)$ Apply the contractive estimate. $\displaystyle$ $\le$ $\displaystyle q^n\left(\dfrac{1-q^m}{1-q}\right) d(a_1,a_0)$ Geometric sum identity applied on the right.

Known facts are $\lim_{n\to\infty} q^n=0$ and $\dfrac{1-q^m}{1-q}\le \dfrac{1}{1-q}$.

Then $\sequence{d\left(a_{n+m},a_n\right)}$ has limit zero at $m=\infty$ for large $n$.

Sequence $\sequence{a_n}$ is a Cauchy sequence convergent to some $p$ in $M$. Then:

 $\displaystyle d \left({f \left(p\right), p}\right)$ $\le$ $\displaystyle d \left({f \left(p\right), f \left(a_n\right)}\right) + d \left({f \left(a_n\right), p}\right)$ Metric Space triangle inequality (M2) $\displaystyle$ $\le$ $\displaystyle q\, d \left( p , a_n \right) + d \left( a_{n+1}, p \right)$ Map $f$ is a contraction and $a_{n+1}=f\left(a_n\right)$

The right side has limit zero at $n=\infty$.

Then $d(f(p),p)=0$.

Then $f(p)=p$ by metric space property (M4). $\blacksquare$

## Also known as

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

## Source of Name

This entry was named for Stefan Banach.