1Numerical Analysis –MTH603 VU

Muller’s Method

Muller’s method is a generalization of the secant method, in the sense that it does not require the derivative
of the function. It is an iterative method that requires three starting points , ,
and . A parabola is constructed that passes through the three points; then the quadratic
formula is used to find a root of the quadratic for the next approximation. It has been proved that near a
simple root Muller's method converges faster than the secant method and almost as fast as Newton's
method. The method can be used to find real or complex zeros of a function and can be programmed to use
complex arithmetic.

Example
Do two iterations of Muller’s method to solve x 3 − 3x + 1 = 0 starting with x0 = 0.5, x2 = 0, x1 = 1
Solution

f ( x0 ) = f 0 = (0.5) 3 − 3(0.5) + 1 = −0.375

f ( x1 ) = f1 = (1)3 − 3(1) + 1 = −1
f ( x2 ) = f 2 = 0 − 3 × 0 + 1 = +1
c = f 0 = −0.375
h1 = x1 − x0 = 0.5
h2 = x0 − x2 = 0.5
h2 f1 − ( h1 + h2 ) f 0 + h1 f 2
a=
h1 h2 ( h1 + h2 )
(0.5)( −1) − ( −0.375) + (0.5)
= = 1.5
0.25
f1 − f 0 − ah12
b= = −2
h1
2c
∴ x = x0 −
+b − b 2 − 4ac
2( −0.375)
= 0.5 −
−2 − 4 + 4(1.5)(0.375)
−0.75
= 0.5 − = 0.33333 ≺ 0.5
−2 − 4 + 2.25

© Copyright Virtual University of Pakistan 1

2Numerical Analysis –MTH603 VU

Take
x2 = 0, x0 = 0.33333, x1 = 0.5
h1 = x1 − x0 = 0.16667, h2 = x0 − x2 = 0.33333
c = f 0 = f (0.33333)
= x03 − 3 x0 + 1 = 0.037046
f1 = x13 − 3 x1 + 1 = −0.375
f 2 = x23 − 3x2 + 1 = 1
h2 f1 − (h1 + h2 ) f 0 + h1 f 2 0.023148
a= =
h1 h2 (h1 + h2 ) 0.027778
= 0.8333
f1 − f 0 − ah12
b= = −2.6
h1
2c
x = x0 −
b − b 2 − 4ac
0.074092
= 0.333333 −
−5.2236
= 0.3475 0.33333 = x0
For third iteration take,
x2 = 0.333333, x0 = 0.3475, x1 = 0.5

Graeffe’s Root Squaring Method

GRAEFFE’S ROOT SQUARING METHOD is particularly attractive for finding all the roots of a
polynomial equation. Consider a polynomial of third degree f ( x ) = a0 + a1 x + a2 x + a3 x
2 3

f ( x) = a0 + a1 x + a2 x 2 + a3 x 3
f (− x) = a0 − a1 x + a2 x 2 − a3 x3
f ( x) f (− x) = a32 x 6 − (a22 − 2a1 a3 ) x 4
+(a12 − 2a0 a2 ) x 2 − a02
f ( x) f (− x) = a32 t 3 − (a22 − 2a1 a3 )t 2
+(a12 − 2a0 a2 )t − a02

The roots of this equation are squares or 2i (i = 1), powers of the original roots. Here i = 1 indicates that
squaring is done once.
The same equation can again be squared and this squaring process is repeated as many times as required.
After each squaring, the coefficients become large and overflow is possible as i increase.

Suppose, we have squared the given polynomial ‘i’ times, then we can estimate the value
of the roots by evaluating 2i root of
ai
, i = 1, 2, … , n
ai −1

Where n is the degree of the given polynomial.

© Copyright Virtual University of Pakistan 2

Numerical Analysis –MTH603
3 VU

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.

