Page 321 - Matrix Analysis & Applied Linear Algebra

5.5 Gram–Schmidt Procedure 317

Thus the modified Gram–Schmidt algorithm produces
     
1 0 0
u 1 =  10 −3  , u 2 =  0  , u 3 =  −1  , (5.5.11)
10 −3 −1 0
which is as good as one can expect using 3-digit arithmetic. Comparing (5.5.11)
with the result (5.5.10) obtained in Example 5.5.4 illuminates the advantage
possessed by modified Gram–Schmidt algorithm over the classical algorithm.

Below is a summary of some facts concerning the modified Gram–Schmidt
algorithm compared with the classical implementation.

Summary

• When the Gram–Schmidt procedures (classical or modified) are ap-
plied to the columns of A using exact arithmetic, each produces an
orthonormal basis for R (A).

• For computing a QR factorization in floating-point arithmetic, the
modified algorithm produces results that are at least as good as and
often better than the classical algorithm, but the modified algorithm
is not unconditionally stable—there are situations in which it fails
to produce a set of columns that are nearly orthogonal.
• For solving the least square problem with floating-point arithmetic,
the modified procedure is a numerically stable algorithm in the sense
that the method described in Example 5.5.3 returns a result that is
the exact solution of a nearby least squares problem. However, the
Householder method described on p. 346 is just as stable and needs
slightly fewer arithmetic operations.

Exercises for section 5.5

1 2 −1
      
 
 
5.5.1. Let S = span x 1 =   , x 2 =   , x 3 =   .
 −1 
 2 
 1 
 1 −1 2 
 
−1 1 1
(a) Use the classical Gram–Schmidt algorithm (with exact arith-
metic) to determine an orthonormal basis for S.
(b) Verify directly that the Gram–Schmidt sequence produced in
part (a) is indeed an orthonormal basis for S.
(c) Repeat part (a) using the modified Gram–Schmidt algorithm,
and compare the results.