Shifting

Remember that the equation:

$$\boldsymbol{A}\cdot\boldsymbol{x} = \lambda\boldsymbol{x}$$

defines $\lambda_i$ up to a constant. That is, you can add the same constant to all $\lambda_i$ and still have the same x_i 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

$$a_{ij}^{(s)}\sim \left(\frac{\lambda_i}{\lambda_j}\right)^s$$

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:

$$\boldsymbol{A}_s - k_s\boldsymbol{1} = \boldsymbol{Q}_s\cdot\boldsymbol{L}_s$$

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

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

So, we can always reconstruct A_s+1 by performing

$$\boldsymbol{A}_{s+1} = \boldsymbol{L}_s\cdot\boldsymbol{Q}_s + k_s \boldsymbol{1}$$

But the convergence in this procedure will be given by

$$\frac{\lambda_i - k_s}{\lambda_j - k_s}$$

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 k_s to the $\lambda_i$ that is closer to a₁₁.

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 P_pq can be used and are cheaper. A sequence of

$$\boldsymbol{P}_{12}, \boldsymbol{P}_{23}, \boldsymbol{P}_{34}, \ldots$$

will eliminate

$$a_{12}, a_{23}, a_{34}, \ldots$$

and

$$a_{21}, a_{32}, a_{43}, \ldots$$

The resulting Q^T will therefore be:

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