Page 194 - Matrices theory and applications

177
10.2. The QR Method
entry of index (l, m) is thus multiplied at each step by a unit number z lm ,
which is not necessarily equal to one if l< m. Hence, the part above the
diagonal of A k does not converge.
Summing up, a convergence theorem may concern only the diagonal of
A k and what is below it.
Lemma 10.2.1 Let A ∈ GL n (K) be given, with K = IR or CC.Let
A k = Q k R k be the sequence of matrices given by the QR algorithm. Let
us define P k = Q 0 ··· Q k−1 and U k = R k−1 ··· R 0 .Then P k U k is the QR
factorization of the kth power of A:
k
A = P k U k .
Proof
From (10.2), we have A k = P −1 AP k ;that is, P k A k = AP k .Then
k
P k+1 U k+1 = P k Q k R k U k = P k A k U k = AP k U k .
k
By induction, P k U k = A . However, P k ∈ U n and U k is triangular, with a
positive real diagonal, as a product of such matrices.
Theorem 10.2.1 Let A ∈ GL n (CC) be given. Assume that the moduli of
the eigenvalues of A are distinct:
|λ 1 | > |λ 2 | > ··· > |λ n | (> 0).
In particular, the eigenvalues are simple, and thus A is diagonalizable:
A = Y −1 diag(λ 1 ,... ,λ n )Y.
Assume also that Y admits an LU factorization. Then the strictly lower
triangular part of A k converges to zero, and the diagonal of A k converges
to D := diag(λ 1 ,... ,λ n ).

Proof
Let Y = LU be the factorization of Y . We also make use of the QR
k
k
factorization of Y −1 : Y −1 = QR.Since A = Y −1 D Y ,wehave P k U k =
k
k
Y −1 D Y = QRD LU.
k
The matrix D LD −k is lower triangular with unit numbers on its di-
agonal. By assumption, its strictly lower part tends to zero (because
k
each term is multiplied by (λ i /λ j ) ,where |λ i /λ j | < 1). Therefore,
k
D LD −k = I n + E k with E k → 0 n as k → +∞. Hence, P k U k =
k
k
k
QR(I n + E k )D U = Q(I n + RE k R −1 )RD U = Q(I n + F k )RD U, where
F k → 0 n .Let O k T k = I n + F k be the QR factorization of I n + F k .By
continuity, O k and T k both tend to I n .Then
k
P k U k =(QO k )(T k RD U).
The first product is a unitary matrix, while the second is a triangular
one. Let |D| be the “modulus” matrix of D (whose entries are the moduli