0
$\begingroup$

I'm trying to find upper and lower bounds of the smallest positive root of a polynomial, stated in terms of its coefficients. As I appreciate it might be a very general problem, My specific interest is in polynomials of the sort

$$ -ax^q + bx^p -c = 0 \, \quad a,b,c>0\, , \quad q>p \, .$$

I know that, under some restrictions, it has real positive roots, and so I'd be interested in either-

  1. Upper and lower bounds on the smallest positive root.
  2. Upper and lower bounds of all real roots.
  3. Upper and lower bounds for all positive roots.
  4. Bounds on the roots of a general polynomial.
  5. Bounds for the specific case $q=p+1$.

Thanks

Amir

$\endgroup$
  • $\begingroup$ note that one can absorb $a$ and $b$, exploiting the different homogeneity, and reduce the equation to a simpler form with $a=b=1$ $\endgroup$ – Pietro Majer May 23 '18 at 6:26
  • $\begingroup$ @Pietro Majer, I'm not familiar with this. Can you elaborate (or give a reference) on how to do this simplifying reduction? $\endgroup$ – Iddo Hanniel May 23 '18 at 15:08
  • $\begingroup$ Just multiply the equation by a suitable constant so that it becomes $-(kx)^q+(kx)^p=m$ then change variabile. $\endgroup$ – Pietro Majer May 23 '18 at 17:44
  • $\begingroup$ hence $k=(a/b)^{1\over q-p}$. $\endgroup$ – Pietro Majer May 23 '18 at 22:34
4
$\begingroup$

The structure of the polynomial $P(x)=−ax^q+bx^p−c$, for $a,b,c>0$, $q>p$ is very suitable for analysis with Descartes Rule of Signs. Since $P(x)$ has two sign changes in its coefficients it can have two or no real positive roots. Since you assume in the question it has positive roots, it must have exactly two.

Furthermore, denoting $d=q-p$, it's derivative is $P'(x)=x^{p-1}(-aqx^d + bp)$. Therefore, it has a single positive extremum point at $x_d=(\frac{bp}{aq})^{\frac{1}{d}}$.

The second derivative is $P''(x)=x^{p-2}(-aq(q-1)x^d + bp(p-1))$, which is negative for $x > (\frac{bp(p-1)}{aq(q-1)})^{\frac{1}{d}}$. In particular, it is negative for $x > (\frac{bp}{aq})^{\frac{1}{d}} = x_d$ so we know $x_d$ is a maximum point (by the way, evaluating $P$ at this point can be a way of determining whether there are zero or two roots). By Rolle's Theorem, this means that one of the roots is smaller and one greater than $x_d$. This already tells us that the $(b/a)^{1/d}$ bound by @Robert Israel is pretty tight since the largest positive root $x^*$ satisfies $(\frac{bp}{aq})^{\frac{1}{d}} < x^* < (\frac{b}{a})^{\frac{1}{d}}$.

But we can do even better. Since $P''$ is negative for $x>x_d$, the function is convex for $x>x_d$. Thus, we can perform Newton's method, starting at an upper bound and get a sequence of upper bounds on $x^*$ that converges from above to $x^*$. This can be formulated and proved formally but I think it's easier to demonstrate with a figure. The figure shows the first two Newton iterations for $P(x)=-x^3+8x^2-10$. Newton's method converges quadratically and even a single iteration improves the bound nicely. enter image description here

Since the function is convex, we can also bound $x^*$ from below using the false position method. This will give us a a sequence of lower bounds that converges from below (although with a slower convergence rate).

For a lower bound on the positive roots (i.e., bound on the smallest positive root) there is a standard trick using the polynomial $Q(x)=x^q P(1/x)$ (I don't have a good reference for this, I think I remember it as part of Uspensky's method). $x$ is a root of $Q(x)$ if $1/x$ is a root of $P(x)$. So if $x$ is an upper bound on the positive roots of $Q(x)$, then $1/x$ is a lower bound on the positive roots of $P(x)$. What is nice in your context is that the same arguments and methods we applied on $P(x)$ can be applied to $Q(x)$ since its coefficients are just the coefficients of $P$ in reverse order and therefore it also has two sign changes and a single extremum. In fact in your context $Q(x) = -c x^q + b x^d - a$ and the initial upper bound from above becomes $(\frac{b}{c})^{\frac{1}{p}}$, which gives the lower bound of $(\frac{c}{b})^{\frac{1}{p}}$, which is the one from the answer by @Robert Israel.

Finally, for negative roots, the standard trick is to analyze the roots of $R(x)=P(-x)$. In your context, this can have zero, one or two sign changes depending on the parity of $p$ and $q$. Each case needs to be analyzed separately but I believe similar arguments should hold for these as well.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Iddo thanks! Will these method yield an upper bound on the lower root? Obviously, $x_d$ is a bound, but can we do better? $\endgroup$ – Amir Sagiv May 23 '18 at 6:54
  • $\begingroup$ Note there is a power series solution (after reduction of the equation to the form $x+x^s=c$, with possibly noninteger $s$ and small $c$) mathoverflow.net/questions/249060/… $\endgroup$ – Pietro Majer May 23 '18 at 7:59
  • $\begingroup$ @Amir, a lower bound $x$ on the larger root of $Q(x)$ will give you an upper bound $1/x$ on the lower root. Since $Q(x)$ is also convex to the right of its extremum, you can bound it from below using the false position method and get a series of tighter bounds. $\endgroup$ – Iddo Hanniel May 23 '18 at 12:20
1
$\begingroup$

The usual idea is to isolate a term on one side of the equation and find conditions under which one side dominates the other. For example,

$$ a x^q = b x^p - c$$ If $x$ is large, the left side is going to be larger than the right. Thus for $x > 0$, $b x^p - c < b x^p \le a x^q$ if $x \ge (b/a)^{1/(q-p)}$ so an upper bound on positive roots is $(b/a)^{1/(q-p)}$.

Similarly, a lower bound on positive roots is $(c/b)^{1/p}$.

For particular cases, you may get tighter bounds using Sturm's theorem.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. The Cauchy bound and the bounds you suggested might be too coarse for my goals, so I've edited my question so it is more informative. $\endgroup$ – Amir Sagiv Jul 5 '16 at 10:03

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.