Root-finding Algorithm Question

  • Thread starter DuncanM
  • Start date
  • Tags
    Algorithm
In summary, there is a root-finding algorithm called Halley's Method that converges at a cubic rate, which is faster than the quadratic convergence rate of the Newton-Raphson method. It involves higher order Taylor series iterations and can also have a fourth order convergence rate, but this requires a fourth derivative calculation.
  • #1
DuncanM
98
2
Some time ago I saw a thread in which was mentioned a root-finding algorithm that converges twice as fast as the Newton-Raphson method. Newton-Raphson converges to a zero at a quadratic rate, and a poster pointed out that another algorithm converges to a zero at a quartic rate.

I have tried to find that thread, but cannot.

Anybody here know what algorithm I am talking about? It is for computing the roots of a function and converges to a solution at twice the rate of Newton-Raphson?
 
Physics news on Phys.org
  • #3
I think I found it, and here is an old thread in these forums about it:

https://www.physicsforums.com/showthread.php?t=409453

It is called Halley's Method.

I was mistaken; it actually offers cubic convergence, not quartic.
In any case, is still faster convergence than the Newton-Raphson Method.

Here are a couple other links with information about it:

http://en.wikipedia.org/wiki/Halley's_method

http://mathworld.wolfram.com/HalleysMethod.html
 
  • #4
The paper I linked to does have a fourth order convergence
 

1. What is a root-finding algorithm?

A root-finding algorithm is a mathematical method used to approximate the roots of a given function. The roots, also known as solutions, are the points where the function equals zero.

2. How does a root-finding algorithm work?

A root-finding algorithm typically uses an iterative process to narrow down the possible range of solutions. It starts with an initial guess and then uses a series of calculations to refine the guess until it reaches a satisfactory approximation of the root.

3. What are some common root-finding algorithms?

Some common root-finding algorithms include the bisection method, the Newton-Raphson method, and the secant method. Each algorithm has its own advantages and disadvantages, and the best one to use depends on the specific function and problem at hand.

4. How accurate are root-finding algorithms?

The accuracy of a root-finding algorithm depends on the initial guess, the complexity of the function, and the chosen algorithm. In general, most algorithms can achieve a high degree of accuracy, but it is important to carefully choose the initial guess and consider the limitations of the chosen algorithm.

5. What are some real-world applications of root-finding algorithms?

Root-finding algorithms are used in a variety of real-world applications, such as financial modeling, engineering, and physics. They can be used to solve complex equations and optimize systems, making them valuable tools in many fields of science and technology.

Similar threads

Replies
16
Views
1K
  • General Math
Replies
7
Views
1K
  • General Math
Replies
9
Views
1K
  • Calculus
Replies
5
Views
4K
  • Calculus
Replies
3
Views
3K
  • Precalculus Mathematics Homework Help
Replies
3
Views
3K
  • General Math
Replies
5
Views
761
  • Programming and Computer Science
Replies
30
Views
4K
  • Programming and Computer Science
Replies
14
Views
1K
Back
Top