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)

see also:

[Examples]
  automatically generated 4/24/2007