3.3 Müller’s method

Newton’s method and the secant method approximate \(f\) by a straight line. Müller’s method approximates it by the parabola through the last three iterates and takes the root of the parabola that is nearer to the last iterate. Because a parabola can have complex roots, the method moves off the real axis on its own and can find complex roots of a real polynomial from real starting values.

Given \(x_0, x_1, x_2\), write the parabola through \((x_k,f(x_k))\), \(k = 0,1,2\), in the form \[p(x) = a(x-x_2)^2+b(x-x_2)+c .\] The three conditions give \(c = f(x_2)\) and, with \(h_1 = x_1-x_0\), \(h_2 = x_2-x_1\), \(\delta _1 = \frac {f(x_1)-f(x_0)}{h_1}\), \(\delta _2 = \frac {f(x_2)-f(x_1)}{h_2}\), \[a = \frac {\delta _2-\delta _1}{h_2+h_1},\qquad b = \delta _2+h_2a .\] The roots of \(p\) satisfy \(x-x_2 = \frac {-2c}{b\pm \sqrt {b^2-4ac}}\) (the rationalized quadratic formula of Example 1.2.10). Choosing the sign that makes the denominator larger in modulus gives the root nearer to \(x_2\) and avoids cancellation: \begin {equation} \label {eq:muller} x_3 = x_2-\frac {2c}{b+\sgn (b)\sqrt {b^2-4ac}}, \end {equation} where, for complex \(b\), the sign is chosen so that \(|b\pm \sqrt {b^2-4ac}|\) is the larger of the two. The process is then repeated with \(x_1, x_2, x_3\).