The Banach fixed point theorem

Proof. We work in $(X, d)$, a complete metric space. Define the contraction mapping $T : X \rightarrow X$, with factor $q \in (0, 1)$. Recall that a contraction mapping satisfies

Define the iterate to be $x_{n+1} = T(x_n)$. Fix $x_0 \in X$. We now claim the following holds for any $n \in \mathbb{N}_0$:

We prove the claim by induction on $n$.

For $n = 0$, we have $d(x_0, x_1) \leq q^0 d(x_0, x_1)$. Assume that $d(x_{k+1}, x_k) \leq q^k d(x_0, x_1)$ holds for some $k \geq 0$. We now prove the claim for the $n = k + 1$ case. $d(x_{(k+1)+1}, x_{k+1}) = d(T(x_{k+1}), T(x_k)) \leq q d(x_{k+1}, x_k)$. By the induction hypothesis, $d(x_{k+1}, x_k) \leq q^k d(x_0, x_1)$, so $d(x_{(k+1)+1}, x_{k+1}) \leq q^{k + 1} d(x_0, x_1)$. Hence by induction, our claim holds for any $n \in \mathbb{N}_0$.

Now, to show that there exists a fixed point $x^* \in X$, we first show that the sequence of iterates $(x_n)$, converges to some point $x^* \in X$. In other words, we have to invoke the completeness of $(X, d)$ somehow. In particular, since every Cauchy sequence in a complete metric space converges to a point in said space, it suffices to show that $(x_n)$ is Cauchy. We can then show that its limit $x^*$ is a fixed point of $T$.

Recall that $(x_n)$ is Cauchy if, for every positive tolerance $\varepsilon$, there exists $N \in \mathbb{N}$ such that whenever $m, n > N$, the terms $x_m$ and $x_n$ are less than $\varepsilon$ far apart.

Let $\varepsilon > 0$ be given. WLOG, let $m > n$. I say WLOG because by symmetry of the metric, we can interchange $x_m$ and $x_n$ with the same results anyways.

We want to show $d(x_m, x_n) < \varepsilon$. We can write

Additionally, for each term in this inequality, notice how

We collect the terms, which gives us

Since $q \in (0, 1)$, we have a sum of a geometric series,

But also $\frac{q^n - q^m}{1 - q} \leq \frac{q^n}{1 - q}$, so we have

Since $q \in (0, 1)$, $q^n/(1 - q) \rightarrow 0$ as $n \rightarrow \infty$. By the convergence of $\frac{q^n}{1 - q} d(x_0, x_1)$, we are guaranteed that for every $\varepsilon > 0$, $\exists N \in \mathbb{N}$ and whenever $n > N$, $\frac{q^n}{1 - q} d(x_0, x_1) < \varepsilon$. Since $m > n$ by hypothesis, $m > n > N$, so $d(x_n, x_m) \leq \frac{q^n}{1 - q} d(x_0, x_1) < \varepsilon$. Thus, $(x_n)$ is Cauchy.

Also, recall that $(X, d)$ is a complete metric space, therefore, every Cauchy sequence in $X$ converges to a point in $X$. We call this point $x^*$. So $x_n \rightarrow x^*$. Now apply $T$, and by continuity² of $T$, $T(x_n) \rightarrow T(x^*)$ because $d(T(x^*), T(x_n)) \leq q d(x^*, x_n) \rightarrow 0$. But $T(x_n) = x_{n+1}$, so $x_{n+1} \rightarrow T(x^*)$. However, we know that subsequences converge to the same limit as their sequence, so $x_{n+1} \rightarrow x^*$. By uniqueness of limits, $T(x^*) = x^*$. Hence there exists a fixed point $x^* \in X$.

Now we can prove that $x^* \in X$ is a unique fixed point. Suppose there are two different fixed points, $x^* \in X$, and $y^* \in X$. We have

Since $q \in (0, 1)$, $1 - q > 0$, and since $d(x, y) \geq 0$, the product cannot be negative. Thus it must be 0. And for $(1 - q) d(x^*, y^*) = 0$, $d(x^*, y^*) = 0$, which can only happen if $x^* = y^*$. Therefore, $x^* \in X$ is a unique fixed point of $T$.

Proof. From the proof of the Banach fixed point theorem, for $m > n$, $d(x_m, x_n) \leq \frac{q^n}{1 - q} d(x_0, x_1)$. By the triangle inequality, $d(x_n, x^*) \leq d(x_n, x_m) + d(x_m, x^*)$. Rearrange, $d(x_n, x^*) - d(x_m, x^*) \leq d(x_n, x_m)$. Applying the triangle inequality again, $d(x_n, x_m) \leq d(x_n, x^*) + d(x^*, x_m)$. So we have $d(x_n, x^*) - d(x_m, x^*) \leq d(x_n, x_m) \leq d(x_n, x^*) + d(x^*, x_m)$. This is equivalent to saying $- d(x_m, x^*) \leq d(x_n, x_m) - d(x_n, x^*) \leq d(x^*, x_m)$, which is simply $| d(x_n, x_m) - d(x_n, x^*) | \leq d(x_m, x^*)$.

Fix $n \geq 0$. We know that $x_m \rightarrow x^*$, so as $m \rightarrow \infty$ the right hand side $d(x_m, x^*) \rightarrow 0$. Therefore $d(x_n, x_m) \rightarrow d(x_n, x^*)$. For every $m > n$ we also have $d(x_m, x_n) \leq \frac{q^n}{1 - q} d(x_0, x_1)$. But since $d(x_n, x_m) \rightarrow d(x_n, x^*)$, $d(x_n, x^*) \leq \frac{q^n}{1 - q} d(x_0, x_1)$, which is exactly what we want to show. Since $n \geq 0$ was arbitrary, this holds for any $n \in \mathbb{N}_0$.

Proof. Fix $n \geq 0$, and let $m > n$. By repeatedly applying the contraction inequality, for every $k \geq n$ we have $d(x_k, x_{k+1}) \leq q^{k-n} d(x_n, x_{n+1})$. Therefore, by the triangle inequality,

By the Banach fixed point theorem, $x_m \rightarrow x^*$. From Corollary (A Priori Error Bound), we showed that $d(x_m,x_n) \rightarrow d(x^*,x_n)$ as $m \rightarrow \infty$. Taking the limit in the inequality above gives $d(x^*,x_n) \leq \frac{1}{1-q} d(x_{n+1},x_n)$. Since $n \geq 0$ was arbitrary, the bound holds for all $n \geq 0$.