1
$\begingroup$

Help me understand a part of Brent's root finding algorithm. In a typical iteration we have samples (a,fa), (b,fb), (c,fc) all real with (a<b<c) or (c<b<a) . Also, in the case I am interested in (1< fa/fb) and (fc/fb <= -1). In that case (using Mathematica syntax), the algorithm attempts inverse quadratic interpolation as follows:

xm=(c-b)/2;
s=fb/fa;
q=fa/fc;
r=fb/fc;
p=s*(2*xm*q*(q-r)-(b-a)(r-1));
q=(q-1)(r-1)(s-1);
If[0<p,q=-q];
p=Abs[p];
If[2*p-Min[Abs[e*q],3*xm*q-Abs[tol*q]]<0,
  "Accept Inverse Quadratic Interpolation",(* else *)"Take a Bisection Step"
]

Suppose

Abs[e*q] > 3*xm*q-Abs[tol*q]

Also suppose (tol) is approximately zero. Then the If condition is effectively:

2*p-3*xm*q<0

Please provide an explanation for why that is used in the condition, and provide values for (a,fa),(b,fb),(c,fc) that meet the inequalities above and put us on the edge of accepting the inverse quadratic interpolation.

$\endgroup$
  • 1
    $\begingroup$ Note that there is a more readable explanation of Brent's method on Wikipedia. $\endgroup$ – Simply Beautiful Art Oct 26 at 13:57
0
$\begingroup$

I was thinking of cases such as the blue and orange curves below. For the blue curve (a,fa)=(0,2.5); (b,fb)=(2.2,0.5); (c,fc)=(5,-0.5). For the yellow-orange curve (a,c,fa,fb,fc) are the same and (b=1.2). In each case inverse quadratic interpolation gives an approximate root similar to using a secant step, and the distance from b to the new approximate root is less than 0.5(c-b). figure1

An example that is on the edge of the If condition used in Brent's method is the blue curve below where (a,fa)=(0,2.5); (b,fb)=(0.5,4.4444444444444455); (c,fc)=(5,-0.5). An example where Brent's method rejects the inverse quadratic interpolation is the yellow-orange curve below where (a,b,c,fb,fc) are the same as the blue curve, but (fa=1.3). The blue curve below gets as far right as it ever gets at x=c=5. The point where the blue curve crosses the x-axis would be the next approximate root at x=b+(c-b)*3/4. That value is right on the edge of accepting the interpolation. figure2

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This answer looks more like an update to your question. $\endgroup$ – nicoguaro Oct 21 at 16:43
  • $\begingroup$ I figured out how to answer my question. In the second plot, the blue curve is on the edge of accepting the interpolation. The points that make the yellow-orange curve on the second plot would be an interpolation Brent's method would reject. $\endgroup$ – Ted Ersek Oct 22 at 13:29

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.