With these lemmas, it is possible to prove that for the QR algorithm and certain conditions, the sequence
A_{k} converges pointwise to an upper triangular matrix having the eigenvalues of A down the diagonal. I will
assume all the matrices are real here.
This convergence won’t always happen. Consider for example the matrix
( )
0 1
1 0
. You can verify
quickly that the algorithm will return this matrix for each k. The problem here is that, although the
matrix has the two eigenvalues −1,1, they have the same absolute value. The QR algorithm
works in somewhat the same way as the power method, exploiting differences in the size of the
eigenvalues.
If A has all real eigenvalues and you are interested in finding these eigenvalues along with the
corresponding eigenvectors, you could always consider A + λI instead where λ is sufficiently large and
positive that A + λI has all positive eigenvalues. (Recall Gerschgorin’s theorem.) Then if μ is an eigenvalue
of A + λI with
(A + λI)x = μx
then
Ax = (μ− λ)x
so to find the eigenvalues of A you just subtract λ from the eigenvalues of A + λI. Thus there is no loss of
generality in assuming at the outset that the eigenvalues of A are all positive. Here is the theorem. It
involves a technical condition which will often hold. The proof presented here follows [32] and is a special
case of that presented in this reference.
Before giving the proof, note that the product of upper triangular matrices is upper triangular. If they
both have positive entries on the main diagonal so will the product. Furthermore, the inverse of an upper
triangular matrix is upper triangular. I will use these simple facts without much comment whenever
convenient.
Theorem 16.3.5Let A be areal matrix having eigenvalues
λ1 > λ2 > ⋅⋅⋅ > λn > 0
and let
A = SDS −1 (16.9)
(16.9)
where
( )
| λ1 0 |
D = |( ... |)
0 λ
n
and suppose S^{−1}has an LU factorization. Then the matrices A_{k}in the QR algorithm described aboveconverge to an upper triangular matrix T^{′}having the eigenvalues of A, λ_{1},
⋅⋅⋅
,λ_{n}descending on the maindiagonal. The matrices Q^{(k)
}converge to Q^{′}, an orthogonal matrix which equals Q except forpossibly having some columns multiplied by −1 for Q the unitary part of the QR factorization ofS,
Let S = QR where this is just a QR factorization which is known to exist and let S^{−1} = LU which is
assumed to exist. Thus
(k) (k) k
Q R = QRD LU (16.11)
(16.11)
and so
Q (k)R (k) = QRDkLU = QRDkLD −kDkU
That matrix in the middle, D^{k}LD^{−k} satisfies
(DkLD −k) = λkiLijλ−j kfor j ≤ i,0 if j > i.
ij
Thus for j < i the expression converges to 0 because λ_{j}> λ_{i} when this happens. When i = j it
reduces to 1. Thus the matrix in the middle is of the form I + E_{k} where E_{k}→ 0. Then it
follows
Ak = Q (k)R(k) = QR (I + E )DkU
k
( −1) k k
= Q I +REkR RD U ≡ Q (I + Fk)RD U
where F_{k}→ 0. Then let I + F_{k} = Q_{k}R_{k} where this is another QR factorization. Then it reduces
to
(k) (k) k
Q R = QQkRkRD U
This looks really interesting because by Lemma 16.3.4Q_{k}→ I and R_{k}→ I because Q_{k}R_{k} =
(I + Fk)
→ I.
So it follows QQ_{k} is an orthogonal matrix converging to Q while
( )−1
RkRDkU R (k)
is upper triangular, being the product of upper triangular matrices. Unfortunately, it is not known that the
diagonal entries of this matrix are nonnegative because of the U. Let Λ be just like the identity matrix but
having some of the ones replaced with −1 in such a way that ΛU is an upper triangular matrix
having positive diagonal entries. Note Λ^{2} = I and also Λ commutes with a diagonal matrix.
Thus
Q(k)R (k) = QQkRkRDk Λ2U = QQkRkR ΛDk (ΛU )
At this point, one does some inspired massaging to write the above in the form
is upper triangular and has all positive entries on the diagonal. This is
because it is an upper triangular matrix which is similar to the upper triangular matrix R_{k}R and so it has
the same eigenvalues (diagonal entries) as R_{k}R. Thus the matrix G_{k}≡ D^{k}
[( )−1 ]
ΛDk RkRΛDk
(ΛU)
is
upper triangular and has all positive entries on the diagonal. Multiply on the right by G_{k}^{−1} to
get
Q (k)R(k)G−k1 = QQk Λ → Q′
where Q^{′} is essentially equal to Q but might have some of the columns multiplied by −1. This is because
Q_{k}→ I and so Q_{k}Λ → Λ. Now by Lemma 16.3.4, it follows
Q(k) → Q ′,R(k)G−k1 → I.
It remains to verify A_{k} converges to an upper triangular matrix. Recall that from 16.10 and the
definition below this (S = QR)
A = SDS −1 = (QR )D (QR )−1 = QRDR −1QT = QT QT
Where T is an upper triangular matrix. This is because it is the product of upper triangular matrices
R,D,R^{−1}. Thus Q^{T}AQ = T. If you replace Q with Q^{′} in the above, it still results in an upper triangular
matrix T^{′} having the same diagonal entries as T. This is because
T ′ T ′ ′T ′
T = Q AQ = (Q Λ) A (Q Λ) = ΛQ AQ Λ
and considering the ii^{th} entry yields
( T ) ∑ ( ′T ′) ( ′T ′) ( ′T ′)
Q AQ ii ≡ Λij Q AQ jk Λki = ΛiiΛii Q AQ ii = Q AQ ii
j,k
TAQ^{(k)
}. Thus taking a limit and using the first part,
(k)T (k) ′T ′ ′
Ak = Q AQ → Q AQ = T .■
An easy case is for A symmetric. Recall Corollary 14.1.6. By this corollary, there exists an orthogonal
(real unitary) matrix Q such that
QT AQ = D
where D is diagonal having the eigenvalues on the main diagonal decreasing in size from the upper left
corner to the lower right.
Corollary 16.3.6Let A be a real symmetric n × n matrix having eigenvalues
λ1 > λ2 > ⋅⋅⋅ > λn > 0
and let Q be defined by
QDQT = A,D = QT AQ, (16.12)
(16.12)
where Q is orthogonal and D is a diagonal matrix having the eigenvalues on the main diagonal decreasingin size from the upper left corner to the lower right. Let Q^{T}have an LU factorization. Then in the QRalgorithm, the matrices Q^{}
(k)
converge to Q^{′}where Q^{′}is the same as Q except having some columnsmultiplied by
(− 1)
. Thus the columns of Q^{′}are eigenvectors of A. The matrices A_{k}converge toD.
Proof:This follows from Theorem 16.3.5. Here S = Q,S^{−1} = Q^{T}. Thus
because formula 16.12 is unaffected by replacing Q with Q^{′}. ■
When using the QR algorithm, it is not necessary to check technical condition about S^{−1} having an LU
factorization. The algorithm delivers a sequence of matrices which are similar to the original one. If that
sequence converges to an upper triangular matrix, then the algorithm worked. Furthermore, the technical
condition is sufficient but not necessary. The algorithm will work even without the technical
condition.
Example 16.3.7Find the eigenvalues and eigenvectors of the matrix
( )
| 5 1 1 |
A = ( 1 3 2 )
1 2 1
It is a symmetric matrix but other than that, I just pulled it out of the air. By Lemma 16.3.3 it follows
A_{k} = Q^{}
(k)
TAQ^{(k)
}. And so to get to the answer quickly I could have the computer raise A to a power and
then take the QR factorization of what results to get the k^{th} iteration using the above formula. Lets pick
k = 10.
By Gerschgorin’s theorem, the eigenvalues are pretty close to the diagonal entries of the above matrix.
Note I didn’t use the theorem, just Lemma 16.3.3 and Gerschgorin’s theorem to verify the eigenvalues are
close to the above numbers. The eigenvectors are close to