Help understanding Brent's root finding method

Question

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.

Answer 1

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

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.