HOME

TheInfoList



OR:

In mathematics, the Banach
fixed-point theorem In mathematics, a fixed-point theorem is a result saying that a function ''F'' will have at least one fixed point (a point ''x'' for which ''F''(''x'') = ''x''), under some conditions on ''F'' that can be stated in general terms. Some authors cla ...
(also known as the contraction mapping theorem or contractive mapping theorem) is an important
tool A tool is an object that can extend an individual's ability to modify features of the surrounding environment or help them accomplish a particular task. Although many animals use simple tools, only human beings, whose use of stone tools dates ba ...
in the theory of
metric space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...
s; 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. The theorem is named after
Stefan Banach Stefan Banach ( ; 30 March 1892 – 31 August 1945) was a Polish mathematician who is generally considered one of the 20th century's most important and influential mathematicians. He was the founder of modern functional analysis, and an origina ...
(1892–1945) who first stated it in 1922.


Statement

''Definition.'' Let (X, d) be a
complete metric space In mathematical analysis, a metric space is called complete (or a Cauchy space) if every Cauchy sequence of points in has a limit that is also in . Intuitively, a space is complete if there are no "points missing" from it (inside or at the bou ...
. Then a map T : X \to X is called a
contraction mapping In mathematics, a contraction mapping, or contraction or contractor, on a metric space (''M'', ''d'') is a function ''f'' from ''M'' to itself, with the property that there is some real number 0 \leq k < 1 such that for all ''x'' and ...
on ''X'' if there exists q \in non-empty_complete_metric_space_ In_mathematical_analysis,_a_metric_space__is_called_complete_(or_a_Cauchy_space)_if_every__Cauchy_sequence_of_points_in__has_a_limit_that_is_also_in_. Intuitively,_a_space_is_complete_if_there_are_no_"points_missing"_from_it_(inside_or_at_the_bou_...
_with_a_contraction_mapping_T_:_X_\to_X._Then_''T''_admits_a_unique_Fixed_point_(mathematics).html" ;"title="Empty_set.html" ;"title=", 1) such that :d(T(x),T(y)) \le q d(x,y) for all x, y \in X.
Banach Fixed Point Theorem. Let (X, d) be a Empty set">non-empty
complete metric space In mathematical analysis, a metric space is called complete (or a Cauchy space) if every Cauchy sequence of points in has a limit that is also in . Intuitively, a space is complete if there are no "points missing" from it (inside or at the bou ...
with a contraction mapping T : X \to X. Then ''T'' admits a unique Fixed point (mathematics)">fixed-point x^* in ''X'' (i.e. T(x^*) = x^*). Furthermore, x^* can be found as follows: start with an arbitrary element x_0 \in X and define a sequence (x_n)_ by x_n = T(x_) for n \geq 1. Then \lim_ x_n = x^*.
''Remark 1.'' The following inequalities are equivalent and describe the speed of convergence: : \begin d(x^*, x_n) & \leq \frac d(x_1,x_0), \\ d(x^*, x_) & \leq \frac d(x_,x_n), \\ d(x^*, x_) & \leq q d(x^*,x_n). \end 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)) for all x \neq y is in general not enough to ensure the existence of a fixed point, as is shown by the map :T :
compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact * Blood compact, an ancient ritual of the Philippines * Compact government, a type of colonial rule utilized in British ...
, 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. ''Remark 3.'' When using the theorem in practice, the most difficult part is typically to define X properly so that T(X) \subseteq X.


Proof

