Banach fixed point theorem

Statement

Let $(X, d)$ be a nonempty complete metric space and let $f \colon X \to X$ be a contraction with constant $k \in [0, 1)$. Then $f$ has exactly one fixed point $x^*$, that is, a point with $f(x^*) = x^*$. Moreover, for each $x_0 \in X$, the sequence $x_{n+1} = f(x_n)$ converges to $x^*$, and $$d(x_n, x^*) \le \frac{k^n}{1 - k} \, d(x_1, x_0) \quad \text{for all } n \ge 0.$$

Remarks

Proof idea: $d(x_{n+1}, x_n) \le k^n d(x_1, x_0)$, so the sequence $(x_n)$ is a Cauchy sequence by a geometric series bound. Its limit is a fixed point because $f$ is continuous. Two fixed points $x, y$ satisfy $d(x, y) \le k \, d(x, y)$, so $x = y$. Completeness is needed: $x \mapsto x/2$ on $(0, 1]$ is a contraction without a fixed point. The theorem gives the existence of solutions of ordinary differential equations in the Picard–Lindelöf theorem.

History

Stefan Banach stated the theorem in 1922.

Explanations

L1 human

Apply the contraction again and again, starting from any point. The points get closer to each other, and in a complete space they converge. The limit does not move under $f$, and it is the only point that does not move.