,
where
and
.
Since is both orthogonal and symmetric, it follows that
.
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) .
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 .
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.
Comments
Post a Comment