1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Note that just looking for sign changes between integers doesn't guarantee that you will find all roots. For example $5x^2-5x+1$ is positive at all integer $x$ but has two roots between $0$ and $1$. $\endgroup$ Mar 11, 2015 at 13:30
  • $\begingroup$ Yes, if the method doesn't turn up the right number of solutions it'll halve the interval and run again. $\endgroup$
    – KnightOfNi
    Mar 11, 2015 at 13:37
  • $\begingroup$ x @KnightOfNi: How do you know what the "right number" of solutions is? A degree-$n$ polynomial has at most $n$ real roots, but can have fewer than that. $\endgroup$ Mar 11, 2015 at 13:39
  • $\begingroup$ @HenningMakholm That's an excellent point. One of the function's terminating cases is if the interval falls below $1/1024$; in that case I'll just assume I have intervals representing all real solutions. This won't be true in every case, obviously, but it will be true in a vast majority. $\endgroup$
    – KnightOfNi
    Mar 11, 2015 at 13:50
  • $\begingroup$ x @KnightOfNi: You'll probably want to supplement that with Descartes' rule of signs. A completely different approach would be to start by (recursively) finding the roots for the derivative. These are the stationary points of $f$, and there's at most one root of $f$ between two of them. $\endgroup$ Mar 11, 2015 at 14:11

3 Answers 3

4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ While I absolutely agree this method is far superior, I'm writing this program for a CS course. I have some leeway in how I can implement it (hence this question), but I'm required to use bisection. Given that, is there anything I can use to find the range of the zeroes? $\endgroup$
    – KnightOfNi
    Mar 11, 2015 at 13:17

You must log in to answer this question.

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