Cleve Moler is the author of the first MATLAB, one of the founders of MathWorks, and is currently Chief Mathematician at the company. He is the author of two books about MATLAB that are available online. He writes here about MATLAB, scientific computing and interesting mathematics.
The QR algorithm is one of the world's most successful algorithms. We can use animated gifs to illustrate three variants of the algorithm, one for computing the eigenvalues of a nonsymmetric matrix, one for a symmetric matrix, and one for the singular values of a rectangular matrix. In all three cases, the QR iteration itself is preceded by a reduction to a compact form. All transformations are orthogonal similarities using Givens and Householder transformations. These are numerically stable, preserve eigenvalues, and preserve any symmetry.
Here is a static picture of the starting matrix. Notice that it is not symmetric.
The initial reduction uses n-2 Householder similarites to introduce zeroes below the subdiagonal a column at a time. The result is known as a Hessenberg matrix (don't let spell-checkers change that to Heisenberg matrix.)
Now the QR algorithm gradually reduces most subdiagonal elements to roundoff level, so they can be set to zero. The corresponding diagonal element is an eigenvalue. The iteration count is shown in the title. The element below the diagonal in the last row is the initial target; it requires four iterations. The next two rows require three iterations each. The remaining subdiagonals require just one or two iterations each.
All this is done with real arithmetic, although a real, nonsymmetric matrix may have complex eigenvalues. So the final matrix may have 2-by-2 bumps on the diagonal. This example has one bump in rows 3 and 4. The eigenvalues of a bump are a complex conjugate pair of eigenvalues of the input matrix. All the other diagonal elements are real eigenvalues of the input matrix.
The computed eigenvalues are:
Here is the static picture. (The computation is done on half of the matrix, but we show the entire array.)
By symmetry the six Householders that zero the columns also zero the rows.
Now the QR iteration works on just two vectors, the diagonal and the off-diagonal.
The limit is the diagonal containing the eigenvalues.
Use a Householder operating from the left to zero a column and then another Householder operating from the right to zero most of a row.
Now a two-sided QR iteration reduces the off diagonal to negligible size.
The resulting diagonal contains the singular values.