Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)?

share|improve this question
1  
This is what "root systems" mean: en.wikipedia.org/wiki/Root_system . Retagged as polynomials for now. –  Willie Wong Nov 6 '10 at 15:04
2  
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. –  Willie Wong Nov 6 '10 at 15:05
    
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. –  J. M. Nov 6 '10 at 15:41
    
I tend to agree with Willie here. –  Nikita Sidorov Nov 6 '10 at 16:08
    
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. –  Thierry Zell Nov 6 '10 at 16:13

1 Answer 1

up vote 2 down vote accepted

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).

share|improve this answer
    
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! –  Andriy Nov 7 '10 at 17:58
    
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. –  Thierry Zell Nov 7 '10 at 21:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.