Try our Free Online Math Solver!

SOLUTION OF NONLINEAR EQUATIONS f(x)=0
Figure 2.17 The starting approximations
, and for
Muller’s method, and the
differences and
.
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 .
Without loss of generality, we assume that
is the best approximation to the
root and consider the parabola through the three starting values , shown in
Figure 2.17.
Make the change of variable
and use the differences
and .
Consider the quadratic polynomial involving the variable t:
(11) y = at^{2} + bt + c.
Each point is used to obtain an equation involving a, b, and c:
From the third equation in (12), we see that
Substituting (13) into the first two equations in (12) and using the definition
and results in the linear system
Solving the linear system for a and b results in
The quadratic formula is used to find the roots of (11):
Formula (16) is equivalent to the standard formula for the
roots of a quadratic and is
better in this case because we know that .
To ensure the stability of the method, we choose the root in (16) that has the
smallest
absolute value. If b > 0, use the positive sign with the square root, and if b <
0,
use the negative sign . Then
is shown in Figure 2.17 and is given by
To update the iterates, choose the new
and the new
to be the two values
selected from among the old that lie closest to
(i.e., throw out
the one
that is farthest away). Then take new
to be old
. Although a lot of
auxiliary
calculations are done in Muller’s method, it only requires one function
evaluation per
iteration.
If Muller’s method is used to find the real roots of f (x) = 0, it is possible
that
one may encounter complex approximations , because the roots of the quadratic in
(16)
might be complex (nonzero imaginary components). In these cases the imaginary
components
will have a small magnitude and can be set equal to zero so that the
calculations
proceed with real numbers .
Table 2.12 Comparison of Convergences near a Simple Root
k  Secant method 
Muller’s method 
Newton’s method 
Steffensen with Newton 
Comparison of Methods
Steffensen’s method can be used together with the NewtonRaphson fixedpoint
function
g(x) = x − f (x)/ f '(x). In the next two examples we look at the roots of
the polynomial f (x) = x^{3} − 3x + 2. The NewtonRaphson function is g(x) =
(2x^{3} − 2)/(3x^{2} − 3). When this function is used in Program 2.7, we get the
calculations
under the heading Steffensen with Newton in Tables 2.12 and 2.13. For example,
starting with = −2.4, we would compute
and
Then Aitken’s improvement will give
= −1.982618143.
Example 2.19 (Convergence near a Simple Root ). This is a comparison of methods
for the function f (x) = x^{3} − 3x + 2 near the simple root p = −2.
Newton’s method and the secant method for this function were given in Examples
2.14
and 2.16, respectively. Table 2.12 provides a summary of calculations for the
methods.
Example 2.20 (Convergence near a Double Root). This is a comparison of the
methods
for the function f (x) = x^{3} − 3x + 2 near the double root p = 1. Table 2.13
provides a
summary of calculations.
Newton’s method is the best choice for finding a simple root (see Table 2.12).
At a
double root, either Muller’s method or Steffensen’s method with the
NewtonRaphson
formula is a good choice (see Table 2.13). Note in the Aitken’s acceleration
formula (4)
that division by zero can occur as the sequence
converges. In this case,
the last
calculated approximation to zero should be used as the approximation to the zero
of f .
Table 2.13 Comparison of Convergence Near a Double Root
k  Secant method 
Muller’s method 
Newton’s method 
Steffensen with Newton 
In the following program the sequence
, generated by Steffensen’s method
with the NewtonRaphson formula, is stored in a matrix Q that has max1 rows and
three columns. The first column of Q contains the initial approximation to the
root,
, and the terms
generated by Aitken’s acceleration
method (4).
The second and third columns of Q contain the terms generated by Newton’s
method.
The stopping criteria in the program are based on the difference between
consecutive
terms from the first column of Q.
Numerical Methods Using Matlab, 4^{th}^{ } Edition, 2004
Prev  Next 