Real Analysis – The Contraction Mapping Theorem and the Existence and Uniqueness Theorem

In analysis, we are sometimes interested in contraction mappings, that is, maps that “shrink” a set in a sense to be defined below. The contraction mapping theorem says that all contraction mappings on a complete metric space have a unique fixed point, that is, a point in the domain which is not moved by the map. This theorem will be used below in a proof of the existence and uniqueness theorem for differential equations.

The proof of the contraction mapping theorem considers the sequence defined by repeated application of a contraction mapping. By definition of a contraction mapping, this sequence is Cauchy and thus converges in our complete metric space. The convergence point of this sequence must be fixed by the contraction mapping, and thus a fixed point must exist. The fixed point is unique because the distance between any two fixed points must be zero.

Definition 1. The map {\Phi: M \rightarrow M} on the metric space {(M, d)} is a contraction mapping if there exists a {k}, {0 \le k < 1} such that

\displaystyle d(\Phi(x), \Phi(y)) \le kd(x, y)\text{ }\forall x, y \in M. \ \ \ \ \ (1)

Theorem 1 (Contraction Mapping). If {\Phi: M \rightarrow M} is a contraction mapping on a complete metric space {(M, d)}, then {\Phi} has a unique fixed point, i.e. a unique point {x^* \in M} such that {\Phi(x^*) = x^*}.

Proof. Consider the sequence {\{x_n\}} in {M} defined by

\displaystyle x_1 = \Phi(x_0), \,x_2 = \Phi(x_1), \,\dots\,, \,x_n = \Phi(x_{n-1}), \,\dots

where {x_0} is any point in {M}. We would like to show that this sequence is Cauchy, so we fix an {\epsilon > 0} and go in search of an {N} such that {d(x_m, x_n) < \epsilon} for all {m, n \ge N}.

Now, our contraction mapping as an associated {k} as in the definition above, {0 \le k < 1}. Consider the sequence of partial sums of the {p}-series for this {k}, that is, {\{\sum_{i=1}^n k^i\}_{n = 1, 2, \dots}}. We know this converges (for all {p}-series converge), and thus is Cauchy. Therefore there exists an {N} such that for {n, m \ge N},

\displaystyle \left| \sum_{i=1}^n k^i - \sum_{i=1}^m k^i\right| < {{\epsilon}\over{d(x_0, \Phi(x_0))}} \ \ \ \ \ (2)

as in the definition of Cauchy.

Without loss of generality, assume {n \le m}. Then {(2)} becomes

\displaystyle \sum_{i=n}^m k^i < {{\epsilon}\over{d(x_0, \Phi(x_0))}}.

Therefore

\displaystyle \sum_{i=n}^m k^id\left(x_0, \Phi(x_0)\right) < \epsilon.

But for each term in this sum,

\displaystyle d(x_i, x_{i+1}) \le kd(x_{i-1}, x_i) \le \dots \le k^id(x_0, x_1) = k^i\,d\left(x_0, \Phi(x_0)\right).

So

\displaystyle \sum_{i=n}^m d(x_i, x_{i+1}) \le \sum_{i=n}^m k^id\left(x_0, \Phi(x_0)\right) < \epsilon,

and by the triangle inequality,

\displaystyle d(x_n, x_m) < \epsilon\text{ }\forall n, m \ge N.

This proves that {\{x_n\}} is Cauchy. Since {M} is a complete metric space, this series converges in {M}, say to a point {x^*}. Since {\Phi} is a continuous map, then

\displaystyle \lim_{n\rightarrow\infty} \Phi(x_n) = \Phi\left(\lim_{n\rightarrow\infty} x_n\right) = \Phi\left(x^*\right).

But

\displaystyle \lim_{n\rightarrow\infty}\Phi(x_n) = \lim_{n\rightarrow\infty} x_{n+1} = x^*,

so finally

\displaystyle x^* = \Phi\left(x^*\right).

It rests only to show that {x^*} is unique. This is easily done because if {y^*} is another fixed point, then

\displaystyle d(x^*, y^*) = d\left(\Phi(x^*), \Phi(y^*)\right) \le kd(x^*, y^*)

