Content deleted Content added
m fi: |
Added a proof! |
||
Line 3:
== 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:
Line 20:
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 [[Cauchy]] 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==
| |||