The QR Transformation A Unitary Analogue to the LR Transformation--Part 1

The LR transformation, due to Rutishauser, has proved to be a powerful method for finding the eigenvalues of symmetric band matrices. Little attention, however, has been paid to its application to the more difficult problem of finding eigenvalues of general unsymmetric matrices. If the matrices are large two important difficulties are likely to occur. Firstly, triangular decomposition, which is the basis of the method, is by no means always numerically stable, and secondly, the amount of computation required by the method is likely to be very great. This paper describes an algorithm similar to the LR transformation except that the transformations involved in it are all unitary and can thus be expected to by numerically stable. It is then shown that there are various advantages in first converting the matrix to almost-triangular form; in particular, the amount of work involved in the algorithm can then be greatly reduced. Part 1 of the paper is largely concerned with proof of convergence, and the theoretical aspect. Part 2, to be published in January, discussed practical computation and gives results of experiments.