On Sun, Jun 12, 2011 at 12:42 PM, SherjilOzair <[email protected]> wrote: > > > On Jun 12, 10:24 pm, Aaron Meurer <[email protected]> wrote: >> If the eigenvalues cannot be expressed in radicals, then it doesn't >> matter what method you use to compute them. > > What about symbolic elements ? Or exact elements ?
You can think of "general" case to mean symbolic elements, and "special cases" to mean numerical elements. > >> >> And for whatever reason, people always seem to be confused about this. >> The general fifth order and higher polynomial does not have a >> solution in radicals, and you can construct specific fifth order and >> higher polynomials whose roots are not expressible in radicals (like >> x**5 - x + 1). But that doesn't mean that *all* fifth order >> polynomials don't have solutions in radicals. It's very easy to >> construct a polynomial of any degree that has solutions in radicals. >> For example (x - 1)**n is a nth degree polynomial, and the roots are >> all 1. It's even possible to have an irreducible polynomial of degree >> 5 or greater whose solution is expressible in radicals. > > You would find that you were wrong in your last statement. If a > polynomial has solutions in radicals, then it is necessarily a > reducible polynomial. If x0, x1, x2, ... are the exact solutions in > radicals then (x - x0)(x - x1)... is the reduced polynomial. Irreducible means irreducible over the rationals. To take an example from Wikipedia, x**5 - 5*x**4 + 30*x**3 - 50*x**2 + 55*x - 21 is solvable in radicals, but you get In [15]: factor(x**5 - 5*x**4 + 30*x**3 - 50*x**2 + 55*x - 21) Out[15]: 5 4 3 2 x - 5⋅x + 30⋅x - 50⋅x + 55⋅x - 21 which if I'm not mistaken, means that it is irreducible (by the way Mateusz, Poly.is_irreducible seems to be broken). > > But we don't want to discuss the theoretical subtleties of the abel- > ruffini theorem. > > My point is that we can't be sure that an arbitrary matrix will have > such a well-conditioned equation like (x - a)**n. Thus the charpoly > method (berwkowitz OR det(A-x*I), doesn't matter) is not a good > method, as it is not reliable for n > 5. The point I was making is that it doesn't matter what method you use. If the eigenvalue is not expressible in radicals, it's not expressible in radicals. > > The method will not return with an exact eigenvalue for large > matrices. > >> >> So there's no reason to just "give up" if the polynomial is degree 5 >> or higher unless you are always solving the general equation. You can >> easily create a square matrix of any size whose eigenvalues are easily >> expressed (in radicals, or for example just integers). Yes, there >> will be cases where it can only produce roots in the form of RootOf, >> but either just let those pass through, or raise the error only when >> that happens (depending on if it works to just let them pass through). > > RootOf is a good method, but only if the eigenval is the final result > desired by the user. What if the user wants the eigenvectors or the > SVD ? > Maybe we could follow the wolfram-alpha example. It returns with "root > of <charpoly> near <approximate solution>". Well, it depends on how well those functions play with it. A single RootOf object would be about as bad to work with as some arbitrary symbolic expression. Like I was saying before, if it can work with it (even if it has to return some enormous expression), just let it. It's better to give a symbolic solution when you can, even if the simplest form of it is not very simple. If it's literally impossible to work with such symbolic eigenvalues, maybe you could raise NotImplementedError. Note that RootOf only works for polynomials with numerical coefficients, so all the standard stuff is computable (e.g., you can compare them). For polynomials that solve() can't handle (whether they aren't solvable or it just isn't implemented) with symbolic coefficients, you will just have to raise NotImplementedError if you need all n roots. > > So, that RootOf objects could return the approximate value if > explicitly asked for. Yes: In [23]: [RootOf(x**5 - 5*x**4 + 30*x**3 - 50*x**2 + 55*x - 21, i).evalf() for i in range(5)] Out[23]: [0.603805884142291, 1.5398957188017 - 4.39504023164041⋅ⅈ, 0.658201339127155 - 1.08185949306609⋅ⅈ, 0.658201339127155 + 1.08185949306609⋅ⅈ, 1.5398957188017 + 4.39504023164041⋅ⅈ] > >> >> And by the way, maybe you were thinking that the characteristic >> polynomial isn't computed by det(A - x*I), as is often taught in >> linear algebra courses? > > Didn't get you here. det(A - x*I) or berkowitz both give a charpoly. > So it wouldn't matter which we use, other than the fact that one is > faster than the other. I was referring to Vinzent's remark that the eigenvalues weren't computed from the characteristic polynomial. Aaron Meurer > >> >> Aaron Meurer >> >> >> >> >> >> >> >> On Sun, Jun 12, 2011 at 6:49 AM, SherjilOzair <[email protected]> wrote: >> >> > On Jun 12, 3:09 am, Vinzent Steinberg >> > <[email protected]> wrote: >> >> On 11 Jun., 10:47, SherjilOzair <[email protected]> wrote: >> >> >> > Do you require to solve eigenvalue problems of matrices bigger than >> >> > 4*4 ? >> >> > How are you doing it currently ? >> >> > Matrix.diagonalize only works for matrices smaller than 5*5, as >> >> > polys.roots can only solve degree 4 equations and less. >> >> >> This is not entirely true, because we can find roots of higher order >> >> using for examples factorization. But yes, for equations of degree >> >> greater than 4 there is no general algorithm. But this does not matter >> >> in this case, because sympy does not calculate eigenvalues using the >> >> characteristic polynomial AFAIK. >> >> > Arbitrary higher-order equations can not be solved. >> > And characteristic polynomial of an arbitrary matrix is arbitrary. >> > This means, that we can't use that method to compute eigenvals >> > reliably. >> > I don't think there are any other direct methods, though. >> >> > sympy uses this method. >> >> > def berkowitz_eigenvals(self, **flags): >> > """Computes eigenvalues of a Matrix using Berkowitz method. >> > """ >> > return roots(self.berkowitz_charpoly(Dummy('x')), **flags) >> >> > eigenvals = berkowitz_eigenvals >> >> > Or are you referring to something else ? >> >> >> Vinzent >> >> > -- >> > You received this message because you are subscribed to the Google Groups >> > "sympy" group. >> > To post to this group, send email to [email protected]. >> > To unsubscribe from this group, send email to >> > [email protected]. >> > For more options, visit this group >> > athttp://groups.google.com/group/sympy?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/sympy?hl=en. > > -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
