HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the Banach fixed-point theorem (also known as the contraction mapping theorem or contractive mapping theorem or Banach–Caccioppoli theorem) is an important
tool A tool is an Physical object, object that can extend an individual's ability to modify features of the surrounding environment or help them accomplish a particular task. Although many Tool use by animals, animals use simple tools, only human bei ...
in the theory of
metric space In mathematics, a metric space is a Set (mathematics), set together with a notion of ''distance'' between its Element (mathematics), elements, usually called point (geometry), points. The distance is measured by a function (mathematics), functi ...
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
metric space In mathematics, a metric space is a Set (mathematics), set together with a notion of ''distance'' between its Element (mathematics), elements, usually called point (geometry), points. The distance is measured by a function (mathematics), functi ...
. Then a map T : X \to X is called a contraction mapping on ''X'' if there exists q \in empty complete metric space">Empty set">empty complete metric space 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), \\ ptd(x^*, x_) & \leq \frac d(x_,x_n), \\ ptd(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, a type of agreement used by U.S. states * Blood compact, an ancient ritual of the Philippines * Compact government, a t ...
, 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 x_n = T(x_). 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 Principle of mathematical induction, 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 is a sequence whose elements become arbitrarily close to each other as the sequence progresses. More precisely, given any small positive distance, all excluding a finite number of elements of the sequence are le ...
. 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) \\ pt& \leq q^d(x_1, x_0) + q^d(x_1, x_0) + \cdots + q^nd(x_1, x_0) \\ pt& = q^n d(x_1, x_0) \sum_^ q^k \\ pt& \leq q^n d(x_1, x_0) \sum_^\infty q^k \\ pt& = q^n d(x_1, x_0) \left ( \frac \right ). \end Let \varepsilon > 0 be arbitrary. Since q \in 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 p_1 and p_2 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 on the space of continuous functions under the uniform norm. 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 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 one has # ''I'' + ''g'' : Ω → Ω′ is a bi-Lipschitz homeomorphism; : precisely, (''I'' + ''g'')−1 is still of the form with ''h'' a Lipschitz map of constant ''k''/(1 − ''k''). A direct consequence of this result yields the proof of the inverse function theorem. * 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. * 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 interdisciplinary area of machine learning and optimal control concerned with how an intelligent agent should take actions in a dynamic environment in order to maximize a reward signal. Reinforcement learnin ...
. * 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 ...
, 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 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 ''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.


Generalizations

There are a number of generalizations (some of which are immediate corollaries). 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''(''T''''n''(''x''), ''T''''n''(''y'')) ≤ ''c''''n''''d''(''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 for generalizations. In a non-empty compact metric space, any function T satisfying d(T(x),T(y)) for all distinct x,y, has a unique fixed point. The proof is simpler than the Banach theorem, because the function d(T(x),x) is continuous, and therefore assumes a minimum, which is easily shown to be zero. A different class of generalizations arise from suitable generalizations of the notion of
metric space In mathematics, a metric space is a Set (mathematics), set together with a notion of ''distance'' between its Element (mathematics), elements, usually called point (geometry), points. The distance is measured by a function (mathematics), functi ...
, 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.


Example

An application of the Banach fixed-point theorem and fixed-point iteration can be used to quickly obtain an approximation of with high accuracy. Consider the function f(x)=\sin(x)+x. It can be verified that is a fixed point of ''f'', and that ''f'' maps the interval \left \pi/4,5\pi/4\right/math> to itself. Moreover, f'(x)=1+\cos(x), and it can be verified that :0\leq1+\cos(x)\leq1-\frac<1 on this interval. Therefore, by an application of the
mean value theorem In mathematics, the mean value theorem (or Lagrange's mean value theorem) states, roughly, that for a given planar arc (geometry), arc between two endpoints, there is at least one point at which the tangent to the arc is parallel to the secant lin ...
, ''f'' has a Lipschitz constant less than 1 (namely 1-1/\sqrt). Applying the Banach fixed-point theorem shows that the fixed point is the unique fixed point on the interval, allowing for fixed-point iteration to be used. For example, the value 3 may be chosen to start the fixed-point iteration, as 3\pi/4\leq3\leq5\pi/4. The Banach fixed-point theorem may be used to conclude that : \pi=f(f(f(\cdots f(3)\cdots)))). Applying ''f'' to 3 only three times already yields an expansion of accurate to 33 digits: : f(f(f(3)))=3.141592653589793238462643383279502\ldots\,.


See also

* Brouwer fixed-point theorem * Caristi fixed-point theorem * Contraction mapping * Fichera's existence principle * Fixed-point iteration * Fixed-point theorems *
Infinite compositions of analytic functions In mathematics, infinite Function composition, compositions of analytic functions (ICAF) offer alternative formulations of Generalized continued fraction, analytic continued fractions, series (mathematics), series, product (mathematics), products ...
* Kantorovich theorem


Notes


References

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