Householder Transformations , Householder's Method

http://mathfaculty.fullerton.edu/mathews/n2003/HouseholderMod.html

Module for
Householder Transformations      
Householder's Method

    Each transformation in Jacobi's method produced two zero off-diagonal elements, but subsequent iterations might make them nonzero. Hence many iterations are required to make the off-diagonal entries sufficiently close to zero.
   
    Suppose that A is a real symmetric matrix.  Householder's method is used to construct a similar symmetric tridiagonal matrix.  Then the QR method can be used to find all eigenvalues of the tridiagonal matrix. 
   
    We now develop the method attributed to Alston Scott Householder (May 5, 1904 - July4, 1993) which is routinely taught in courses in linear algebra, and numerical analysis. Several several zero off-diagonal elements are created with each iteration, and they remain zero in subsequent iterations. We start by developing an important step in the process.

Theorem (Householder Reflection)  If and are vectors with the same norm, there exists an orthogonal symmetric matrix such that

            , 
        where
              
        and
            . 

Since is both orthogonal and symmetric, it follows that

            .  
Proof  Householder Method

Remark.  It should be observed that the effect of the mapping is to reflect through the line whose direction is , hence the name Householder reflection.
Corollary ( Householder Matrix)  Let be an matrix, and any vector.  If is an integer with , we can construct a vector and matrix    so that 

(1)             .  
Proof  Householder Method

Householder Transformations

    Suppose that is a symmetric matrix. Then a sequence of transformations of the form    will reduce to a symmetric tridiagonal matrix.  Let us visualize the process when .  The first transformation is defined to be  ,  where is constructed by applying the above Corollary with the vector being the first column of the matrix .  The general form of is

             

where the letter stands for some element in .  As a result, the transformation    does not affect the element of :

(2)            . 
    The element denoted is changed because of premultiplication by , and is changed because of postmultiplication by ; since is symmetric, we have .  The changes to the elements denoted    have been affected by both premultiplication and postmultiplication.  Also, since is the first column of , equation (1) implies that  . 

    The second Householder transformation is applied to the matrix defined in (2) and is denoted  ,  where is constructed by applying the Corollary with the vector being the second column of the matrix .  The form of is

              

where stands for some element in .  The identity block in the upper-left corner ensures that the partial tridiagonalization achieved in the first step will not be altered by the second transformation .  The outcome of this transformation is 

(3)            . 
    The elements and were affected by premultiplication and postmultiplication by .  Additional changes have been introduced to the other elements by the transformation.  The third Householder transformation,  ,  is applied to the matrix defined in (3) where the Corollary is used with being the third column of .  The form of is 

              

Again, the identity block ensures that    does not affect the elements of , which lie in the upper corner, and we obtain


            .  

Thus it has taken three transformations to reduce to tridiagonal form.  
    In general, for efficiency, the transformation    is not performed in matrix form.  The next result shows that it is more efficiently carried out via some clever vector manipulations.

Theorem (Computation of One Householder Transformation)  If is a Householder matrix, the transformation    is accomplished as follows.  Let 

        Let         and compute

                 
        and
               ,  
   
        then       .   
Proof  Householder Method

Reduction to Tridiagonal 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 symmetric tridiagonal matrix that is similar to .  This process is called Householder's method.
Example 1.  Use Householder's method to reduce the symmetric matrix    to symmetric tridiagonal form. 
Solution 1.

Algorithm

    Let us combine the steps used in Example 1 and make an algorithm for performing one Householder transformation.
Mathematica Subroutine (One Householder Transformation).  To reduce the symmetric matrix to tridiagonal form by using Householder transformations.

Example 2.  Use the Householder step algorithm to reduce the symmetric matrix    to symmetric tridiagonal form. 
Solution 2.

Exercise 3.  Use the Householder step algorithm to reduce the symmetric matrix    to symmetric tridiagonal form. 
Solution 3.

Exercise 4.  Use the Householder step algorithm to reduce the symmetric matrix    to symmetric tridiagonal form. 
Solution 4.

Traditional Programming

    We now present a version of the Householder program that uses traditional more traditional loops to perform the computations.  It also takes into consideration that once a portion of the tridiagonal structure has been created one only needs to continue the process on the submatrix below and to the right.  This program will be harder to read, but might prove to be more efficient when the size of the matrix is larger. 
Computer Programs  Householder Method
Mathematica Subroutine (Householder Reduction to Tridiagonal Form).  To reduce the symmetric matrix to tridiagonal form by using Householder transformations.

Exercise 5.  Use traditional Householder subroutine to reduce the symmetric matrix    to symmetric tridiagonal form. 
Solution 5.

Research Experience for Undergraduates
Householder Method  Internet hyperlinks to web sites and a bibliography of articles. 

Download this Mathematica Notebook Householder Method