Banach fixed-point theorem: Difference between revisions

Revision as of 05:17, 6 November 2005

Revision as of 17:46, 6 December 2005

Line 3:

== The theorem==

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

:<math>d(Tx,Ty) \le q\cdot d(x,y)</math>

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 an [[iterative method|iterative]] 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:

Line 19:

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.

When using the theorem in practice, the most difficult part is typically to define ''X'' properly so that ''T'' actually maps elements from ''X'' to ''X'', i.e. that ''Tx'' is always an element of ''X''.

==Applications==