Page 161 - Matrices theory and applications

8. Matrix Factorizations
144
−1
diagonal entries. Defining Q := MR
,we have
−1
−1
∗
∗
∗
−∗
−∗
Q Q = R
= I n ;
M MR
R RR
= R
hence Q is unitary. Finally, M = QR by construction.
The method used above is unsatisfactory from a practical point of view,
because one can compute Q and R directly, at a lower cost, without com-
puting M M or its Choleski factorization. Moreover, the direct method,
∗
which we shall present now, is based on a theoretical observation: The QR
factorization is nothing but the Gram–Schmidt orthonormalization proce-
n
dure in CC , endowed with the canonical scalar product ·, ·
.In fact, if
1
V ,... ,V n denote the column vectors of M, then giving M in GL n (CC)
1
n
amounts to giving a basis of CC .If Y ,... ,Y n denote the column vectors
1
n
of Q,then {Y ,... ,Y } is an orthonormal basis. Moreover, if M = QR,
then
k
j
k
V = r jk Y .
j=1
1
k
Denoting by E k the linear subspace spanned by Y ,... ,Y ,of dimension
1
k
1
k, one sees that V ,... ,V k are in E k ;thatis, {V ,... ,V } is a basis of
E k . Hence, the columns of Q are obtained by the Gram–Schmidt procedure,
applied to the columns of M.
The practical computation of Q and R is done by induction on k.If
k =1, then
1 1
1
1
r 11 = V , Y = V .
r 11
1
If k> 1, and if Y ,... ,Y k−1 are already known, one looks for Y k and the
entries r jk (j ≤ k). For j< k,we have
k
j
r jk = V ,Y
.
Then
1 k
k
r kk = Z k , Y = Z ,
r kk
where
k−1

k k j
Z := V − r jk Y .
j=1
Let us examine the complexity of the procedure described above. To
pass from the step k − 1to the step k, one computes k − 1 scalar products,
k
k
then Z , its norm, and finally Y . This requires (4n − 1)k +3n operations.
3
2
Summing from k =1 to n yields 2n + O(n ) operations. This method is
not optimal, as we shall see in Section 10.2.3.