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.

Next: Generalized Fundamental Theorem     Previous: From Residual to Root Error

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

%d bloggers like this: