Next: QL Algorithm with Implicit Up: The QR and QL Previous: The QR and QL

### Shifting

Remember that the equation:

defines up to a constant. That is, you can add the same constant to all 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

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

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

So, we can always reconstruct As+1 by performing

But the convergence in this procedure will be given by

and by choosing we can, in principle, speed it up enormously.

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

A common strategy is to compute the eigenvalues of the leading diagonal submatrix of A and then set ks to the 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

will eliminate

and

The resulting QT will therefore be:

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