Muller's Method

• Most of the root-finding methods that we have considered so far have approximated the function in the neighbourhood of the root by a straight line.
• Muller's method is based on approximating the function in the neighbourhood of the root by a quadratic polynomial.

Figure 2: Parabola $a\nu ^2 + b\nu + c=p_2(\nu )$

• A second-degree polynomial is made to fit three points near a root, at $x_0,x_1,x_2$ with $x_0$ between $x_1$, and $x_2$.
• The proper zero of this quadratic, using the quadratic formula, is used as the improved estimate of the root.

• A quadratic equation that fits through three points in the vicinity of a root, in the form $a\nu^2 + b\nu + c$. (See Fig. 2)

• Transform axes to pass through the middle point, let
  • $\nu=x-x_0$,
  • $h_1=x_1-x_0$
  • $h_2=x_0-x_2$.

  $\nu =0\Longrightarrow ~a(0)^2 + b(0) + c=f_0$

  $\nu =h_1\Longrightarrow~ ah_1^2 + bh_1 + c =f_1$

  $\nu =-h_2\Longrightarrow~ ah_2^2 -bh_2 + c=f_2$

  We evaluate the coefficients by evaluating $p_2(\nu)$ at the three points:

• From the first equation, $c=f_0$.
• Letting $h_2/h_1=\gamma$, we can solve the other two equations for a, and b.
  
  $$a=\frac{\gamma f_1-f_0(1+\gamma)+f_2}{\gamma h_1^2(1+\gamma)},~b=\frac{f_1-f_0-ah_1^2}{h_1}$$
  
  

• After computing a, b, and c, we solve for the root of $a\nu^2 + b\nu + c$ by the quadratic formula

$$\nu_{1,2}=\frac{2c}{-b\pm\sqrt{b^2-4ac}},$$

$$~\nu=x-x_0,$$

$$root=x_0-\frac{2c}{b\pm\sqrt{b^2-4ac}}$$

See Figs. 3-4 that an example is given

Figure 3: An example of the use of Muller's method.

Figure 4: Cont. An example of the use of Muller's method.

• Experience shows that Muller's method converges at a rate that is similar to that for Newton's method.
• It does not require the evaluation of derivatives, however, and (after we have obtained the starting values) needs only one function evaluation per iteration.

An algorithm for Muller's method :