3
$\begingroup$

I'm trying to list all roots of a polynomial so I found this paper, in Part 9 on page 29 it gives a simple recipe to find all the roots. But there is this remark:

We have assumed throughout the paper that our polynomial $p$ has all its roots in the unit disk. If instead the roots are in the disk $|z| < r$, you may simply scale all the starting points by a factor of $r$.

My problem is finding some $r$ which matches this. I can see that $r$ is basically any number larger than the maximum magnitude of all the roots. It dosen't matter if it's the smallest $r$, but the smaller the better.

I found a way that I have ben unable to find counter exambles to, albeit the $r$ will be much bigger in some cases, which is having $r$ be the product of the absolute value of all coefficients. (Not counting the polynomial $0$ since anything is a root). But I have no idea how I would go about proving that this $r$ is sufficient.

$\endgroup$
  • 1
    $\begingroup$ Taking $r$ to be the product of the coefficients doesn't work; in fact, the product of the coefficients can be made arbitrarily small without changing the roots. For instance, $0.01 z^2 - 1$ has the same roots as $z^2 - 100$: $z=\pm 10$. $\endgroup$ – mjqxxxx May 15 '14 at 17:15
  • $\begingroup$ See also this question. $\endgroup$ – Antonio Vargas May 15 '14 at 18:14
  • $\begingroup$ See en.wikipedia.org/wiki/Properties_of_polynomial_roots for various root bounds. $\endgroup$ – LutzL May 19 '14 at 6:52
3
$\begingroup$

Eventually the leading-order term dominates. More precisely, if your polynomial is $P(z)=a_n z^n + a_{n-1} z^{n-1} + \cdots + a_1 z + a_0$, then for large enough $|z|$ the term $a_n z^n$ is greater in magnitude than the sum of the magnitudes of all the other terms, and there can be no more roots. We want $$|a_n z^n|>|a_{n-1}z^{n-1}|+\cdots + |a_1 z| + |a_0|;$$ dividing both sides by $|z|^n$ gives the equivalent $$|a_n|>|a_{n-1}/z|+\cdots + |a_1/z^{n-1}| + |a_0/z^n|,$$ which is clearly true as long as $|z|>1$ and $$|z|>\frac{|a_{n-1}|+\cdots+|a_1|+|a_0|}{|a_n|}.$$

$\endgroup$
  • $\begingroup$ This is the Lagrange bound. Another is the Cauchy bound $r=1+\max\left\{\dfrac{|a_k|}{|a_n|}:k=0,...,n-1\right\}$. $\endgroup$ – LutzL May 19 '14 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.