Householder Method for Tridiagonalization: Ver. 1.0
Taisuke Ozaki, RCIS, JAIST
The Householder method [1] is a way of transforming
a Hermitian matrix to a real symmetric tridiagonalized
matrix .
Let be a column vector of ,
and consider that the vector consists of
the real part and the imaginary part as
|
|
|
(1) |
Also let us introduce a vector of which real
part has just one non-zero component
and
imaginary part is a zero vector as
|
|
|
(2) |
Then, consider a mirror transform bridging the two vectors
and by
|
|
|
(3) |
where let us assume that
|
|
|
(4) |
Putting Eq. (3) into Eq. (4), and solving it with respect to
, we have
|
|
|
(5) |
Thus, Eq. (5) allows us to write
as
|
|
|
(6) |
If is normalized, is given by
Comparing Eqs. (5) with (6) and making use of Eq. (7), we have
|
|
|
(8) |
with and given by
|
|
|
(9) |
and
|
|
|
(10) |
Then, it is verified that
Thus, the transformation for the Hermitian matrix is
a similarity transformation, and given by
By defining
|
|
|
(13) |
Eq. (12) becomes
Moreover, by defining
|
|
|
(15) |
we have a compact form:
|
|
|
(16) |
For the numerical stability, we furthermore modify Eq. (16) as shown below.
Let us introduce a vector as.
|
|
|
(17) |
Then, can be written by as
Also, noting that
|
|
|
(19) |
can be rewritten by
|
|
|
(20) |
Putting Eqs. (19) and (20) into Eq. (16), we have
|
|
|
(21) |
with defined by
|
|
|
(22) |
where
|
|
|
(23) |
The transformation by Eq. (21) can be applied to each
column vector step by step in which the place occupied by
in Eq. (2) is shifted one by one. Then, the tridiagonalized matrix
is given by
|
|
|
(24) |
-
- 1
-
A. S. Householder, J. ACM 5, 339 (1958).
2007-08-18