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" ]
Abs[e*q] > 3*xm*q-Abs[tol*q]
Also suppose (tol) is approximately zero. Then the If condition is effectively:
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.