How to find the range of zeroes in a polynomial

Question

I am writing a java program that finds all of the zeroes of a polynomial by bisection. The first step, clearly, is to iterate through integers in a certain range looking for sign changes. I could simply use Integer.MIN_VAL and Integer.MAX_VAL for my range, but that seems horribly inefficient. Is there a method (preferably relatively simple to implement in a program) that can give me a better idea of what range to look in? Or am I out of luck? It needs to work on polynomials of any degree.

Answer 1

There are several bounds on the size of polynomial roots. Two of the easier ones are $$ R=1+\max_{k=0,...,n-1}\left|\frac{a_k}{a_n}\right| $$ and $$ R=\max\left(1,\frac{|a_0|+|a_1|+...+|a_{n-1}|}{|a_n|}\right). $$

See also https://en.wikipedia.org/wiki/Properties_of_polynomial_roots#Bounds_on_.28complex.29_polynomial_roots

Answer 2

The bisection method, very useful from a logical point of view, as you have noticed, is terribly inefficient from a computational one.

There are several other methods, the most efficient I found for polynomials is the Newton-Raphson one.

Given a function $f$, derivable on an interval, you guess $x_0$ is a root, if it's not you approximate the function linearly by the curve $y = f'(x_0)(x-x_0) + f(x_0)$ then find the $x_1$ where $y=0$ i.e. $x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$, try if $f(x_1)=0$. If $x_1$ is not a root reiterate the procedure til the precision desired.

Answer 3

Let $P = a_n x^n + \dots + a_0$.

You can find explicitly $\tilde x_{\max} = \sum_k (|a_k/a_n|)^{1/(n-k)}$, from which $a_n x^n$ dominates over $a_k x^k$. This gives you an upper bound for the absolute value of the largest root.

Fujiwara bound is $x_{\max} = \max ( |a_0/a_n|^{1/n} + 2\max_{n>k>0} |a_k/a_n|^{1/(n-k)})$, see http://www.sciencedirect.com/science/article/pii/S0377042703003819 and http://www.sciencedirect.com/science/article/pii/S0377042703009397