Department of Computer ScienceUniversity of Illinois at Urbana-Champaign
201 North Goodwin Avenue, Urbana, IL 61801
This module demonstrates QR iteration with shifts for computing all the eigenvalues and eigenvectors of a matrix. Starting with a given matrix, the QR factorization of the current matrix is computed at each iteration, the new matrix is then given by the reverse product RQ of the Q and R factors, and the process is repeated. The resulting sequence of orthogonally similar matrices converges to triangular form, with the eigenvalues as diagonal entries, and the eigenvectors can be recovered from the product of all the orthogonal factors. Scalar shifts can be used to accelerate convergence.
The user first selects a matrix size, then selects a matrix by choosing a preset example, a random matrix, or typing desired entries into the array on the left. The successive steps of QR iteration are then carried out sequentially by repeatedly clicking on NEXT or on the currently highlighted step. At each iteration, the user can select the Rayleigh quotient shift, the Wilkinson shift, or can enter any desired value for the shift. Changes in the matrix are shown in the array on the left, while the two arrays on the right show the computed Q and R factors. QR iteration converges to (block) upper triangular form for a nonsymmetric matrix, or to diagonal form for a symmetric matrix. The computed eigenvalues are the diagonal entries (or eigenvalues of the diagonal blocks), while the computed eigenvectors are given by the columns of the product of the successive Q matrices (though the latter is not shown).
Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 4.5.6, especially Algorithm 4.8 and Example 4.16.
Developers: Jeffrey Naisbitt and Michael Heath