Background for 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 ).  

Example 1.  Find the QR decomposition of the matrix  .  
Solution 1.

Example 2.  Find the    decomposition of the matrix  .  
2 (a).  Perform the computation using decimal arithmetic.  
2 (a).  Perform the computation using exact arithmetic.  
Solution 2 (a).
Solution 2 (b).

QR transformation

    After finding the    factorization, the transformation is  

        .   

Remark.  We will not write our own subroutine for finding the     factorization, we will use Mathematica's subroutine.   

QR Method

    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  

Proof  The QR Method  The QR Method  

Computer Programs  The QR Method  The QR Method  

Mathematica Subroutine (QR method).  To reduce the    real tri-diagonal matrix     to diagonal form.  

Example 3.  Apply the QR method to transform the tri-diagonal matrix     into diagonal matrix D that has the same eigenvalues.  
Solution 3.

Reduction to Hessenberg Form

    We need to find the Hessenberg form.  Suppose that is a symmetric matrix.  Start with

      

Construct the sequence    of Householder matrices, so that

       for   ,  

where has zeros below the subdiagonal in columns  .  Then    is a Hessenberg matrix that is similar to . This process is called Householder’s method.

    We are most interested in finding eigenvalues of symmetric matrices.  If  A  is symmetric, then the above process will construct a symmetric tri-diagonal matrix. we will build on this theme. As mentioned previously, the QR iteration will work faster on tri-diagonal matrices  

Proof  The QR Method  The QR Method  

Computer Programs  The QR Method  The QR Method  

Mathematica Subroutine (Householder reduction to upper-Hessenberg Form).  To reduce the    real matrix    to Hessenberg form by using   Householder transformations. The following version of the program uses "loops" extensively and is more traditional in programming structure.  It also contains a print statement so that you can watch the Householder transformations perform their "magic."  

Example 4.  Apply the QR method and find the eigenvalues of the following matrix  .  
Solution 4.

Acceleration shifts for the QR method

    As outlined above QR method will work, but convergence is slow, even for matrices of small dimension.  We can add a shifting technique that speeds up the rate of convergence.  Recall that if   is an eigenvalue of  A, then    is an eigenvalue of the matrix  . This idea is incorporated in the modified step  

        
then form
            for   ,  

where    is a sequence whose sum is  ;  that is, .

Proof  The QR Method  The QR Method  

Computer Programs  The QR Method  The QR Method  

Mathematica Subroutine (QR method with shifts).  To reduce the    real tri-diagonal matrix to diagonal form.  

Example 5.  Apply the QR method with shifts and find the eigenvalues of the following matrix  .  
Solution 5.

Application of the QR Factorization to "least squares"

    Is is common practice to use the  A = QR  factorization for underdetermined system and get a "least squares solution."   We will illustrate the method for the problem of finding a "least squares parabola."

An overdetermined system of equations will arise which does not have a solution

        MX = B  

The QR factorization of  M  is obtained  ,  and we "wish" to solve
        
          

Multiplication on the left by    produces the system  

        

which we will be able to solve in the form

        .  

The details in Example 7 will make clear what is happening.

Example 6.  Find the "least squares parabola" through the six points  .  
Use Mathematica's subroutine Fit to find the solution.
Solution 6.

Example 7.  Find the "least squares parabola" through the six points  .  Write down six equations in three unknowns that we "wish" could be solved.  Observe that this is an underdetermined system and envision a "least squares solution."   
Use the A = QR factorization to get a "least squares solution. "
Solution 7.

Research Experience for Undergraduates

The QR Method  The QR Method  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook The QR Method for Eigenvalues

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004