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.
Sources
- 2003: John M. Lee: Introduction to Smooth Manifolds: Appendix $C$