Understanding the $QR$ Algorithm
David S. Watkins · SIAM Review · 1982
The $QR$ algorithm is currently the most popular method for finding all eigenvalues of a full matrix. While $QR$ is now well understood by specialists in eigenvalue computations, this understanding is not being conveyed effectively to the mathematical public. Many accounts present Wilkinson’s 1965 convergence proof. Others establish some of the connections between the $QR$ algorithm, the power method and inverse iteration. Usually much emphasis is (rightly) placed on the refinements, such as shifts of origin, which are required to make the algorithm competitive. But practically all accounts fail to explain the basic meaning of $QR$ iterations. As a consequence, the $QR$ algorithm is widely thought to be difficult to understand. The purpose of this paper is to try to convince the reader that the opposite is true. In fact, the $QR$ algorithm is neither more nor less than a clever implementation of simultaneous iteration, which is itself a natural, easily understood extension of the power method. This point of view deserves pre-eminence because it shows exactly what $QR$ iterations are and evokes a clear geometric picture of the $QR$ process. Furthermore, it provides a framework within which the rapid convergence associated with shifts of origin may be explained. No reference to inverse iteration is necessary. Inverse iteration has not, however, been banished from the paper—one section is devoted to an explanation of the interplay between inverse iteration, direct iteration and the $QR$ algorithm. The key result of that section is a duality theorem which shows that whenever direct iteration takes place, inverse iteration automatically takes place at the same time.