Content deleted Content added
m →Proof: Rephrased "Cauchy" into "Cauchy sequence" to point readers to the right page |
m →Proof: force PNG render even if user selected "use HTML as much as possible" by adding \! to end of TeX markup |
||
Line 22:
==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>.
Line 36:
::{|
|-
|<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>
|-
|
Line 49:
|-
|
|<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>,
::{|
Line 84:
|-
|
|<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>,
Line 93:
::<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==
| |||