3.

3 QR factorization via Gram-Schmidt Methods

We seek a Q and R such that A = QR , QT Q = I and R is nonsingular and upper

triangular. Such factorizations are called QR factorizations . These are very useful for both

least squares problems and eigenvalue problems.

There are two numerical versions of this QR factorization:

Assume m > n and A is mxn.

1. Skinny: where A is mxn , Q is mxn and R is nxn

ˆ is mxm and Rˆ is mxn. Rˆ =  R  .

2. Fat : where A is mxn, Q 0 
 

In Matlab, qr(A,0) will give the skinny factorization, and qr(A) will give the fat factorization..

In order to find QR, we represent A and Q by

A = [ a 1 ,a 2 ,.........,a n ] Q = [q,q,...........,q
1 2 n] where a i and q i are mx1 column vectors.
.

 r11 r12 L r1 n 

 r22 L r2 n 
R= .
 O M 
 
 rnn 

Lets look at the transposed system: A T = R TQ T

 a1T   r11   q1T 

 T   T 
 a2  = r12 r22   q1  .
M  M O  M 
 T   
 an  r1 n L rnn   qnT 

The classical Gram-Schmidt method is computed by rows on the transposed system.

 2

a1T = r11q1T
a2T = r12 q1T + r22 q2T ROW
a = r q +r q + r q
T
3
T
13 1
T
23 2
T
33 3

M
COLUMN

0 , i ≠ j
Note: QT Q = I ⇒ qiT q j = 
1 , i = j

First Step.

⇒ r11 = ( a1T a1 ) 2
a1T a1 1
q1T q1 = 1 =
r11 r11

Second Step.

q2T q1 = 0
a2T q1 = r12q T1 q1 + 0
Note, q1T q1 = 1 sothatr12 = aT2 q1.
In general , rik = akT qi i ≠ k .
Either , solve for q2 ( row version ), or update each ak T ( column version ).

In the modified Gram-Schmidt these calculations are done by columns of the transposed

system. rikqiT is found and then subtracted from the left hand side so the remaining system has a

smaller dimension.

a2T − r12 q1T = r22 q2T

a3T − r13 q1T = r23 q2T + r33 q3T
a4T − r14 q1T = r24 q2T + r34 q3T + r44 q4T
M
 3

Gram-Schmidt Method (row version).

r11 = ( a1T a1 ) 2
1

a1T
q =
T
1
r11
for k = 2 : n
z T = akT
for i = 1: k -1
rik = akT qi
z T = z T - rik qiT
end

rkk = ( z T z ) 2
1

zT
q =T
k
rkk
end

Modified Gram-Schmidt Method (column version).

for k = 1: n
qTk = aTk
end
for k = 1: n
1

rkk = ( qTk qk ) 2
qkT
qTk =
rkk
for j = k + 1: n
rkj = aTj qk
qTj = qTj - rkj qkT
end
end
 4

1 1 1
1 1 0
A=
Example. 1 0 2 Notice that A has full column rank.
 
1 0 0
q1 q2 q3

Modified Gram-Schmidt:

1
  1  2
  1 
k = 1: r11 = (q 1T q1 ) = (1 1 1 1)    = 2

1/2

  1 
  1 
  

q1T  1 1 1 1 
q1T = = 
2 2 2 2 2
j = 2:
1
2
 
1
 
r12 = a T2 q1 = (1 1 0 0 )  2  = 1
1
2
1
 
2
 1 1 -1 -1 
q T2 = q 2T -r12 q1T =  
2 2 2 2 
j = 3:
1 
2 
 
1 
  3
r13 = (1 0 2 0 )  2  =
1  2
2 
1 
 
2 
1
q T3 = q 3T -r13q 1T = (1 -3 5 -3)
4
 5

k = 2:

r22 = ( q T2 q 2 ) 2 = 1
1

qT2  1 1 -1 -1 
q =
T
2 = 
r22  2 2 2 2 
j = 3:
-1
r23 = a T3 qT2 =
2
1
q T3 = q 3T -r23q T2 = (1 -1 2 -2 )
2

k = 3:

r33 = ( q q 3 ) =
T 2
10
3
2
qT3 1
q T3 = = (1 -1 2 -2 )
r33 10

1 1 1 
2 2 10 

1 1 −1   2 1 3 
2 
2 2 10   
So, A =   0 1 −1 2  .
 1 −1 2 
 
2 2 10  0 0 10 
  2
 1 −1 −2 
 2 2 10 

Remark: The modified Gram-Schmidt is better because of less round off errors. It requires

8
O( n3 ) operations.
3