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
will thus have a form:
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:
row of this equation can be written as
Once we know
we can evaluate :
Quod erat demonstrandum.
The lemma is used by observing that equation:
Once we have
QTs we form the next iterate
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.