27
$\begingroup$

Basically I'm trying to find good starting values for algorithms that determine the roots of a polynomial (e.g. newton method). Obviously we are trying to get as close as possible to the root as we can, but how can we estimate where the roots of a polynomial lie?

Is a argument like: "If the coefficients are relatively small compared to the degree of the polynomial, then the magnitude of the roots is somewhere near the coefficients" correct?

Are there counterexamples of polynomials with very small coefficients and very large roots?

$\endgroup$
3
  • 11
    $\begingroup$ wikipedia has a list of bounds of for roots of polynomials: en.wikipedia.org/wiki/… if you assume the $a_n$=1 then e.g. the hölders inequality give you that the bounds for the root is the square root of the sum of the squares of the coefficients. but you can get better bounds from the inequalities listed there.. $\endgroup$
    – mond
    Mar 3 at 10:11
  • 1
    $\begingroup$ Also, consider a polynomial $p$ with arbitrary coefficients and let $a$ be the coefficient with the largest modulus. Then in some sense, $p/a$ has small coefficients (modulus at most 1). If that's not small enough, divide by a sufficiently large number $b>>a$. The polynomial still has the same roots as the original polynomial. The takeaway: the size of the coefficients has zero influence on the roots. $\endgroup$ Mar 3 at 10:15
  • 6
    $\begingroup$ Perhaps OP meant size of coefficients in the monic polynomial? $\endgroup$
    – HehBot
    Mar 4 at 3:34

4 Answers 4

51
$\begingroup$

There exist estimates for the size of the largest root. The most general go back to the idea that $z$ is not a root of $$ p(z)=a_nz^n+a_{n-1}+...+a_1z+a_0 $$ if $|z|>R>0$ with an outer root radius $R$ that satisfies the intequality $$ |a_n|R^n\ge |a_{n-1}|R^{n-1}+...|a_1|R+|a_0| $$ This polynomial inequality for $R$ is easier to solve numerically than zeroing in on any specific root of the original polynomial. Especially as for the further numerical purposes only a low relative accuracy is needed. The smallest $R$ is obtained as the only positive root of a polynomial with only one sign change in the coefficient sequence, meaning there is exactly one positive root. This situation allows for the secure use of simple scalar root-finding methods like the Newton method.

But one can also obtain simple (over-)estimates like $$ R=\max\left(1,\frac{|a_{n-1}|+...+|a_0|}{|a_n|}\right) $$ or $$ R=1+\frac{\max_{k<n} |a_k|}{|a_n|} $$

These estimates support the general idea, if the coefficients are small relative to the leading coefficient, then the roots will also be small.

The last bounds only give $R\ge 1$. To get beyond that restriction, "guess" a smaller scale $\rho$ and compute the root bound $R_\rho$ from $p_\rho(z)=p(\rho z)$. Then $R=\rho R_\rho$ gives a better bound. $\rho$ can be estimated as power of 2 from the exponent of the coefficients as floating-point numbers. The aim is that the coefficient sequence of $p_\rho$ is about balanced with the leading coefficient dominating and at least one other coefficient of similar magnitude.

I'd recommend studying the techreport to the Jenkins-Traub RPOLY method. I have some of that also reproduced in the corresponding Wikipedia article.

$\endgroup$
2
  • $\begingroup$ In the first paragraph, can $R \ge 1$ be weakened to $R > 0$? $\endgroup$
    – Rufflewind
    Mar 4 at 10:32
  • $\begingroup$ Thank you, done. And added some adaptive mechanism. $\endgroup$ Mar 4 at 13:19
32
$\begingroup$

No. Take a polynomial with all roots "very large" (according to the context), and scale it down by dividing by an even larger number.

To employ the counterexample in the comments, take $p(x) = x - 10^{50}$.
Then, $q(x) = 10^{-100}p(x)$ is also a polynomial, with root $10^{50}$. But $$q(x) = \color{blue}{10^{-100}}x - \color{blue}{10^{-50}}$$

$\endgroup$
2
  • 3
    $\begingroup$ So this shows that one would want to "normalize" the polynomial into a monic polynomial (polynomial with leading coefficient (coefficient of the highest-degree term) equal to 1). Or, equivalently, like in the answer by Lutz Lehmann, take everything relative to the magnitude of the leading coefficient. $\endgroup$ Mar 6 at 9:18
  • $\begingroup$ Yes, @JeppeStigNielsen I use the freedom of scaling as we wish to get counterexamples, but this freedom is restricted if we take a monic polynomial. $\endgroup$
    – D S
    Mar 6 at 9:34
0
$\begingroup$

A bit late to the party, but I always find it insightful to look at the easiest or most know answers. In this case look at the standard roots for the quadratic equation $ax^2+bx+c$: $$ x = \frac{-b\pm \sqrt{b^2-4ac}}{2a} $$ From this we can see that whenever $a$, the coefficient of the quadratic term, is very small compared to $b$, there will be a very large negative root, which is a simple counterexample to your statement.

To provide some insight to your overarching question of finding relatively good intial guesses, you might want to find an $x_0$ s.th. $f(x_0)f''(x_0)>0$, which can be done relatively easily for polynomial functions.

See Darboux's theorem for more details.

$\endgroup$
-1
$\begingroup$

Say you want to solve the polynomial equation: $$ \sum_{n=0}^da_nx^n = 0 $$ with $a_d\neq 0$. You can normalise the equation by setting $a_d=1$ (possible since it is non zero). I will also assume that $a_0\neq0$ or else you can always factor out powers of $x$. By rescaling $x$, I can also assume $a_0=-1$.

There won't be a one size fits all. One possible approach is to revert to the "closest" equation which you can solve analytically and use its solutions or its perturbed solutions as starting values. This reference equation may be more or less natural depending on your context.

A natural general limit is when $a_1 ... a_{d-1}$ are all zero since the non perturbed solutions are the $d$ roots of unity. Formally, you can introduce the parameter $\lambda$ and solve generally for: $$ x^d=1-\lambda\sum_{n=1}^{d-1}a_nx^n $$ Your equation is $\lambda=1$, and you can solve it by taking for initial values the perturbed solutions in the limit $\lambda\to0$ by setting $\lambda=1$. At leading order, you have the $n$ roots for $k=1 ... d$: $$ x_k = e^{i2\pi k/d}-\frac\lambda d\sum_{n=1}^{d-1}a_ne^{i2\pi kn/d}+O(\lambda^2) $$ The issue with this method is that the perturbative method will give a reasonable approximation as long as for all $|\lambda|\leq 1$ there is no collision of the roots. If not, the radius of convergence of the perturbation method will not be larger than $1$, so it will not converge when you set $\lambda=1$.

Hope this helps.

$\endgroup$
3
  • $\begingroup$ Did you ever encounter the Dandelin-Graeffe iteration that allows to rapidly and rather precisely identify annular regions and how many roots they contain? $\endgroup$ Mar 19 at 9:24
  • $\begingroup$ No thanks for the reference $\endgroup$
    – LPZ
    Mar 20 at 7:04
  • $\begingroup$ It is also known as "root squaring", as the roots of the new polynomial are the squares of the original roots. Repeated application quickly isolates the roots in scale. The coefficient relation is similar or the same as used in your other answer for the $c_k$ that should be $b_k$. $\endgroup$ Mar 20 at 9:24

You must log in to answer this question.

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