Fast and robust root of a cubic polynomial with constraints

If your function $f$ is convex and increasing, or concave and decreasing, on an interval $[a,b]$ that contains a solution of $f(x) = 0$, Newton's method starting at $b$ will converge to a solution. Similarly if it is concave and increasing, or convex and decreasing, and you start at $a$. For a cubic it's easy to identify the critical points and inflection and thus find such an interval.


I think you can avoid the Newton-Raphson altogether, since cubic is solvable in radicals.

Here is the complete algorithm (working under constraints outlined in the problem), in Mathematica:

Clear[PositiveCubicRoot];
PositiveCubicRoot[p_, q_, r_] := 
 Module[{po3 = p/3, a, b, det, abs, arg},
  b = ( po3^3 - po3 q/2 + r/2);
  a = (-po3^2 + q/3);
  det = a^3 + b^2;
  If[det >= 0,
   det = Power[Sqrt[det] - b, 1/3];
   -po3 - a/det + det
   ,
   (* evaluate real part, imaginary parts cancel anyway *)
   abs = Sqrt[-a^3];
   arg = ArcCos[-b/abs];
   abs = Power[abs, 1/3];
   abs = (abs - a/abs);
   arg = -po3 + abs*Cos[arg/3]
   ]
  ]

Then

In[222]:= PositiveCubicRoot[-2.52111798, -71.424692, -129.51520]

Out[222]= 10.499

However, if the Newton-Raphson method must be used, then a good initial guess is imperative. Binary division is a good method to isolate the root in the case at hand. We start with an arbitrary point $x$, I chose $x=1$, and double it while the polynomial at that point is negative. Then do binary division a certain number of times (the code below does it twice). Ultimately, polish it off with Newton-Raphson iterations:

In[283]:= 
NewtonRaphsonStartingPoint[{p_, q_, r_}] := Module[{x1=0, x2=1,f1,f2,xm,fm},
   f1 = r + x1 (q + (p + x1) x1);
   While[(f2 = r + x2 (q + (p + x2) x2)) <= 0, 
      x1 = x2; f1 = f2; x2 = 2 x2];
   Do[xm = (x1 + x2)/2; fm = r + xm (q + (p + xm) xm); 
    If[fm <= 0, f1 = fm; x1 = xm, f2 = fm; x2 = xm], {i, 2}];
   (f2 x2 - f1 x1)/(f2 - f1)
];
NewtonRaphsonIterate[{p_, q_, r_}, x0_Real] := 
 FixedPoint[
  Function[x, x - (r + x (q + (p + x) x))/(q + (2 p + 3 x) x)], x0]

In[285]:= 
NewtonRaphson[p_, q_, r_] := 
 NewtonRaphsonIterate[{p, q, r}, NewtonRaphsonStartingPoint[{p, q, r}]]

In[286]:= NewtonRaphson[-2.52111798, -71.424692, -129.51520]

Out[286]= 10.499