7

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?

Vicent
  • 231
  • 1
    The Wikipedia article says the exponent of convergence is roughly 1.8, so it's much better than bisection (linear convergence, exponent 1) and nearly as good as Newton's method (exponent 2, for an isolated root). How much detail or precision are you looking for? – hardmath May 19 '14 at 02:53
  • @hardmath, thank you!! I haven't seen it!! :( If you want to add that as an answer, you'll win the 'bounty'. – Vicent May 19 '14 at 05:15

2 Answers2

5

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.

hardmath
  • 37,015
  • Thank you, @hardmath.

    As far as I understand, it is right to say that the convergence rate of Brent's method is between 1 (bisection) and 1.839 (inverse quadratic interpolation) depending on how many times applies each method in each particular case, isn't it??

     – Vicent May 19 '14 at 08:52
  • I'll give you the '+50' when I am allowed to (in 9 hours from now). – Vicent May 19 '14 at 08:57
  • Yes, the hope/expectation is that after a small number of steps that may need to resort to "conservative" bisection, the root approximations get close enough that "aggressive" inverse quadratic interpolation behaves well (and exhibits its rapid convergence). – hardmath May 19 '14 at 11:48
  • It's worth noting that the order of convergence is actually more complicated than this. In "half" of the cases (in some sense) the order of convergence is your claimed $\mu$, but in others it is actually $\phi$. – Simply Beautiful Art Aug 28 '20 at 18:28
  • @SimplyBeautifulArt: I think a fair reading of my Answer takes account of its describing the hybrid nature of Brent's method. Rather than assuring that the inverse quadratic interpolation steps always converges at rate $\mu$, the existence of its fallback to bisection (with only linear convergence) implies that the actual "order of convergence" is between those extremes. Of course I welcome elucidation of those conditions in which inverse quadratic interpolation fails to achieve order of convergence $\mu$. – hardmath Aug 28 '20 at 20:22
  • This isn't actually the issue prescribed in my answer, which is due to the fact that Brent's method is a bracketing method. If a bracket must be kept, then one endpoint may not improve (more commonly seen with regula falsi), which theoretically leaves only two points converging to the root. These two points will then converge similarly as with the secant method. Nothing to do with the hybrid nature of using bisection here. – Simply Beautiful Art Aug 28 '20 at 20:27
  • For a fairly simple test case that demonstrates my claim, you may try $\tan(x)$, which will have negative third derivative of its inverse. – Simply Beautiful Art Aug 28 '20 at 20:37
  • After a lot of testing, I found some rather interesting results, which I have edited into my answer below. It turns out Brent's method is usually much slower than what is claimed, since it is usually impossible for it to use inverse quadratic interpolation on the 3 best estimates of the root every iteration. D: – Simply Beautiful Art Sep 10 '20 at 22:18
  • 1
    @Vicent A minor detail I had not noticed earlier, but interpolation methods can converge sublinearly (slower than bisection), especially initially. Because of this, Brent's method actually has worst case $\mathcal O(N^2)$ iterations rather than $\mathcal O(N)$ iterations, where $N$ is the number of iterations required by bisection. Although such a case practically never happens, it's worth pointing out that in theory such a function could even have only one simple root over the bracket. – Simply Beautiful Art Oct 20 '20 at 23:52
2

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.)

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

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

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

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

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

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

  7. 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.

Simply Beautiful Art
  • 74,685
  • I did not respond immediately as I felt sure that your misrepresentation of what my Answer says was more colorful exposition than intentionally false. The Question (even as later edited) asks about bounding the rate of convergence (for Brent's root finding algorithm) between "known values." The OP provides a linear rate of convergence for the lower bound, leaving only the question of an upper bound. Strictly speaking if $\mu \approx 1.839$ is not attained, it is an upper bound. Perhaps we disagree based on the felicitous use of inverse quadratic interpolation if the upper bound is sharp? – hardmath Oct 22 '20 at 15:47
  • @hardmath I had understood the question asked for bounds on the order of convergence, but I think there's no reason not to be interested in the precise order, which still satisfies the question. In part this answer was also a journey for myself, as it can be seen that a thorough analysis for a bracketing method can be quite difficult. So all the more interesting in my opinion. – Simply Beautiful Art Oct 22 '20 at 15:58