Report Number: CS-TR-67-56
Institution: Stanford University, Department of Computer Science
Title: QD-method with Newton shift
Author: Bauer, Friedrich L.
Date: March 1967
Abstract: Theoretically, for symmetric matrices, a QR-step is equivalent to two successive LR-steps, and the LR-transformation for a tridiagonal matrix is, apart from organizational details, identical with the qd-method. For non-positive definite matrices, however, the LR-transformation cannot be guaranteed to be numerically stable unless pivotal interchanges are made. This has led to preference for the QR-transformation, which is always numerically stable. If, however, some of the smallest or some of the largest eigenvalues are wanted, then the QR-transformation will not necessarily give only these, and bisection might seem too slow with its fixed convergence rate of 1/2. In this situation, Newton's method would be fine if the Newton correction can be computed sufficiently simply, since it will always tend monotonically to the nearest root starting from a point outside the spectrum. Consequently, if one always worked with positive (or negative) definite matrices, there would be no objection to using the now stable qd-algorithm. The report shows that for a qd-algorithm, the Newton correction can very easily be calculated, and accordingly a shift which avoids under-shooting, or a lower bound. Since the last diagonal element gives an upper bound, the situation is quite satisfactory with respect to bounds.
http://i.stanford.edu/pub/cstr/reports/cs/tr/67/56/CS-TR-67-56.pdf