# Help understanding Brent's root finding method

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.

• Note that there is a more readable explanation of Brent's method on Wikipedia. Oct 26, 2020 at 13:57