CHAPTER 6

Open Methods
For the bracketing methods in Chap. 5, the root is located within an interval prescribed by a
lower and an upper bound.

Repeated application of these methods always results in closer estimates of the true value of the
root.

Such methods are said to be convergent because they move closer to the truth as the computation
progresses (Fig. 6.1a).

In contrast, the open methods described in this chapter are based on formulas that require only a
single starting value of x or two starting values that do not necessarily bracket the root.

As such, they sometimes diverge or move away from the true root as the computation progresses
(Fig. 6.16).

However, when the open methods converge (Fig. 6.1c), they usually do so much more quickly
than the bracketing methods.

6.1 SIMPLE FIXED-POINT ITERATION

As mentioned above, open methods employ a formula to predict the root.

Such a formula can be developed for simple fixed-point iteration (or, as it is also called, one-
point iteration or successive substitution) by rearranging the function f(x) = 0 so that x is on the
left-hand side of the equation:

(6.1)

This transformation can be accomplished either by algebraic manipulation or by simply adding x

to both sides of the original equation. For example,

2
2x 4 - 3 = 0
can be simply manipulated to yield

2 2 -{- 3

whereas sin x = 0 could be put into the form of Eq. (6.1) by adding x to both sides to yield
 x = s t i t x 4 z

The utility of Eq. (6.1) is that it provides a formula to predict a new value of x as a function of an
old value of x. Thus, given an initial guess at the root xi, Eq. (6.1) can be used to compute a new
estimate JCZ'+I as expressed by the iterative formula

X Tr l — g[X ) s (62)

As with other iterative formulas in this book, the approximate error for this equation can be
determined using the error estimator [Eq. (3.5)]:

00'

E X A M P L E 6.1 Simple Fixed-Point Iteration

Problem Statement. Use simple fixed-point iteration to locate the root of/(;c) = e~ ~ x.
x

Solution. The function can be separated directly and expressed in the form of Eq. (6.2) as

Uo X o = O X1
 0 0 100.0
1 1.000000 100.0 76.3
5 0.367370 171.8 35.1
3 0.692201 46.9 22.1
4 0^:500473 S i .3 11.8
5 0.606244 17.4 6.89
6 0..545396 11.2 3,83
7 0.579612 5.90 2.20
3 0.56O1 15 3.4B 1.24
9 0.571143 1.93 €3.705
0 0.564879 1.11 0.399

6.1.1 Convergence

Notice that the true percent relative error for each iteration of Example 6.1 is roughly
proportional (by a factor of about 0.5 to 0.6) to the error from the previous iteration. This
property, called linear convergence is characteristic of fixed-point iteration.

Aside from the "rate" of convergence, we must comment at this point about the "possibility" of
convergence. The concepts of convergence and divergence can be depicted graphically.

Such an approach is employed in Fig. 6.2a for the function / (x) =e~* - x. An alternative
graphical approach is to separate the equation into two component parts, as in

fx(x)=fi(x)

Then the two equations

v, =fi(x) (6.3)

and

yi=h(x) (6.4)

can be plotted separately (Fig. 6.2Z»). The x values corresponding to the intersections of these
functions represent the roots off(x) = 0.

E X A M P L E 6.2 The Two-Curve Graphical Method

Problem Statement. Separate the equation e-x - x = 0 into two parts and determine its root
graphically.
Solution. Reformulate the equation as yl = x and y2 = e-x. The following values can be
computed:

e _ >< ^ O

0.0 o.c 1 ."COO

D . jt 02 0.6! 0
0,4 0.4 0.670
Duft 0.6 - *'**
OJ 0.44°
1.0 i n 0.363
 r ffr* -
FIGURE 6 . 5
0

Graohicai depiction of the

Newton-Raphson method.
A tangeni to the Junction of x»
[that is, ?\x-\[ is extrapolated
down to the x axis to provide
an estimate of the root at x-. •.

The Newton-Raphson method can be derived on the basis of this geometrical interpretation (an
alternative method based on the Taylor series is described in Box 6.2). As in Fig. 6.5, the first
derivative at x is equivalent to the slope:

ffrl \ I • •
(6.5)

which can be rearranged to yield

ft*J
x J f l — x i

(6.6)

which is called the Newton-Raphson formula.

E X A M P L E 6.3 Newton-Raphson Method

Problem Statement. Use the Newton-Raphson method to estimate the root of / (x) = e' - x, x

employing an initial guess of xO = 0.

Solution. The first derivative of the function can be evaluated as

 —e. — 1

• • • • • • • • • • • • • • • • • • • • • • • • • ^

0 0 100
1 0.50CW0OOCO 11.3
2 0.566311003 Q.147
3 0.567' 43165 0.XOQ22C
4 0.567* 4 3 2 9 0 < 10~
a

6.2.2 Pitfalls of the Newton-Raphson Method

Although the Newton-Raphson method is often very efficient, there are situations where it
performs poorly. A special case—multiple roots—will be addressed later in this chapter.

However, even when dealing with simple roots, difficulties can also arise, as in the following
example.

Aside from slow convergence due to the nature of the function, other difficulties can arise, as
illustrated in Fig. 6.6.

For example, Fig. 6.6a depicts the case where an inflection point [that is,f"(x) = 0] occurs in the
vicinity of a root.

Notice that iterations beginning at x progressively diverge from the root.

0

Figure 6.6b illustrates the tendency of the Newton-Raphson technique to oscillate around a local
maximum or minimum.

Such oscillations may persist, or as in Fig. 6.6Z>, a near-zero slope is reached, whereupon the
solution is sent far from the area of interest.

Figure 6.6c shows how an initial guess that is close to one root can jump to a location several
roots away. This tendency to move away from the area of interest is because near-zero slopes are
encountered. Obviously, a zero slope [f'(x) = 0] is truly a disaster because it causes division by
zero in the Newton-Raphson formula [Eq. (6.6)].
Graphically (Fig 6.6c/), it means that the solution shoots off horizontally and never hits the x axis.

Thus, there is no general convergence criterion for Newton-Raphson. Its convergence depends
on the nature of the function and on the accuracy of the initial guess.

The only remedy is to have an initial guess that is "sufficiently" close to the root.

And for some functions, no guess will work! Good guesses are usually predicated on knowledge
of the physical problem setting or on devices such as graphs that provide insight into the
behavior of the solution.

The lack of a general convergence criterion also suggests that good computer software should be
designed to recognize slow convergence or divergence.

XD i, i
w

FIGURE 6.6
Fduf cases wh=re tie NewlcrrRaphson melhzd [Link].
 Pool
\
t v 1

j Ur)
/tr) j

jf Root

AT

FIGURE 6.2
Two aheraaiwB gjapbieol methods for dfetenrVining the row of f(xj = e~* — x |o| toot' at the
pc m nvhere i crosses lie x ox's; |b) root ar "-e -arsediai* erf the component functions,

6.2 T H E NEWTON-RAPHSON METHOD

Perhaps the most widely used of all root-locating formulas is the Newton-Raphson equation (Fig.
6.5).

If the initial guess at the root is xi, a tangent can be extended from the point [xi,f(xi)].

The point where this tangent crosses the x axis usually represents an improved estimate of the
root.
6.3 T H E SECANT METHOD

A potential problem in implementing the Newton-Raphson method is the evaluation of the

derivative.

Although this is not inconvenient for polynomials and many other functions, there are certain
functions whose derivatives may be extremely difficult or inconvenient to evaluate.

For these cases, the derivative can be approximated by a backward finite divided difference, as in
(Fig. 6.7)

This approximation can be substituted into Eq. (6.6) to yield the following iterative equation:

Equation (6.7) is the formula for the secant method. Notice that the approach requires two initial
estimates of x. However, because/(JC) is not required to change signs between the estimates, it is
not classified as a bracketing method.

FIGURE 6 . 7
Graphical depiction of Ihe secant method. Th's techno _e is i mihr to the Newlortfcaphson tech-
nique (Fig. 6.5] in ihe sense thai an estimate at the soot is predicted by e«rapobfing a tangent
of the function to ihe x cab. However, the secant method uses a difference rather than a deriva-
tive <=-.-!—
 E X A M P L E 6.6 The Secant Method

Problem Statement. Use the secant method to estimate the root of f(x) — e~ - x . Start with x

initial estimates of x-i = 0 and xo = 1.0.

Solution. Recall that the true root is 0.56714329

f ( - f (KO)

« 0.612-fO

f + 0 , 6 3 2 \

Second \"Ve_rcy\~ior\

Xjl- 0,M2fO_ [Link] ft-0^270 ) _ 0 > 5 < m £ ± - 0 . 5 8 ° / ,

- 0 . 63212 _ (-O,O7O?0

Tin \rd I W r a V i o r»

-O O?0^i
l _ ( - 0 . QGSW)
6.3.3 Modified Secant Method

Rather than using two arbitrary values to estimate the derivative, an alternative approach
involves a fractional perturbation of the independent variable to estimate f (x),
l

J [Xt) = -

where d = a small perturbation fraction. This approximation can be substituted into Eq. (6.6) to
yield the following iterative equation:

(6.8)

E X A M P L E 6.8 Modified Secant Method

Problem Statement. Use the modified secant method to estimate the root of/(x) = e — x. Use a x

value of 0.01 for S and start with xO = 1.0. Recall that the true root is 0.56714329

Solution.

First iteration:

Xo= 1 0 , 6 3212.

><i= Xo- o^o.-fGco) _ \ o . Q \ ) ^ c , 7 , , ,

— — -—- - — = 0,b^f--Z6v5

Second :WaV\oo\

0.537263 Sx,«[Link] 537-26 3 0.0±?083

^ = " ^ X u f ^ O = 0539-263- 0 , 0 0 5 3 ^ 6 3 io.O^fOU)

1 ^ 1 = 0.023^ °/-
X 5 _ Xa. _ J x ^ U f l - — - 0.S67OU 0^0056^1, (0.000209}

^ fa) - f W - 0.00*6?_ 0.000209

6.5 M U L T I P L E ROOTS

A multiple root corresponds to a point where a function is tangent to the x axis.

For example, a double root results from

j f j t ) = (x — 3)(x — l)Lx — 1) f
f ( x ) - x 3 - S x ^ ^ x . . 3

