8. The Contraction Mapping Principle and Its Applications

Definition 14. A mapping A of a metric space X into itself is called contracting if d(Ax, Ay) ≤ ad(x, y), where 0<a<1.

Theorem 14 (The contraction mapping principle). If A: X→X is a contraction mapping on a complete metric space (X, d), then there exists a unique point y∈X: Ay = y (fixed point).

Proof. For an arbitrary x1∈X define x2 = Ax1, x3 = Ax2, ... xk = Axk-1. We obtain a sequence {xk} for which d(x3, x2) = d(Ax2, Ax1) ≤ ad(x2, x1). By the same scheme we derive the general formula: d(xn+1 , xn) = d(Axn, Axn-1) ≤ ad(xn, xn-1) ≤ ... ≤ an-1 d(x2, x1). By the triangle inequality and the formula derived we obtain

d(xn+p, xn) ≤ d(xn+p, xn+p-1) +...+ d(xn+1, xn) ≤ (an+p-2 + an+p-3 +...+ an-1) d(x2, x1) = an-1(1 – ap)d(x2, x1)/(1 – a) ≤ an-1d(x2, x1)/(1 – a)

(the inner equality – the sum of a geometric progression).

By virtue of the inequality 0<a<1 and the inequality d(xn+p, xn) ≤ an-1d(x2, x1)/(1 - a), for "e>0 there exists N: d(xn+p, xn) < e, n ≥ N and any natural p. Thus, the sequence {xn} is fundamental, and hence, by the completeness of the space, xn → x0 ∈X

Now let us prove that Ax0 = x0. We have d(Ax0, x0) ≤ d(Ax0, xn) + d(xn, x0) < d(Ax0, Axn-1) + e ≤ ad(x0, xn-1) + e < 2e (a<1) for sufficiently large n. By the arbitrariness of e>0, it follows from this inequality that d(Ax0, x0) = 0. From the axioms of a metric, the equality we need follows.

Let us prove the uniqueness of the fixed point. Let y0∈X: Ay0 = y0 and y0 ≠ x0. Then d(x0, y0) = d(Ax0, Ay0) ≤ ad(x0, y0) < d(x0, y0), and we obtain a contradiction.

The method of finding the solution of the equation, proposed in the theorem on contraction mappings, is called the method of iterations.

The contraction mapping principle has numerous applications in proofs of the existence of a solution and its determination. We shall give only three sufficiently important applications.

1. The Cauchy problem: Find the solution of the differential equation y′ = f(x, y) with the initial condition y(x0) = y0.

On the function f (x, y) we impose the following conditions: f(x, y) is defined and continuous in some open region G, to which the point (x0, y0) belongs, and satisfies in this region the Lipschitz condition in y, i.e.

|f(x, y1) - f(x, y2)| ≤ M|y1 -y2|.

Theorem 15 (Picard). Under the conditions given above there exists such d > 0 that the Cauchy problem posed, on the interval |x - x0| ≤ d, has a unique solution y = j(x).

Proof. The Cauchy problem posed is obviously equivalent to the following integral equation

j(x) = y0 +

By the continuity of the function f(x, y) we have |f(x, y)| ≤ K in some closed bounded region D ⊂ G, for which the point (x0, y0) is an interior point. Let us choose d > 0 so that the following conditions hold:

1) (x, y) ∈ D, if |x - x0| ≤ d, |y - y0| ≤ Kd;

2) Md < 1.

It is fairly obvious that these conditions can be satisfied. Consider the set X of continuous functions j(x), defined on the interval |x - x0| ≤ d and such that |j(x) - y0| ≤ Kd, with the metric d(j1, j2) = max |j1(x) - j2(x)|, where the maximum is sought on the interval [x0 - d, x0 + d]. It is easy to see that X is a closed set in the space C[x0 - d, x0 + d] and hence is a complete metric space. Consider on this space X the mapping y = Aj, defined by the equality

y(x) = y0 +

This mapping sends the space X into itself and is contractive. Indeed, if j∈X, |x - x0| ≤ d, then |y(x) - y0| = ≤ Kd. The latter means that y(x) = (Aj)(x) ∈X. Further, by the Lipschitz condition,

|y1(x) - y2(x)| ≤ ≤ Md |j1(x) - j2(x)|.

By virtue of the assumptions Md < 1 and the operator A is a contraction. Then, by the contraction mapping principle, the equation y(x) = (Aj)(x), and with it the original Cauchy problem, has a unique solution in the space X.

2. Solution of systems of linear algebraic equations by the method of iterations. Consider n-dimensional space Rn. If Rn, ∈ Rn, then let us set . It is easy to see that the metric space Rn thus defined is complete. Consider on this space the mapping Ax = y, given by means of the equalities

, i=1, … , n.

Then we obtain

If we now assume that <1 for all i, then we find ourselves in the conditions of applicability of the contraction mapping principle and, consequently, the mapping will have a unique fixed point. Thus, we have obtained the theorem.

Theorem 16. If the matrix is such that <1 for all i, then the system of equations

i=1, 2, … , n,

has a unique solution

This solution can be obtained by the method of iterations, starting from an arbitrary vector .

The condition of Theorem 16 is a sufficient condition for the convergence of the method of iterations for the system under consideration. If in Rn we introduce a different metric, we obtain a different convergence condition. Let, for example, . With such a metric

Therefore, the condition for the convergence of the method of iterations will this time be the inequality

.

It is easy to see that the conditions obtained here for the existence and uniqueness of solutions for systems of linear equations can be extended fairly easily to the case of infinite systems of linear equations in the corresponding metric spaces.

3. The Fredholm integral equation. Let us now apply the contraction mapping principle to the solvability of the so-called inhomogeneous linear Fredholm integral equation of the second kind:

f(x) = l + j(x).

Here K(x, y) is called the kernel of the integral operator, j(x) is a given function, l is an arbitrary parameter, f(x) is the unknown function.

Suppose that K(x, y) and j(x) are continuous functions for a ≤ x ≤ b, a ≤ y ≤ b. Then, by Cantor's theorem, |K(x, y)| ≤ M. Consider the mapping Af in the metric space C[a, b], given by the equality:

(Af)(x) = l + j(x).

The following inequalities are quite obvious:

d(Af1, Af2) = |(Af1)(x) - (Af2)(x)| ≤ |l|M(b - a) |f1(x) – f2(x)|.

Consequently, for |l| <1/M(b - a) the mapping A is a contraction in the space C[a, b]. By the contraction mapping principle we conclude that the Fredholm integral equation, for |l| <1/M(b - a), has a unique solution, which can be obtained by the method of iterations using the formula:

fn(x) = l + j(x).

In this formula, the zero function can be taken as the initial approximation f0(x).