# Contraction Mapping Theorem

We have seen that solving an equation $f(u)=0$ with $f:R^N\rightarrow R^N$ iteratively by time stepping or by Newton’s method, can be formulated as the iteration

• $u^{n+1}=g(u^n)$ , $n= 0, 1, 2,...,$ with $u^0$ a given initial value,

where

• $g(u) = u - f(u)$ or $g(u) = u - \frac{f(u)}{f^\prime (u)}$.

This our experience can be formalized as follows: A mapping $u\rightarrow g(u)$ given by a Lipschitz continuous function $g:R^N\rightarrow R^N$ with Lipschitz constant $L < 1$, is said to be a contraction. This is because

• $\vert g(u)-g(v)\vert\le L\vert u-v\vert <\vert u-v\vert$

expressing that the distance between the images $\vert g(u)-g(v)\vert$ is smaller than the distance between the arguments $\vert u-v\vert$.

For a given contraction mapping $g:R^N\rightarrow R^N$, the iteration

• $u^{n+1}=g(u^n)$ , $n= 0, 1, 2,...,$ with $u^0$ a given intial value,

is referred to as fixed point iteration because $u^n$ will converge to a fixed point $\bar u\in R^N$ satisfying $\bar u = g(\bar u)$ as $n$ gets large.  More precisely, we have the following basic result:

Contraction Mapping Theorem: If $g:R^N\rightarrow R^N$ is a contraction with Lipschitz constant $L<1$, then fixed point iteration $u^{n+1}=g(u^n)$ converges to a unique fixed point $\bar u\in R^N$ with residual

• $R(u^n)\equiv\vert u^n - g(u^n)\vert\leq L^{n}\vert u^1-u^0\vert$

and corresponding fixed point error

• $\vert u^n-\bar u\vert\leq\frac{1}{1- L}R(u^n)$.

Proof: To prove uniqueness assume $\bar u$ and $\hat u$ are two fixed points, and conclude that

• $\vert\bar u - \hat u\vert = \vert g(\bar u) - g(\hat u)\vert\le L \vert \bar u - \hat u\vert$,

which is only possible if $\bar u = \hat u$.

Next,  we have

• $\vert u^{n+1} - u^n\vert =\vert g(u^n) -g(u^{n-1})\vert\leq L\vert u^n - u^{n-1}\vert$,
• $\vert u^n - u^{n-1}\vert\leq L\vert u^{n-1} - u^{n-2}\vert$,
• ….
• $\vert u^2 - u^1\vert\leq L\vert u^1 - u^0\vert$

from which follows

• $\vert u^{n+1} - u^n\vert =\vert g(u^n) - u^n\vert\leq L^n\vert u^1 - u^0\vert$,    (1)

as stated. More generally, we have for $m=1, 2,...,$, by adding and subtracting $u^{n+m-1}, u^{n+m-2},...u^{n+1}$ and so on,

• $u^{n+m} - u^n = (u^{n+m} - u^{n+m-1}) + (u^{n+m-1} - u^{n+m -2}) +...+ (u^{n+1} -u^n)$,

from which follows that

• $\vert u^{n+m} - u^n\vert\le (L^{m-1} + L^{m-2} +...+ 1)\vert u^{n+1} -u^n\vert$

Recalling now the following formula for the sum of a geometric series:

• $1 + L + L^2 + L^{m-1} = \frac{1-L^{m}}{1-L}\le \frac{1}{1-L}$,

we have finally the following generalization of (1)

• $\vert u^{n+m} - u^n\vert\le \frac{1}{1-L}\vert u^{n+1} -u^n\vert\leq \frac{L^n}{1-L}\vert g(u^0)-u^0\vert$ for $m=1, 2,…$.

This estimate shows that the sequence $u^{n}$, $n=1, 2,...,$ determines the decimals of a unique vector $\bar u$ which satisfies $\bar u - g(\bar u)=0$. This proves that the contraction mapping $g:R^N\rightarrow R^N$ has a unique fixed point, and the proof is complete.