The equation has a double root because one value of x makes two terms in Eq. (6.11) equal to
zero.

Graphically, this corresponds to the curve touching the x axis tangentially at the double root.

Examine Fig. 6.13a at x = 1. Notice that the function touches the axis but does not cross it at the
root.

A triple root corresponds to the case where one x value makes three terms in an equation equal to
zero, as in
 f x ) = (x - 3)(x - I K i - l>(x - I)

Another alternative, also suggested by Ralston and Rabinowitz (1978), is to define a new
function w(x), that is, the ratio of the function to its derivative, as in

fix)
mix j =
f T ( x ) ( , 13)
It can be shown that this function has roots at all the same locations as the original function.
Therefore, Eq. (6.13) can be substituted into Eq. (6.6) to develop an alternative form of the
Newton-Raphson method:

X, f I = X. — , ,
• r f .• X
• IS 1 (6.14)
Equation (6.13) can be differentiated to give

LTWP (6 . 15)

Equations (6.13) and (6.15) can be substituted into Eq. (6.14) and the result simplified to yield

x r-l — ~~
l/'t'i)] 2 — Jlx,)f"t.x,i .
(6 16)

E X A M P L E 6.10 Modified Newton-Raphson Method for Multiple Roots

Problem Statement. Use both the standard and modified Newton-Raphson methods to evaluate
the multiple root of Eq. (6.11), with an initial guess of x = 0. 0

