## 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?
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
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 you want to write a special case for when the two roots are complex.
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.
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.
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.
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.
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
Puzzler183
Unregistered

Post: #9
Yeah, not as fast as I'd like, but it's what I'll have to do. Thanks for the help.
Member
Posts: 749
Joined: 2003.01
Post: #10
btw... what do you need that for?

Â©hâ‚¬ck Ã¸ut Âµy stuÆ’Æ’ Ã¥t ragdollsoft.com
New game in development Rubber Ninjas - Mac Games Downloads
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
Member
Posts: 749
Joined: 2003.01
Post: #12
wow ... i thought nobody would ever use eigenvalues in games... yet you proved me wrong...

Â©hâ‚¬ck Ã¸ut Âµy stuÆ’Æ’ Ã¥t ragdollsoft.com
New game in development Rubber Ninjas - Mac Games Downloads
Puzzler183
Unregistered

Post: #13
Heh, I try ^___^.

And I got it working so thanks all.
Tasnu Arakun
Unregistered

Post: #14
i should have guessed since i study game engine technology at the moment including among other things... inertia tensors . 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)?
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).