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:

    “From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.”
    —Johan Huizinga (1872–1945)

    “The moment a man begins to talk about technique that’s proof that he is fresh out of ideas.”
    —Raymond Chandler (1888–1959)

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