Solution. The first derivative of Eq. (6.11) i s / ' fx) = 3.x" — lOx + 7, and therefore, the standard
3

Newton-Raphson method for this problem is [Eq. (6.6)]

f ' ( * ) - 3*3- Sxi-?

1=0 x ,o
0 =

0 0 "CO
1 O4205714 57
2 UL6B57F43 31
3 0.8325654 17
4 0.9133?;C 8.7
5 0,9557833
6 a077rSS il
r 2.2.

x^ ^UOfVxO

(x; _S^%?x;-3)
3 (3x;^0x;-r*)
^ x,v
 I *$

0 0 100
] I 105263 ! I
2 I .C03OB2 0,31
3 1.000002 0.00024

Jfxl
/ (x)f

The preceding example illustrates the trade-offs involved in opting for the modified Newton-
Raphson method. Although it is preferable for multiple roots, it is somewhat less efficient and
requires more computational effort than the standard method for simple roots.

It should be noted that a modified version of the secant method suited for multiple roots can also
be developed by substituting Eq. (6.13) into Eq. (6.7).

The resulting formula is (Ralston and Rabinowitz, 1978)

• ,-• • • • . . - •:• . . . ;.: . ' ' • •-::--:vV . • ' ' .
: :

fx, ) 1- X, t
• J rI = x i "
fx -i) - fx )
Y

