What is the convergence rate of Brent's method (root-finding algorithm)?

Question

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?

Answer 1

Corrected answer:

After a lot of testing on my own time, I noticed a particular anomaly when running Brent's method to high precisions. Brent's method never attains an order of convergence of $\mu\approx1.839$. In fact it doesn't attain an order of convergence of $1.7$. After spending some time working through the details, I found that Brent's method actually attains an order of convergence of at most $\mu^{1/3}\phi^{2/3}\approx1.689$ in general. I'll also point out that my implementation of Brent's method is essentially a copy of the one on Wikipedia, which may be incorrect.

As I discuss below in my now incorrect answer, the asymptotic behavior of inverse quadratic interpolation is dependent on the sign of $C$ (defined below). If $C<0$ then inverse quadratic interpolation always yields estimates on one side of the root. This leads to secant-like behavior on one side of the root and an order of convergence given by $\phi\approx1.618$.

If $C>0$, then a much more interesting situation happens. Let $a,b,c$ be the bracketing point, the best estimate of the root, and the previous value of $b$ respectively (as done on Wikipedia). Consider the case when $b$ and $c$ are on the same sides of the root.

1. According to below, the new IQI estimate $s$ will replace $a$.

2. $c$ is then set to $b$.

3. $a$ is then set to $b$.

4. $a$ and $b$ are swapped.

5. Since $a=c$ now, IQI cannot be used, causing the secant method to be used to compute $s$ instead of IQI.

• Suppose $s$ is on the same side as $a$. We consider the opposite case later. (The side that the secant $s$ lands on is fixed.)

6. $c$ is then set to $b$.

7. $a$ is then set to $s$.

8. $a$ and $b$ are swapped, since the new estimate is better than the previous.

9. Since $a=c$ again, IQI still can't be used, so another round of the secant method is tried.

10. $c$ is then set to $b$.

11. $b$ is then set to $s$. Note that the secant $s$ lands on the same side of the root.

12. IQI is applied again, repeat all previous steps.

Concerning the case when the secant method lands on the same side as $b$ on step 5-6, we skip to step 12 and the next iteration will enter the above loop.

In total, the above cycle yields one IQI iteration and two secant iterations. Since only the best estimates of the root are used for each case, we can safely confirm that the optimal order of convergence for each method is used. This leads to an order of convergence of $\mu\phi^2$ over 3 iterations, or an expected $\mu^{1/3}\phi^{2/3}$ per single iteration.

---

Erroneous claim:

It is not actually the case that Brent's method always has an order of convergence of $\mu\approx1.839$ as given by hardmath's answer. This behavior is similar to what I have described concerning Ridder's method in this answer. In particular, if

$$C=\frac16(f^{-1})'''(0)[f'(x_\mathrm{root})]^3$$

is positive, then the order of convergence is indeed $1.839$. If it is negative, or negative in a neighborhood of the root, then the order of convergence actually drops down to $\phi\approx1.618$, which is the speed of the secant method.

This is of course assuming that the root is simple.

Answer 2

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.