Finding an interval in which all the real roots of a polynomial lie

Question

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.

Answer 1

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.

Answer 2

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.