Welcome to MathOverflow

Question

1

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

edited Nov 6 2010 at 15:03

Willie Wong
6,987●20●43

asked Nov 6 2010 at 14:49

Andriy
89●4

1

This is what "root systems" mean: en.wikipedia.org/wiki/Root_system . Retagged as polynomials for now. – Willie Wong Nov 6 2010 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 2010 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 2010 at 15:41

I tend to agree with Willie here. – Nikita Sidorov Nov 6 2010 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 2010 at 16:13

show 1 more comment

Thierry Zell · Accepted Answer · 2010-11-06 15:15:40Z UTC

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

real roots of algebraic equation

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.