Banach fixed-point theorem: Difference between revisions

Revision as of 02:32, 3 February 2005

Revision as of 03:15, 3 February 2005

Line 1:

The '''Banach fixed point theorem''' is an important tool in the theory of [[metric space]]s; it guarantees the existence and uniqueness of [[fixed point (mathematics)|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 Banach in [[1922]].

Let (''X'', d) be a non-empty [[complete metric space]]. Let ''T'' : ''X'' <tt>-></tt> ''X'' be a ''[[contraction mapping]]'' on ''X'', i.e: there is a [[real number]] ''q''&nbsp;<&nbsp;1 such that

Line 5:

for all ''x'', ''y'' in ''X''. Then the map ''T'' admits one and only one fixed point ''x''^* in ''X'' (this means ''Tx''^* = ''x''^*). Furthermore, this fixed point can be found as follows: start with an arbitrary element ''x''₀ in ''X'' and define a sequence by ''x''_''n'' = ''Tx''_''n''-1 for ''n'' = 1, 2, 3, ... This sequence [[limit (mathematics)|converges]], and its limit is ''x''^*. The following inequality describes the speed of convergence:

:<math>d(x^*, x_n) \leleq \frac{q^n}{1-q} d(x_1,x_0)</math>.

Equivalently,

:<math>d(x^*, x_{n+1}) \leq \frac{q}{1-q} d(x_{n+1},x_n)</math>

and

:<math>d(x^*, x_{n+1}) \leq q d(x_n,x_0)</math>.

The smallest such value of ''q'' is sometimes called the ''[[Lipschitz constant]]''.

Note that the requirement d(''Tx'', ''Ty'') < d(''x'', ''y'') for all unequal ''x'' and ''y'' is in general not enough to ensure the existence of a fixed point, as is shown by the map ''T'' : <nowiki>[1,&infin;) &rarr; [1,&infin;)</nowiki> with ''T''(''x'') = ''x'' + 1/''x'', which lacks a fixed point. However, if the space ''X'' is [[compact]], then this weaker assumption does imply all the statements of the theorem.