Page 193 - Matrices theory and applications

10. Approximation of Eigenvalues
176
1
sends a 1 to a 1 2 e .The matrix H 1 A has the form


x ···
a 1 2
.
.


0
.
˜


.
A =
.

.

.
.


.
.


0
y
···
We then perform these operations again on the matrix extracted from A ˜
by deleting the first rows and columns, and so on. At the kth step, H k is a
matrix of the form

I k 0 ,
0 I n−k − 2v k v ∗
k
where v k ∈ CC n−k is a unit vector. The computation of v k requires O(n−k)
operations. The product H k A (k) ,where A (k) is block-triangular, amounts
to that of two square matrices of size n−k,one of them I −2v k v .Wethus
∗
k
compute a matrix N − 2vv N from v and N, which costs about 4(n − k) 2
∗
operations. Summing from k =1 to k = n − 1, we find that the complexity
3
2
of the computation of R alone is 4n /3+ O(n ). As indicated above, we
do not compute the factor Q, but compute all the matrices RH n−1 ··· H k .
3
That necessitates 2n + O(n) operations (check this!). The complexity of
2
3
one step of the QR method on a generic matrix is thus 10n /3+ O(n ).
Let us now analyze the situation when A is a Hessenberg matrix. By
k
induction on k,we see that v k belongs to the plane spanned by e and
e k+1 . Its computation needs O(1) operations. Then the product of H k and
A (k) can be obtained by simply recomputing the rows of indices k and k+1,
about 6(n − k) operations. Summing from k =1 to n − 1, we find that the
2
complexity of the computation of R alone is 3n + O(n). The computation
of the product (RH n−1 ··· H k+1 )H k needs about 6k operations. Finally, the
2
complexity of the QR factorization of a Hessenberg matrix is 6n + O(n),
2
in which there are 4n + O(n) multiplications.
To sum up, the cost of the preliminary reduction of a matrix to Hessen-
berg form is less than or equal to what is saved during the first iteration
of the QR method.
10.2.4 Convergence of the QR Method
As explained above, the best convergence statement assumes that the
eigenvalues have distinct moduli.
Let us recall that the sequence A k is not always convergent. For example,
if A is already triangular, its QR factorization is Q = D, R = D −1 A,with
d j = a jj /|a jj |. Hence, A 1 = D −1 AD is triangular, with the same diagonal
as that of A. By induction, A k is triangular, with the same diagonal as
k
that of A.Wehave thus Q k = D for every k,so that A k = D −k AD .The