Banach Fixed-Point Theorem

From ProofWiki
Jump to navigation Jump to search

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