Page 313 - Matrix Analysis & Applied Linear Algebra

5.5 Gram–Schmidt Procedure 309

Gram–Schmidt Orthogonalization Procedure
If B = {x 1 , x 2 ,..., x n } is a basis for a general inner-product space S,
then the Gram–Schmidt sequence defined by

k−1
x 1 x k − i=1 u i x k u i
u 1 = and u k =

for k =2,...,n
x 1
k−1

x k − i=1 u i x k u i
is an orthonormal basis for S. When S is an n-dimensional subspace
m×1
of C , the Gram–Schmidt sequence can be expressed as
∗
(I − U k U ) x k
k
u k = for k =1, 2,...,n (5.5.4)
∗
(I − U k U ) x k
k

in which U 1 = 0 m×1 and U k = u 1 | u 2 |···| u k−1 for k> 1.
m×k−1
Example 5.5.1
Classical Gram–Schmidt Algorithm. The following formal algorithm is the
straightforward or “classical” implementation of the Gram–Schmidt procedure.
Interpret a ← b to mean that “a is defined to be (or overwritten by) b.”

For k =1:
x 1
u 1 ←
x 1
For k> 1:
k−1

∗
u k ← x k − (u x k )u i
i
i=1
u k
u k ←
u k
(See Exercise 5.5.10 for other formulations of the Gram–Schmidt algorithm.)
Problem: Use the classical formulation of the Gram–Schmidt procedure given
above to find an orthonormal basis for the space spanned by the following three
linearly independent vectors.

     
1 1 3
 0   2   1 
0 0 1
x 1 =   , x 2 =   , x 3 =   .
−1 −1 −1