In mathematics, the Banach fixed-point theorem (also known as the contraction mapping theorem or contractive mapping theorem or Banach–Caccioppoli theorem) 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. It can be understood as an abstract formulation of Picard's method of successive approximations. [1] The theorem is named after Stefan Banach (1892–1945) who first stated it in 1922. [2] [3]
Definition. Let be a metric space. Then a map is called a contraction mapping on X if there exists such that
for all
Banach fixed-point theorem. Let be a non- empty complete metric space with a contraction mapping Then T admits a unique fixed-point in X (i.e. ). Furthermore, can be found as follows: start with an arbitrary element and define a sequence by for Then .
Remark 1. The following inequalities are equivalent and describe the speed of convergence:
Any such value of q is called a Lipschitz constant for , and the smallest one is sometimes called "the best Lipschitz constant" of .
Remark 2. for all is in general not enough to ensure the existence of a fixed point, as is shown by the map
which lacks a fixed point. However, if 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 , indeed, a minimizer exists by compactness, and has to be a fixed point of It then easily follows that the fixed point is the limit of any sequence of iterations of
Remark 3. When using the theorem in practice, the most difficult part is typically to define properly so that
Let be arbitrary and define a sequence by setting . We first note that for all we have the inequality
This follows by induction on n, using the fact that T is a contraction mapping. Then we can show that is a Cauchy sequence. In particular, let such that :
Let ε > 0 be arbitrary. Since , we can find a large so that
Therefore, by choosing and greater than we may write:
This proves that the sequence is Cauchy. By completeness of (X,d), the sequence has a limit Furthermore, must be a fixed point of T:
As a contraction mapping, T is continuous, so bringing the limit inside T was justified. Lastly, T cannot have more than one fixed point in (X,d), since any pair of distinct fixed points p1 and p2 would contradict the contraction of T:
Several converses of the Banach contraction principle exist. The following is due to Czesław Bessaga, from 1959:
Let f : X → X be a map of an abstract set such that each iterate fn has a unique fixed point. Let then there exists a complete metric on X such that f is contractive, and q is the contraction constant.
Indeed, very weak assumptions suffice to obtain such a kind of converse. For example if is a map on a T1 topological space with a unique fixed point a, such that for each we have fn(x) → a, then there already exists a metric on X with respect to which f satisfies the conditions of the Banach contraction principle with contraction constant 1/2. [8] In this case the metric is in fact an ultrametric.
There are a number of generalizations (some of which are immediate corollaries). [9]
Let T : X → X be a map on a complete non-empty metric space. Then, for example, some generalizations of the Banach fixed-point theorem are:
In applications, the existence and uniqueness of a fixed point often can be shown directly with the standard Banach fixed point theorem, by a suitable choice of the metric that makes the map T a contraction. Indeed, the above result by Bessaga strongly suggests to look for such a metric. See also the article on fixed point theorems in infinite-dimensional spaces for generalizations.
A different class of generalizations arise from suitable generalizations of the notion of metric space, e.g. by weakening the defining axioms for the notion of metric. [10] Some of these have applications, e.g., in the theory of programming semantics in theoretical computer science. [11]
Banach theorem allows for example fast and accurate calculation of the π number using the trigonometric functions which numerically are the power Taylor series.
Because and the π is the fixed point of for example the function
i.e.
and also the function is around π the contraction mapping from the obvious reasons because its derivative in π vanishes therefore π can be obtained from the infinite superposition for example for the argument value 3:
Already the triple superposition of this function at gives π with accuracy to 33 digits:
This article incorporates material from Banach fixed point theorem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
In mathematics, the Banach fixed-point theorem (also known as the contraction mapping theorem or contractive mapping theorem or Banach–Caccioppoli theorem) 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. It can be understood as an abstract formulation of Picard's method of successive approximations. [1] The theorem is named after Stefan Banach (1892–1945) who first stated it in 1922. [2] [3]
Definition. Let be a metric space. Then a map is called a contraction mapping on X if there exists such that
for all
Banach fixed-point theorem. Let be a non- empty complete metric space with a contraction mapping Then T admits a unique fixed-point in X (i.e. ). Furthermore, can be found as follows: start with an arbitrary element and define a sequence by for Then .
Remark 1. The following inequalities are equivalent and describe the speed of convergence:
Any such value of q is called a Lipschitz constant for , and the smallest one is sometimes called "the best Lipschitz constant" of .
Remark 2. for all is in general not enough to ensure the existence of a fixed point, as is shown by the map
which lacks a fixed point. However, if 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 , indeed, a minimizer exists by compactness, and has to be a fixed point of It then easily follows that the fixed point is the limit of any sequence of iterations of
Remark 3. When using the theorem in practice, the most difficult part is typically to define properly so that
Let be arbitrary and define a sequence by setting . We first note that for all we have the inequality
This follows by induction on n, using the fact that T is a contraction mapping. Then we can show that is a Cauchy sequence. In particular, let such that :
Let ε > 0 be arbitrary. Since , we can find a large so that
Therefore, by choosing and greater than we may write:
This proves that the sequence is Cauchy. By completeness of (X,d), the sequence has a limit Furthermore, must be a fixed point of T:
As a contraction mapping, T is continuous, so bringing the limit inside T was justified. Lastly, T cannot have more than one fixed point in (X,d), since any pair of distinct fixed points p1 and p2 would contradict the contraction of T:
Several converses of the Banach contraction principle exist. The following is due to Czesław Bessaga, from 1959:
Let f : X → X be a map of an abstract set such that each iterate fn has a unique fixed point. Let then there exists a complete metric on X such that f is contractive, and q is the contraction constant.
Indeed, very weak assumptions suffice to obtain such a kind of converse. For example if is a map on a T1 topological space with a unique fixed point a, such that for each we have fn(x) → a, then there already exists a metric on X with respect to which f satisfies the conditions of the Banach contraction principle with contraction constant 1/2. [8] In this case the metric is in fact an ultrametric.
There are a number of generalizations (some of which are immediate corollaries). [9]
Let T : X → X be a map on a complete non-empty metric space. Then, for example, some generalizations of the Banach fixed-point theorem are:
In applications, the existence and uniqueness of a fixed point often can be shown directly with the standard Banach fixed point theorem, by a suitable choice of the metric that makes the map T a contraction. Indeed, the above result by Bessaga strongly suggests to look for such a metric. See also the article on fixed point theorems in infinite-dimensional spaces for generalizations.
A different class of generalizations arise from suitable generalizations of the notion of metric space, e.g. by weakening the defining axioms for the notion of metric. [10] Some of these have applications, e.g., in the theory of programming semantics in theoretical computer science. [11]
Banach theorem allows for example fast and accurate calculation of the π number using the trigonometric functions which numerically are the power Taylor series.
Because and the π is the fixed point of for example the function
i.e.
and also the function is around π the contraction mapping from the obvious reasons because its derivative in π vanishes therefore π can be obtained from the infinite superposition for example for the argument value 3:
Already the triple superposition of this function at gives π with accuracy to 33 digits:
This article incorporates material from Banach fixed point theorem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.