3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Yes there are; an interesting question I'd like to hear asked, is which method we know of has the highest rate. $\endgroup$ – KR136 Apr 22 '16 at 0:26
  • $\begingroup$ Oh so I suppose that question is a pointless one as well $\endgroup$ – KR136 Apr 22 '16 at 0:36
  • $\begingroup$ @YuriyS, thank you for your comment. Can you name one such method? $\endgroup$ – IgotiT Apr 22 '16 at 0:40
  • 2
    $\begingroup$ As an example, please see Halley's Method., which often has cubic convergence. $\endgroup$ – André Nicolas Apr 22 '16 at 0:51
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.