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

Implementation of the 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
One step $ A \mapsto B$ of the tridiagonal $ QR$-iteration with shift $ \lambda$ computes a sparsity preserving $ QR$-factorization,

$\displaystyle A-\lambda E = QR $

and forms

$\displaystyle B=RQ +\lambda E =Q^{\operatorname t} A Q \,. $

It can be implemented as follows. First, a Givens rotation $ Q_1^{\operatorname t} $ based on the vector $ (a_{1,1} - \lambda ,\, a_{2,1})^{\operatorname t}$ is applied to rows one and two from the left and $ Q_1$ is applied to columns one and two from the right. This destroys the tridiagonal form of $ A$ by introducing an entry in position $ (3,1)$. Now, Givens rotations $ Q_i^{\operatorname t},\, i=2, \hdots ,n-1$ are successively applied to rows $ i$ and $ i+1$ and their transposes $ Q_i$ to the corresponding columns:

$\displaystyle B= Q_{n-1}^{\operatorname t} \cdots Q_{1}^{\operatorname t} A Q_1 \cdots Q_{n-1} \,. $

The transformation $ Q_i^{\operatorname t}$ is based on the vector of the current entries in positions $ (i:i+1,i-1)$. Hence, the similarity transformation with $ Q_i$ restores the tridiagonal form up to column $ i-1$. This process is illustrated schematically below.

$\displaystyle \left( \begin{array}{c} {\mbox{\includegraphics[width=0.2\linewidth,bb=125 619 214 708,clip]{Num_18_2_Bild1}}} \end{array} \right)$ $\displaystyle \stackrel{Q_1}{\longrightarrow} \left( \begin{array}{c} {\mbox... ...8,clip]{Num_18_2_Bild2}}} \end{array} \right) \stackrel{Q_2}{\longrightarrow}$    
$\displaystyle \left( \begin{array}{c} {\mbox{\includegraphics[width=0.2\linewidth,bb=125 619 214 708,clip]{Num_18_2_Bild3}}} \end{array} \right)$ $\displaystyle \stackrel{Q_3}{\longrightarrow} \left( \begin{array}{c} {\mbox... ...214 708,clip]{Num_18_2_Bild4}}} \end{array} \right) \longrightarrow \cdots$    

We have indicated modifications in the entries with different symbols. Moreover, we have highlighted the entries which determine the subsequent Givens rotation. This transformation annihilates the entry in the circled position.

If, accidentally, both entries in position $ (i:i+1,i-1)$ are zero, the $ i$-th transformation can be omitted. In this case, the off-diagonal entry $ b_{i,i-1}$ is zero and the dimension of the eigenvalue problem can be reduced.

(Authors: Höllig/Pfeil/Walter)

Download:

( .m, 1.4K,  24.04.2007)
[Annotations] [Links]
  automatically generated 4/24/2007