Banach fixed point theorem

 related topics {math, number, function}

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 non-empty complete metric space. Let T : XX 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 x0 in X and define an iterative sequence by xn = T(xn−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 $x_0 \in (X, d)$. For each $n \in \{1, 2, \ldots\}$, define $x_n = T(x_{n-1})\,\!$. We claim that for all $n \in \{1, 2, \dots\}$, the following is true: