1
$\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$
4
  • $\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$ Commented May 23, 2018 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$ Commented May 23, 2018 at 15:08
  • 1
    $\begingroup$ Just multiply the equation by a suitable constant so that it becomes $-(kx)^q+(kx)^p=m$ then change variabile. $\endgroup$ Commented May 23, 2018 at 17:44
  • $\begingroup$ hence $k=(a/b)^{1\over q-p}$. $\endgroup$ Commented May 23, 2018 at 22:34

2 Answers 2

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.

$\endgroup$
3
  • $\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
    Commented May 23, 2018 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$ Commented May 23, 2018 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$ Commented May 23, 2018 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.

$\endgroup$
1
  • $\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
    Commented Jul 5, 2016 at 10:03

You must log in to answer this question.

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