## Monday, February 1, 2010

### QR method

Suppose that A is a real symmetric matrix. Householder’s method is used to construct a similar tridiagonal matrix. Then the QR method is used to find all eigenvalues of the tridiagonal matrix. In the latter construction, plane rotations similar to those that were introduced in Jacobi’s method are used to construct the orthogonal matrices . The important step the QR method is the factorization and iteration .

Definition (QR Decomposition): For a nonsingular square matrix , there exists a factorization

where is a unitary and is an upper triangular matrix.

Remark: is a unitary means .

For a real nonsingular square matrix , there exists a factorization

where is an orthogonal matrix and is an upper triangular matrix.

Remark: is a orthogonal means (also ).

QR transformation

After finding the factorization, the transformation is

.

We now investigate a well known and efficient method for finding all the eigenvalues of a general real matrix. The method can be used for an arbitrary real matrix, but for a general matrix it takes many iterations and becomes time consuming.

The method works much faster on special matrices, preferably:
(i) symmetric tri-diagonal,
(ii) Hessenberg matrices,
(iii) symmetric band matrices.

For this module, we will illustrate the QR method for real symmetric matrices.

When solving for eigenvalues of a dense symmetric matrix , the standard practice is to reduce the dense matrix to a tridiagonal matrix through a series of orthogonal transformations, and then to apply an eigenvalue solver for tridiagonal matrices to . The transformations applied to preserve eigenvalues, and the eigenvalues of and are the same.

The popular eigenvalue solver for symmetric tridiagonal matrices is called the implicit method. It applies a series of orthogonal transformations to a tridiagonal matrix which converges to a diagonal matrix . Furthermore, has the same eigenvalues as which are the diagonal elements of . In addition, the product of the orthogonal transformations is a matrix whose columns are the eigenvectors of . The method is called because in each iteration the factorization is computed. The LAPACK routine implementing the implicit algorithm on tridiagonal symmetric matrices is called DSTEQR.

QR Algorithm: The pseudocode for the QR method is:

1. i = 0
2.
3. repeat
4. Factor
5.
6. i = i+1
7. until convergence