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

Wielandt 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 Wielandt iteration is an improvement of the von Mises method which generates a sequence of simultaneous approximations to an eigenvalue $ \lambda$ and a corresponding normalized eigenvector $ u$ of a matrix $ A$, starting from a sufficiently good initial guess. An iteration step is defined by

$\displaystyle \lambda_\ell$ $\displaystyle = u^{\operatorname t}_\ell A u_\ell$    
$\displaystyle v_\ell$ $\displaystyle = \left( A-\lambda_\ell E \right)^{-1} u_\ell$    
$\displaystyle u_{\ell+1}$ $\displaystyle = \frac{v_\ell}{\left\Vert v_\ell \right\Vert _2}$    

where, in an implementation, $ v_\ell$ is computed as a solution of a linear system.

For a simple eigenvalue of a symmetric matrix, the iteration converges cubically:

$\displaystyle \Delta_{\ell+1} \leq c \Delta_\ell^3 $

with $ \Delta_\ell=\max \left\{ \left\vert \lambda_\ell - \lambda \right\vert,\, \left\Vert u_\ell - \sigma_\ell u \right\Vert _2 \right\}$ and the sign $ \sigma_\ell$ chosen so that $ u_\ell^{\operatorname t} \left( \sigma_\ell u \right) \geq 0$.
The proof is divided into several steps.

(i) First we observe that

$\displaystyle \left\Vert u_\ell - \sigma _\ell u \right\Vert _2 \leq \Delta_\el... ...right\Vert _2 \right) \left\Vert u_\ell - \sigma_\ell u \right\Vert _2 \,. $

Hence, it is sufficient to prove the cubic convergence of the sequence $ \left( u_\ell \right)$. The left inequality is trivial and the right estimate follows from

$\displaystyle \left\vert \lambda_\ell - \lambda \right\vert$ $\displaystyle = \left\vert u_\ell^{\operatorname t} A_\ell u_\ell - \left( ... ...ma_\ell u \right)^{\operatorname t} A \left( \sigma_\ell u \right) \right\vert$    
  $\displaystyle = \left\vert \left( u_\ell +\sigma_\ell u \right)^{\operatorname t} A \left( u_\ell - \sigma_\ell u \right) \right\vert$    
  $\displaystyle \leq 2 \left\Vert A \right\Vert _2 \left\Vert u_\ell - \sigma_\ell u \right\Vert _2 \,.$    

(ii) Next we express all vectors as linear combinations of a basis of orthonormal eigenvectors of $ A$. Denoting the eigenvalues of $ A$ by $ \lambda= d_1 ,\,d_2,\, \hdots ,\, d_n$ and the coefficients of $ u_\ell$ and $ v_\ell$ by $ x_1 ,\, x_2 ,\, \hdots ,\, x_n$ and $ y_1 ,\, y_2 ,\, \hdots ,\, y_n$ we have

$\displaystyle \lambda_\ell =\sum_{i=1}^n d_i x_i^2, \quad y_i = \frac{1}{d_i-\lambda_\ell} x_i \,. $

(iii) As a last preliminary step, the error is expressed in terms of the coordinates. By orthonormality, because of the normalization $ x_1^2+ \cdots + x_n^2=1$ and since $ x_1 \sigma_\ell = \left\vert x_1 \right\vert,$ we have

$\displaystyle \left\Vert u_\ell - \sigma_\ell u \right\Vert _2 = \sqrt{\left(x_1-\sigma_\ell\right)^2+\sum_{i=2}^n x_i^2} = \sqrt{2-2\sqrt{1-\epsilon^2}} $

with $ \epsilon^2=\sum\limits_{i=2}^n x_i^2$. Assuming that

$\displaystyle \frac{1}{2} \leq \left\vert x_1 \right\vert^2 = 1- \epsilon^2 \leq 1 \,, $

by the mean value theorem, the square root equals

$\displaystyle \sqrt{\epsilon^2/\sqrt{t}} \,, \quad t \in \left[ 1/2, 1 \right]. $

Hence, with

$\displaystyle p_\ell = \max_{2 \leq i \leq n} \left\vert \frac{x_i}{x_1} \right\vert, $

the square root can be bounded by

$\displaystyle \frac{1}{2} p_\ell \leq t^{-1/4} \epsilon \leq 2^{1/4} \sqrt{n} \, p_\ell\,. $

Hence, $ \left\Vert u_\ell - \sigma_\ell u \right\Vert _2$ and $ p_\ell$ are asymptotically equivalent, the latter quantity being independent of the normalization.

(iv) The proof of

$\displaystyle p_{\ell+1} \leq c p_\ell^3, $

which implies the cubic convergence, is now straightforward. By (ii), we have

$\displaystyle p_{\ell+1} = \max_{2 \leq i \leq n} \left\vert y_i/y_1\right\vert... ...\vert d_1 - \lambda_\ell \right\vert}{\left\vert x_1 \right\vert} \right] \,. $

Substituting $ \lambda_\ell= \sum\limits_{i=1}^n d_i x_i^2$ and using that $ \sum\limits_{i=1}^n x_i^2=1$, the term in brackets can be bounded by

$\displaystyle \left[ \hdots \right] \leq \frac{\left\vert x_i \right\vert}{\lef... ...s_{k=2}^n \left\vert d_i-d_k \right\vert \left\vert x_k/x_1 \right\vert^2}. $

Since $ \lambda=d_1$ is simple,

$\displaystyle 0 < \gamma \leq \left\vert d_i-d_1 \right\vert \leq 2 \left\Vert A \right\Vert _2 \,. $

Therefore,

$\displaystyle \left[ \hdots \right] \leq p_\ell \frac{2 \left\Vert A \right\Ver... ... \gamma -2 \left\Vert A \right\Vert _2 p_\ell^2} = O\left(p_\ell^3 \right) $

as claimed.

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