Muller's method is a root-finding algorithm, a numerical method for solving equations of the form f(x) = 0. It was first presented by David E. Muller in 1956. Muller's method proceeds according to a third-order recurrence relation similar to the second-order recurrence relation of the secant method. Whereas the secant method proceeds by constructing a line through two points on the graph of f corresponding to the last two iterative approximations and then uses the line's root as the next approximation at every iteration, by contrast, Muller's method uses three points corresponding to the last three iterative approximations, constructs a parabola through these three points, and then uses a root of the parabola as the next approximation at every iteration.

Recurrence relation

Muller's method is a recursive method that generates a new approximation of a root ξ of f at each iteration using the three prior iterations. Starting with three initial values x0, x−1 and x−2, the first iteration calculates an approximation x1 using those three, the second iteration calculates an approximation x2 using x1, x0 and x−1, the third iteration calculates an approximation x3 using x2, x1 and x0, and so on: the kth iteration generates approximation xk using xk-1, xk-2, and xk-3. Each iteration takes as input the last three generated approximations and the value of f at these approximations: the values xk-1, xk-2 and xk-3 and the function values f(xk-1), f(xk-2) and f(xk-3). The approximation xk is calculated as follows from those six values. First, a parabola yk(x) is constructed by interpolating through the three points (xk-1, f(xk-1)), (xk-2, f(xk-2)) and (xk-3, f(xk-3)) using a Newton polynomial. yk(x) is where f[xk-1, xk-2] and f[xk-1, xk-2, xk-3] denote divided differences. This can be rewritten as where The iterate xk is then given as the solution of the quadratic equation yk(x) = 0 closest to xk-1. Altogether, this implies the overall nonlinear third-order recurrence relation where the sign of the square root should be chosen such that the total denominator is as large as possible in magnitude. Note that xk can be complex even when the previous iterates are all real. This is in contrast with other root-finding algorithms like the secant method, Sidi's generalized 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

For well-behaved functions, the order of convergence of Muller's method is approximately 1.84 and exactly the tribonacci constant. This can be compared with approximately 1.62, exactly the golden ratio, for the secant method and with exactly 2 for Newton's method. So, the secant method makes less progress per iteration than Muller'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 μ ≈ 1.84 is the positive solution of, the defining equation for the tribonacci constant.

Generalizations and related methods

Muller's method fits a parabola, i.e. a second-order polynomial, to the last three obtained points f(xk-1), f(xk-2) and f(xk-3) in each iteration. One can generalize this and fit a polynomial pk,m(x) of degree m to the last m+1 points in the kth iteration. Our parabola yk is written as pk,2 in this notation. The degree m must be 1 or larger. The next approximation xk is now one of the roots of the pk,m, i.e. one of the solutions of pk,m(x)=0. Taking m=1 we obtain the secant method whereas m=2 gives Muller's method. Muller calculated that the sequence {xk} generated this way converges to the root ξ with an order μm where μm is the positive solution of. The method is much more difficult though for m>2 than it is for m=1 or m=2 because it is much harder to determine the roots of a polynomial of degree 3 or higher. Another problem is that there seems no prescription of which of the roots of pk,m to pick as the next approximation xk for m>2. These difficulties are overcome by Sidi's generalized secant method which also employs the polynomial pk,m. Instead of trying to solve pk,m(x)=0, the next approximation xk is calculated with the aid of the derivative of pk,m at xk-1 in this method.

Computational example

Below, Muller's method is implemented in the Python programming language. It is then applied to find a root of the function .