implies that {d\left(x^*, y^*\right) = 0} and thus {x^* = y^*}.

{\square}

We note that in this theorem, it is necessary that {M} be complete. As a counterexample, consider the incomplete metric space {M = \left(\mathbb{R}^2 \setminus \{(0, 0)\}, d\right)}, where {d} is the normal distance metric in {\mathbb{R}^2}. We will exhibit a {\Phi} without a fixed point. Say {\Phi} is multiplication by a {k}, {0 \le k < 1} as before. Then

\displaystyle d\left(\Phi(x), \Phi(y)\right) = d(kx, ky) = \|kx - ky\| = k\|x-y\| = kd(x, y) \text{ }\forall x, y \in M

so {\Phi} satisfies {(1)}. Assume {\Phi} has a fixed point {x^* \in M}. Since {M \subset \left(\mathbb{R}^2, d\right)}, {x^*} will also be a fixed point for {\Phi} in {\left(\mathbb{R}^2, d\right)}. But it should be clear that {(0, 0)} is also a fixed point for {\Phi} in {\left(\mathbb{R}^2, d\right)}. These points are distinct (i.e. {x^* \neq (0, 0)}), because {x^* \in M} and {(0, 0) \not\in M}. Therefore {\Phi} has two distinct fixed points in {\left(\mathbb{R}^2, d\right)} and we arrive at a contradiction. This implies {\Phi} has no fixed point in {M}. We conclude that the hypothesis that {M} be complete cannot be removed from the theorem.

It is similarly necessary that our {k} as defined in {(1)} must be greater or equal to zero but strictly less than one. If {k < 0} then the contradiction is immediate. If we allow {k \ge 1} then consider the identity map on {\left(\mathbb{R}^2, d\right)}, which clearly satisfies {(1)}. Every point in {\mathbb{R}^2} is a fixed point of the identity, therefore the fixed point of {\Phi} is not unique, which is a contradiction.

The reader should also note that this proof has shown not only existence, but also constructibility of the fixed point. Construction is achieved through repeated application of the contraction mapping.

We will use the contraction mapping theorem in the proof of our next theorem, the existence and uniqueness theorem for Cauchy problems, which are differential equations where an initial point is given. An exciting fact is that we will be using the contraction mapping theorem on a subset of the metric space of functions on an interval. We will require that the functions in our metric space satisfy an initial condition and have properties of continuity and boundedness within a specific bound. This metric space will supply candidates for the solutions to our Cauchy problem. To show that a solution exists, we will show how any Cauchy problem gives rise to a contraction mapping—for which we have demonstrated there exists a fixed point. This fixed point will be a solution to the original problem.

We formalize our definition of a Cauchy problem. Suppose {f} is a continuous {\mathbb{R}^2 \rightarrow \mathbb{R}} map and {(t_0, x_0) \in \mathbb{R}^2}. We say that the Cauchy problem defined by {f} and {(t_0, x_0)} has a unique local solution at {t_0} if there exists a {\delta > 0} and a unique differentiable curve {x(t): [t_0 - \delta, t_0 + \delta] \rightarrow \mathbb{R}} satisfying

\displaystyle \dot{x}(t) = f(t, x(t)), \text{ } x(t_0) = x_0. \ \ \ \ \ (3)

Here {\dot{x}} is as usual the derivative of {x(t)} with respect to {t}.

We cannot always prove that a given Cauchy problem will have a solution. However, when {f} is Lipschitz (a term to be defined below), we can use the contraction mapping theorem to show existence of a local solution in the metric space of functions defined below. Define a subset of the metric space of functions on {I = [a, b]} as

\displaystyle C(I) = \{f: f \text{ is a continuous real-valued function on } I\}.

Define the metric on {C(I)} as

\displaystyle d(f, g) = ||f - g|| = \sup_{t \in I} \left|f(t) - g(t)\right|.

Now we define the Lipschitz criterion which we will use. We will say {f} is Lipschitz around {(t_0, x_0)} if there exists an epsilon-ball {B_\epsilon (t_0, x_0)} such that

\displaystyle |f(t, x_1) - f(t, x_2)| \le K|x_1 - x_2 |\ \ \ \ \ (4)

