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]

When? | 10.05.2011 17:15 |
---|---|

Where? | PER 08 Phys 2.52 Chemin du Musée 3 1700 Fribourg |

Contact | Department of Mathematics isabella.schmutz@unifr.ch |