It is well known that Francis' QR algorithm for computing eigenvalues
emerged from Rutishauser's LR algorithm, but it is less obvious how
Rutishauser discovered the matrix interpretation of his qd algorithm,
which is just the LR algorithm for tridiagonal matrices, and it is
far from obvious how he discovered the qd algorithm in the first place.
There are various ways to derive the latter and to detect its
property of approaching eigenvalues of the matrix.
Rutishauser was well educated in classical complex analysis, and he
built on previous independent work of Hadamard and Aitken.
Stiefel provided another elegant derivation based on continued
fractions. And at some point Rutishauser must have realized that
his rhombus rules of the progressive qd algorithm can be viewed as
LR transformation of a tridiagonal matrix.


References: Martin H. Gutknecht and Beresford N. Parlett. From qd to LR and QR, or, How were the qd and LR algorithms discovered? IMA J. Numer. Anal., advanced access, May 27, 2010.


[Invited by Prof. Jean-Paul Berrut]