Page 264 - 35Linear Algebra

264 Orthonormal Bases and Complements

14.4.1 The Gram-Schmidt Procedure

In fact, given an ordered set (v 1 , v 2 , . . .) of linearly independent vectors, we
can define an orthogonal basis for span{v 1 , v 2 , . . .} consisting of the vectors

v ⊥
1 := v 1
⊥
v · v 2
v ⊥ := v 2 − 1 v ⊥
2 ⊥ ⊥ 1
v · v
1 1
⊥ ⊥
⊥
1
2
v ⊥ := v 3 − v · v 3 v − v · v 3 v ⊥
3 ⊥ ⊥ 1 ⊥ ⊥ 2
v · v 1 v · v 2
1
2
. . .
⊥
⊥ v · v i v ⊥ · v i
v · v i
⊥
⊥
⊥
v i ⊥ := v i − 1 v − 2 v − · · · − i−1 v i−1
1
2
⊥
⊥
v · v ⊥ v · v ⊥ v ⊥ · v ⊥
1 1 2 2 i−1 i−1
. . .
⊥
⊥
Notice that each v here depends on v for every j < i. This allows us to
i j
inductively/algorithmically build up a linearly independent, orthogonal set
⊥
⊥
⊥
⊥
of vectors {v , v , . . .} such that span{v , v , . . .} = span{v 1 , v 2 , . . .}. That
1 2 1 2
is, an orthogonal basis for the latter vector space.
Note that the set of vectors you start out with needs to be ordered to
uniquely specify the algorithm; changing the order of the vectors will give a
different orthogonal basis. You might need to be the one to put an order on
the initial set of vectors.
This algorithm is called the Gram–Schmidt orthogonalization pro-
cedure–Gram worked at a Danish insurance company over one hundred years
ago, Schmidt was a student of Hilbert (the famous German mathmatician).
3
Example 135 We’ll obtain an orthogonal basis for R by appling Gram-Schmidt to
     
 1 1 3 
,
1
the linearly independent set       .
1
1
,
1 0 1
 
Because he Gram-Schmidt algorithm uses the first vector from the ordered set the
largest number of times, we will choose the vector with the most zeros to be the first
in hopes of simplifying computations; we choose to order the set as
     
1 1 3
1
(v 1 , v 2 , v 3 ) :=       .
,
,
1
1
0 1 1
264