Banach Fixed-point Theorem - The Theorem

The Theorem

Let (X, d) be a non-empty complete metric space. Let T : X → X be a contraction mapping on X, i.e.: there is a nonnegative real number q < 1 such that

for all x, y in X. Then the map T admits one and only one fixed-point x* in X (this means T(x*) = x*). Furthermore, this fixed point can be found as follows: start with an arbitrary element x₀ in X and define an iterative sequence by x_n = T(x_n−1) for n = 1, 2, 3, ... This sequence converges, and its limit is x*. The following inequality describes the speed of convergence:

Equivalently,

and

Any such value of q is called a Lipschitz constant for T, and the smallest one is sometimes called "the best Lipschitz constant" of T.

Note that the requirement d(T(x), T(y)) < d(x, y) for all unequal x and y is in general not enough to ensure the existence of a fixed point, as is shown by the map T : [1,∞) → [1,∞) with T(x) = x + 1/x, which lacks a fixed point. However, if the metric space X is compact, then this weaker assumption does imply the existence and uniqueness of a fixed point, that can be easily found as a minimizer of d(x, T(x)) : indeed, a minimizer exists by compactness, and has to be a fixed point of T. It then easily follows that the fixed point is the limit of any sequence of iterations of T.

When using the theorem in practice, the most difficult part is typically to define X properly so that T actually maps elements from X to X, i.e. that T(x) is always an element of X.