3

It is a well-known fact that, for solving algebraic equations, the bisection method has a linear rate of convergence, the secant method has a rate of convergence equal to 1.62 (approx.) and the Newton-Raphson method has a rate of convergence equal to 2.

Is there any numerical method for solving algebraic equations with a rate of convergence greater than 2?

IgotiT
  • 734

2 Answers2

3

As mentioned, the Halley method has cubic convergence, the so-called "Householder methods" in generalization of that have higher orders of convergence. However, if you count the convergence rate in terms of complexity and that in terms of function evaluations, i.e., the "Ostrowski index", where derivatives of order $k$ count as $k$ (or $2k$) function evaluations, then you reach the point of diminishing returns at convergence order 2-3. I put numbers to that at https://en.wikipedia.org/wiki/Householder%27s_method

Lutz Lehmann
  • 126,666
2

In fact, one can go further. Joseph Traub has an entire book devoted to the construction of a family of methods that are effectively high-order generalizations of the Newton-Raphson and secant methods. On a more modern front, Bahman Kalantari constructed a "basic iteration" family that is a generalization of the Newton-Raphson and Halley methods. He also managed to produce some cool artwork in the process.