This method has a great advantage over other methods in that it does not require prior information about
approximate values etc. of the roots. But it is applicable to polynomials only and it is capable of giving all
the roots. Let us see the case of the polynomial equation having real and distinct roots. Consider the
following polynomial equation
f ( x) = x n + a1 x n −1 + a2 x n − 2 + ... + an −1 x + an (1)
separating the even and odd powers of x and squaring we get
( x n + a2 x n − 2 + a4 x n − 4 + ...) 2 = (a1 x n −1 + a3 x n −3 + a5 x n −5 + ...) 2
puttig x 2 = y and simplifying we get the new equation
y n + b1 y n −1 + b1 y n −1 + ... + b1 y n −1 + bn = 0 (2)
b1 = − a12 + 2a 2
b2 = a2 2 − 2a1a3 + 2a4
..... .... ...
bn = (−1) an n 2

if p1 , p2 ,... pn be the roots of eq 1 then the roots of the equation 2 are p12 , p2 2 ,... pn 2

Example
Using Graeffe root squaring method, find all the roots of the equation x 3 − 6 x 2 + 11x − 6 = 0

Solution
Using Graeffe root squaring method, the first three squared polynomials are as under:
For i = 1, the polynomial is

x3 − (36 − 22) x 2 + (121 − 72) x − 36

= x3 − 14 x 2 + 49 x − 36
For i = 2, the polynomial is

© Copyright Virtual University of Pakistan 3

Numerical Analysis –MTH603
4 VU

x3 − (196 − 98) x 2 + (2401 − 1008) x − 1296

= x3 − 98 x 2 + 1393 x − 1296
For i = 3, the polynomial is
x3 − (9604 − 2786) x 2 + (1940449 − 254016) x − 1679616
= x3 − 6818 x 2 + 16864333x − 1679616
The roots of polynomial are
36 49 14
= 0.85714, = 1.8708, = 3.7417
49 14 1
Similarly the roots of the p; oynomial 2 are
1296 1393 98
4 = 0.9821, 4 = 1.9417, 4 = 3.1464
1393 98 1
Still better estimates of the roots obtained from polynomial (3) are
1679616 1686433 6818
8 = 0.99949, 8 = 1.99143, 8 = 3.0144
1686433 6818 1
The exact values of the roots of the given polynomial are 1, 2 and 3.

Example
Apply Graeffe,s root squaring method to solve the equation x 3 − 8 x 2 + 17 x − 10 = 0

Solution

f ( x) = x3 − 8 x 2 + 17 x − 10
here three chnges are observed form + ve to − ve , −ve to + ve , + ve to − ve
hence according to deccarte rule of signs f ( x) may have three positive roots
rewriting eq as x( x 2 + 17) = (8 x 2 + 10)
and squaring on both sides and putting x 2 = y
y ( y + 17) 2 = (8 y + 10) 2
y 3 + 34 y 2 + 289 = 64 y 2 + 160 y + 100
y ( y 2 + 129) = 30 y 2 + 100
putting y 2 = z we get
z ( z + 129) 2 = (30 z + 100) 2
z 3 + 258 z 2 + 16641z = 900 z 2 + 6000 z + 10000
z ( z 2 + 16641) = (642 z 2 + 10000)
squaring again and putting z 2 = u we get
u (u + 16641) 2 = (642u + 10000) 2
u 3 + 33282u 2 + 276922881u = 412164u 2 + 12840000u + 108
u 3 − 378882u 2 + 264082u − 108 = 0

© Copyright Virtual University of Pakistan 4

Numerical Analysis –MTH603
5 VU

if the roots of the eq1 are p1 , p2, p3, and those of eqiuation 5 are q1 , q2 , q3
p1 = (q1 )1/ 8 = (−λ1 )1/ 8 = (378882)1/ 8 = 4.9809593 ≅ 5
p2 = (q2 )1/ 8 = (−λ2 / λ1 )1/ 8 = (264082 / 378882)1/ 8 = 0.9558821 ≅ 1
p3 = (q3 )1/ 8 = (−λ3 / λ2 )1/ 8 = (108 / 264082)1/ 8 = 2.1003064 ≅ 2
here f (5) = f (2) = f (1) = 0
hence all are the roots of the eqiuation

