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 ).
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.
1. i = 0
6. i = i+1
7. until convergence