Computational (Numerical) Methods For Chemical Engineers 2014 E.C.
CHAPTER TWO
Roots of Nonlinear Equations in One Variable
Objective
After reading this chapter, student should be able to:
Follow the algorithm of the bisection method of solving a nonlinear equation,
Use the bisection method to solve engineering problems of finding roots of a nonlinear equation,
Enumerate the advantages and disadvantages of the bisection method.
Follow the algorithm of the false-position method of solving a nonlinear equation,
Apply the false-position method for engineering problems to find roots of a nonlinear equation.
Derive the secant method to solve for the roots of a nonlinear equation,
Use the secant method to numerically solve engineering problems.
Derive the newton-raphson method formula,
Develop the algorithm of the newton-raphson method,
Use the newton-raphson method to solve engineering problems, and
Discuss the drawbacks of the newton-raphson method.
2.1 Introduction
Most of Engineering Problems are complex and difficult to solve analytically. If the modeling equation
is linear and quadratic equation; it is possible to solve analytical and using the general formula of
quadratic equation. But if our modeling equation is non-linear equation we have no general formula to
solve our modeling problem. Therefore, we inference to use numerical method to solve the non-linear
model equation. There are two common numerical methods to solve non-linear equation: the first one is
closed – domain (Bracketing) and the other one is Open domain method.
DTU CHED By Marye M. (MSc) Page 15
Computational (Numerical) Methods For Chemical Engineers 2014 E.C.
2.2. Bracketing Methods
2.2.1. Bisection Method of Solving a Nonlinear Equation
What is the bisection method and what is it based on?
One of the first numerical methods developed to find the root of a nonlinear equation f ( x) 0 was the
bisection method (also called binary-search method). The method is based on the following theorem.
Theorem
An equation f ( x) 0 , where f (x) is a real continuous function, has at least one root between
x and xu if f ( x ) f ( xu ) 0 (See Figure 1).
Note that if f ( x ) f ( xu ) 0 , there may or may not be any root between x and xu (Figures 2 and
3).
If f ( x ) f ( xu ) 0 , then there may be more than one root between x and xu (Figure 4). So the
theorem only guarantees one root between x and xu .
Bisection method
Since the method is based on finding the root between two points, the method falls under the
category of bracketing methods.
Since the root is bracketed between two points, x and xu , one can find the mid-point, xm between
x and xu . This gives us two new intervals
1. x and xm , and
2. xm and xu .
f(x)
xℓ
x
xu
Figure 2.1 At least one root exists between the two points if the function is real, continuous, and
changes sign.
DTU CHED By Marye M. (MSc) Page 16
Computational (Numerical) Methods For Chemical Engineers 2014 E.C.
f(x)
x
xℓ xu
Figure 2.2 If the function f (x) does not change sign between the two points, roots of the
equation f ( x) 0 may still exist between the two points.
f(x) f(x)
xℓ xu
x x
xℓ xu
Figure 2.3 If the function f (x) does not change sign between two points, there may not
be any roots for the equation f ( x) 0 between the two points.
f(x)
xu
xℓ x
Figure 2.4: If the function f (x) changes sign between the two points, more than one root for the
equation f ( x) 0 may exist between the two points.
DTU CHED By Marye M. (MSc) Page 17
Computational (Numerical) Methods For Chemical Engineers 2014 E.C.
Is the root now between x and xm or between xm and xu ? Well, one can find the sign of f ( x ) f ( xm ) ,
and if f ( x ) f ( xm ) 0 then the new bracket is between x and xm , otherwise, it is between xm and xu .
So, you can see that you are literally halving the interval. As one repeats this process, the width of the
interval x , xu becomes smaller and smaller, and you can zero in to the root of the equation f ( x) 0 .
The algorithm for the bisection method is given as follows.
Class activity
Write the Algorithm for the bisection method?
Example 1
You are working for „DOWN THE TOILET COMPANY‟ that makes floats for ABC commodes. The
floating ball has a specific gravity of 0.6 and has a radius of 5.5 cm. You are asked to find the depth to
which the ball is submerged when floating in water.
The equation that gives the depth x to which the ball is submerged under water is given by
x 3 0.165x 2 3.993 104 0
Use the bisection method of finding roots of equations to find the depth x to which the ball is
submerged under water. Conduct three iterations to estimate the root of the above equation.
Find the absolute relative approximate error at the end of each iteration, and the number of
significant digits at least correct at the end of each iteration.
Figure 2.5 Floating ball problem.
[Link] Advantages of bisection method
a) The bisection method is always convergent. Since the method brackets the root, the method
is guaranteed to converge.
b) As iterations are conducted, the interval gets halved. So one can guarantee the error in the
solution of the equation.
[Link] Drawbacks of bisection method
a) The convergence of the bisection method is slow as it is simply based on halving the interval.
b) If one of the initial guesses is closer to the root, it will take larger number of iterations to
reach the root.
c) If a function f (x) is such that it just touches the x -axis (Figure 6) such as
f ( x) x 2 0
it will be unable to find the lower guess, x , and upper guess, xu , such that
DTU CHED By Marye M. (MSc) Page 18
Computational (Numerical) Methods For Chemical Engineers 2014 E.C.
f ( x ) f ( xu ) 0
d) For functions f (x) where there is a singularity 1 and it reverses sign at the singularity, the
bisection method may converge on the singularity (Figure 7).An example includes
1
f ( x)
x
where x 2 , xu 3 are valid initial guesses which satisfy
f ( x ) f ( xu ) 0
However, the function is not continuous and the theorem that a root exists is also not
applicable.
f (x)
Figure:2.6 The equation f ( x) x 2 0 has a single root at x 0 that cannot be bracketed.
1
A singularity in a function is defined as a point where the function becomes infinite. For example, for a function
such as 1 / x , the point of singularity is x 0 as it becomes infinite.
f(x)
Figure: 2.7 The equation f x
1
0 has no root but changes sign.
x
DTU CHED By Marye M. (MSc) Page 19
Computational (Numerical) Methods For Chemical Engineers 2014 E.C.
2.2.2. FALSE-POSITION METHOD
[Link] Introduction
In chapter 03.03, the bisection method was described as one of the simple bracketing methods for
solving a nonlinear equation of the general form
f ( x) 0 (1)
f x
f xU
Exact root
xL
O xr xU x
f xL
Figure 1 False-Position Method
The above nonlinear equation can be stated as finding the value of xsuch that Equation (1) is satisfied. In
the bisection method, we identify proper values of xL (lower bound value) and xU (upper bound value)
for the current bracket, such that
f ( xL ) f ( xU ) 0 . (2)
The next predicted/improved root xm can be computed as the midpoint between xL and xU as
x xU
xm L (3)
2
The new upper and lower bounds are then established, and the procedure is repeated until the
convergence is achieved (such that the new lower and upper bounds are sufficiently close to each other).
However, in the example shown in Figure 1, the bisection method may not be efficient because it does
not take into consideration that f ( x L ) is much closer to the zero of the function f (x) as compared to
f ( xU ) . In other words, the next predicted root xr would be closer to xL (in the example as shown in
Figure 1), than the mid-point between xL and xU . The false-position method takes advantage of this
observation mathematically by drawing a secant from the function value at xL to the function value at
xU , and estimates the root as where it crosses the x-axis.
False-Position Method
Based on two similar triangles, shown in Figure 1, one gets
DTU CHED By Marye M. (MSc) Page 20
Computational (Numerical) Methods For Chemical Engineers 2014 E.C.
0 f ( x L ) 0 f ( xU )
(4)
xm x L xm xU
From Equation (4), one obtains
xm xL f xU xm xU f xL
xU f xL xL f xU xm f xL f xU
The above equation can be solved to obtain the next predicted root xm as
x f x L x L f xU
xm U (5)
f x L f xU
The above equation, through simple algebraic manipulations, can also be expressed as
f xU
xm xU (6)
f x L f xU
x L xU
or
f x L
xm x L (7)
f xU f x L
xU x L
Class Activity
Write the Algorithm for False-Position Method
Example 1
You are working for “DOWN THE TOILET COMPANY” that makes floats for ABC commodes. The
floating ball has a specific gravity of 0.6 and has a radius of 5.5cm. You are asked to find the depth to
which the ball is submerged when floating in [Link] equation that gives the depth x to which the
ball is submerged under water is given by
x 3 0.165x 2 3.993 104 0
Use the false-position method of finding roots of equations to find the depth x to which the ball is
submerged under water. Conduct three iterations to estimate the root of the above equation. Find the
absolute relative approximate error at the end of each iteration, and the number of significant digits at
least correct at the end of third iteration.
Example 2
Find the root of f x x 42 x 2 0 , using the initial guesses of xL 2.5 and xU 1.0, and a
pre-specified tolerance of s 0.1% .
2.3. Open Domain Methods
2.3.1 Newton-Raphson Method of Solving a Nonlinear Equation
Introduction
Methods such as the bisection method and the false position method of finding roots of a nonlinear
equation f ( x) 0 require bracketing of the root by two guesses. Such methods are called bracketing
methods. These methods are always convergent since they are based on reducing the interval between
the two guesses so as to zero in on the root of the equation.
DTU CHED By Marye M. (MSc) Page 21
Computational (Numerical) Methods For Chemical Engineers 2014 E.C.
In the Newton-Raphson method, the root is not bracketed. In fact, only one initial guess of the root is
needed to get the iterative process started to find the root of an equation. The method hence falls in the
category of open methods. Convergence in open methods is not guaranteed but if the method does
converge, it does so much faster than the bracketing methods.
Derivation
The Newton-Raphson method is based on the principle that if the initial guess of the root of f ( x) 0 is
at x i , then if one draws the tangent to the curve at f ( xi ) , the point xi 1 where the tangent crosses the x
-axis is an improved estimate of the root (Figure 1).
Using the definition of the slope of a function, at x xi
f xi 0
f xi = tanθ =
xi xi 1
which gives
f xi
xi 1 = xi (1)
f xi
Equation (1) is called the Newton-Raphson formula for solving nonlinear equations of the form
f x 0 . So starting with an initial guess, x i , one can find the next guess, xi 1 , by using Equation (1).
One can repeat this process until one finds the root within a desirable tolerance.
Class Activity
Write the Algorithm for Newton-Raphson method
Example 1
You are working for „DOWN THE TOILET COMPANY‟ that makes floats for ABC commodes. The
floating ball has a specific gravity of 0.6 and has a radius of 5.5 cm. You are asked to find the depth to
which the ball is submerged when floating in water.
The equation that gives the depth x in meters to which the ball is submerged under water is given by
x 3 0.165x 2 3.993 104 0
Use the Newton-Raphson method of finding roots of equations to find
a) the depth x to which the ball is submerged under water. Conduct three iterations to estimate
the root of the above equation.
b) the absolute relative approximate error at the end of each iteration, and
c) the number of significant digits at least correct at the end of each iteration.
Drawbacks of the Newton-RaphsonMethod
1. Divergence at inflection points: If the selection of the initial guess or an iterated value of the root
turns out to be close to the inflection point (see the definition in the appendix of this chapter) of
the function f x in the equation f x 0 , Newton-Raphson method may start diverging away
from the root. It may then start converging back to the root.
2. Division by zero
3. Oscillations near local maximum and minimum: Results obtained from the Newton-Raphson
method may oscillate about the local maximum or minimum without converging on a root but
converging on the local maximum or minimum. Eventually, it may lead to division by a number
close to zero and may diverge.
DTU CHED By Marye M. (MSc) Page 22
Computational (Numerical) Methods For Chemical Engineers 2014 E.C.
2.3.2. Secant Method of Solving Nonlinear Equations
What is the secant method and why would we want to use it instead of the Newton-Raphson
method?
The Newton-Raphson method of solving a nonlinear equation f ( x) 0 is given by the iterative formula
f ( xi )
xi 1 = xi (1)
f ( xi )
One of the drawbacks of the Newton-Raphson method is that you have to evaluate the derivative of the
function. With availability of symbolic manipulators such as Maple, MathCAD, MATHEMATICA and
MATLAB, this process has become more convenient. However, itstill can be a laborious process, and
even intractable if the function is derived as part of a numerical scheme. To overcome these drawbacks,
the derivative of the function, f (x) is approximated as
f ( xi ) f ( xi 1 )
f ( xi ) (2)
xi xi 1
Substituting Equation (2) in Equation (1) gives
f ( xi )(xi xi 1 )
xi 1 xi (3)
f ( xi ) f ( xi 1 )
The above equation is called the secant method. This method now requires two initial guesses, but
unlike the bisection method, the two initial guesses do not need to bracket the root of the equation. The
secant method is an open method and may or may not converge. However, when secant method
converges, it will typically converge faster than the bisection method. However, since the derivative is
approximated as given by Equation (2), it typically converges slower than the Newton-Raphson method.
The secant method can also be derived from geometry,as shown in Figure 1. Taking two initial guesses,
xi 1 and xi , one draws a straight line between f ( xi ) and f ( xi 1 ) passing through the x -axis at xi 1 . ABE
and DCE are similar triangles.
Hence
AB DC
AE DE
f ( xi ) f ( xi 1 )
xi xi 1 xi 1 xi 1
On rearranging, the secant method is given as
f ( xi )(xi xi 1 )
xi 1 xi
f ( xi ) f ( xi 1 )
DTU CHED By Marye M. (MSc) Page 23
Computational (Numerical) Methods For Chemical Engineers 2014 E.C.
f(x)
f(xi) B
f(xi–1) C
E D A
x
xi+1 xi–1 xi
Figure 1 Geometrical representation of the secant method.
Example 1
You are working for „DOWN THE TOILET COMPANY‟ that makes floats (Figure 2) for ABC
commodes. The floating ball has a specific gravity of 0.6 and a radius of 5.5 cm. You are asked to find
the depth to which the ball is submerged when floating in water.
The equation that gives the depth x to which the ball is submerged under water is given by
x 3 0.165x 2 3.993 104 0
Use the secant method of finding roots of equations to find the depth x to which the ball is
submerged under water. Conduct three iterations to estimate the root of the above equation.
Find the absolute relative approximate error and the number of significant digits at least
correct at the end of each iteration.
DTU CHED By Marye M. (MSc) Page 24