for any {(t, x_1), (t, x_2) \in B_\epsilon (t_0, x_0)}.

Now, armed with our complete metric space of functions and the contraction mapping principle, we can prove the existence and uniqueness theorem for Cauchy problems. The formal statement follows.

Theorem 2 (Existence and Uniqueness). Any Cauchy problem {(3)} defined by {f: \mathbb{R}^2 \rightarrow \mathbb{R}} and {(t_0, x_0) \in \mathbb{R}^2} in which {f} satisfies the Lipschitz condition {(4)} has a unique local solution.

The idea of the proof is to consider the integral equation corresponding to our Cauchy problem {(3)}, which is

\displaystyle x(t) = x_0 + \int_{t_0}^t f\left(s, x(s)\right)\,ds.

This solution is clearly a fixed point for the map

\displaystyle \Phi: x(t) \rightarrow x_0 + \int_{t_0}^t f\left(s, x(s)\right)\,ds \ \ \ \ \ (5)

which will be shown to be a contraction map.

Proof. We begin by finding the value of the {\delta} where the solution is valid. We know that {f} is continuous and Lipschitz in some {D_{\epsilon_0}(t_0, x_0)}. Therefore we can find an {L > 0} such that {|f(t, x)| \le L} for {x, t \in D_{\epsilon_0}(t_0, x_0)}. Then choose a {\delta} such that

\displaystyle 0 < \delta < \min\left({{\epsilon_0}\over{\sqrt{L^2+1}}}, {1\over{K}}\right). \ \ \ \ \ (6)

This done we know that having {|t - t_0| \le \delta} and {|x - x_0| \le L\delta} will imply

\displaystyle d\left((t,x), (t_0, x_0)\right) \le \sqrt{\delta^2 + (\delta{L})^2} = \delta\sqrt{1 + L^2} < \epsilon_0.

Therefore {(t, x)} will be in our {D_{\epsilon_0}(t_0, x_0)}, and thus {|f(t, x)| \le L}. We also have chosen our {\delta} less than {1\over{K}}, so that {\delta{K} < 1}. As will become clear later, having {\delta{K}} less than one will allow us to create the aforementioned contraction mapping of functions.

Now we define a subset {M} of the complete metric space of functions {C\left([t_0 - \delta, x_0 + \delta]\right)} defined by

\displaystyle M = \{\phi : [t_0 - \delta, x_0 + \delta] \rightarrow \mathbb{R} : \phi \text{ is continuous, } \phi(t_0) = x_0, \text{ and } |\phi(t) - x_0| \le L\delta\}.

We know from before that the metric

\displaystyle d(\phi_1, \phi_2) = \sup_{t_0 - \delta \le t \le x_0 + \delta} \left|\phi_1(t) - \phi_2(t)\right|

makes {C([t_0 - \delta, x_0 + \delta])} complete. If we show that our {M} is closed, then we have shown that it is complete, for it is a subset of a complete metric space.

To demonstrate that {M} is closed, we assume the existence of a limit point of {M} and show that it lies within {M}. Assume {\theta \in C([t_0 - \delta, x_0 + \delta])} is such a limit point, so every ball around it will intersect {M}. Find a sequence of points {\{\phi_n\}} in {M} in this intersection, so that

\displaystyle \phi_n \in M \cap D_{1/n}(\theta).

Because {\phi_n \in D_{1/n}(\theta)}

\displaystyle d(\phi_n, \theta) = \sup_{t_0 - \delta \le t \le x_0 + \delta} \left|\phi_n(t) - \theta(t)\right| < 1/n.

The {\phi_n} converge uniformly to {\theta}, so {\theta} is continuous. Furthermore

\displaystyle |\theta(t_0) - x_0| \le |\theta(t_0) - \phi_n(t_0)| + |\phi_n(t_0) - x_0| < 1/n

and

\displaystyle |\theta(t) - x_0| \le |\theta(t) - \phi_n(t)| + |\phi_n(t) - x_0| < L\delta + 1/n.

As {n} goes to infinity, we get {|\theta(t_0) - x_0| = 0} and {|\theta(t) - x_0| \le L \delta}. These imply {\theta \in M}. Therefore {M} contains all of its limit points, so {M} is closed and a complete metric space.

