6
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – Kirill Apr 27 at 16:29
10
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.