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:

    “Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
    —Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)

    “If any proof were needed of the progress of the cause for which I have worked, it is here tonight. The presence on the stage of these college women, and in the audience of all those college girls who will some day be the nation’s greatest strength, will tell their own story to the world.”
    —Susan B. Anthony (1820–1906)

    “A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
    —Samuel Johnson (1709–1784)