08. Muller’s Method
Dated: 16-08-2025
Example
Do two iterations of Muller’s method to solve \(x^3 - 3x + 1 = 0\) starting with \(x_0 = 0.5, x_2 = 0, x_1 = 1\)
Solution
\[f(x_0) = f_0 = (0.5)^3 - 3(0.5) + 1 = -0.375\]
\[f(x_1) = f_1 = (1)^3 - 3(1) + 1 = -1\]
\[f(x_2) = f_2 = 0 - 3 \times 0 + 1 = +1\]
\[c = f_0 = -0.375\]
\[h_1 = x_1 - x_0 = 0.5\]
\[h_2 = x_0 - x_2 = 0.5\]
\[a = \frac{h_2 f_1 - (h_1 + h_2)f_0 + h_1 f_2}{h_1 h_2 (h_1 + h_2)} = \frac{(0.5)(-1) - (-0.375) + (0.5)}{0.25} = 1.5\]
\[b = \frac{f_1 - f_0 - ah_1^2}{h_1} = -2\]
\[\therefore x = x_0 - \frac{2c}{+b - \sqrt{b^2 - 4ac}} = 0.5 - \frac{2(-0.375)}{-2 - \sqrt{4 + 4(1.5)(0.375)}} = 0.5 - \frac{-0.75}{-2 - \sqrt{4 + 2.25}} = 0.33333 < 0.5\]
Take
\[x_0 = 0.\overline{3}, \quad x_1 = 0.5, \quad x_2 = 0\]
\[h_1 = x_1 - x_0 = 0.16667, \quad h_2 = x_0 - x_2 = 0.\overline 3\]
\[c = f_0 = f(0.\overline 3)\]
\[= x_0^3 - 3x_0 + 1 = 0.037046\]
\[f_1 = x_1^3 - 3x_1 + 1 = - 0.375\]
\[f_2 = x_2^3 - 3x_2 + 1 = 1\]
\[a = \frac{h_2 f_1 - (h_1 + h_2)f_0 + h_1 f_2}{h_1 h_2 (h_1 + h_2)} = \frac{0.023148}{0.027778} = 0.8333\]
\[b = \frac{f_1 - f_0 - ah_1^2}{h_1} = -2.6\]
\[x = x_0 - \frac{2c}{b - \sqrt{b^2 - 4ac}} = 0.333333 - \frac{0.074092}{-5.2236} = 0.3475 > 0.333333 = x_0\]
For 3rd iteration, we take
\[x_0 = 0.3475, \quad x_1 = 0.5, \quad x_2 = 0.\overline 3\]
Graeffe’s Root Squaring Method
This one is for 3rd degree polynomial
\[f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3\]
\[f(-x) = a_0 - a_1 x + a_2 x^2 - a_3 x^3\]
\[f(x)f(-x) = a_3^2 x^6 - (a_2^2 - 2a_1 a_3)x^4 + (a_1^2 - 2a_0 a_2)x^2 - a_0^2\]
\[f(x)f(-x) = a_3^2 t^3 - (a_2^2 - 2a_1 a_3)t^2 + (a_1^2 - 2a_0 a_2)t - a_0^2 \quad \text{where } t = x^2\]
Suppose, we have squared the given polynomial \(i\) times, then we can estimate the value of the roots by evaluating \(2i\) root of
\[\left| \frac{a_i}{a_{i-1}} \right|, \quad i=1,2,\dots,n\]
Where \(n\) is the degree of the polynomial.
The proper sign of each root can be determined by recalling the original equation. This method fails, when the roots of the given polynomial are repeated.
\[f(x) = x^n + a_1 x^{n-1} + a_2 x^{n-2} + \dots + a_{n-1}x + a_n\]
\[\left(x^n + a_2 x^{n-2} + a_4 x^{n-4} + \dots\right)^2 = \left(a_1 x^{n-1} + a_3 x^{n-3} + a_5 x^{n-5} + \dots\right)^2\]
Putting \(x^2 = y\) and after simplifying, we have
\[y^n + b_1 y^{n-1} + b_1 y^{n-1} + \dots + b_1 y^{n-1} + b_n = 0\]
\[
\begin{aligned}
b_1 &= -a_1^2 + 2a^2 \\
b_2 &= a_2^2 - 2a_1 a_3 + 2a_4 \\
\cdots &= \cdots \\
b_n &= (-1)^n a_n^2
\end{aligned}
\]
Example
Using Graeffe root squaring method, find all the roots of the equation
\[x^3 - 6x^2 + 11x - 6 = 0\]
Solution
Using Graeffe root squaring method, the first three squared polynomials are as under
For \(i = 1\), the polynomial is
\[x^3 - (36 - 22)x^2 + (121 - 72)x - 36 = x^3 - 14x^2 + 49x - 36\]
For \(i = 2\), the polynomial is
\[x^3 - (196 - 98)x^2 + (2401 - 1008)x - 1296 = x^3 - 98x^2 + 1393x - 1296\]
For \(i = 3\), the polynomial is
\[x^3 - (9604 - 2786)x^2 + (1940449 - 254016)x - 1679616 = x^3 - 6818x^2 + 1686433x - 1679616\]
The roots of polynomial are
\[\sqrt{\frac{36}{49}} = 0.85714, \quad \sqrt{\frac{49}{14}} = 1.8708, \quad \sqrt{\frac{14}{1}} = 3.7417\]
Similarly the roots of the polynomial are
\[\sqrt[4]{\frac{1296}{1393}} = 0.9821, \quad \sqrt[4]{\frac{1393}{98}} = 1.9417, \quad \sqrt[4]{\frac{98}{1}} = 3.1464\]
\[\sqrt[8]{\frac{1679616}{1686433}} = 0.99949, \quad \sqrt[8]{\frac{1686433}{6818}} = 1.99143, \quad \sqrt[8]{\frac{6818}{1}} = 3.0144\]
The exact values of the roots of the given polynomial are \(1, 2\) and \(3\).
References
Read more about notations and symbols.