Banach Fixed-Point Theorem
Theorem
Let $\struct {M, d}$ be a complete metric space.
Let $f: M \to M$ be a contraction.
That is, there exists $q \in \hointr 0 1$ such that for all $x, y \in M$:
- $\map d {\map f x, \map f y} \le q \, \map d {x, y}$
Then there exists a unique fixed point of $f$.
Proof
Uniqueness
Let $f$ have two fixed points $p_1, p_2 \in M$.
It is to be proved that $p_1 = p_2$.
\(\displaystyle \map d {p_1, p_2}\) | \(=\) | \(\displaystyle \map d {\map f {p_1}, \map f {p_2} }\) | Definition of Fixed Point | ||||||||||
\(\displaystyle \) | \(\le\) | \(\displaystyle q \, \map d {p_1, p_2}\) | Definition of Contraction Mapping | ||||||||||
\(\displaystyle \leadsto \ \ \) | \(\displaystyle \paren {1 - q} \map d {p_1, p_2}\) | \(\le\) | \(\displaystyle 0\) | subtracting $q \, \map d {p_1, p_2}$ from both sides |
Then from $\paren {1 - q} > 0$ and $\map d {p_1, p_2} \ge 0$:
- $\map d {p_1, p_2} = 0$
From Metric Space Property $(\text M 4)$:
- $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 $\displaystyle p = \lim_{n \mathop \to \infty} a_n$ with definition $a_{n + 1} = \map f {a_n}$.
The sequence of iterates converges in complete metric space $M$ because it is a Cauchy sequence in $M$, as is proved in the following.
Induction on $n$ applies to obtain the contractive estimate:
- $\map d {a_{n + 1}, a_n} \le q^n \, \map d {a_1, a_0}$
Induction details $n = 1$:
\(\displaystyle \map d {a_2, a_1}\) | \(=\) | \(\displaystyle \map d {\map f {a_1}, \map f {a_0} }\) | Definition of $\sequence {a_n}$ | ||||||||||
\(\displaystyle \) | \(\le\) | \(\displaystyle q \, \map d {a_1, a_0}\) | Definition of Contraction Mapping |
Assume the contractive estimate for $n = k$.
Induction details for $n = k + 1$:
\(\displaystyle \map d {a_{k + 2}, a_{k + 1} }\) | \(=\) | \(\displaystyle \map d {\map f {a_{k + 1} }, \map f {a_k} }\) | |||||||||||
\(\displaystyle \) | \(\le\) | \(\displaystyle q \, \map d {a_{k + 1}, a_k}\) | Definition of Contraction Mapping | ||||||||||
\(\displaystyle \) | \(\le\) | \(\displaystyle q \, q^k \, \map d {a_1, a_0}\) | Induction hypothesis applied. Induction complete. |
Next it is to be proved that $\sequence {a_n}$ is a Cauchy sequence in $M$ by showing that $\displaystyle \lim_{m \mathop \to \infty} \map d {a_{n + m}, a_n} = 0$ for $n$ large.
\(\displaystyle \map d {a_{n + m}, a_n}\) | \(\le\) | \(\displaystyle \sum_{j \mathop = n}^{n + m - 1} \map d {a_{j + 1}, a_j}\) | Metric Space Property $(\text M 2)$: Triangle Inequality and telescoping sum ideas | ||||||||||
\(\displaystyle \) | \(\le\) | \(\displaystyle \sum_{j \mathop = n}^{n + m - 1} q^j \, \map d {a_1, a_0}\) | Apply the contractive estimate. | ||||||||||
\(\displaystyle \) | \(\le\) | \(\displaystyle q^n \paren {\dfrac {1 - q^m} {1 - q} } \, \map d {a_1, a_0}\) | Sum of Geometric Sequence on right hand side |
We have that:
- $\displaystyle \lim_{n \mathop \to \infty} q^n = 0$
and:
- $\dfrac {1 -q^m} {1 - q} \le \dfrac 1 {1 - q}$
Then $\sequence {\map d {a_{n + m}, a_n} }$ 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 \map d {\map f p, p}\) | \(\le\) | \(\displaystyle \map d {\map f p, \map f {a_n} } + \map d {\map f {a_n}, p}\) | Metric Space Property $(\text M 2)$: Triangle Inequality | ||||||||||
\(\displaystyle \) | \(\le\) | \(\displaystyle q \, \map d {p, a_n} + \map d {a_{n + 1}, p}\) | Definition of Contraction Mapping, and $a_{n + 1} = \map f {a_n}$ |
The right hand side has limit zero at $n = \infty$.
Then:
- $\map d {\map f p, p} = 0$
Then by Metric Space Property $(\text M 4)$:
- $\map f p = p$.
$\blacksquare$
Also known as
Also known as:
- the Contraction Mapping Theorem
- the Contraction Theorem
- the Banach Contraction Theorem
- the Contraction Lemma.
Source of Name
This entry was named for Stefan Banach.
Sources
- 2003: John M. Lee: Introduction to Smooth Manifolds: Appendix $C$
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Entry: Contraction Mapping Theorem