Page 188 - Matrices theory and applications

We construct a sequence M 1 = M,... ,M n−1 of unitarily similar
matrices. The matrix M n−r will be of the form

B
H
,
N
r
where H ∈ M n−r (CC) is Hessenberg and Z is a vector in CC . Hence, M n−1
will be suitable. 0 r,n−r−1 Z 10.1. Hessenberg Matrices 171
One passes from M n−r to M n−r+1 ,that is,from r to r−1, in the following
r
1
way. Let e be the first vector of the canonical basis of CC .If Z is colinear
1
to e , one does nothing besides defining M n−r+1 = M n−r .Otherwise, one
1
r
chooses X ∈ CC so that SZ is parallel to e (we discuss below the possible
choices for X). Then one sets

I n−r 0 n−r,r
V = ,
0 r,n−r S
which is a unitary matrix, with V = V −1 = V (such a matrix is called a
∗
Householder matrix). We then have

H BS
−1
V M n−r V = .
0 n,n−r−1 SZ SNS
We thus define M n−r+1 = V −1 M n−r V .
There are two possible choices for S,given by
1 z 1 1
X ± := (Z ± Z 2q), q = e .
q
Z ± Z 2 2 |z 1 |
It is always advantageous to choose the sign that gives the largest denom-
inator, namely the positive sign. One thus optimizes the round-off errors
1
when Z is almost aligned with e .
Let us consider now the complexity of the (n−r)th step. Only the terms
2
of order r and r(n − r) are meaningful. The computation of X,in O(r)
operations, is thus negligible, like that of X and of 2X. The computation
∗
∗
of BS = B − (BX)(2X ) needs about 4r(n − r)operations. Then 2NX
2
needs 2r operations, as does 2X N.Wenext compute4X NX,and then
∗
∗
form the vector T := 4(X NX)X − 2NX at the cost O(r). The product
∗
2
∗
∗
∗
TX takes r operations, as 2X(X N). Then N + TX − X(2X N) needs
∗
2 2
2r additions. The complete step is thus accomplished in 7r +4r(n −
r)+ O(n) operations. A sum from r =1 to n − 2 yields a complexity
3
2
3
2
of 3n + O(n ), in which one recognizes 5n /3+ O(n ) multiplications,
3
2
4n /3+ O(n ) additions, and O(n)square roots.
When M is Hermitian, the matrix U −1 MU is still Hermitian. Since it
is Hessenberg, it is tridiagonal, with a j,j+1 =¯a j+1,j and a jj ∈ IR.The
3
2
symmetry reduces the complexity to 2n /3+ O(n ) multiplications. One
can then use the Hessenberg form of M in order to localize its eigenvalues.