Game Development Reference
In-Depth Information
16.3 Eigenvalues and Eigenvectors
Eigenvalues and eigenvectors were introduced in Section 3.5. We have studied
how they are important for performing principal component analysis (see Section
8.1.1) and for determining principal axes of inertia (see Section 14.2.4). Both of
these problems required calculating the eigenvalues and eigenvectors of a 3
symmetric matrix, and we restrict our discussion to that particular problem in this
section. 1
×
3
Recall from Section 3.6 that a symmetric matrix M can be written as
T
M
=
(16.36)
where D is a diagonal matrix whose entries are the eigenvalues of M , and A is an
orthogonal matrix whose columns are the eigenvectors of M . Our strategy in this
section is to apply a series of transformations to a given symmetric matrix
M of
the form
M
=
RM R ,
T
(16.37)
k
k
k
1
k
where R is an orthogonal matrix, in such a way that each iteration moves the
matrix M closer to being diagonal. Once the off-diagonal entries have been
made sufficiently small (perhaps even zero to machine precision), we are left
with the following.
TT
T
M
=
RR
RMRR
R
(16.38)
m
m
m
1
1
0
1
2
m
After m iterations, the diagonal entries of the matrix
M are the eigenvalues of
are the corresponding eigen-
M , and the columns of the product
RR
12
m
vectors.
We choose each matrix R to be a rotation matrix that annihilates one of the
three distinct off-diagonal entries of
M when Equation (16.37) is evaluated.
The use of this process to diagonalize the matrix M is known as the Jacobi
method . Each iteration sets a symmetric pair of off-diagonal entries to zero, but
also undoes previous annihilations. We will show, however, that the off-diagonal
entries become smaller in magnitude as a group and eventually vanish.
k
1
matrix M , the rotation matrix R may assume one of the follow-
ing three forms, where s and c represent the sine and cosine of a rotation angle θ .
For a 3
×
3
1 For a treatment of larger and nonsymmetric matrices, see William H. Press et al., Nu-
merical Recipes in C , Cambridge, 1988.