# 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 Newton-Raphson fixed-point
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 Newton-Raphson 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
Newton-Raphson

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 Newton-Raphson 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 |