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 [27] 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 14.2.5Let A be areal matrix having eigenvalues
λ1 > λ2 > ⋅⋅⋅ > λn > 0
and let
−1
A = SDS (14.10)
(14.10)
where
( )
λ1 0
|| .. ||
D = ( . )
0 λn
and suppose S^{−1}has an LU factorization. Then the matrices A_{k}in the QR algorithm describedabove converge to an upper triangular matrix T^{′}having the eigenvalues of A, λ_{1},
⋅⋅⋅
,λ_{n}descending on the main diagonal. The matrices Q^{(k)
}converge to Q^{′}, an orthogonal matrix whichequals Q except for possibly having some columns multiplied by −1 for Q the unitary part of theQR factorization of S,
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 (14.12)
(14.12)
and so
Q(k)R(k) = QRDkLU = QRDkLD −kDkU
That matrix in the middle, D^{k}LD^{−k} satisfies
( )
DkLD −k = λkiLijλ−jk for 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 + Ek)DkU
( )
= Q I + REkR −1 RDkU ≡ Q(I +Fk )RDkU
where F_{k}→ 0. Then let I + F_{k} = Q_{k}R_{k} where this is another QR factorization. Then it reduces
to
Q(k)R (k) = QQkRkRDkU
This looks really interesting because by Lemma 14.2.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
( )
R RDkU R(k) −1
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
(k) (k) k 2 k
Q R = QQkRkRD Λ U = QQkRkR ΛD (Λ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}
[ ]
(ΛDk )−1RkR Λ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 −1= QQ Λ → Q ′
k k
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 14.2.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 14.11 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 = QT AQ = (Q ′Λ)T A(Q ′Λ ) = ΛQ ′TAQ ′Λ
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 6.4.13. By this corollary, there exists an
orthogonal (real unitary) matrix Q such that
T
Q 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 14.2.6Let A be a real symmetric n × n matrix having eigenvalues
λ1 > λ2 > ⋅⋅⋅ > λn > 0
and let Q be defined by
T T
QDQ = A, D = Q AQ, (14.13)
(14.13)
where Q is orthogonal and D is a diagonal matrix having the eigenvalues on the main diagonaldecreasing in size from the upper left corner to the lower right. Let Q^{T}have an LU factorization.Then in the QR algorithm, the matrices Q^{}
(k)
converge to Q^{′}where Q^{′}is the same as Q excepthaving some columns multiplied by
(− 1)
. Thus the columns of Q^{′}are eigenvectors of A. Thematrices A_{k}converge to D.
Proof:This follows from Theorem 14.2.5. Here S = Q,S^{−1} = Q^{T}. Thus
because formula 14.13 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 14.2.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 14.2.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 14.2.3 and Gerschgorin’s theorem
to verify the eigenvalues are close to the above numbers. The eigenvectors are close
to