The Banach fixed point theorem (also known as the contraction mapping theorem or contraction mapping principle) is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of certain self maps of metric spaces, and provides a constructive method to find those fixed points. The theorem is named after Stefan Banach (1892–1945), and was first stated by him in 1922^{[1]}.
Contents
The theorem
Let (X, d) be a nonempty 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_{0} 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 the limit of any sequence of iterations of T, as in the fixed point theorem for contractions, or also variationally, as a minimizer of d(x,T(x)) : indeed, a minimizer exists by compactness, and has to be a fixed point 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.
Proof
Choose any . For each , define . We claim that for all , the following is true:
Full article ▸
