History
The QR algorithm was preceded by the LR algorithm, which uses the LU decomposition instead of the QR decomposition. The QR algorithm is more stable, so the LR algorithm is rarely used nowadays. However, it represents an important step in the development of the QR algorithm.
The LR algorithm was developed in the early 1950s by Heinz Rutishauer, who worked at that time as a research assistant of Eduard Stiefel at ETH Zurich. Stiefel suggested that Rutishauer use the sequence of moments y0T Ak x0, k = 0, 1, … (where x0 and y0 are arbitrary vectors) to find the eigenvalues of A. Rutishauer took an algorithm of Alexander Aitken for this task and developed it into the quotient–difference algorithm or qd algorithm. After arranging the computation in a suitable shape, he discovered that the qd algorithm is in fact the iteration Ak = LkUk (LU decomposition), Ak+1 = UkLk, applied on a tridiagonal matrix, from which the LR algorithm follows.
Read more about this topic: QR Algorithm
Famous quotes containing the word history:
“The history of all hitherto existing society is the history of class struggles.”
—Karl Marx (1818–1883)
“Tell me of the height of the mountains of the moon, or of the diameter of space, and I may believe you, but of the secret history of the Almighty, and I shall pronounce thee mad.”
—Henry David Thoreau (1817–1862)