1
$\begingroup$

Given a root-finding function f(x)=0, what is the sufficient global/local convergence condition of inverse quadratic interpolation?

  • 0
    I'm far away from my library to check, but IIRC this was discussed in Traub's *[Iterative Methods for the Solution of Equations](http://books.google.com/books?hl=en&id=Q-1QAAAAMAAJ)*. Maybe you can take a look? (The thing I do remember is that the global convergence is not too good, which is why in Brent's polyalgorithm, it is only used when the secant method has already picked up some steam.)2012-04-27
  • 0
    "Iterative Methods for the Solution of Equations" is published in 1982. I have difficulty in finding such an old book. Is there any similiar book or paper?2012-04-27

1 Answers 1

1

In Brent's original 1971 paper that had introduced this method, also in his book Algorithms for Minimization without Derivatives, he mentioned the local convergence condition is that $f$ has a Lipschitz continuous derivative near the root we would like to find.

For the global convergence, Brent didn't gave the requirement for global convergence or something similar in the book. And in the notes here, the author gives the a universal global convergence condition, see Theorem 5.1 Sharkovsky’s No-Swap Theorem. (PS. the pdf isn't properly rendered in Google Chrome web browser)