Müller's method
Encyclopedia
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.
, is
where f[xk, xk-1] and f[xk, xk-1, xk-2] denote divided differences
. This can be rewritten as
where
The next iterate is now given by the root of the quadratic equation y = 0. This yields the recurrence relation
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 equation
s because that may lead to loss of significance
.
Note that xk+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.
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 x0, x1, and x2 are taken sufficiently close to ξ, then the iterates satisfy
where p ≈ 1.84 is the positive root of
.
Root-finding algorithm
A root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f = 0, for a given function f. Such an x is called a root of the function f....
, a numerical
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
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
Secant method
In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function f. The secant method can be thought of as a finite difference approximation of Newton's method. However, the method was developed...
, 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
Parabola
In mathematics, the parabola is a conic section, the intersection of a right circular conical surface and a plane parallel to a generating straight line of that surface...
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 xk, xk-1 and xk-2. The parabola going through the three points (xk, f(xk)), (xk-1, f(xk-1)) and (xk-2, f(xk-2)), when written in the Newton formNewton polynomial
In the mathematical field of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is the interpolation polynomial for a given set of data points in the Newton form...
, is
where f[xk, xk-1] and f[xk, xk-1, xk-2] denote divided differences
Divided differences
In mathematics divided differences is a recursive division process.The method can be used to calculate the coefficients in the interpolation polynomial in the Newton form.-Definition:Given n data points,\ldots,...
. This can be rewritten as
where
The next iterate is now given by the root of the quadratic equation y = 0. This yields the recurrence relation
Recurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....
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 equation
Quadratic equation
In mathematics, a quadratic equation is a univariate polynomial equation of the second degree. A general quadratic equation can be written in the formax^2+bx+c=0,\,...
s because that may lead to loss of significance
Loss of significance
Loss of significance is an undesirable effect in calculations using floating-point arithmetic. It occurs when an operation on two numbers increases relative error substantially more than it increases absolute error, for example in subtracting two large and nearly equal numbers. The effect is that...
.
Note that xk+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
Secant method
In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function f. The secant method can be thought of as a finite difference approximation of Newton's method. However, the method was developed...
or Newton's method
Newton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley'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 convergenceRate of convergence
In numerical analysis, the speed at which a convergent sequence approaches its limit is called the rate of convergence. Although strictly speaking, a limit does not give information about any finite first part of the sequence, this concept is of practical importance if we deal with a sequence of...
of Müller's method is approximately 1.84. This can be compared with 1.62 for the secant method
Secant method
In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function f. The secant method can be thought of as a finite difference approximation of Newton's method. However, the method was developed...
and 2 for Newton's method
Newton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley'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
where p ≈ 1.84 is the positive root of
.