Conditions of Brent's method

[wj636]

Hello,

I checked your video on Brent's method for root finding and I'm having trouble understanding the second condition that we test before choosing Secant/IQI/Bisection.

If the previously used method is Secant/IQI, we check if abs(s-b) < 1/2 * abs(c-d) and if it's not we use bisection, otherwise Secant/IQI. My question is why do we look at the second to last steps if the previously used method is Secant/IQI ?

Also, I checked the wikipedia page of the Brent's algorithm here and it additionally uses a tolerance to check the last and second to last steps. In your tutorial, you didn't introduce these additional checks, are the two methods equivalent ?

Thank you in advance for your answer

[osveliz]

Hi @wj636

The second condition test is there to force a Bisection in the event that Secant/IQI aren't reducing the size of the interval enough. It is a heuristic that looks at the trend of the step sizes, and if all is going well, it never needs to force a Bisection. Without it though, the method can't guarantee that it will converge in a reasonable number of iterations.

The tolerance check mattered a lot more when Brent first published "Algorithms for Minimization Without Derivatives", but nowadays Arithmetic Logic Units (processors in general) have gotten really good at doing high precision mathematics. Truncation and Roundoff errors are still a thing, although odds are that the ending epsilon being used is much larger than the machine precision on the chip. I didn't include the tolerance checks just to simplify the algorithm.