Graphics Reference
In-Depth Information
tion above to find an orthonormal basis for the space spanned by
v
1
and
v
2
. Assume
that
u
1
and
u
2
form such a basis. Now find the third vector
u
3
by projecting
v
3
to the
vector
x
in the subspace
X
spanned by
u
1
and
u
2
. The difference
w
=
v
3
-
x
is a vector
orthogonal to
X
that is then normalized to have unit length (assuming again that it
is not zero). This leaves one question unanswered, namely, how does one compute
x
?
The example in Figure 1.4(b) motivates the answer. We see that the projection
of (1,2,3) onto the plane is (1,2,0). This vector is the sum of two vectors (1,0,0) and
(0,2,0), which happen to be the orthogonal projections of (1,2,3) onto the vectors
e
1
and
e
2
, respectively. It turns out that the only important property of
e
1
and
e
2
is that
these vectors form an orthonormal basis for the plane. We have now sketched the key
ideas needed for the general case. This leads to the recursive construction described
in Algorithm 1.4.1.
v
3
w
(1, 2, 3)
u
3
x
v
2
u
2
v
1
(0, 2, 0)
(1, 2, 0)
u
1
projection of
v
3
onto X
X
(1, 0, 0)
(a)
(b)
Figure 1.4.
More orthogonal projections.
Input:
a set of vectors S = {
v
1
,
v
2
, º ,
v
k
}
Output:
an orthonormal basis B = {
u
1
,
u
2
, º ,
u
m
} for span(S)
If S = f , then return f .
Let s = 1, B = f , and m = 0 .
Step 1: If s > k, then return B.
Step 2: Let
w
=
v
s
- (
v
s
∑
u
1
)
u
1
- (
v
s
∑
u
2
)
u
2
-º- (
v
s
∑
u
m
)
u
m
If
w
π
0
, then add
u
m+1
= (1/|
w
|)
w
to B and increment m.
Increment s.
Go to Step 1.
Algorithm 1.4.1.
The Gram-Schmidt algorithm.
