Monday, February 1, 2010

Householder's Method

If [Graphics:Images/HouseholderMod_gr_1.gif] and [Graphics:Images/HouseholderMod_gr_2.gif] are vectors with the same norm, there exists an orthogonal symmetric matrix [Graphics:Images/HouseholderMod_gr_3.gif] such that

[Graphics:Images/HouseholderMod_gr_4.gif],
where
[Graphics:Images/HouseholderMod_gr_5.gif]
and
[Graphics:Images/HouseholderMod_gr_6.gif].

Since [Graphics:Images/HouseholderMod_gr_7.gif] is both orthogonal and symmetric, it follows that

[Graphics:Images/HouseholderMod_gr_8.gif].

Corollary ([Graphics:Images/HouseholderMod_gr_12.gif] Householder Matrix)

Let [Graphics:Images/HouseholderMod_gr_13.gif] be an [Graphics:Images/HouseholderMod_gr_14.gif] matrix, and [Graphics:Images/HouseholderMod_gr_15.gif] any vector. If [Graphics:Images/HouseholderMod_gr_16.gif] is an integer with [Graphics:Images/HouseholderMod_gr_17.gif], we can construct a vector [Graphics:Images/HouseholderMod_gr_18.gif] and matrix [Graphics:Images/HouseholderMod_gr_19.gif] so that

(1) [Graphics:Images/HouseholderMod_gr_20.gif].

Householder Transformations

Suppose that
[Graphics:Images/HouseholderMod_gr_21.gif] is a symmetric [Graphics:Images/HouseholderMod_gr_22.gif] matrix. Then a sequence of [Graphics:Images/HouseholderMod_gr_23.gif] transformations of the form [Graphics:Images/HouseholderMod_gr_24.gif] will reduce [Graphics:Images/HouseholderMod_gr_25.gif] to a symmetric tridiagonal matrix. Let us visualize the process when [Graphics:Images/HouseholderMod_gr_26.gif]. The first transformation is defined to be [Graphics:Images/HouseholderMod_gr_27.gif], where [Graphics:Images/HouseholderMod_gr_28.gif] is constructed by applying the above Corollary with the vector [Graphics:Images/HouseholderMod_gr_29.gif] being the first column of the matrix [Graphics:Images/HouseholderMod_gr_30.gif]. The general form of [Graphics:Images/HouseholderMod_gr_31.gif] is

[Graphics:Images/HouseholderMod_gr_32.gif]

where the letter
[Graphics:Images/HouseholderMod_gr_33.gif] stands for some element in [Graphics:Images/HouseholderMod_gr_34.gif]. As a result, the transformation [Graphics:Images/HouseholderMod_gr_35.gif] does not affect the element [Graphics:Images/HouseholderMod_gr_36.gif] of [Graphics:Images/HouseholderMod_gr_37.gif]:

(2) [Graphics:Images/HouseholderMod_gr_38.gif].

The element denoted [Graphics:Images/HouseholderMod_gr_39.gif] is changed because of premultiplication by [Graphics:Images/HouseholderMod_gr_40.gif], and [Graphics:Images/HouseholderMod_gr_41.gif] is changed because of postmultiplication by [Graphics:Images/HouseholderMod_gr_42.gif]; since [Graphics:Images/HouseholderMod_gr_43.gif] is symmetric, we have [Graphics:Images/HouseholderMod_gr_44.gif]. The changes to the elements denoted [Graphics:Images/HouseholderMod_gr_45.gif] have been affected by both premultiplication and postmultiplication. Also, since [Graphics:Images/HouseholderMod_gr_46.gif] is the first column of [Graphics:Images/HouseholderMod_gr_47.gif], equation (1) implies that [Graphics:Images/HouseholderMod_gr_48.gif].

The second Householder transformation is applied to the matrix
[Graphics:Images/HouseholderMod_gr_49.gif] defined in (2) and is denoted [Graphics:Images/HouseholderMod_gr_50.gif], where [Graphics:Images/HouseholderMod_gr_51.gif] is constructed by applying the Corollary with the vector [Graphics:Images/HouseholderMod_gr_52.gif] being the second column of the matrix [Graphics:Images/HouseholderMod_gr_53.gif]. The form of [Graphics:Images/HouseholderMod_gr_54.gif] is

[Graphics:Images/HouseholderMod_gr_55.gif]

where
[Graphics:Images/HouseholderMod_gr_56.gif] stands for some element in [Graphics:Images/HouseholderMod_gr_57.gif]. The [Graphics:Images/HouseholderMod_gr_58.gif] 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 [Graphics:Images/HouseholderMod_gr_59.gif]. The outcome of this transformation is

(3) [Graphics:Images/HouseholderMod_gr_60.gif].

The elements [Graphics:Images/HouseholderMod_gr_61.gif] and [Graphics:Images/HouseholderMod_gr_62.gif] were affected by premultiplication and postmultiplication by [Graphics:Images/HouseholderMod_gr_63.gif]. Additional changes have been introduced to the other elements [Graphics:Images/HouseholderMod_gr_64.gif] by the transformation. The third Householder transformation, [Graphics:Images/HouseholderMod_gr_65.gif], is applied to the matrix [Graphics:Images/HouseholderMod_gr_66.gif] defined in (3) where the Corollary is used with [Graphics:Images/HouseholderMod_gr_67.gif] being the third column of [Graphics:Images/HouseholderMod_gr_68.gif]. The form of [Graphics:Images/HouseholderMod_gr_69.gif] is

[Graphics:Images/HouseholderMod_gr_70.gif]

Again, the
[Graphics:Images/HouseholderMod_gr_71.gif] identity block ensures that [Graphics:Images/HouseholderMod_gr_72.gif] does not affect the elements of [Graphics:Images/HouseholderMod_gr_73.gif], which lie in the upper [Graphics:Images/HouseholderMod_gr_74.gif] corner, and we obtain


[Graphics:Images/HouseholderMod_gr_75.gif].

Thus it has taken three transformations to reduce
[Graphics:Images/HouseholderMod_gr_76.gif] to tridiagonal form.

In general, for efficiency, the transformation [Graphics:Images/HouseholderMod_gr_77.gif] 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 [Graphics:Images/HouseholderMod_gr_78.gif] is a Householder matrix, the transformation [Graphics:Images/HouseholderMod_gr_79.gif] is accomplished as follows. Let

Let
[Graphics:Images/HouseholderMod_gr_80.gif] and compute

[Graphics:Images/HouseholderMod_gr_81.gif]
and
[Graphics:Images/HouseholderMod_gr_82.gif],

then
[Graphics:Images/HouseholderMod_gr_83.gif].

Reduction to Tridiagonal Form

Suppose that
[Graphics:Images/HouseholderMod_gr_84.gif] is a symmetric [Graphics:Images/HouseholderMod_gr_85.gif] matrix. Start with

[Graphics:Images/HouseholderMod_gr_86.gif].

Construct the sequence
[Graphics:Images/HouseholderMod_gr_87.gif] of Householder matrices, so that

[Graphics:Images/HouseholderMod_gr_88.gif] for [Graphics:Images/HouseholderMod_gr_89.gif],

where
[Graphics:Images/HouseholderMod_gr_90.gif] has zeros below the subdiagonal in columns [Graphics:Images/HouseholderMod_gr_91.gif]. Then [Graphics:Images/HouseholderMod_gr_92.gif] is a symmetric tridiagonal matrix that is similar to [Graphics:Images/HouseholderMod_gr_93.gif]. This process is called Householder's method.


No comments:

Post a Comment

Introductory Methods of Numerical Analysis