Banach Fixed-point Theorem - Proof

Proof

Choose any . For each, define . We claim that for all, the following is true:

To show this, we will proceed using induction. The above statement is true for the case, for

Suppose the above statement holds for some . Then we have

\begin{align} d(x_{(k + 1) + 1}, x_{k + 1}) & = d(x_{k + 2}, x_{k + 1}) \\ & = d(T(x_{k + 1}), T(x_k)) \\ & \leq q d(x_{k + 1}, x_k) \\ & \leq q \cdot q^kd(x_1, x_0) \\ & = q^{k + 1}d(x_1, x_0). \end{align}

The inductive assumption is used going from line three to line four. By the principle of mathematical induction, for all, the above claim is true.

Let . Since, we can find a large so that

Using the claim above, we have that for any, with ,

\begin{align} d\left(x_m, x_n\right) & \leq d(x_m, x_{m-1}) + d(x_{m-1}, x_{m-2}) + \cdots + d(x_{n+1}, x_n) \\ & \leq q^{m-1}d(x_1, x_0) + q^{m-2}d(x_1, x_0) + \cdots + q^nd(x_1, x_0) \\ & = d(x_1, x_0)q^n \cdot \sum_{k=0}^{m-n-1} q^k \\ & \leq d(x_1, x_0)q^n \cdot \sum_{k=0}^\infty q^k \\ & = d(x_1, x_0)q^n \frac{1}{1-q} \\ & = q^n \frac{d(x_1, x_0)}{1-q} \\ & \leq \frac{\epsilon(1-q)}{d(x_1, x_0)}\cdot\frac{d(x_1, x_0)}{1-q} \\ & = \epsilon. \end{align}

The inequality in line one follows from repeated applications of the triangle inequality; the series in line four is a geometric series with and hence it converges. The above shows that is a Cauchy sequence in and hence convergent by completeness. So let . We make two claims: (1) is a fixed point of . That is, ; (2) is the only fixed point of in .

To see (1), we take the limit of both sides of the recurrence ,

Since T is a contraction mapping, it is continuous, so we may take the limit inside: . Thus, .

To show (2), we suppose that also satisfies . Then

Remembering that, the above implies that, which shows that, whence by positive definiteness, and the proof is complete.

The above is essentially Banach's original proof. What follows is a considerably simpler proof that appeared recently in the Journal of Fixed Point Theory and its Application (see reference).

By the triangle inequality, for any x and y, in X,

so subtracting the middle term on the right from both sides and dividing by the positive quantity (1-q) we get the ``Fundamental Contraction Inequality":

and we note that if x and y are both fixed points then this implies that d(x,y) = 0, so x =y, proving that has at most one fixed point. Now define the mapping by composing with itself n times and note by induction that it satisfies a Lipschitz condition with constant . It remains to show that for any, the sequence is Cauchy and so converges to a point of X, which as noted above is clearly a fixed point of . If in the Fundamental Inequality we replace x and y by and, we find that

or

and since q<1, the right hand side of this latter inequality converges to zero as n and m tend to infinity, proving that is Cauchy. Note also that letting m tend to infinity in the latter inequality gives the inequality derived in the first proof that gives the rate at which converges to .

Read more about this topic:  Banach Fixed-point Theorem

Famous quotes containing the word proof:

    “If some books are deemed most baneful and their sale forbid, how, then, with deadlier facts, not dreams of doting men? Those whom books will hurt will not be proof against events. Events, not books, should be forbid.”
    —Herman Melville (1819–1891)

    “The insatiable thirst for everything which lies beyond, and which life reveals, is the most living proof of our immortality.”
    —Charles Baudelaire (1821–1867)

    “The thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is “what should be.” Now, if you’re taught to live up to a “what should be” that never existed—only an occult superstition, no proof of this “should be”Mthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!”
    —Lenny Bruce (1925–1966)