Banach fixed point theorem
In mathematics, 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.
Definition. Let (X, d) be a metric space. Then a map T : X → X is called a contraction mapping on X if there exists q ∈ [0, 1) such that
for all x, y in X.
Banach Fixed Point Theorem. Let (X, d) be a non-empty complete metric space with a contraction mapping T : X → X. Then T admits a unique fixed-point x* in X (i.e. T(x*) = x*). Furthermore, x* can be found as follows: start with an arbitrary element x0 in X and define a sequence {xn} by xn = T(xn−1), then xn → x*.
Remark 1. The following inequalities are equivalent and describe the speed of convergence:
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.
Remark 2. d(T(x), T(y)) < d(x, y) for all x ≠ y is in general not enough to ensure the existence of a fixed point, as is shown by the map T : [1, ∞) → [1, ∞), T(x) = x + 1/x, which lacks a fixed point. However, if 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.
...
Wikipedia