Content deleted Content added
No edit summary |
m BOT - rv 193.112.229.249 (talk) to last version by Sullivan.t.j |
||
Line 1:
The '''Banach [[fixed point theorem]]''' (also known as the '''contraction mapping theorem''' or '''contraction mapping principle''') 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]].
== The theorem==
Let (''X'', ''d'') be a non-empty [[complete metric space]]. Let ''T'' : ''X'' → ''X'' be a ''[[contraction mapping]]'' on ''X'', i.e: there is a nonnegative [[real number]] ''q'' < 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''<sup>*</sup> in ''X'' (this means ''Tx''<sup>*</sup> = ''x''<sup>*</sup>). Furthermore, this fixed point can be found as follows: start with an arbitrary element ''x''<sub>0</sub> in ''X'' and define an [[iterative method|iterative]] sequence by ''x''<sub>''n''</sub> = ''Tx''<sub>''n''-1</sub> for ''n'' = 1, 2, 3, ... This sequence [[limit (mathematics)|converges]], and its limit is ''x''<sup>*</sup>. The following inequality describes the speed of convergence:
:<math>d(x^*, x_n) \leq \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^*)</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,∞) → [1,∞)</nowiki> with ''T''(''x'') = ''x'' + 1/''x'', which lacks a fixed point. However, if the space ''X'' is [[Compact space|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''.
==Proof==
<!-- The \,\! at the end of some math markup is to keep the formula rendered as PNG instead of HTML. Please don't remove it.-->
Choose any <math>x_0 \in (X, d)</math>. For each <math>n \in \{1, 2, \ldots\}</math>, define <math>x_n = Tx_{n-1}\,\!</math>. We claim that for all <math>n \in \{1, 2, \dots\}</math>, the following is true:
::<math>d(x_{n+1}, x_n) \leq q^n d(x_1, x_0)</math>.
To show this, we will proceed using induction. The above statement is true for the case <math>n = 1\,\!</math>, for
::<math>d(x_{1+1}, x_1) = d(x_2, x_1) = d(Tx_1, Tx_0) \leq qd(x_1, x_0)</math>.
Suppose the above statement holds for some <math>k \in \{1, 2, \ldots\}</math>. Then we have
::{|
|-
|<math>d(x_{(k + 1) + 1}, x_{k + 1})\,\!</math>
|<math>= d(x_{k + 2}, x_{k + 1})\,\!</math>
|-
|
|<math>= d(Tx_{k + 1}, Tx_k)\,\!</math>
|-
|
|<math>\leq q d(x_{k + 1}, x_k)</math>
|-
|
|<math>\leq q \cdot q^kd(x_1, x_0)</math>
|-
|
|<math>= q^{k + 1}d(x_1, x_0)\,\!</math>.
|}
The inductive assumption is used going from line three to line four. By the [[principle of mathematical induction]], for all <math>n \in \{1, 2, \ldots\}</math>, the above claim is true.
Let <math>\epsilon > 0\,\!</math>. Since <math>0 \leq q < 1</math>, we can find a large <math>N \in \{1, 2, \ldots\}</math> so that
::<math>q^N < \frac{\epsilon(1-q)}{d(x_1, x_0)}</math>.
Using the claim above, we have that for any <math>m\,\!</math>, <math>n \in \{0, 1, \ldots\}</math> with <math>m > n \geq N</math>,
::{|
|-
|<math>d\left(x_m, x_n\right)</math>
|<math>\leq d(x_m, x_{m-1}) + d(x_{m-1}, x_{m-2}) + \cdots + d(x_{n+1}, x_n)</math>
|-
|
|<math>\leq q^{m-1}d(x_1, x_0) + q^{m-2}d(x_1, x_0) + \cdots + q^nd(x_1, x_0)</math>
|-
|
|<math>= d(x_1, x_0)q^n \cdot \sum_{k=0}^{m-n-1} q^k</math>
|-
|
|<math>< d(x_1, x_0)q^n \cdot \sum_{k=0}^\infty q^k</math>
|-
|
|<math>= d(x_1, x_0)q^n \frac{1}{1-q}</math>
|-
|
|<math>= q^n \frac{d(x_1, x_0)}{1-q}</math>
|-
|
|<math>< \frac{\epsilon(1-q)}{d(x_1, x_0)}\cdot\frac{d(x_1, x_0)}{1-q}</math>
|-
|
|<math>= \epsilon\,\!</math>.
|}
The inequality in line one follows from repeated applications of the [[triangle inequality]]; the series in line four is a [[geometric series]] with <math>0 \leq q < 1</math> and hence it converges. The above shows that <math>\{x_n\}_{n\geq 0}</math> is a [[Cauchy sequence]] in <math>(X, d)\,\!</math> and hence convergent by completeness. So let <math>x^* = \lim_{n\to\infty} x_n</math>. We make two claims: (1) <math>x^*\,\!</math> is a [[fixed point]] of <math>T\,\!</math>. That is, <math>Tx^* = x^*\,\!</math>; (2) <math>x^*\,\!</math> is the only fixed point of <math>T\,\!</math> in <math>(X, d)\,\!</math>.
To see (1), we note that for any <math>n \in \{0, 1, \ldots\}</math>,
::<math>0 \leq d(x_{n+1}, Tx^*) = d(Tx_n, Tx^*) \leq q d(x_n, x^*)</math>.
Since <math>qd(x_n, x^*) \to 0</math> as <math>n \to \infty</math>, the [[squeeze theorem]] shows that <math>\lim_{n\to\infty} d(x_{n+1}, Tx^*) = 0</math>. This shows that <math>x_n \to Tx^*</math> as <math>n \to \infty</math>. But <math>x_n \to x^*</math> as <math>n \to \infty</math>, and limits are unique; hence it must be the case that <math>x^* = Tx^*\,\!</math>.
To show (2), we suppose that <math>y\,\!</math> also satisfies <math>Ty = y\,\!</math>. Then
::<math>0 \leq d(x^*, y) = d(Tx^*, Ty) \leq q d(x^*, y)</math>.
Remembering that <math>0 \leq q < 1</math>, the above implies that <math>0 \leq (1-q) d(x^*, y) \leq 0</math>, which shows that <math>d(x^*, y) = 0\,\!</math>, whence by [[positive definiteness]], <math>x^* = y\,\!</math> and the proof is complete.
==Applications==
A standard application is the proof of the [[Picard-Lindelöf theorem]] about the existence and uniqueness of solutions to certain [[ordinary differential equation]]s. 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.
==Converses==
Several converses of the Banach contraction principle exist. The following is due to [[Czeslaw Bessaga]], from [[1959]]:
Let <math>f:X\rightarrow X</math> be a map of an abstract [[set (mathematics)|set]] such that each [[iterated function|iterate]] ''f''<sup> n</sup> has a unique fixed point. Let ''q'' be a real number, 0 < q < 1. Then there exists a complete metric on ''X'' such that ''f'' is contractive, and ''q'' is the contraction constant.
==Generalizations==
See the article on [[fixed point theorems in infinite-dimensional spaces]] for generalizations.
==References==
* Vasile I. Istratescu, ''Fixed Point Theory, An Introduction'', D.Reidel, the Netherlands (1981). ISBN 90-277-1224-7 See chapter 7.
* Andrzej Granas and James Dugundji, ''Fixed Point Theory'' (2003) Springer-Verlag, New York, ISBN 0-387-00173-5.
* William A. Kirk and Brailey Sims, ''Handbook of Metric Fixed Point Theory'' (2001), Kluwer Academic, London ISBN 0-7923-7073-2.
----
An earlier version of this article was posted on [http://planetmath.org/encyclopedia/BanachFixedPointTheorem.html Planet Math]. This article is [[open content]].
[[Category:Topology]]
[[Category:Mathematical analysis]]
[[Category:Fixed points]]
[[Category:Mathematical theorems]]
[[de:Fixpunktsatz von Banach]]
[[fr:Application contractante]]
[[it:Teorema del punto fisso di Banach]]
[[he:משפט נקודת השבת של בנך]]
[[pl:Twierdzenie Banacha o kontrakcji]]
[[fi:Banachin kiintopistelause]]
[[ru:Теорема Банаха о неподвижной точке]]
| |||