Tolerance criteria Brent's method

Question

Stop criteria for Brent's method is

if abs(m) <= tol or fb == 0.0 then    // root found (interval is small enough) 
    found := true;

However, what if abs(m) reaches below said tolerance but the value of f(b) is no where close to zero? Will this case be considered as failed to converge or successfully converged? I can see that abs(m) < tolerance, i.e. |b-a| < tolerance, but the value of the function is not equal to zero or anywhere close. Isn't the whole point of Brent's method to find the root of a function such that f(b) == 0.0 or below a certain tolerance?

Is it always the case that when |b-a| < tolerance convergence is achieved even though the value of the function is not close to zero, i.e. below given tolerance?

Answer 1

If r is the root then you want to approximate r (not f(r)) to within a given tolerance, which is exactly what is happening here. It is of course possible that the graph of f is almost vertical at this point so that if b is your approximation f(b) isn't close to 0. If that happens, you need a smaller tolerance. For most applications, knowing a root to 6 decimal places is more than adequate, but if your application involves a function whose values can change dramatically in response to a change in the 7th decimal place you will of course run into problems. This is the reason why in a numerical analysis course, expressions for the error in the method involve bounds on the derivatives. You need some sort of smoothness assumption to get reasonable results.