next up previous index
Next: Example Code Up: The QR and QL Previous: Shifting

QL Algorithm with Implicit Shifts

In this algorithm we begin by applying a Jacobi rotation, from the left hand side only, whose purpose is to annihilate An-1, n, i.e., the last superdiagonal element.

This rotation will usually screw the tridiagonal form, so the tridiagonal form must be restored either by using a Housholder or a Givens transformation. It turns out that a single Givens transformation won't do though: it must be followed by a serious of those, so as to comb away the non-tridiagonal terms. A single iteration $\bar{\boldsymbol{Q}}^T$ will thus have a form:

\begin{displaymath}\bar{\boldsymbol{Q}}^T_s = \bar{\boldsymbol{P}}_1^{(s)}
\cd...
...\boldsymbol{P}}_{n-2}^{(s)}
\cdot\boldsymbol{P}_{n-1}^{(s)}
\end{displaymath} (3.57)

where Pn-1(s) is the corresponding Jacobi rotation and $\bar{\boldsymbol{P}}_{n-2}^{(s)}$ (with a bar) are Givens transformations that re-tridiagonalize the matrix.

Now, the question is if this transformation Qis going to be a correct Q for a QLiteration. There is a tricky lemma, which proves that this is indeed the case:

lemma
$\,$
If A is a symmetric nonsingular matrix and $\boldsymbol{B} = \boldsymbol{Q}^T\cdot\boldsymbol{A}\cdot\boldsymbol{Q}$, where Q is orthogonal and B is tridiagonal, not necessarily symmetric, with positive off-diagonal terms, then Q and B are fully determined by the last row of QT.
proof
$\,$
Let q1 through qn be the rows of matrix QT:

\begin{displaymath}\boldsymbol{Q}^T =
\left(
\begin{array}{c}
\boldsymbol{q}_...
...l{q}_2 \\
\vdots \\
\boldsymbol{q}_n
\end{array} \right)
\end{displaymath}

Since Q is orthogonal, $\boldsymbol{B} = \boldsymbol{Q}^T\cdot\boldsymbol{A}\cdot\boldsymbol{Q}$ can be multiplied by QT from the right yielding:

\begin{displaymath}\boldsymbol{B}\cdot\boldsymbol{Q}^T
= \boldsymbol{Q}^T\cdot\boldsymbol{A}
\end{displaymath}

This can be written down in some detail as

\begin{displaymath}\left(
\begin{array}{ccccccc}
\beta_1 & \gamma_1 & & & & & ...
... \boldsymbol{q}_n
\end{array} \right)
\cdot
\boldsymbol{A}
\end{displaymath}

The $n^{\hbox{\scriptsize {th}}}$ row of this equation can be written as

\begin{displaymath}\alpha_n \boldsymbol{q}_{n-1} + \beta_n \boldsymbol{q}_n
= \boldsymbol{q}_n \cdot \boldsymbol{A}
\end{displaymath}

The rows qi of matrix Q are orthonormal to each other, so if we multiply the above equation from the right by qnT, we get:

\begin{displaymath}\beta_n = \boldsymbol{q}_n \cdot \boldsymbol{A} \cdot \boldsymbol{q}_n^T
\end{displaymath}

Once we know $\beta_n$ we can evaluate $\alpha_n$:

\begin{displaymath}\alpha_n \boldsymbol{q}_{n-1} = \boldsymbol{q}_n \cdot \boldsymbol{A}
- \beta_n \boldsymbol{q}_n = \boldsymbol{z}_{n-1}
\end{displaymath}

Using orthonormality of qi:

\begin{displaymath}\alpha_n^2 = \boldsymbol{z}_{n-1} \cdot \boldsymbol{z}_{n-1}
\end{displaymath}

and

\begin{displaymath}\alpha_n = \vert \boldsymbol{z}_{n-1} \vert
\end{displaymath}

And, therefore

\begin{displaymath}\boldsymbol{q}_{n-1} = \boldsymbol{z}_{n-1} / \alpha_n
\end{displaymath}

We can now climb up towards $\beta_1$ and $\gamma_1$ reconstructing the whole B and Q in this way.

Quod erat demonstrandum.

The lemma is used by observing that equation:

\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}

which defines the iterative procedure for the QLmethod implies that the last row of $\bar{\boldsymbol{Q}}^T$, which is determined solely by P(s)n-1,n, is the same as the last row of QTs.

Once we have QTs we form the next iterate As+1by:

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

In this method not only are shifts implicit. The QLalgorithm itself is masked. We rely on the lemma to demonstrate that the computation, which at first glance looks quite different, is equivalent to a QL algorithm.


next up previous index
Next: Example Code Up: The QR and QL Previous: Shifting
Zdzislaw Meglicki
2001-02-26