Contraction Mapping Theorem

Banach's theorem: a contraction reels every point to one fixed point.

The idea

Theorem (Banach fixed-point theorem).

Let $(X, d)$ be a non-empty complete metric space, and let $T \colon X \to X$ be a contraction: there is a single constant $k < 1$ with $d(Tx, Ty) \le k\,d(x, y) \quad \text{for all } x, y \in X.$ Then $T$ has exactly one fixed point $L$, a point with $T(L) = L$, and for every starting point $x_{0}$ the iterates $x_{n+1} = T(x_{n})$ converge to $L$.

On a graph, the iteration bounces between the curve $y = T(x)$ and the diagonal $y = x$ — each bounce off the diagonal turns the latest output into the next input — and the path closes in on their crossing, which is the fixed point $L$.

Why it holds. A contraction shrinks the gap between successive iterates geometrically: the contraction inequality applied to the pair $(x_{n}, x_{n-1})$ gives $d(x_{n+1}, x_{n}) \le k\,d(x_{n}, x_{n-1})$, so the step sizes are dominated by a geometric series with ratio $k < 1$. The iterates therefore form a Cauchy sequence, completeness of $X$ supplies a limit $L$, and continuity of $T$ shows $T(L) = L$. Uniqueness follows from the same inequality: two fixed points $L$ and $L'$ would satisfy $d(L, L') \le k\,d(L, L')$, which forces $d(L, L') = 0$.

Neither hypothesis can be weakened. The constant must be one $k$ valid for every pair of points, and it must be strictly below $1$: a map that merely moves every pair of distinct points strictly closer together need not have a fixed point. And $X$ must be complete, or the iterates can converge to a point the space does not contain.

Ways to work on it

• Walkthrough. The contraction condition, a fixed point, and the Lipschitz constant.
• Practice. Find the fixed point of a random linear contraction.
• Hardest. The Babylonian iteration for the square root of two as a contraction.

Not sure where to start? Take the ten-question placement test.