Example
Find all the root of the equation x 4 − 3 x + 1 = 0

Solution

© Copyright Virtual University of Pakistan 5

Numerical Analysis –MTH603
6 VU

f ( x) = x 4 − 3x + 1 (1)
here there are two changes in the sign so there are two positive roots of the equation and
there are no chnge in the roots of the equation f (− x) so two positive real roots and two
are complex roots
rewriting the above equation as
x 4 + 1 = 3x
squaring the equation and putting x 2 = y
we have
( y 2 + 1) 2 = 9 y
squaring again and putting y 2 = z
( z +1)4 = 81z
z 4 + 4 z 3 + 6 z 2 − 77 z + 1 = 0
z 4 + 6 z 2 + 1 = − z (4 z 2 − 77) (2)
squaring once again and putting z = u , we get 2

(u 2 + 6u + 1) = u (4u − 77) 2
u 4 − 4u 3 + 645u 2 − 5917u + 1 = 0 (3)
if p1 , p2 , p3 , p4 are the roots of the equation 1 and q1 , q2 , q3 , q4 are roots of equation 3 then
p1 = (q1 )1/ 8 = (−λ1 )1/ 8 = (4)1/ 8 = 1.189207
−λ2 654 1/ 8
p2 = (q2 )1/ 8 = [ ]1/ 8 = [ ] = 1.8909921
λ1 4
−λ 5917 1/ 8
p3 = (q3 )1/ 8 = [ 3 ]1/ 8 = [ ] = 1.3169384
λ2 654
−λ 1 1/ 8
p4 = (q4 )1/ 8 = [ 4 ]1/ 8 = [ ] = 0.3376659
λ3 5971
from equation (2 ) and (3)
from equation 2 and 3 , we observe the magnitude of the cofficients λ1 and λ2 have become
cons tan t which implies p1 and p4 are the real roots , then p2 and p3 are real roots,
let the complex roots be ρ 2 e± iϕ2 = ξ 2 + iη 2
from equation (3) it ' s magnitude is given by
3 λ3 5917
ρ 2(2 ) 2 = = ∴ ρ 2 = 1.5780749
λ1 4
also from equation 1 sum of roots is zero i.e ρ1 + 2ξ 2 + p4 = 0
ξ 2 = −1/ 2( p1 + p4 ) = −0.7634365
η 2 = ρ 2 2 − ξ 2 2 = 1.9074851 = 1.3811173
hence, the four roots are 1.1892071, 0.3376659, −0.734365 and ± 1.3811173i

Revision Example
Obtain the Newton-Raphson extended formula
f ( x0 ) 1 [ f ( x0 )]2
x1 = x0 − − f ′′( x0 )
f ′( x0 ) 2 [ f ( x0 )]3
For finding the root of the equation f(x)=0

© Copyright Virtual University of Pakistan 6

Numerical Analysis –MTH603
7 VU

Solution
Expanding f (x) by Taylor’s series and retaining up to second order term,
0 = f ( x) = f ( x0 ) + ( x − x0 ) f ′( x0 )
( x − x0 ) 2
+ f ′′( x0 )
2
Therefore,
f ( x1 ) = f ( x0 ) + ( x1 − x0 ) f ′( x0 )
( x1 − x0 ) 2
+ f ′′( x0 ) = 0
2
This can also be written as
2
1 [ f ( x0 )]
f ( x0 ) + ( x1 − x0 ) f ′( x0 ) + f ′′( x0 ) = 0
2 [ f ′( x0 )]2
Thus, the Newton-Raphson extended formula is given by
f ( x0 ) 1 [ f ( x0 )]2
x1 = x0 − − f ′′( x0 )
f ′( x0 ) 2 [ f ′( x0 )]3
This is also known as Chebyshev’s formula of third order

© Copyright Virtual University of Pakistan 7