Eigenvalues of a 3 by 3 symmetric matrix

Puzzler183
Unregistered
 
Post: #1
Ok, so I'm putting this here because there is no math or physics forum (maybe one could be added?).

Anyway, my trouble comes from finding the eigenvalues of a 3 by 3 symmetric matrix - I'm wondering if there is a good (read: fast) way to do it numerically and if so, what that is. Google hasn't been exactly helpful on this, nor have my books on linear algebra. So, any ideas?
Quote this message in a reply
Member
Posts: 749
Joined: 2003.01
Post: #2
I admit, thats an ugly problem. I looks like the fact that it's symmetric doesnt helps much... you still have a third degree polinomial to solve [I guess you know that]. You are lucky that at least one eigenvalue is real, the other ones may be both real or both complex. Its not hard to find the real one [you use the usual algorithm to solve an equation, i.e. you find a value of lamda for which the polinomial is positive and another one for which it,s negative, so you know that by continuity there must be a solution between the two values, then you keep iterating], but I guess its much harder to find the complex roots.

©h€ck øut µy stuƒƒ åt ragdollsoft.com
New game in development Rubber Ninjas - Mac Games Downloads
Quote this message in a reply
Tasnu Arakun
Unregistered
 
Post: #3
heh, when solving polynomials by hand we were taught to make educated guesses regarding possible solutions. don't forget that, for a polynomial containing only real numbers, if there is a complex solution z = a + bi then there's also a solution z = a - bi.

by using interval bisection (a.k.a. interval halving) you guarantee a logarithmic time complexity. in other words, quite efficient.

when you've found one root, divide the polynomial by that root to yield a 2nd degree polynomial. once you've got that there's a simple formula to calculate the two solutions (i assume you know it). just make sure to check the sign of the value within the square root Wink you want to write a special case for when the two roots are complex.
Quote this message in a reply
Nibbie
Posts: 2
Joined: 2006.10
Post: #4
The power method is not too hard to code:

Code:
function [lambda, v] = powermethod(v0, A, n)
% Power iteration
% POWERMETHOD(v0, A, n) returns lambda and v which converge towards
% the largest eigenvalue and associated eigenvector of A as n gets big.
% The function iterates through n steps of the algorithm.
v = v0/norm(v0);
for k = 1:n
    w = A*v;
    v = w/norm(w);
    lambda = v'*A*v;
end

Or you could look at Chapter 11 of Numerical Recipes.

EDIT: I just remembered this -- the vecLib framework includes functions from CLAPACK, which means that it can do just about any matrix-related operation that you could possibly want. The only hard part is making sure that you pass in the arguments in the right way, but for a symmetric matrix, this probably won't even be an issue. A quick google suggests that the LAPACK function you want is called ssyevd / dsyevd.
Quote this message in a reply
Puzzler183
Unregistered
 
Post: #5
Well in theory, they should all be real since it's symmetric, or so I've read. I don't know very much aobut it honestly. I'll have to check out that numerical recipes stuff...

I was just kind of hoping there was something faster than using the formula for third order polynomials... Guess not though, oh well.
Quote this message in a reply
Oldtimer
Posts: 834
Joined: 2002.09
Post: #6
If it is symmetric, all three roots are real. Still, the third-grade polynomial is tough to solve.
Quote this message in a reply
Tasnu Arakun
Unregistered
 
Post: #7
sorry if i'm stating the obvious - i don't know if this will be a problem - but the numerical solution won't be exact and it's error will grow as you do the polynomial division and solve the 2nd degree polynomial. still i believe the eigen values will be fairly accurate.
Quote this message in a reply
Member
Posts: 749
Joined: 2003.01
Post: #8
I believe its a good way to go too.

©h€ck øut µy stuƒƒ åt ragdollsoft.com
New game in development Rubber Ninjas - Mac Games Downloads
Quote this message in a reply
Puzzler183
Unregistered
 
Post: #9
Yeah, not as fast as I'd like, but it's what I'll have to do. Thanks for the helpSmile.
Quote this message in a reply
Member
Posts: 749
Joined: 2003.01
Post: #10
btw... what do you need that for? Sneaky

©h€ck øut µy stuƒƒ åt ragdollsoft.com
New game in development Rubber Ninjas - Mac Games Downloads
Quote this message in a reply
Puzzler183
Unregistered
 
Post: #11
In this case, I'm finding the moments of inertia about the principal axes of a body, given the intertia tensor. For more info, check out http://scienceworld.wolfram.com/physics/...ertia.html and http://kwon3d.com/theory/moi/prin.html
Quote this message in a reply
Member
Posts: 749
Joined: 2003.01
Post: #12
wow Blink ... i thought nobody would ever use eigenvalues in games... yet you proved me wrong... Wink

©h€ck øut µy stuƒƒ åt ragdollsoft.com
New game in development Rubber Ninjas - Mac Games Downloads
Quote this message in a reply
Puzzler183
Unregistered
 
Post: #13
Heh, I try ^___^.

And I got it working so thanks allSmile.
Quote this message in a reply
Tasnu Arakun
Unregistered
 
Post: #14
i should have guessed since i study game engine technology at the moment including among other things... inertia tensors Wink . must say i'm curious about trying it out myself.

hmm, or maybe not. the mathematical formula for calculating the tensor looks slightly too complicated (may be the reason it is not described in detail in my book). is there any easy algorithm to do the job (based on a mesh)?
Quote this message in a reply
Puzzler183
Unregistered
 
Post: #15
Well it's a triple integral over a volume. Or should I say nine triple integrals since when you take it from matrix form you have nine elements. There is no simple way to do it from a mesh AFAIK, but if you have the volume's bounding functions and the density function it's a very simple thing to compute. Most of this is studied in Calculus III (multivariate).

Doing things based off of meshes = lots of nasty numerical integration with weird limits but I'm sure some modeling packages can do it. Usually you are better off to pick numbers which is pretty simple if you just stick to the diagonal of the matrix and 0's elsewhere and then rotate that (getting the nasty thing you see).
Quote this message in a reply
Post Reply