t t

M | X | . . . . 1 ) " — ti ( X j J
6.6 SYSTEMS OF NONLINEAR EQUATIONS

To this point, we have focused on the determination of the roots of a single equation.

A related problem is to locate the roots of a set of simultaneous equations,

f\, . - . s X w ) — 0

The solution of this system consists of a set of x values that simultaneously result in all the
equations equaling zero.

In Part Three, we will present methods for the case where the simultaneous equations are
linear—that is, they can be expressed in the general form

fix) = a\x\- aixi + * • - 4- a„x -b = 0 n

(6.18)

where the b and the a's are constants.

Algebraic and transcendental equations that do not fit this format are called nonlinear equations.

For example,

j + xv = 10
2

and

y + 3xy = 57 2
are two simultaneous nonlinear equations with two unknowns, x and v.

They can be expressed in the form of Eq. (6.17) as

y) = x + xy — 10 = 0
p(x y) = y + 3ry - 57 = 0
f z

(6.19)

Thus, the solution would be the values of x and y that make the functions u(x, y) and V(JC, y) equal
to zero.

Most approaches for determining such solutions are extensions of the open methods for solving
single equations.

In this section, we will investigate two of these: fixed-point iteration and Newton-Raphson.

6.6.1 Fixed-Point Iteration

The fixed-point-iteration approach (Sec. 6.1) can be modified to solve two simultaneous,
nonlinear equations. This approach will be illustrated in the following example.

E X A M P L E 6.11 Fixed-Point Iteration for a Nonlinear System

Problem Statement. Use fixed-point iteration to determine the roots of Eq. (6.19). Note that a
correct pair of roots is x = 2 and y = 3. Initiate the computation with guesses of x = 1.5 and y =
3.5.

u(j, v) = x -f xy — 10 = 0
2

u(x, y) = y 4- 3xjr — 57 = 0

Solution.

Equation (6.19a) can be solved for

 *«, = 1.5" . 3.5"

\ors

yi = -24.

XJL= lO-** 2 , _ |<0_ =r - 0 . 2 0 ^ 0

J2 6

Tfc, cap r o Q C 3

bu^ M -Hie. w-tyoal

3*;
F~i r<sV~ I 4-<ercxi~i o

Xo = 1.5 jc =3.5

Xo ^ 2H7945 y « -3,5

57- X - ^52-3.5 *
=r 2,S60Sf
H y 3 ^.17945)

2.17^ U^2^6051

X1 = 1,94053 ^=2,S&0Sl

^ 7 " ^ _ n^L2.S6GSp « 3.04955

3^1

Thus, "tW approach 1 J ^ r

X -2 cur->c\ - 3>
6.6.2 Newton-Raphson

By

dx By By dx

Biii dm

>/ + !
diii dVi

dx By By Bx (6.24)

Equation (6.24) is the two-equation version of the Newton-Raphson method.

As in the following example, it can be employed iteratively to home in on the roots of two
simultaneous equations.

E X A M P L E 6.12 Newton-Raphson for a Nonlinear System

Problem Statement. Use the multiple-equation Newton-Raphson method to determine roots of

Eq. (6.19). Note that a correct pair of roots is x = 2 and y = 3. Initiate the computation with
guesses ofx= 1.5 and y = 3.5.

x -hxj-10 =0
z

y + Jxy 2 -57-0

Solution.

First compute the partial derivatives and evaluate them at the initial guesses of JC and y:
 * = 1 . 5 = 3.<5

= 2 * + u = 2, (l.s)-t 3,5 = 6.5

J^£__ - X ^ 1,5

6«

X o a + X 0 y 0 - I D - 1.5% 1.5(3,5)-iO^r - 2 &

Vo y<>_ 3x u 0 0 x _ 5 7 = 3,5_ 3 ( l , 5 ) ( 3 . s ) - S 7 = H25

a

Up - Vo d u o , . t . ,

X l - Xo _ .
156.125

X i ^ 2 , 0 3 6 0 3

= 3 5 _ (U2S^^

2.SJ33S