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

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 :-)

• Just because an expression is in closed form doesn't mean it's better (numerically, computationally) to evaluate that closed form over an equivalent iterative algorithm. Closed-form solutions for polynomials of degrees higher than 2 tend to be kind of gnarly, and are better solved through other methods. – Kirill Apr 27 '19 at 16:29

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