Müller's method

Müller's method is a root-finding algorithm, a numerical method for solving equations of the form f(x) = 0. It is first presented by D. E. Müller in 1956.

Müller's method is based on the secant method, which constructs at every iteration a line through two points on the graph of f. Instead, Müller's method uses three points, constructs the parabola through these three points, and takes the intersection of the x-axis with the parabola to be the next approximation.

Recurrence relation

The three initial values needed are denoted as x_k, x_k-1 and x_k-2. The parabola going through the three points (x_k, f(x_k)), (x_k-1, f(x_k-1)) and (x_k-2, f(x_k-2)), when written in the Newton form, is

$y = f(x_k) + (x-x_k) f[x_k, x_{k-1}] + (x-x_k) (x-x_{k-1}) f[x_k, x_{k-1}, x_{k-2}], \,$

where f[x_k, x_k-1] and f[x_k, x_k-1, x_k-2] denote divided differences. This can be rewritten as

$y = f(x_k) + w(x-x_k) + f[x_k, x_{k-1}, x_{k-2}] \, (x-x_k)^2 \,$

where

$w = f[x_k,x_{k-1}] + f[x_k,x_{k-2}] - f[x_{k-1},x_{k-2}]. \,$

The next iterate is now given by the root of the quadratic equation y = 0. This yields the recurrence relation

$x_{k+1} = x_k - \frac{2f(x_k)}{w \pm \sqrt{w^2 - 4f(x_k)f[x_k, x_{k-1}, x_{k-2}]}}.$

In this formula, the sign should be chosen such that the denominator is as large as possible in magnitude. We do not use the standard formula for solving quadratic equations because that may lead to loss of significance.

Note that x_k+1 can be complex, even if the previous iterates were all real. This is in contrast with other root-finding algorithms like the secant method or Newton's method, whose iterates will remain real if one starts with real numbers. Having complex iterates can be an advantage (if one is looking for complex roots) or a disadvantage (if it is known that all roots are real), depending on the problem.

Speed of convergence

The order of convergence of Müller's method is approximately 1.84. This can be compared with 1.62 for the secant method and 2 for Newton's method. So, the secant method makes less progress per iteration than Müller's method and Newton's method makes more progress.

More precisely, if ξ denotes a single root of f (so f(ξ) = 0 and f'(ξ) ≠ 0), f is three times continuously differentiable, and the initial guesses x₀, x₁, and x₂ are taken sufficiently close to ξ, then the iterates satisfy

$\lim_{k\to\infty} \frac{|x-x_k|}{|x-x_{k-1}|^p} = \left| \frac{f'''(\xi)}{6f'(\xi)} \right|^{(p-1)/2},$

where p ≈ 1.84 is the positive root of x³ − x² − x − 1 = 0.

References

• Muller, David E., "A Method for Solving Algebraic Equations Using an Automatic Computer," MTAC, 10 (1956), 208-215.
• Atkinson, Kendall E. (1989). An Introduction to Numerical Analysis, 2nd edition, Section 2.4. John Wiley & Sons, New York. ISBN 0-471-50023-2.
• Burden, R. L. and Faires, J. D. Numerical Analysis, 4th edition, pages 77ff.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 9.5.2. Muller's Method". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. http://apps.nrbook.com/empanel/index.html#pg=466. 

External links

• Module for Muller's Method by John H. Mathews