next up previous index
Next: QL Algorithm with Implicit Up: The QR and QL Previous: The QR and QL

Shifting

Remember that the equation:

\begin{displaymath}\boldsymbol{A}\cdot\boldsymbol{x} = \lambda\boldsymbol{x}
\end{displaymath}

defines $\lambda_i$ up to a constant. That is, you can add the same constant to all $\lambda_i$ and still have the same xi solving the equation above. In physics, for example, this translates into the statement that energy is defined up to an additive constant, or that there is no absolute zero for energy. And energy levels in Quantum Mechanics are eigenvalues of the Hamiltonian.

The rate with which off-diagonal elements converge to zero in the QL sequence is given by

\begin{displaymath}a_{ij}^{(s)}\sim \left(\frac{\lambda_i}{\lambda_j}\right)^s
\end{displaymath}

which explains why it is so hard to kill off-diagonal terms that correspond to degenerate eigenvalues. If two eigenvalues $\lambda_i$ and $\lambda_j$ are very close then convergence can be slow. This convergence can be accelerated by decomposing:

\begin{displaymath}\boldsymbol{A}_s - k_s\boldsymbol{1} = \boldsymbol{Q}_s\cdot\boldsymbol{L}_s
\end{displaymath}

instead of As. The QL transformation of this equation now yields:

\begin{displaymath}\boldsymbol{L}_s\cdot\boldsymbol{Q}_s = \boldsymbol{Q}_s^T \c...
... k_s \boldsymbol{1}= \boldsymbol{A}_{s+1} - k_s \boldsymbol{1}
\end{displaymath}

So, we can always reconstruct As+1 by performing

\begin{displaymath}\boldsymbol{A}_{s+1} = \boldsymbol{L}_s\cdot\boldsymbol{Q}_s +
k_s \boldsymbol{1}
\end{displaymath}

But the convergence in this procedure will be given by

\begin{displaymath}\frac{\lambda_i - k_s}{\lambda_j - k_s}
\end{displaymath}

and by choosing $k_s \approx \lambda_j$ we can, in principle, speed it up enormously.

But the difficulty is that we don't know what $\lambda_j$ is going to be!

A common strategy is to compute the eigenvalues of the leading $2\times2$ diagonal submatrix of A and then set ks to the $\lambda_i$ that is closer to a11.

One can show that the convergence here is cubic or at worst quadratic if eigenvalues are degenerate.

Although in general the QL decomposition is obtained by a sequence of Householder transformations, for a tridiagonal matrix Jacobi rotations Ppq can be used and are cheaper. A sequence of

\begin{displaymath}\boldsymbol{P}_{12}, \boldsymbol{P}_{23}, \boldsymbol{P}_{34}, \ldots
\end{displaymath}

will eliminate

\begin{displaymath}a_{12}, a_{23}, a_{34}, \ldots
\end{displaymath}

and

\begin{displaymath}a_{21}, a_{32}, a_{43}, \ldots
\end{displaymath}

The resulting QT will therefore be:

\begin{displaymath}\boldsymbol{Q}^T_s = \boldsymbol{P}^{(s)}_{1,2}\cdot
\boldsy...
...l{P}^{(s)}_{3,4}\cdot\ldots\cdot
\boldsymbol{P}^{(s)}_{n-1,n}
\end{displaymath}


next up previous index
Next: QL Algorithm with Implicit Up: The QR and QL Previous: The QR and QL
Zdzislaw Meglicki
2001-02-26