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:
“All objects, all phases of culture are alive. They have voices. They speak of their history and interrelatedness. And they are all talking at once!”
—Camille Paglia (b. 1947)
“Whenever we read the obscene stories, the voluptuous debaucheries, the cruel and torturous executions, the unrelenting vindictiveness, with which more than half the Bible is filled, it would be more consistent that we called it the word of a demon than the Word of God. It is a history of wickedness that has served to corrupt and brutalize mankind.”
—Thomas Paine (1737–1809)
“The only history is a mere question of one’s struggle inside oneself. But that is the joy of it. One need neither discover Americas nor conquer nations, and yet one has as great a work as Columbus or Alexander, to do.”
—D.H. (David Herbert)