Recall the theorem about the QR factorization in Theorem 5.7.5. 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 14.2.1Let A be an m × n complex matrix. Then there exists a unitary Q andR, where R is all zero below the main diagonal (R_{ij} = 0if i > j) such that A = QR.
Proof: This is obvious if m = 1.
( ) ( )
a1 ⋅⋅⋅ an = (1) a1 ⋅⋅⋅ an
Suppose true for m − 1 and let
( )
A = a1 ⋅⋅⋅ an , A is m × n
Using Theorem ??, there exists Q_{1} a unitary matrix such that Q_{1}
(a1∕|a1|)
= e_{1} in case a_{1}≠0.
Thus Q_{1}a_{1} =
|a1|
e_{1}. If a_{1} = 0, let Q_{1} = I. Thus
( a b )
Q1A =
0 A1
where A_{1} is
(m − 1)
×
(n− 1)
. If n = 1, this obtains
( ) ( )
a ∗ a ∗
Q1A = 0 , A = Q 1 0 , let Q = Q 1.
That which is desired is obtained. So assume n > 1. By induction, there exists Q_{2}^{′} an
(m − 1)
×
(n − 1)
unitary matrix such that Q_{2}^{′}A_{1} = R^{′}, R_{ij}^{′} = 0 if i > j. Then
( 1 0 ) ( a b )
′ Q1A = ′ = R
0 Q2 0 R
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 14.2.2The QR algorithmis the following. In the description of this algorithm, Q isunitary and R is upper triangular having nonnegative entries on the main diagonal. Starting withA an n × n matrix, form
A0 ≡ A = Q1R1 (14.6)
(14.6)
Then
A1 ≡ R1Q1. (14.7)
(14.7)
In general given
Ak = RkQk, (14.8)
(14.8)
obtain A_{k+1}by
Ak = Qk+1Rk+1,Ak+1 = Rk+1Qk+1 (14.9)
(14.9)
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 14.2.3Let A be an n×n matrix and let the Q_{k}and R_{k}be as described in the algorithm.Then each A_{k}is unitarily similar to A and denoting by Q^{}
(k)
the product Q_{1}Q_{2}
⋅⋅⋅
Q_{k}and R^{(k)
}theproduct R_{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
and since r_{22}^{k}> 0, it follows as in the first part that r_{22}^{k}→ 1. Hence
kli→m∞ qk2 = q2.
Continuing this way, it follows
lim rkij = 0
k→∞
for all i≠j and
k k
kl→im∞ rjj = 1, lk→im∞ qj = qj.
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 −1a1,⋅⋅⋅,An−1an)
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.