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.

  • $\begingroup$ 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. $\endgroup$ – Joel Cohen Jun 30 '11 at 20:36

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.

  • $\begingroup$ I asked my first question. I learned something. That's a good link. $\endgroup$ – Mark Bennet Jun 30 '11 at 20:48

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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