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:

    “There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
    —Herman Melville (1819–1891)

    “The source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
    —Andrew Michael Ramsay (1686–1743)

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