Graphics Reference
In-Depth Information
1.4.1. Theorem.
The Gram-Schmidt algorithm gives the correct result.
Proof.
There are two parts to proving that the algorithm works. We have to show
(1) the vectors
u
i
form an orthonormal set and
(2) they span the same space as the
v
j
.
One uses induction in both cases. To prove (1) it suffices to check that
w
•
u
i
= 0,
i = 1, 2,..., m, which is straightforward. This shows that orthogonality is preserved
as we go along.
To prove (2), assume inductively that at the beginning of Step 2
(
)
=
(
)
span
vv
,
,...,
v
span
uu
,
,...,
u
.
(1.11)
12
s
-
1
1 2
m
The inductive hypothesis (1.11) implies that
w
belongs to span (
v
1
,
v
2
,...,
v
s
), and
therefore so does
u
m+1
. This and (1.11) shows that
(
)
Õ
(
)
span
uu
,
,...,
u
span
vv
,
,...,
v
.
(1.12)
12
m
+
1
12
s
Now solve the equation for
w
in Step 2 of the algorithm for
v
s
. Using the inductive
hypothesis (1.11), we see that
v
s
lies in span(
v
1
,
v
2
,...,
v
s-1
,
u
m
) and this and another
use of the inductive hypothesis (1.11) shows that
(
)
Õ
(
)
span
vv
,
,...,
v
span
uu
,
,...,
u
.
(1.13)
12
s
1 2
m
+
1
The inclusions (1.12) and (1.13) imply that we actually have an equality of sets,
proving (2) and the theorem (modulo some special cases such as
w
=
0
that we leave
to the reader).
It should be clear that m = k in the Gram-Schmidt algorithm if and only if the
vectors
v
1
,
v
2
,...,
v
k
are linearly independent. In the worst case, where S is empty or
v
1
=
v
2
= ...=
v
k
=
0
, then m = 0.
1.4.2. Corollary.
Every subspace of an inner product space has an orthonormal basis.
1.4.3. Example.
To find an orthonormal basis
u
1
and
u
2
for the subspace
X
in
R
3
spanned by the vectors
v
1
= (2,-1,1) and
v
2
= (-1,4,0).
Solution.
Applying the Gram-Schmidt algorithm we get
1
1
6
(
)
u
=
v
=
211
,,.
-
1
1
v
1
To get
u
2
, let
(
)
(
)
vvuu
wv v
=∑
=-
21 1
,,
-
,
and
211
=-=
(
)
131
,, .
2
