HOME

TheInfoList



Click Here for Items Related To - Banach fixed-point theorem
OR:
Banach fixed-point theorem on:   [Wikipedia]   [Google]   [Amazon]

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 settin ...
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 original ...
(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 boun ...
. 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_ In_mathematics,_the_empty_set_is_the_unique_set_having_no__elements;_its_size_or_cardinality_(count_of_elements_in_a_set)_is_zero._Some_axiomatic_set_theories_ensure_that_the_empty_set_exists_by_including_an_axiom_of_empty_set,_while_in_other_t_...
_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_boun_...
_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 In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other t ...
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 boun ...
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 In numerical analysis, the order of convergence and the rate of convergence of a limit of a sequence, convergent sequence are quantities that represent how quickly the sequence approaches its limit. A sequence (x_n) that converges to x^* is said ...
: : \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 In mathematical analysis, Lipschitz continuity, named after German mathematician Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: there ex ...
'' 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 Induction, Inducible or Inductive may refer to: Biology and medicine * Labor induction (birth/pregnancy) * Induction chemotherapy, in medicine * Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
on ''n'', using the fact that ''T'' is a contraction mapping. Then we can show that (x_n)_ is a
Cauchy sequence In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in m ...
. 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 th ...
. *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 embedded into some Euclidean space. Isometric means preserving the length of every path. For instan ...
. *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 Cournot competition is an economic model used to describe an industry structure in which companies compete on the amount of output they will produce, which they decide on independently of each other and at the same time. It is named after Antoine A ...
, and other dynamic economic models.


Converses

Several converses of the Banach contraction principle exist. The following is due to
Czesław Bessaga Czesław, ( cz, Česlav, be, italic=yes, Časłaŭ; Česłaŭ, lt, Česlovas) is an old given name derived from the Slavic elements ''ča'' (to await) and ''slava'' (glory). Feminine form: Czesława/Česlava. The name may refer to: * Ceslaus, ...
, from 1959: Let ''f'' : ''X'' → ''X'' be a map of an abstract
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
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 settin ...
, 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 simplest ...
*
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 In mathematics, and particularly in functional analysis, Fichera's existence principle is an existence and uniqueness theorem for solution of functional equations, proved by Gaetano Fichera in 1954. More precisely, given a general vector space and ...
*
Fixed-point iteration In numerical analysis, fixed-point iteration is a method of computing fixed points of a function. More specifically, given a function f defined on the real numbers with real values and given a point x_0 in the domain of f, the fixed-point iterat ...
*
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 The Kantorovich theorem, or Newton–Kantorovich theorem, is a mathematical statement on the semi-local convergence of Newton's method. It was first stated by Leonid Kantorovich in 1948. It is similar to the form of the Banach fixed-point theorem, ...


Notes


References

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