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:

    “War is a beastly business, it is true, but one proof we are human is our ability to learn, even from it, how better to exist.”
    —M.F.K. Fisher (1908–1992)

    “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)

    “He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
    —Herman Melville (1819–1891)