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

Disturbed Linear System

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
A typical application of Banach's fixed point theorem is a perturbed linear system

$\displaystyle Ax + \varepsilon f(x) = b $

with an invertible matrix $ A$ and a Lipschitz continuous function $ f$ (Lipschitz constant $ c_f$). For computing the solution $ x$, we use the iteration

$\displaystyle x \leftarrow g(x) = A^{-1}(b-\varepsilon f(x)) \,, $

and, to prove convergence, we verify the hypotheses of Banach's fixed point theorem for the closed set

$\displaystyle D=\{y:\ \Vert y-p\Vert\le r\},\quad p=A^{-1} b \,. $

(i)     
$ g(D)\subset D$: For $ x\in D$,

$\displaystyle \Vert g(x)-p\Vert = \varepsilon \Vert A^{-1}f(x)\Vert \le \varepsilon \Vert A^{-1}\Vert \max_{y\in D} \Vert f(y)\Vert \,.$

Hence, $ g(x)\in D$ (distance to $ p$ $ \le r$) if

$\displaystyle \varepsilon \le \frac{r}{\Vert A^{-1}\Vert \max_{y\in D} \Vert f(y)\Vert} \,. $

(ii) Contraction:
The estimate

$\displaystyle \Vert g(x)-g(y)\Vert = \varepsilon \Vert A^{-1}(f(x)-f(y)\Vert \le \underbrace{\varepsilon \Vert A^{-1}\Vert c_f}_{c} \Vert x-y\Vert $

shows that $ g$ is contractive, if $ c<1$, i.e., if

$\displaystyle \varepsilon < \frac{1}{\Vert A^{-1}\Vert c_f} \,. $

Both conditions ((i) und (ii)) are satisfied if $ \varepsilon$ is sufficiently small.

[Links]
  automatisch erstellt am 22.  9. 2016