# Mathematics Prelims

## July 21, 2008

### The Banach Fixed Point Theorem

Filed under: Analysis,Functional Analysis — cjohnson @ 10:06 pm

A mapping $T : X \to X$ from a metric space $X$ to itself is called a contraction if there exists an $\alpha \in (0, 1)$ such that for every $x, y \in X$ we have $d(Tx, Ty) \leq \alpha d(x, y)$.  The Banach fixed point theorem (aka the contraction theorem) says that every contraction on a non-empty complete metric space has exactly one fixed point.

Proof:  Suppose $X$ is a complete metric space and that $T : X \to X$ is a contraction.  Let $x_0 \in X$ be any point.  Define $x_1 = T x_0$, $x_2 = T x_1 = T^2 x_0$, $x_3 = T x_2 = T^3 x_0$ and so forth.  If we write $d(x_{n+1}, x_n)$ in terms of $Tx_n$ and$Tx_{n-1}$, we see that $d(x_{n+1}, x_n) \leq \alpha^n d(x_1, x_0)$.  Now consider $d(x_n, x_m)$ where we assume, without loss of generality, that $n > m$.  By the triangle inequality we have

$\displaystyle d(x_n, x_m) \leq (\alpha^{n-1} + \alpha^{n-2} + ... + \alpha^m) d(x_1, x_0)$

$\displaystyle \qquad = \frac{\alpha^m (1 - \alpha^{n - m})}{1 - \alpha} d(x_1, x_0)$

$\displaystyle \qquad \leq \frac{\alpha^m}{1 - \alpha} d(x_0, x_1)$

We can obviously make this value as small as we’d like by picking a large enough $m$, so the sequence $(x_n)_{n \in \mathbb{N}}$ is Cauchy and must converge.  Call the limit of this sequence $x$.  Now consider the distance between $x$ and $Tx$.

$\displaystyle d(x, Tx) \leq d(x, x_m) + d(x_m, Tx) \leq d(x, x_m) + \alpha d(x_{m-1}, x)$

By picking a large enough $m$, we can make this as small as we’d like as well, so we have $d(x, Tx) = 0$ so $T$ has a fixed point.  For the uniqueness of $x$, suppose $y$ is also a fixed point.

$\displaystyle d(x, y) = d(Tx, Ty) \leq \alpha d(x, y)$

The only way this holds is if $d(x, y) = 0$, so $x = y$.  Note that the $x$ we constructed didn’t depend on on our initial value of $x_0$, so every sequence we construct by picking a point in $X$ and iterating $T$ will result in the same limit.