Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag

Mathematics-Online lexicon:

QR-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 QR-iteration approximates an eigenvalue of a matrix $ A$ in Hessenberg form with the aid of a sequence of orthogonal similarity transformations

$\displaystyle A_\ell \mapsto A_{\ell+1} = Q_{\ell +1}^t A_\ell Q_{\ell+1} \,, \quad
A_0=A\,.
$

The matrix $ Q_{\ell+1}$ is defined by the QR-decomposition

$\displaystyle A_\ell - \lambda_\ell E = Q_{\ell +1} R_{\ell +1}
$

with the diagonal shift $ \lambda_\ell$ the eigenvalue of the $ 2 \times 2$ submatrix $ A_\ell \left(n-1:n,n-1:n\right)$ closest to $ A_\ell \left(n,n \right)$:

$\displaystyle \lambda_\ell = \frac{d_+}{2} + \frac{\sigma }{2}
\sqrt{d_-^2+4 A_\ell \left(n,n-1\right) A_\ell \left( n-1,n \right)}
$

where

$\displaystyle d_\pm$ $\displaystyle = A_\ell \left( n,n \right) \pm 
 A_\ell \left( n-1,n-1 \right)$    
$\displaystyle \sigma$ $\displaystyle = 
 \left\{ 
 \begin{array}{cl}
 \mbox{sign} \left( d_- \right) \,, & \mbox{if } d_- \neq 0 \\ 
 1 \,, & \mbox{if } d_-=0 \,.
 \end{array}
 \right.$    

Moreover, zero diagonals of the Hessenberg form are preserved. In particular, for syymetric $ A$, all matrices $ A_\ell$ are tridiagonal.

As $ \ell\to\infty$, the off-diagonal entry $ A_\ell ( n,n-1)$ converges to zero and, as a consequence, $ A_\ell (n,n)$ approaches an eigenvalue $ \lambda$ of $ A$. Moreover, for symmetric $ A$ the convergence is locally cubic.

If the iteration has converged, i. e., if the last off-diagonal entry of $ A_\ell$ is zero within tolerance, the process is applied to the submatrix $ A_\ell (1:n-1,1:n-1)$. Thus, eventually, all eigenvalues are computed.

(Authors: Höllig/Pfeil/Walter)

[Examples] [Links]

  automatically generated 4/24/2007