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

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.

We have to show that the implementation of the similarity transformation is consistent with the formulas

$\displaystyle A-\lambda E=QR \,, \quad B=Q^{\operatorname t} A Q $

To this end we denote the Givens transformation for constructing the QR-factorization by $ Q_i$,

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

and the transformations used in the implementation by $ \widetilde{Q}_i$. By construction, $ \widetilde{Q}_1^{\operatorname t}= Q_1^{\operatorname t}$. The other transformations also agree. This follows from the uniqueness of the Givens QR-factorization in case of non-zero off-diagonal entries and the fact that the tridiagonal form is preserved. Indeed, if not both entries in positions $ (i:i+1,i-1)$ are zero, $ \widetilde{Q}_i^{\operatorname t}$ is uniquely determined by the requirement that the tridiagonal form must be restored.

It remains to discuss the exceptional cases. If $ A$ has a zero off-diagonal entry $ a_{i,i-1}$, the dimension of the eigenvalue problem can be reduced:

$\displaystyle \det (A-\lambda E)= \det (A(1,i-1,1:i-1) - \lambda E_{i-1}) \cdot \det (A(i:n,i:n)-\lambda E_{n-i+1}) \,, $

with $ E_k$ the $ k \times k$ unit matrix.

A reduction is also possible, if the entries $ (i:i+1,i-1)$, which determine $ \widetilde{Q}_i^t$, are zero. For arbitrary $ \widetilde{Q}_i^t$, the similarity transformation produces a zero in position $ (i,i-1)$.

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