\chapter{Contraction Mappings}
An operator $\b F$ that maps a Euclidean space $\mb{\Bb R}^p$ into self is called a {\em contraction mapping} if for any two elements $\b x$ and $\b y$ of $\mb{\Bb R}^p$ the following condition holds
\[
\left\Arrowvert \b F(\b x)-\b F(\b y) \right\Arrowvert \le L\|\b x-\b y\|,\quad 0<L<1.
\]
A point $\b x^{*} \in \mb{\Bb R}^p$ is called a {\em fixed point} if
\[
\b F(\b x^{*})=\b x^{*}.
\]
The imporatnce of the contraction operators lies in the fact that there is a unique fixed point. Furthermore, this point may be found by successive iterations as stated in the following theorem.
\begin{thm}
Let $\b F:\mb{\Bb R}^p \to \mb{\Bb R}^p$ be a contraction mapping with contraction constant $0<L<1$. Then $\b F$ has a unique fixed point, and the sequence
\[
\b x_1,\b x_2,\ldots
\]
generated by $\b x_{n+1}=\b F(\b x_n)$, $n=0,1,2,\ldots$, converges to $\b x^{*}$ for any initial choice of $\b x_0 \in \mb{\Bb R}^p$.
\end{thm}
{\bf Proof}\quad To show the uniqueness of the fixed point $\b x^{*}$, suppose that there exist two distinct fixed points $\b x^{*}$ and $\b y^{*}$. We then have
\begin{eqnarray*}
\left\Arrowvert \b x^{*} - \b y^{*}\right\Arrowvert &=& \left\Arrowvert \b F(\b x^{*}) - \b F(\b y^{*}) \right\Arrowvert \\
&\le& L\left\Arrowvert \b x^{*} - \b y^{*}\right\Arrowvert.
\end{eqnarray*}
Thus,
\[
\left\Arrowvert \b x^{*} - \b y^{*}\right\Arrowvert \le L\left\Arrowvert \b x^{*} - \b y^{*}\right\Arrowvert,
\]
which is impossible unless $\left\Arrowvert \b x^{*} - \b y^{*}\right\Arrowvert=0$. Hence, $\b x^{*}=\b y^{*}$ which means that $\b F$ has at most one fixed point.

We now show that a fixed point exists, and that the sequence
\[
\b x_1,\b x_2,\ldots
\]
generated by $\b x_{n+1}=\b F(\b x_n)$, $n=0,1,2,\ldots$, converges to $\b x^{*}$ for any initial choice of $\b x_0 \in \mb{\Bb R}^p$. If $\b F(\b x_0)=\b x_0$, then the theorem is proved. In general $\b F(\b x_0)\ne\b x_0$. For any $n$, $m$ with $m>n$ we have
\begin{eqnarray*}
\|\b x_m - \b x_n\| &=& \left\Arrowvert \b F^m(\b x_0) - \b F^n(\b x_0)\right\Arrowvert\\
&=& \left\Arrowvert \b F\left(\b F^{m-1}(\b x_0)\right) - \b F\left(\b F^{n-1}(\b x_0)\right)\right\Arrowvert\\
&\le& L\left\Arrowvert \b F^{m-1}(\b x_0) - \b F^{n-1}(\b x_0)\right\Arrowvert\\
&\vdots&{}\\
&\le&L^n\|\b x_{m-n}-\b x_0\|\\
&=& L^n\|\b x_0-\b x_{m-n}\|.
\end{eqnarray*}
We write
\[
\|\b x_0-\b x_{m-n}\|=\|\b x_0-\b x_1+\b x_1-\b x_2+\b x_2-\cdots-\b x_{m-n-1}+\b x_{m-n-1}+\b x_{m-n}\|.
\]
Applying the triangle inequality yields
\[
\|\b x_m-\b x_n\|\le L^n\left(\|\b x_0-\b x_1\|+\|\b x_1-\b x_2\|+\cdots+\|\b x_{m-n-1}-\b x_{m-n}\| \right).
\]
Taking into account that
\begin{eqnarray*}
\|\b x_j-\b x_{j+1}\|&=&\left\Arrowvert\b F(\b x_{j-1})-\b F(\b x_j)\right\Arrowvert\\
&\le& L\|\b x_{j-1}-\b x_{j}\|\\
&\vdots&{}\\
&\le& L^j\|\b x_{0}-\b x_{1}\|,
\end{eqnarray*}
we obtain
\begin{eqnarray*}
\|\b x_m-\b x_n\| &\le& L^n\|\b x_0-\b x_1\|\left( 1+L+\cdots+L^{m-n-1}\right)\\
&\le& L^n\|\b x_0-\b x_1\|\left( 1+L+\cdots+L^{m-n-1}+\cdots\right)\\
&=&\frac{L^n}{1-L}\|\b x_0-\b x_1\|
\end{eqnarray*}
because $0<L<1$. Recall that a sequence
\[
\b x_0,\b x_1,\ldots
\]
is a Cauchy sequence if for each $\varepsilon>0$ there exists a positive integer $n=n(\varepsilon)$ such that $\|\b x_m-\b x_n\|<\varepsilon$ for all $m>n$. Given an $\varepsilon>0$, let $n$ be such that
\[
L^n < \frac{\varepsilon(1-L)}{\|\b x_0-\b x_1\|}.
\]
Then,
\begin{eqnarray*}
\|\b x_m-\b x_n\| &\le& \frac{L^n}{1-L}\|\b x_0-\b x_1\|\\
&<&\varepsilon,\quad \mb{for all}\quad m>n.
\end{eqnarray*}
Therefore the sequence $\b x_0,\b x_1,\ldots$ is a Cuachy sequence, and we will now show that the limit $\b g$ of this sequence is the fixed point $\b x^{*}$ of the mapping $\b F$. Note that $\b F$ is uniformly continuous. Indeed, for each $\varepsilon >0$ there exists a $\delta=\delta(\varepsilon)$ such that if $\|\b x-\b y\| < \delta$, then $\left\Arrowvert\b F(\b x)-\b F(\b y)\right\Arrowvert <\varepsilon$. Since $\left\Arrowvert\b F(\b x)-\b F(\b y)\right\Arrowvert \le L\|\b x -\b y\|$, given an $\varepsilon>0$, we can choose $\delta=\varepsilon/L$. Since $F$ is continuous we have
\begin{eqnarray*}
\lim_{n\to \infty}\b F(\b x_n) &=& \b F\left( \lim_{n\to \infty}\b x_n\right)\\
&=& \b F(\b g).
\end{eqnarray*}
However, $\b x_{n+1}=\b F(\b x_n)$. Therefore,
\begin{eqnarray*}
\b g &=& \lim_{n\to \infty}\b x_{n+1}\\
&=& \lim_{n \to \infty}\b F(\b x_n)\\
&=& \b F\left(\lim_{n\to \infty}\b x_n \right)\\
&=& \b F(\b g).
\end{eqnarray*}
Hence $\b g=\b x^{*}$ is a fixed point of $\b F$, and the proof is complete.\\
\hspace*{5.5in}$\Box$

Using the above proof we can give an estimate of the norm of $\|\b x_n-\b x^{*}\|$. For all $m>n$ we have
\[
\|\b x_n-\b x_m\|\le \frac{L^n}{1-L}\|\b x_0-\b x_1\|.
\]
If we now fix $n$ and allow $m\to \infty$, then we obtain
\[
\|\b x_0-\b x^{*}\|\le \frac{L^n}{1-L}\|\b x_0-\b F(\b x_0)\|.
\]