Define {\Phi : M \rightarrow C([t_0 - \delta, x_0 + \delta])} as

\displaystyle \Phi(\phi)(t) = x_0 + \int_{t_0}^t f(s, \phi(s))\,ds.

Now we define the contraction mapping mentioned in {(5)}. First we will show that {\Phi} maps {M} to {M}. Take any {\phi \in M}, define {\psi(t)} by

\displaystyle \psi(t) = \Phi(\phi)(t) = x_0 + \int_{t_0}^t f(s, \phi(s))\,ds.

The following demonstrates that {\psi} is continuous. Our method will be to show that

\displaystyle |\psi(y) - \psi(x)| < L|y - x|, \ \ \ \ \ (7)

which implies that {\psi} is continuous. First,

\displaystyle |\psi(y) - \psi(x)| = \left| \int_x^y f(t, \phi(t))\,dt\right|. \ \ \ \ \ (8)

If we can show that {|f(t, \phi(t))| \le L} then {(7)} will follow. But remember from {(6)}, {|f(t, \phi(t))| \le L} if {|t - t_0| \le \delta} and {|\phi(t) - x_0| \le L\delta}. Both of these conditions are met in this case because {t \in [t_0 - \delta, x_0 + \delta]} and {\phi \in M}. Therefore {\psi} is continuous.

To show {\psi \in M} we need only to show

\displaystyle \psi(t_0) = x_0 \ \ \ \ \ (9)

and

\displaystyle |\psi(t) - x_0| \le L\delta. \ \ \ \ \ (10)

Condition {(9)} is obvious from the definition of {\phi}. For {(10)}, notice that

\displaystyle |\psi(t) - x_0| = \left| \int_{t_0}^t f(s, \phi(s))\,ds\right|

\displaystyle \le \int_{t_0}^t |f(s, \phi(s))|\,ds

\displaystyle \le L\delta.

Therefore {\psi \in M}, and {\Phi} is {M \rightarrow M}.

Now we will show that {\Phi} is a contraction.

\displaystyle d\left(\Phi(\phi_1), \Phi(\phi_2)\right) = \sup_{t_0 - \delta \le t \le x_0 + \delta} \left|\Phi(\phi_1(t)) - \Phi(\phi_2(t))\right|

\displaystyle = \sup_{t_0 - \delta \le t \le x_0 + \delta} \left| \int_{t_0}^t f(s, \phi_1(s))\,ds - \int_{t_0}^t f(s, \phi_2(s))\,ds\right|

\displaystyle = \sup_{t_0 - \delta \le t \le x_0 + \delta} \left| \int_{t_0}^t [f(s, \phi_1(s)) - f(s, \phi_2(s))]\,ds\right|

\displaystyle \le \sup_{t_0 - \delta \le t \le x_0 + \delta} \int_{t_0}^t |f(s, \phi_1(s)) - f(s, \phi_2(s))|\,ds.

Since the function generated by the integral of an absolute value is monotonically increasing,

\displaystyle \sup_{t_0 - \delta \le t \le x_0 + \delta} \int_{t_0}^t |f(s, \phi_1(s)) - f(s, \phi_2(s))|\,ds = \int_{t_0}^{t_0 + \delta} |f(s, \phi_1(s)) - f(s, \phi_2(s))|\,ds.

Which in turn is less than

\displaystyle \delta \cdot \sup_{t_0 - \delta \le t \le x_0 + \delta} |f(t, \phi_1(t)) - f(t, \phi_2(t))|.

Since {f} is Lipschitz, this value is less than {\delta \cdot Kd(\phi_1, \phi_2)}. We choose {k = \delta{K}}. By {(6)}, {0 < k < 1}. Finally we arrive at

\displaystyle d(\Phi(\phi_1), \Phi(\phi_2)) \le kd(\phi_1, \phi_2),

and {\Phi} is a contraction. So by the contraction mapping theorem, {\Phi} will have a fixed point. This unique fixed point will be of the form

\displaystyle x(t) = x_0 + \int_{t_0}^t f(s, x(s))\,ds

and we have found a unique solution to {(3)}.

{\square}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s