Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Recent posts on polynomials have got me thinking.

I want to find the real roots of a polynomial with real coefficients in one real variable $x$. I know I can use a Sturm Sequence to find the number of roots between two chosen limits $a < x < b$.

Given that $p(x) = \sum_{r=0}^n a_rx^r$ with $a_n = 1$ what are the tightest values for $a$ and $b$ which are simply expressed in terms of the coefficients $a_r$ and which make sure I capture all the real roots?

I can quite easily get some loose bounds and crank up the computer to do the rest, and if I approximate solutions by some algorithm I can get tighter. But I want to be greedy and get max value for min work.

share|improve this question
    
Maybe not the best you can do, but roots $\lambda$ of $p$ satisfy $|\lambda| \le \max(|a_1|, \ldots, |a_n|)$ (works when $a_n = 1$), so it gives you something to work with. –  Joel Cohen Jun 30 '11 at 20:36
add comment

2 Answers

up vote 2 down vote accepted

What counts as "simply expressed"? The Fujiwara bound on the magnitude of all the roots (complex ones included) is certainly a very good starting point. I used it for a solution to a codegolf.SE problem involving complex roots and found it perfectly good enough for that context.

share|improve this answer
    
I asked my first question. I learned something. That's a good link. –  Mark Bennet Jun 30 '11 at 20:48
add comment

I actually had to do this for school about a month ago, and the method I came up with was as follows:

  1. Note that all zeros of a polynomial are between a local minimum and a local maximum (including the limits at infinity). However, not all adjacent pairs of a min and a max have a zero in between, but that is irrelevant.
  2. Therefore, one can find the mins and maxes and converge on the root in between by using the bisection method (if they're on opposite sides of the x-axis).
  3. Finding the mins and maxes is accomplished by taking the derivative and finding its zeros.
  4. Considering that this is a procedure for finding zeros, step 3 can be done recursively.
  5. The base case for recursion is a line. Here, $y=ax+b$ and the zero is $-\frac{b}{a}$.

This is a very easy and quick way to find all real zeros (to theoretically arbitrary precision). :D

share|improve this answer
add comment

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.