Let x_0 \in X be arbitrary and define a sequence (x_n)_ by setting ''xn'' = ''T''(''x''''n''−1). We first note that for all n \in \N, we have the inequality :d(x_, x_n) \le q^n d(x_1, x_0). This follows by induction on ''n'', using the fact that ''T'' is a contraction mapping. Then we can show that (x_n)_ is a
Cauchy sequence In mathematics, a Cauchy sequence (; ), named after Augustin-Louis Cauchy, is a sequence whose elements become arbitrarily close to each other as the sequence progresses. More precisely, given any small positive distance, all but a finite numbe ...
. In particular, let m, n \in \N such that ''m'' > ''n'': : \begin d(x_m, x_n) & \leq d(x_m, x_) + d(x_, x_) + \cdots + d(x_, x_n) \\ & \leq q^d(x_1, x_0) + q^d(x_1, x_0) + \cdots + q^nd(x_1, x_0) \\ & = q^n d(x_1, x_0) \sum_^ q^k \\ & \leq q^n d(x_1, x_0) \sum_^\infty q^k \\ & = q^n d(x_1, x_0) \left ( \frac \right ). \end Let ε > 0 be arbitrary. Since ''q'' ∈ fixed point of ''T'': :x^*=\lim_ x_n = \lim_ T(x_) = T\left(\lim_ x_ \right) = T(x^*). 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'': : d(T(p_1),T(p_2)) = d(p_1,p_2) > q d(p_1, p_2).


Applications

*A standard application is the proof of the Picard–Lindelöf theorem about the existence and uniqueness of solutions to certain ordinary differential equations. The sought solution of the differential equation is expressed as a fixed point of a suitable integral operator which transforms continuous functions into continuous functions. The Banach fixed-point theorem is then used to show that this integral operator has a unique fixed point. *One consequence of the Banach fixed-point theorem is that small Lipschitz perturbations of the identity are bi-lipschitz homeomorphisms. Let Ω be an open set of a Banach space ''E''; let ''I'' : Ω → ''E'' denote the identity (inclusion) map and let ''g'' : Ω → ''E'' be a Lipschitz map of constant ''k'' < 1. Then #Ω′ := (''I''+''g'')(Ω) is an open subset of ''E'': precisely, for any ''x'' in Ω such that ''B''(''x'', ''r'') ⊂ Ω one has ''B''((''I''+''g'')(''x''), ''r''(1−''k'')) ⊂ Ω′; #''I''+''g'' : Ω → Ω′ is a bi-lipschitz homeomorphism; :precisely, (''I''+''g'')−1 is still of the form ''I'' + ''h'' : Ω → Ω′ with ''h'' a Lipschitz map of constant ''k''/(1−''k''). A direct consequence of this result yields the proof of the
inverse function theorem In mathematics, specifically differential calculus, the inverse function theorem gives a sufficient condition for a function to be invertible in a neighborhood of a point in its domain: namely, that its ''derivative is continuous and non-zero at ...
. *It can be used to give sufficient conditions under which Newton's method of successive approximations is guaranteed to work, and similarly for Chebyshev's third order method. *It can be used to prove existence and uniqueness of solutions to integral equations. *It can be used to give a proof to the
Nash embedding theorem The Nash embedding theorems (or imbedding theorems), named after John Forbes Nash Jr., state that every Riemannian manifold can be isometrically embedding, embedded into some Euclidean space. Isometry, Isometric means preserving the length of every ...
. *It can be used to prove existence and uniqueness of solutions to value iteration, policy iteration, and policy evaluation of
reinforcement learning Reinforcement learning (RL) is an area of machine learning concerned with how intelligent agents ought to take actions in an environment in order to maximize the notion of cumulative reward. Reinforcement learning is one of three basic machine ...
. *It can be used to prove existence and uniqueness of an equilibrium in Cournot competition, and other dynamic economic models.


Converses

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 Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...
''fn'' has a unique fixed point. Let q \in (0, 1), 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 f : X \to X is a map on a ''T''1 topological space with a unique fixed point ''a'', such that for each x \in X 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. In this case the metric is in fact an
ultrametric In mathematics, an ultrametric space is a metric space in which the triangle inequality is strengthened to d(x,z)\leq\max\left\. Sometimes the associated metric is also called a non-Archimedean metric or super-metric. Although some of the theorems ...
.


Generalizations

There are a number of generalizations (some of which are immediate
corollaries In mathematics and logic, a corollary ( , ) is a theorem of less importance which can be readily deduced from a previous, more notable statement. A corollary could, for instance, be a proposition which is incidentally proved while proving another ...
). 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: *Assume that some iterate ''Tn'' of ''T'' is a contraction. Then ''T'' has a unique fixed point. *Assume that for each ''n'', there exist ''cn'' such that ''d(Tn(x), Tn(y)) ≤ cnd(x, y)'' for all ''x'' and ''y'', and that ::\sum\nolimits_n c_n <\infty. :Then ''T'' has a unique fixed point. 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 In mathematics, a number of fixed-point theorems in infinite-dimensional spaces generalise the Brouwer fixed-point theorem. They have applications, for example, to the proof of existence theorems for partial differential equations. The first resu ...
for generalizations. A different class of generalizations arise from suitable generalizations of the notion of
metric space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...
, e.g. by weakening the defining axioms for the notion of metric. Some of these have applications, e.g., in the theory of programming semantics in theoretical computer science.


See also

*
Brouwer fixed-point theorem Brouwer's fixed-point theorem is a fixed-point theorem in topology, named after L. E. J. (Bertus) Brouwer. It states that for any continuous function f mapping a compact convex set to itself there is a point x_0 such that f(x_0)=x_0. The simples ...
*
Caristi fixed-point theorem In mathematics, the Caristi fixed-point theorem (also known as the Caristi–Kirk fixed-point theorem) generalizes the Banach fixed-point theorem for maps of a complete metric space into itself. Caristi's fixed-point theorem modifies the ''ε''- va ...
*
Contraction mapping In mathematics, a contraction mapping, or contraction or contractor, on a metric space (''M'', ''d'') is a function ''f'' from ''M'' to itself, with the property that there is some real number 0 \leq k < 1 such that for all ''x'' and ...
* Fichera's existence principle * Fixed-point iteration *
Fixed-point theorem In mathematics, a fixed-point theorem is a result saying that a function ''F'' will have at least one fixed point (a point ''x'' for which ''F''(''x'') = ''x''), under some conditions on ''F'' that can be stated in general terms. Some authors cla ...
s *
Infinite compositions of analytic functions In mathematics, infinite compositions of analytic functions (ICAF) offer alternative formulations of analytic continued fractions, series, products and other infinite expansions, and the theory evolving from such compositions may shed light on the ...
* Kantorovich theorem


Notes


References

* * * * See chapter 7. * {{DEFAULTSORT:Banach Fixed-Point Theorem Articles containing proofs Fixed-point theorems Metric geometry Topology