As far as I know, Brent's method for root finding is said to have superlinear convergence, but I haven't been able to find any more concrete information.
Is its convergence rate known to be at least bounded between some known values?
What is a good bibliographic reference for that?
[EDIT]
Also, another related question (I add it here because it is closely related to the previous one): How many calls to the function makes Brent's method per iteration, on average?
[EDIT]
Thanks to a comment by @Barry Cipra, I've reviewed the original source (Brent, 1971).
This gave me an answer to one of my two questions:
- Brent's algorithms calls the function whose root is to be found once per iteration.
The first question I posted remains open to me, as I am not an expert. As far as I understand, Brent's algorithm combines bisection with inverse quadratic interpolation. Bisection convergence is known to be linear, but I don't know about the convergence rate of inverse quadratic interpolation.
I guess the convergence rate of Brent's method can be considered to be bounded between linear and that of inverse quadratic interpolation. So, the remaining question is: What is the convergence rate of inverse quadratic interpolation?
Best Answer
Brent proposed his method as combining bisection steps, with guaranteed linear convergence, with inverse quadratic interpolation, whose order of convergence is the positive root of:
$$ \mu^3 - \mu^2 - \mu - 1 = 0 $$
Thus $\mu \approx 1.839$. We can compare this with the "golden section" order of convergence of the secant method, the positive root of:
$$ \phi^2 - \phi - 1 = 0 $$
or $\phi \approx 1.618 $ on one hand, and the order of convergence 2 of Newton's method on the other.
Of course there are trade-offs involved. Inverse quadratic interpolation requires only one new function evaluation per step, like the secant method, but uses a more complicated formula to update the root approximation, and inverse quadratic interpolation avoids the evaluation of a derivative as Newton's method requires.