Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online lexicon: Annotation to

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z overview
If $ g$ is a contraction of a non-empty closed set $ D\subset\mathbb{R}^n$, i.e., if with $ c<1$, then $ g$ has a unique fixed point $ x_*=g(x_*)\in D$. Starting with any point $ x_0\in D$, $ x_\ast$ can be approximated by the sequence

$\displaystyle x_0,\, x_1 = g(x_0),\, x_2=g(x_1),\,\ldots \,. $

The error satisfies

$\displaystyle \Vert x_*-x_k\Vert\le \frac{c^k}{1-c}\, \Vert x_1-x_0\Vert \,, $

i.e., the iteration converges linearly.

More generally, the fixed point theorem holds in complete metric spaces. Since the proof neither requires translation invariance nor homogeneity of the norm, $ \Vert x-y\Vert$ can be replaced by a general distance function $ d(x,y)$.

The proof is divided into several steps.

(i) Since $ g(D)\subseteq D$, $ x_\ell\in D$ for all $ \ell>0$.

(ii) Iteration of the inequality

$\displaystyle \Vert x_{\ell+1}-x_\ell\Vert = \Vert g(x_\ell)-g(x_{\ell-1})\Vert \le c\, \Vert x_\ell-x_{\ell-1}\Vert $

leads to

$\displaystyle \Vert x_{\ell+1}-x_\ell\Vert\le c^\ell\, \Vert x_1-x_0\Vert \,. $

(iii) With the aid of the triangle inequality we obtain

\begin{displaymath} \begin{array}{rcl} \Vert x_j-x_\ell\Vert&\le& \Vert x_j-x_{... ...\\ &\le& \frac{c^\ell}{1-c}\Vert x_1-x_0\Vert \end{array}\,, \end{displaymath}

establishing Cauchy covergence of the sequence $ (x_\ell)$ to a limit $ x_*$.

(iv) Again, using the Lipschitz condition for $ g$,

$\displaystyle \Vert g(x_*)-x_*\Vert\le\Vert g(x_*)-g(x_j)\Vert+\Vert g(x_j)-x_*\Vert\le c\, \Vert x_*-x_{j}\Vert+\Vert x_{j+1}-x_*\Vert \,. $

Passing to the limit for $ j\to\infty$ shows that $ x_*$ is a fixed point of $ g$.

$ (v)$ The fixed point $ x_*$ is unique since

$\displaystyle \Vert\tilde x_*-x_*\Vert= \Vert g(\tilde x_*)-g(x_*)\Vert\le c \Vert\tilde x_*-x_*\Vert $

with $ c<1$.

(vi) Finally, we obtain the estimate for the error by letting $ j$ tend to $ \infty$ in the inequality (iii) for $ \Vert x_j-x_\ell\Vert$.

[Back]
  automatisch erstellt am 22.  9. 2016