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

Von Mises Iteration

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
The von Mises iteration applies powers of a matrix to a start vector $ x$. The resulting normalized sequence

$\displaystyle u_n = A^n x / \left\Vert A^n x \right\Vert _2 $

will generally approximate a dominant eigenvector. Sufficient for convergence is that $ A$ is diagonalizable and has an eigenvalue $ \lambda$ with largest absolute value. Then, for any vector $ x$ with a nontrivial component $ u$ in the eigenspace of $ \lambda$,

$\displaystyle \left\Vert e^{- \mathrm{i} n \varphi} u_n - \frac{u }{\left\Vert... ...2} \right\Vert= O \left( \left\vert \varrho / \lambda \right\vert^n \right) $

with $ e^{\mathrm{i} \varphi}=\lambda / \left\vert \lambda \right\vert$ and $ \varrho$ an eigenvalue of $ A$ with second largest absolute value.
Let $ \lambda ,\, \varrho ,\, \sigma ,\, \hdots$ with

$\displaystyle \left\vert \lambda \right\vert > \left\vert \varrho \right\vert \geq \left\vert \sigma \right\vert \geq \cdots $

denote the eigenvalues of $ A$ and let

$\displaystyle x=u+v+w+\cdots $

be the decomposition with respect to the corresponding eigenspaces. Then

$\displaystyle A^n x = \lambda ^n u + \varrho^n v + \sigma^n w + \cdots $

and

$\displaystyle A^n x / \left\Vert A^n x \right\Vert _2= \frac{\left( \lambda /\... ... \sigma /\left\vert \lambda \right\vert \right)^n w +\cdots \right\Vert _2}. $

By definition of $ e^{i \varphi}$, the numerator equals

$\displaystyle e^{\mathrm{i} n \varphi} u + O \left( \left\vert \varrho / \lambda \right\vert^n \right) $

and hence

$\displaystyle e^{-\mathrm{i} n \varphi} u_n=\frac{u + O \left( \left\vert \varr... ...\right\Vert _2} + O \left( \left\vert \varrho / \lambda \right\vert^n \right) $

as claimed.
(Authors: Höllig/Pfeil/Walter)
[Back]
  automatisch erstellt am 24.  4. 2007