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 [Graphics:Images/QRmethodMod_gr_1.gif]. The important step the QR method is the factorization [Graphics:Images/QRmethodMod_gr_2.gif] and iteration [Graphics:Images/QRmethodMod_gr_3.gif].

Definition (QR Decomposition): For a nonsingular square matrix [Graphics:Images/QRmethodMod_gr_4.gif], there exists a factorization

[Graphics:Images/QRmethodMod_gr_5.gif]

where [Graphics:Images/QRmethodMod_gr_6.gif] is a unitary and [Graphics:Images/QRmethodMod_gr_7.gif] is an upper triangular matrix.

Remark: [Graphics:Images/QRmethodMod_gr_8.gif] is a unitary means [Graphics:Images/QRmethodMod_gr_9.gif].

For a real nonsingular square matrix [Graphics:Images/QRmethodMod_gr_10.gif], there exists a factorization

[Graphics:Images/QRmethodMod_gr_11.gif]

where [Graphics:Images/QRmethodMod_gr_12.gif] is an orthogonal matrix and [Graphics:Images/QRmethodMod_gr_13.gif] is an upper triangular matrix.

Remark: [Graphics:Images/QRmethodMod_gr_14.gif] is a orthogonal means [Graphics:Images/QRmethodMod_gr_15.gif] (also [Graphics:Images/QRmethodMod_gr_16.gif]).

QR transformation

After finding the [Graphics:Images/QRmethodMod_gr_84.gif] factorization, the [Graphics:Images/QRmethodMod_gr_85.gif] transformation is

[Graphics:Images/QRmethodMod_gr_86.gif].


We now investigate a well known and efficient method for finding all the eigenvalues of a general [Graphics:Images/QRmethodMod_gr_88.gif] real matrix. The [Graphics:Images/QRmethodMod_gr_89.gif] method can be used for an arbitrary real matrix, but for a general matrix it takes many iterations and becomes time consuming.

The [Graphics:Images/QRmethodMod_gr_90.gif] 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 [Graphics:Images/QRmethodMod_gr_91.gif] real symmetric matrices.

When solving for eigenvalues of a dense symmetric matrix [Graphics:Images/QRmethodMod_gr_92.gif], the standard practice is to reduce the dense matrix to a tridiagonal matrix [Graphics:Images/QRmethodMod_gr_93.gif] through a series of orthogonal transformations, and then to apply an eigenvalue solver for tridiagonal matrices to [Graphics:Images/QRmethodMod_gr_94.gif]. The transformations applied to [Graphics:Images/QRmethodMod_gr_95.gif] preserve eigenvalues, and the eigenvalues of [Graphics:Images/QRmethodMod_gr_96.gif] and [Graphics:Images/QRmethodMod_gr_97.gif] are the same.

The popular eigenvalue solver for symmetric tridiagonal matrices is called the implicit[Graphics:Images/QRmethodMod_gr_98.gif] method. It applies a series of orthogonal transformations [Graphics:Images/QRmethodMod_gr_99.gif] to a tridiagonal matrix [Graphics:Images/QRmethodMod_gr_100.gif] which converges to a diagonal matrix [Graphics:Images/QRmethodMod_gr_101.gif]. Furthermore, [Graphics:Images/QRmethodMod_gr_102.gif] has the same eigenvalues as [Graphics:Images/QRmethodMod_gr_103.gif] which are the diagonal elements of [Graphics:Images/QRmethodMod_gr_104.gif]. In addition, the product of the orthogonal transformations [Graphics:Images/QRmethodMod_gr_105.gif] is a matrix whose columns are the eigenvectors of [Graphics:Images/QRmethodMod_gr_106.gif]. The method is called [Graphics:Images/QRmethodMod_gr_107.gif] because in each iteration the [Graphics:Images/QRmethodMod_gr_108.gif] factorization is computed. The LAPACK routine implementing the implicit [Graphics:Images/QRmethodMod_gr_109.gif] algorithm on tridiagonal symmetric matrices is called DSTEQR.

QR Algorithm: The pseudocode for the QR method is:

1. i = 0
2. [Graphics:Images/QRmethodMod_gr_110.gif]
3. repeat
4. Factor [Graphics:Images/QRmethodMod_gr_111.gif]
5. [Graphics:Images/QRmethodMod_gr_112.gif]
6. i = i+1
7. until convergence

No comments:

Post a Comment

Introductory Methods of Numerical Analysis