Let we have algebraic equation on one variable. Which methods (exept Sturm's theorem and Descartes' rule) exist to find real roots of equation (or real positive)?
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ This is what "root systems" mean: en.wikipedia.org/wiki/Root_system . Retagged as polynomials for now. $\endgroup$– Willie WongCommented Nov 6, 2010 at 15:04
-
2$\begingroup$ Also, without further motivation ad clarification, your question is overbroad: please read the FAQ and note the part where it says MO is not an encyclopaedia. $\endgroup$– Willie WongCommented Nov 6, 2010 at 15:05
-
$\begingroup$ I'm personally fond of using Sturm sequences to generate the (symmetric!) tridiagonal matrix whose characteristic polynomial is the original polynomial. If there is no such matrix, you know at once that the polynomial has complex roots. $\endgroup$– J. M. isn't a mathematicianCommented Nov 6, 2010 at 15:41
-
$\begingroup$ I tend to agree with Willie here. $\endgroup$– Nikita SidorovCommented Nov 6, 2010 at 16:08
-
$\begingroup$ I would agree with the encyclopaedia criticism, except that in this case, once you ruled out Sturm's theorem and Descartes' rule, there shouldn't be much left. $\endgroup$– Thierry ZellCommented Nov 6, 2010 at 16:13
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
Well, it depends what you mean by finding. Computer algebra systems commonly use isolation methods (approximations) that are based on an improved Uspensky's algorithm (by Rouillier and Zimmerman), but that's based off Descartes's rule of signs.
On the other hand, you can encode a real root by specifying the signs of all derivatives of the polynomial at the root. Thom's lemma guarantees that there cannot be more than one root satisfying all the sign conditions. Sturm's theorem helps you find which conditions are met. This does not give you any approximation of the root, but surprisingly enough allows you to compute symbolically with them. More details about this can be found on the book by Basu-Pollack-Roy freely available here.
I realize both of these options are refinements of the things you didn't want to talk about... I don't know of any other methods though (or if I do, they're escaping me right now).
answered Nov 6, 2010 at 15:15
-
$\begingroup$ Thank you so much for answer. actually I am interesting first of all to find how many real solutions has my polynomial (so finding here means finding number of real solutions or positive real solutions). I can not use Descartes's rule because my coefficient depend on parameters (with some conditions on parameters) and I do not know sign of all coefficients. To use Sturm's theorem is also difficult because there I need to find remainder(f_{i-1},f_{i}) what is hard. Thank you for the book! it is really interesting! $\endgroup$– AndriyCommented Nov 7, 2010 at 17:58
-
$\begingroup$ Andriy: In that case, what you really want to use is the Cylindrical Algebraic Decomposition (also explained in the book, and available in any standard computer algebra system such as Maple or Mathematica). You can write a formula that describes, for instance, the fact that your polynomial has at least 3 distinct real roots, and the algorithm will return polynomial conditions on your coefficients that are equivalent to the initial statement. $\endgroup$ Commented Nov 7, 2010 at 21:32