Is the notion "If a polynomial has small coefficients (relative to the exponent), then it has small roots" true?

Question

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?

Answer 1

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.

Answer 2

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}}$$

Answer 3

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.

Answer 4

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.