Positive root of $x^q + bx - b$

Question

Is there either a closed-form expression or fast/elegant algorithm for computing the positive root of the polynomial $$f(x)=x^q + \beta x - \beta,$$ where $\beta>0$ and $q\geq2$? How about the $q\in\mathbb R$ case with $q\geq1$?

Note there is exactly one positive root of the function $f(x)$, since $f(0)=-\beta<0$, $\lim_{x\to\infty} f(x)=\infty$, and $f(x)$ is a convex function on $\mathbb R_+$ given our bound on $q$.

Bracketing/bisection will give an estimate in linear time, and by the argument in this response I guess Newton's method will have have global quadratic convergence specifically for this function so long as $q\geq2$. Just wanted to make sure I'm not missing a more slick approach!

I'll be embarrassed if there's an obvious closed-form expression that I missed :-)

Answer 1

According to Wolfram Alpha, $x^5+3(x-1)=0$ has no closed-form solution, so you can forget about a nice closed-form expression. :)

I see nothing wrong with Newton's method; it should be quick and accurate, and with some analysis like the one you are sketching I think you can identify a safe starting point and prove global convergence. It might even be faster than a complicated closed-form solution for $q=4$.

Answer 2

You have demonstrated that the polynomial has only a single positive root (I assume here that you are only interested in positive real roots). Using Cauchy's upper bound for polynomial roots $$1+ \max\left\{\left|\frac{a_{n-1}}{a_{n}}\right|, \left|\frac{a_{n-2}}{a_{n}}\right|, \ldots, \left|\frac{a_{0}}{a_{n}}\right|\right\}$$ you can obtain an upper bound for the roots of your polynomial equal to $U = 1+\beta$. Hence you have your root bracketed $x_0 \in [0, 1+\beta]$.

Next, I would use a guaranteed solver like the Dekker-Brent method. This method combines bisection (slow but sure) with inverse quadratic interpolation (fast but could predict outside the bracketed interval). It has superlinear convergence ($p\approx 1.6$ if I'm not mistaken) so it might be slower than Newton's method but it has the guarantee that it will converge. Newton's method might "jump" to another root.