3
$\begingroup$

I'm making a program which uses simple bisection method to find the roots of a polynomial. For me to implement this method, I need a rough interval where it can be said with absolute certainty that all the roots are lying. I wasn't quite able to find such a method.

$\endgroup$
4
  • 1
    $\begingroup$ What if the polynomial has no real solution? $\endgroup$
    – N74
    Jun 11, 2016 at 8:58
  • $\begingroup$ How many degrees should the polynomial have at most ? $\endgroup$ Jun 11, 2016 at 9:11
  • 3
    $\begingroup$ A two-second Google search of "bounds of polynomial roots": en.wikipedia.org/wiki/… $\endgroup$ Jun 11, 2016 at 9:11
  • $\begingroup$ Maybe Sturm sequences can help you: en.m.wikipedia.org/wiki/Sturm%27s_theorem $\endgroup$
    – user274886
    Jun 11, 2016 at 9:14

2 Answers 2

4
$\begingroup$

Up to division by a constant, $$p(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_0$$

Call $M=\max\{1,\lvert a_0\rvert,\lvert a_1\rvert,\cdots,\lvert a_{n-1}\rvert\}$

For $\lvert x\rvert\ge 1$, by inverse triangular identity you know that $$\lvert p(x)\rvert\ge \lvert x\rvert^n-nM\lvert x\rvert^{n-1}=\lvert x\rvert^{n-1}(\lvert x\rvert -nM)$$

So, for $n\ge2$, $p(x)\ne 0$ as soon as $\lvert x\rvert\ge nM$.

So, all the real roots of $p$ must lie in $[-nM,nM]$. This does not guarantee the existence of roots in that interval (because $p$ might not have any). However, to check it there's Sturm's theorem.

$\endgroup$
3
$\begingroup$

Extend to complex plane, you can use Rouche's theorem to conclude that zeros of polynomial $a_nz^n+...+a_0$ (where $a_n\neq 0$ and $a_0\neq 0$) lies in $A(0;r,R)=\{r<|z|<R\}$ where $R=1+\frac{\max\{|a_j|:0\leq j\leq n-1\}}{|a_n|}$, $r=(1+\frac{\max\{|a_j|:1\leq j\leq n\}}{|a_0|})^{-1}$. See Problem 6.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .