Müller's Method is a iterative root finding method that is somewhat similar to the to "regula falsi" method, also known as the secant method. Whereas the secant method estimates a root by projecting a straight line through two points, Müller's method takes three points, and projects a quadratic polynomial through them, estimating the root at the point where this intersects the x-axis.

The derivation for Müller's method goes something along these lines.

Assume that the polynomial through the points x0, x1, and x2 can be written in the form:

f(x) = a(x - x2)2 + b(x - x2) + c

Then, when we evaluate this function at the points x0, x1, and x2 to get:

f(x0) = a(x0 - x2)2 + b(x0 - x2) + c
f(x1) = a(x1 - x2)2 + b(x1 - x2) + c
f(x2) = a(x2 - x2)2 + b(x2 - x2) + c

Knowing that f(x2) = c, we can then do a bit of subtraction to find that:

f(x0) - f(x2) = a(x0 - x2)2 + b(x0 - x2) 
f(x1) - f(x2) = a(x1 - x2)2 + b(x1 - x2) 

Now comes the fun part, we get to manipulate this to find values of a and b.

h0 = x1 - x0
h1 = x2 - x1

d0 = (f(x1) - f(x0))/h0
d1 = (f(x2) - f(x1))/h1

Toss this into the two equations above, do a little algebra, and you come up with:

a = (d1 - d0)/(h1 + h0)
b = ah1 + d1
c = f(x2)

Fun, eh! We're not done yet! We can then find that the new estimate for the root, x3, is at:

x3 = x2 - 2c/(b +-√(b2 - 4ac))

We want to use the sign of √(b2 - 4ac) that agrees with the sign of b. If b is positive, add the square root, if b is negative, subtract the square root.

Now that we have the new guess for the root of the function, we get to do it all again! But which of the old guesses do we throw out? That depends. If you know that the function only has real roots, keep the two values that are closest to x3. If you are trying to find complex roots as well, use a sequential approach. Toss out the old value of x0, for the next iteration, x0 new is x1 old, x1 new is x2 old, and x2 new is x3.

Repeat Until Dead.

Or keep going until the guess is close enough to the actual root to suit your purposes. How close you want it is up to you, or whoever's marking your assignment in my case.

The fact that this method can be used to find complex roots is one of the main advantages of Müller's method, since that's what it was designed for. Otherwise, you'd probably want to just stick to something with less calculations, like the "regula falsi" method.

Node Your Homework!

Log in or register to write something here or to contact authors.