Contraction Mapping Principle

Section 5.4 Contraction Mapping Principle

A solution to an analysis problem can often be identified and obtained as a fixed point of a certain map. The Contraction Mapping Principle gives a sufficient condition to show the existence and uniqueness (in a specified setting) of a fixed point of a certain map.

🔗

Definition 5.4.1.

A map $\phi:X\mapsto X$ of a metric space $(X, d)$ to itself is called a contraction if there exists some $c, 0\lt c \lt 1\text{,}$ such that

\begin{equation*} d(\phi(\bx), \phi(\by)) \le c\, d(\bx, \by) \quad \text{ for all $\bx, \by \in X$.} \end{equation*}

🔗

Proposition 5.4.2.

Suppose that $\phi:X\mapsto X$ is a contraction of $X\text{.}$ Then it can have at most one fixed point.

🔗

Proof.

Suppose that $\bx, \by\in X$ are fixed points of $\phi\text{,}$ namely, $\phi(\bx)=\bx, \phi(\by)=\by\text{.}$ Then

\begin{equation*} 0\le d(\bx, \by)=d(\phi(\bx), \phi(\by)) \le c\, d(\bx, \by) \end{equation*}

and $0\lt c \lt 1$ imply that $d(\bx, \by)=0\text{.}$ This forces $\bx=\by\text{,}$ proving that $\phi$ can have at most one fixed point.

🔗

Theorem 5.4.3. Fixed Point Theorem of a Contraction.

Suppose that $\phi:X\mapsto X$ is a contraction of a complete metric space $X\text{.}$ Then it has a unique fixed point.

🔗

Proof.

Pick any $\bx_{0}\in X$ and define $\bx_{1}=\phi(\bx_{0})\text{.}$ Then define $\bx_{k+1}=\phi(\bx_{k})$ for $k=1, 2, \cdots$ recursively. It follows from the contraction property that

\begin{equation*} d(\bx_{k+1}, \bx_{k})\le c d(\bx_{k},\bx_{k-1})\le\cdots \le c^{k}d(\bx_{1}, \bx_{0}). \end{equation*}

This then leads to $d(\bx_{k+l}, \bx_{k})\le \left(c^{k+l-1}+\cdots+c^{k}\right) d(\bx_{1}, \bx_{0}),$ proving that $\{\bx_{k}\}$ is a Cauchy sequence in $X\text{.}$ Since $X$ is assumed to be complete, there exists some $\bx$ such that $\bx_{k}\to \bx$ as $k\to \infty\text{.}$ Since a contraction must be continuous, taking the limit in $\bx_{k+1}=\phi(\bx_{k})$ gives $\bx=\phi(\bx)\text{.}$ This shows the existence of a fixed point. The uniqueness is given earlier.

🔗

Corollary 5.4.4.

Suppose that $X$ is a complete normed space and $A:X\mapsto Y$ is an invertible linear map from $X$ onto another normed vector space $Y$ with a finite operator norm for both itself and its inverse. Then any linear map $B:X \mapsto Y$ with a finite operator norm satisfying

\begin{equation*} \lambda :=\Vert A^{-1}\Vert \Vert A-B\Vert \lt 1 \end{equation*}

is also invertible with its inverse having a finite operator norm.

🔗

Proof.

The invertibility of $B$ is equivalent to the solvability of $B\bx =\by$ for any $\by \in Y\text{.}$ But the latter is equivalent to $A\bx =(A-B)\bx +\by\text{,}$ which is equivalent to $\bx= A^{-1}(A-B)\bx + A^{-1}\by\text{.}$ The solvability of the last equation is equivalent to the existence of a fixed point of

\begin{equation*} \phi(\bx)= A^{-1}(A-B)\bx + A^{-1}\by. \end{equation*}

But under our condition, $\phi$ is a contraction on $X\text{,}$ therefore, has a unique fixed point.

🔗

Furthermore, any fixed point $\bx$ satisfies

\begin{equation*} \Vert \bx \Vert \le \Vert A^{-1}(A-B)\bx \Vert + \Vert A^{-1}\by\Vert \le \lambda \Vert \bx \Vert + \Vert A^{-1}\by\Vert \end{equation*}

from which and $\lambda \lt 1$ it follows that

\begin{equation*} \Vert \bx \Vert \le (1-\lambda)^{-1} \Vert A^{-1}\Vert \Vert\by\Vert \end{equation*}

proving that $B^{-1}$ has a finite operator norm, with $\Vert B^{-1}\Vert \le (1-\lambda)^{-1} \Vert A^{-1}\Vert\text{.}$

