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 A_{n-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:

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

where P_n-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 Q^T.

proof

$\,$
Let q₁ through q_n be the rows of matrix Q^T:

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

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

$$\boldsymbol{B}\cdot\boldsymbol{Q}^T = \boldsymbol{Q}^T\cdot\boldsymbol{A}$$

This can be written down in some detail as

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

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

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

The rows q_i of matrix Q are orthonormal to each other, so if we multiply the above equation from the right by q_n^T, we get:

$$\beta_n = \boldsymbol{q}_n \cdot \boldsymbol{A} \cdot \boldsymbol{q}_n^T$$

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

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

Using orthonormality of q_i:

$$\alpha_n^2 = \boldsymbol{z}_{n-1} \cdot \boldsymbol{z}_{n-1}$$

and

$$\alpha_n = \vert \boldsymbol{z}_{n-1} \vert$$

And, therefore

$$\boldsymbol{q}_{n-1} = \boldsymbol{z}_{n-1} / \alpha_n$$

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:

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

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 Q^T_s.

Once we have Q^T_s we form the next iterate A_s+1by:

$$\boldsymbol{A}_{s+1} = \boldsymbol{Q}^T_s\cdot\boldsymbol{A}_s\cdot\boldsymbol{Q}_s$$

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.