Recall the theorem about the QR factorization in Theorem 13.2.9. It says that given an n×n real matrix
A, there exists a real orthogonal matrix Q and an upper triangular matrix R such that A = QR and that
this factorization can be accomplished by a systematic procedure. One such procedure was given in proving
this theorem.
Theorem 16.3.1Let A be an n × n complex matrix. Then there exists a unitary Q and uppertriangular R such that A = QR.
Proof: This is obvious if n = 1. Suppose true for n and let
( )
A = a1 ⋅⋅⋅ an an+1
Let Q_{1} be a unitary matrix such that Q_{1}a_{1} =
|a1|
e_{1} in case a_{1}≠0. If a_{1} = 0, let Q_{1} = I.
Thus
( )
Q A = a b
1 0 A1
where A_{1} is
(n− 1)
×
(n − 1)
. By induction, there exists Q_{2}^{′} an
(n− 1)
×
(n − 1)
unitary matrix such
that Q_{2}^{′}A_{1} = R^{′}, an upper triangular matrix. Then
( ) ( )
1 0 a b
0 Q ′ Q1A = 0 R ′ = R
2
Since the product of unitary matrices is unitary, there exists Q unitary such that Q^{∗}A = R and so
A = QR. ■▸▸
The QR algorithm is described in the following definition.
Definition 16.3.2The QR algorithmis the following. In the description of this algorithm, Q is unitaryand R is upper triangular having nonnegative entries on the main diagonal. Starting with A an n × nmatrix, form
A0 ≡ A = Q1R1 (16.5)
(16.5)
Then
A1 ≡ R1Q1. (16.6)
(16.6)
In general given
Ak = RkQk, (16.7)
(16.7)
obtain A_{k+1}by
Ak = Qk+1Rk+1, Ak+1 = Rk+1Qk+1 (16.8)
(16.8)
This algorithm was proposed by Francis in 1961. The sequence
{Ak}
is the desired sequence of iterates.
Now with the above definition of the algorithm, here are its properties. The next lemma shows each of the
A_{k} is unitarily similar to A and the amazing thing about this algorithm is that often it becomes
increasingly easy to find the eigenvalues of the A_{k}.
Lemma 16.3.3Let A be an n × n matrix and let the Q_{k}and R_{k}be as described in the algorithm. Theneach A_{k}is unitarily similar to A and denoting by Q^{}
(k)
the product Q_{1}Q_{2}
⋅⋅⋅
Q_{k}and R^{(k)
}the productR_{k}R_{k−1}
⋅⋅⋅
R_{1}, it follows that
Ak = Q(k)R(k)
(The matrix on the left is A raised to the k^{th}power.)
A = Q (k)AkQ (k)∗,Ak = Q (k)∗AQ (k).
Proof: From the algorithm, R_{k+1} = A_{k+1}Q_{k+1}^{∗} and so
Taking the inner product of both sides with q_{1}^{k} it follows
k ( k)
kli→m∞ r12 = kli→m∞ q2 ⋅q1 = (q2 ⋅q1) = 0.
Therefore,
lim r2k2qk2 = q2
k→ ∞
and since r_{22}^{k}> 0, it follows as in the first part that r_{22}^{k}→ 1. Hence
lim qk= q .
k→ ∞ 2 2
Continuing this way, it follows
k
kli→m∞ rij = 0
for all i≠j and
lim rkjj = 1, lim qkj = qj.
k→∞ k→∞
Thus R_{k}→ I and Q^{}
(k)
→ Q. This proves the first part of the lemma.
The second part follows immediately. If QR = Q^{′}R^{′} = A where A^{−1} exists, then
Q∗Q ′ = R (R ′)−1
and I need to show both sides of the above are equal to I. The left side of the above is unitary and the
right side is upper triangular having positive entries on the diagonal. This is because the inverse of such an
upper triangular matrix having positive entries on the main diagonal is still upper triangular having
positive entries on the main diagonal and the product of two such upper triangular matrices gives another
of the same form having positive entries on the main diagonal. Suppose then that Q = R where Q is
unitary and R is upper triangular having positive entries on the main diagonal. Let Q_{k} = Q and R_{k} = R. It
follows
IRk → R = Q
and so from the first part, R_{k}→ I but R_{k} = R and so R = I. Thus applying this to Q^{∗}Q^{′} = R
(R ′)
^{−1}
yields both sides equal I. ■
A case of all this is of great interest. Suppose A has a largest eigenvalue λ which is real. Then A^{n} is of
the form
(An −1a ,⋅⋅⋅,An−1a )
1 n
and so likely each of these columns will be pointing roughly in the
direction of an eigenvector of A which corresponds to this eigenvalue. Then when you do the QR
factorization of this, it follows from the fact that R is upper triangular, that the first column of Q will be
a multiple of A^{n−1}a_{1} and so will end up being roughly parallel to the eigenvector desired.
Also this will require the entries below the top in the first column of A_{n} = Q^{T}AQ will all be
small because they will be of the form q_{i}^{T}Aq_{1}≈ λq_{i}^{T}q_{1} = 0. Therefore, A_{n} will be of the
form
( )
λ′ a
e B
where e is small. It follows that λ^{′} will be close to λ and q_{1} will be close to an eigenvector for λ. Then if
you like, you could do the same thing with the matrix B to obtain approximations for the
other eigenvalues. Finally, you could use the shifted inverse power method to get more exact
solutions.