🔗

Example 5.4.5. Existence of a Local Solution of an Initial Value Problem of an ODE.

Suppose that $f(x, t)$ is a continuous function defined on $(x, t)\in [x_{0}-\delta_{0}, x_{0}+\delta_{0}]\times [-\epsilon_{0}, \epsilon_{0}]\text{,}$ and that there exists some $L\gt 0$ such that

\begin{equation*} \vert f(x, t) -f(y, t)\vert \le L |x-y| \text{ for all $(x, t), (y, t)\in [x_{0}-\delta_{0}, x_{0}+\delta_{0}]\times [-\epsilon_{0}, \epsilon_{0}]$.} \end{equation*}

Then there exists some $\epsilon, 0 \lt \epsilon \le \epsilon_{0}$ and a unique function $x(t)$ in $C^{1}[ -\epsilon, \epsilon]$ satisfying

\begin{equation} x'(t)=f(x(t), t), \; t\in [ -\epsilon, \epsilon]; \; x(0)=x_{0}.\tag{5.4.1} \end{equation}

🔗

A solution $x(t)$ to (5.4.1) is equivalent to a solution of

\begin{equation*} x(t) =x_{0} +\int_{0}^{t} f(x(s), s)\, ds, \end{equation*}

which can be regarded as a fixed point of

\begin{equation*} \phi (x)= x_{0} +\int_{0}^{t} f(x(s), s)\, ds \end{equation*}

on an appropriate space $X\text{.}$ We will choose

\begin{equation*} X_{\epsilon}=\{x(t)\in C[ -\epsilon, \epsilon]: |x(t)-x_{0}|\le \delta_{0} \text{ for all $t\in [ -\epsilon, \epsilon]$} \} \end{equation*}

for $0 \lt \epsilon \le \epsilon_{0}$ appropriately chosen so that $\phi$ is a contraction on $X_{\epsilon}\text{.}$ Note that a fixed point $x(t)$ in $X_{\epsilon}$ of $\phi$ is automatically in $C^{1}[ -\epsilon, \epsilon]$ and satisfied the (5.4.1).

🔗

Since $f(x, t)$ is continuous on $[x_{0}-\delta_{0}, x_{0}+\delta_{0}]\times [-\epsilon_{0}, \epsilon_{0}]\text{,}$ there exists some $M\gt 0$ such that

\begin{equation*} |f(x, t)|\le M \text{ for all $(x, t)\in [x_{0}-\delta_{0}, x_{0}+\delta_{0}]\times [-\epsilon_{0}, \epsilon_{0}]$.} \end{equation*}

Then, for any $x\in X_{\epsilon}\text{,}$

\begin{equation*} |\phi(x)-x_{0}|\le \left| \int_{0}^{t} f(x(s), s)\, ds \right| \le M |t| \le \delta_{0} \end{equation*}

provided that $0\lt \epsilon \le \epsilon_{0}$ is chosen such that $M \epsilon \le \delta_{0}\text{.}$

🔗

Then for any $x(t), y(t)\in X_{\epsilon}\text{,}$ we have

\begin{align*} |\phi(x(t))-\phi(y(t))|\le \amp \left| \int_{0}^{t} \left( f(x(s), s)-f(y(s), s)\right) \, ds \right|\\ \le \amp L |t|\ \max_{s\in [ -\epsilon, \epsilon]} |x(s)-y(s)| \end{align*}

for $t\in [ -\epsilon, \epsilon]\text{.}$ Thus if $\epsilon$ is chosen to further satisfy $L\epsilon \lt 1\text{,}$ then $\phi$ becomes a contraction on $X_{\epsilon}\text{.}$ Note that $X_{\epsilon}$ is a complete metric space with the metric $d(x, y)=\max_{s\in [ -\epsilon, \epsilon]} |x(s)-y(s)|\text{.}$ Thus the Contraction Mapping Principle is applicable and it implies the existence and uniqueness of a fixed point of $\phi$ in $X_{\epsilon}\text{.}$

🔗

Note that if $0\lt \epsilon' \lt \epsilon\text{,}$ then the fixed point in $X_{\epsilon}$ must coincide with fixed point in $X_{\epsilon'}\text{.}$ Since any solution $x(t)$ of (5.4.1) must be a fixed point in $X_{\epsilon'}$ for some $\epsilon' >0\text{,}$ this shows the uniqueness in this context.

🔗

Prev Top Next