1

Unity University
Department of Civil Engineering

Numerical & Computational Methods

Chapter-2
ROOTS OF EQUATIONS

By: Feysel N.
(MSc-Geotechnical Engineering & Geo-hazard)
Introduction 2

• Years ago, you have learned that; to solve

f(x) = ax2 + bx + c = 0 (1)
you use the quadratic formula
ି௕േ ௕మ ିସ௔௖
(2)
ଶ௔
• The values calculated with Eq. (2) are called the “roots” of Eq. (1).
They represent the values of x that make Eq. (1) equal to zero.
• Thus, we can define the root of an equation as the values of x that
makes f(x) = 0.
• Although the quadratic formula is handy for solving Eq. (1), there
are many other functions for which the root cannot be determined
ି௫
so easily. For example, cannot be solved
analytically. For these cases, the numerical methods described in
this chapter provide efficient means to obtain the root.
Introduction 3

• Many problems in engineering and science require finding the

roots of a nonlinear equation.
• The nonlinear equation, f(x), can be
 Algebraic equation or
 Transcendental equation
 An algebraic equation is an equation involving +, −, ×, /, and
radicals. Polynomials are a simple example of such equations.
 A transcendental equation is a non-algebraic equation
involving trigonometric, logarithmic, exponential, and other
functions.
• Nonlinear equations behave in various ways in the vicinity of a
root. They may have distinct (simple) real roots, repeated
(multiple) real roots, or complex roots.
• Figure 2.1a - 2.1h in the following slides show these behaviors.
Introduction 4

(a) No Real root (b) Simple root

(Complex roots may exist) E.g. f(x)=x3+x2+x-4
E.g. f(x)=x4+6x2+x+5

(c) Two simple roots (d) Three simple roots

E.g. f(x)=x4-x3+9x2+4x-7 E.g. f(x)=x3+x2-4x-2
Introduction 5

(e) Double root (f) Triple root

E.g. f(x)=x2-4x+4 E.g. f(x)=x3-3x2+3x-1

(g) One simple root &

(h) General case:
Double root
any number of simple or
E.g. f(x)=x3-5x2+7x-3 multiple roots.
Non-computer methods for finding roots 6

• The roots of some equations can be obtained directly, as we have

done with the quadratic equation. But there are many other
functions for which the root cannot be determined directly.
• One method to obtain an approximate solution is to plot the
function and determine where it crosses the x axis. This point,
which represents the x value for which f(x) = 0, is the root.
Although graphical methods are useful for obtaining rough
estimates of roots, they are limited because of their lack of
precision.
• An alternative approach is to use trial and error. This consists of
guessing a value of x and evaluating f(x). If f(x) is close enough to
zero, stop. If not, guess another x, and continue until f(x) is close
enough to zero.
• Such disorganized methods are obviously inefficient and
inadequate for the requirements of engineering practice.
Types of numerical methods for root finding 7
• The roots of an equation can be calculated efficiently using
approximate solution techniques (Numerical methods).
• Any numerical method for finding roots involve two phases;
1) Bounding the root
2) Refining the root
• Bounding the root involves finding a rough estimate of the root that
can be used as the initial approximation, or a starting point.
• Refining the root involves determining the solution to a specified
tolerance by an efficient systematic procedure.
• There are two general categories of root-finding methods:
I) Bracketing (closed) methods
II) Open methods
 8

Bracketing Methods
1) Bisection method
2) False-Position method
Introduction 9

• Bracketing methods use the fact that a function typically changes

sign in the vicinity of a root.
• In bracketing methods, two initial estimates of the root (xl & xu)
which bracket the root must first be found by the bounding
process. The root, x = xr, is bracketed by the two estimates.
• The objective is to locate the root to within a specified tolerance
by a systematic procedure while keeping the root bracketed.
• Two bracketing methods will be discussed here;
1) Bisection method
2) False-Position method
• Before discussing these techniques, let us see how to get a rough
estimate of the root (Bounding the root).
Bounding the root 10

• Some of the possible bounding methods are:

I. Graphical method
II. Incremental search
III. Past experience with the problem or a similar problem
IV. Solution of a simplified approximate model
V. Previous solution in a sequence of solutions
• Graphical method and incremental search are discussed on the
following slides.
Bounding the root 11

I. Graphical method
• Graphical method involves plotting the equation over the range of
interest and observing where it crosses the x axis. This point,
which represents the x value for which f(x)=0, provides a rough
approximation of the root.
• Graphing calculators, spreadsheet apps like Excel & software like
Matlab and Mathcad have the capability to plot a function simply
by defining the function and specifying the range of interest.
• Graphical interpretations are important tools for understanding
the properties of the functions and anticipating the pitfalls of the
numerical methods.
• Figure 2.2a-2.2f in the following slide shows a number of ways in
which roots can occur (or be absent) in an interval specified by a
lower bound xl and an upper bound xu.
Bounding the root 12

I. Graphical method
• Fig. 2.2a & 2.2c show that if
f(xl) and f(xu) have the same
sign, there are either no
roots or an even number of
roots in the interval.
• Fig. 2.2b & 2.2d show that
if f(xl) and f(xu) have
opposite sign, there are an
odd number of roots in the
interval
• Although these generalizations are usually true, there are cases
where they do not hold. For example, functions that are tangential
to the x axis (Fig. 2.2e) and discontinuous functions (Fig. 2.2f) can
violate these principles.
Bounding the root 13

I. Graphical method
• When a function is tangential to the x axis but
do not cross it at the root, it will have double
or quadruple…(even multiple roots) roots at
that point.
• An example of a function that is tangential to
the x axis is f(x)=x3-8x2+20x-16 (which can be
written as f(x)=(x-2)(x-2)(x-4)) and its roots
are x=2 and x=4. Notice that x=2 is a multiple
(double) root.
Bounding the root 14

II. Incremental search

• An incremental search is conducted by starting at one end of the
region of interest and evaluating the nonlinear function at small
increments across the region. When the value of the function
changes sign, it is assumed that a root lies in that interval.
• The two end points of the interval containing the root can be used
as initial guesses for a refining method.
• If multiple roots are suspected, check for sign changes in the
derivative of the function between the ends of the interval.
1) Bisection method 15

• If a function f(x) is real and continuous in an interval from xl to xu

and f(xl) & f(xu) have opposite signs, i.e. f(xl)*f(xu)<0, then there is
at least one real root xr between xl and xu.
• If a function changes sign over an interval, the function value at
the midpoint is evaluated. The location of the root is then
determined as lying at the midpoint of the subinterval within
which the sign change occurs. The process is repeated to obtain
refined estimates.
1) Bisection method 16

Procedure
Step-1: Choose lower xl and upper xu guesses for the root such that
the function changes sign over the interval. This can be checked by
ensuring that f(xl)*f(xu)<0.
௫೗ ା௫ೠ
Step-2: Estimate the root xr using ௥ ଶ
Step-3: Make the following evaluations to determine the interval in
which the root lies:
(a) If f(xl)*f(xr)<0, the root lies in the lower subinterval.
Therefore, set xl =xl & xu =xr and return to step-2.
(b) If f(xl)*f(xr)>0, the root lies in the upper subinterval.
Therefore, set xl =xr & xu =xu and return to step-2.
(c) If f(xl)*f(xr)=0, the root equals xr and terminate the iteration.
1) Bisection method 17

Termination Criteria and Error Estimates

• The iteration is terminated when the relative error εa is ≤ a
prespecified stopping criterion εs (or in terms of absolute error,
when Ea ≤ Es). x new  x old
a  r
new
r
 100%
new old
Ea  xr  xr
x
r

Where xrnew is the root for the present iteration and xrold is the root
from the previous iteration.
• Since the interval is always halved at each iteration, the above
equations can be written as; xu  xl xu  xl
a   100% Ea 
xu  xl 2
• Because each succeeding iteration halves the error, the relative
error for the present iteration will be half of the error from the
previous iteration.
1) Bisection method 18

Advantages
• The root is bracketed (i.e., trapped) within the bounds of the
interval, so the method is guaranteed to converge.
• Another benefit of the bisection method is that the number of
iterations required to attain a tolerable error E can be computed
before starting the iterations using;
log( xuinit  xlinit )  log E
n
log 2

Where xuinit and xlinit are the initial guesses of xu and xl.
Disadvantages
• The major disadvantage of the bisection method is that the
solution converges slowly (it can take a large number of iterations).
1) Bisection method 19

Algorithm for bisection

2) False-Position method 20

• In bisection method, in dividing the interval from xl to xu into

equal halves, no account is taken of the magnitudes of f(xl) and
f(xu). E.g. if f(xl) is much closer to zero than f(xu), it is likely that
the root is closer to xl than to xu as shown in the figure below.
• The False-Position (regula falsi in Latin) is a method that exploits
this graphical insight by joining f(xl) and f(xu) with a straight line.
The intersection of this line with the x axis represents an
improved estimate of the root.
• Using similar triangles (see Figure),
the intersection of the straight line
with the x axis (xr) will be;

This is the false-position formula.

2) False-Position method 21

Procedure: The procedure is the same as that of bisection method

except the estimation of the root (step-2) as shown below.
Step-1: Choose lower xl and upper xu guesses for the root such that
the function changes sign over the interval. This can be checked by
ensuring that f(xl)*f(xu)<0.
f ( xu )  ( xl  xu )
Step-2: Estimate the root xr using xr  xu 
f ( xl )  f ( xu )
Step-3: Make the following evaluations to determine the interval in
which the root lies:
(a) If f(xl)*f(xr)<0, the root lies in the lower subinterval.
Therefore, set xl =xl & xu =xr and return to step-2.
(b) If f(xl)*f(xr)>0, the root lies in the upper subinterval.
Therefore, set xl =xr & xu =xu and return to step-2.
(c) If f(xl)*f(xr)=0, the root equals xr and terminate the iteration.
2) False-Position method 22

Termination Criteria and Error Estimates

• The iteration is terminated when the relative error εa is ≤ a
prespecified stopping criterion εs (or in terms of absolute error,
when Ea ≤ Es). xrnew  xrold
a  new
 100% Ea  xr
new
 xr
old

xr

Advantages
• The false position method generally converges more rapidly than
the bisection method.
Disadvantages
• Its one-sided. That is, as iterations are proceeding, one of the
bracketing points will tend to stay fixed. This can lead to poor
convergence, particularly for functions with significant curvature
as shown in the figure below.
2) False-Position method 23

Disadvantages
Figure:- Plot of f(x)=x10−1, illustrating slow
convergence of false-position method. the
curve violates the basis upon which false
position was based—that is, if f(xl) is much
closer to zero than f(xu), then the root is
closer to xl than to xu. But in this case, the
opposite is true.
• One way to mitigate the “one-sided” nature
of false position is when one of the bounds
is stuck, the function value at the stagnant
bound can be divided in half. This is called
the modified false-position method.
2) False-Position method 24

Algorithm for
Modified False-Position
 25

Open Methods
1) Fixed-point iteration method
2) Newton-Raphson method
3) Secant method
Introduction 26

• Open methods also involve systematic trial-and-error iterations but

they 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 iteration progresses. However, when the open methods
converge, they usually do so much more quickly than the
bracketing methods.
• Three open methods will be discussed here;
1) Fixed-point iteration method
2) Newton-Raphson method
3) Secant method
1) Fixed-point iteration method 27

• This method involves solving f(x)=0 by rearranging the function

f(x) so that x is on the left-hand side of the equation i.e. x=g(x).
• Fixed-point iteration essentially solves two functions
simultaneously: y1=x and y2=g(x). The point of intersection of
these two functions is the solution to x=g(x), and thus to f(x)=0.
• The transformation can be accomplished either by algebraic
manipulation or by adding x to both sides of the original equation.
• For example, x2−2x+3=0 can be manipulated as;
x 3
2 2
x 3 3 3
x
2
i.e. g ( x ) 
2
or x 
x2
i .e. g ( x ) 
x2
whereas sin(x)=0 could be put into the form of x=g(x) by adding x
to both sides to yield x=sin(x)+x. That is g(x)=sin(x)+x.
• An initial guess xi is substituted into g(x) to get the next
approximation xi+1 as expressed by the iterative formula;
x i 1  g ( x i )
1) Fixed-point iteration method 28

Termination Criteria and Error Estimates

• The iteration is terminated when the relative error εa is ≤ a
xi 1  xi
prespecified stopping criterion εs. a   100%
xi 1
• Assuming xr is the true root; if the true error for iteration i is
Eti=xr−xi then the true error for the next iteration will be
Eti+1=g’(ξ)+Eti (see Box 6.1 of your text book, Chapra)
g ( xr )  g ( xi )
where g '( )  and ξ is between xi and xr.
xr  xi
• Consequently, if |g’(x)|<1, the errors decrease with each iteration
and x gets closer to the true root (convergence). But if |g’(x)|>1,
the errors grow with each iteration and x gets farther from the true
root (Divergence). See next slides.
• Therefore, When the method converges, the error is roughly
proportional to and less than the error of the previous step. Hence
fixed-point iteration is linearly convergent.
1) Fixed-point iteration method 29

(a) Monotone Convergence (b) Oscillating Convergence

(when 0<g′(x)<1) (when −1<g′(x)<0)
⸫ if |g’(x)|<1 then it converges.
1) Fixed-point iteration method 30

(c) Monotone Divergence (d) Oscillating Divergence

(when g′(x)>1) (when g′(x)<−1)
⸫ if |g’(x)|>1 then it Diverges.
1) Fixed-point iteration method 31

Advantage
• Once you figure out the function g(x); the iteration is so simple,
you can even do it on a calculator (see next slide on how to this).
Disadvantage
• It is not a reliable method & is not recommended for computer use.
Algorithm for Fixed-point iteration
1) Fixed-point iteration method 32

Fixed-point iteration using a non-programmable calculator

1) Insert your x0 value and then press =
2) Type the function g(x)
3) Press = (this gives you the value of x1)
4) Press = (this gives you the value of x2)
5) Press = (this gives you the value of x3)
Continue pressing the = sign until the value stops to change or until
the value is close to your desired significant figures.
Example
Consider the function f(x) = x4 − 2x − 5. Incremental search shows
that it has real roots in the interval [1,2] and [-1,-2]. Find the roots
using fixed-point iteration method.
1) Fixed-point iteration method 33

SOLUTION
Manipulating the function using the x4 term;
x4  2 x  5  0
x4  2 x  5
x  (2 x  5)1/4
g ( x)  (2 x  5)1/4

Since the power (¼) is even, it will always give a positive result. Note
that the term in the bracket must be >0 (i.e. x must be ≥ -2.5).
⸫ Let us try x0 = 1
Do the following on your calculator
1) Press 1 and then =
2) Type (2ANS+5)^0.25
3) Press = (this gives you the value of x1 = 1.626576562)
1) Fixed-point iteration method 34

…SOLUTION
1) Fixed-point iteration method 35

…SOLUTION
Pressing = sign afterwards displays values of x1,2,3… as shown
⸫ The root in the interval [1,2] is
x = 1.702706371
• You will get the same final result if you
try x0=2, x0=0, x0=-1 or x0=-2
1) Fixed-point iteration method 36

…SOLUTION
Manipulating the function using the x1 term;

Since the power (1) is odd, it can either give a +ve or -ve result.
Let us try x0 = -1
Do the following on your calculator
1) Press -1 and then =
2) Type (ANS^4 – 5)÷2
3) Press = (this gives you the value of x1 = -2)
1) Fixed-point iteration method 37

…SOLUTION
Pressing = sign afterwards displays values of x1,2,3… as shown
• As can be seen, the values get
increasing and we get “Math ERROR”
message. Hence g(x) diverges at this
point (Monotone Divergence).
• You will get the same pattern if you try
x0=-2, x0=0, x0=1 or x0=2.
• Therefore, we have to manipulate the
function in other way as shown in the
next slide.
1) Fixed-point iteration method 38

…SOLUTION
Manipulate the function as follows;

Since the power (1) is odd, it can either give a +ve or -ve result.
Let us try x0 = -1
Do the following on your calculator
1) Press -1 and then =
2) Type 5÷(ANS3 – 2)
3) Press = (this gives you the value of x1 = -1.666666667)
1) Fixed-point iteration method 39

…SOLUTION
Pressing = sign afterwards displays values of x1,2,3… as shown
• As can be seen, the values get alternating.
Hence the iteration with this g(x) has
gone into an infinite loop without
convergence (Oscillating Divergence).
• You will get the same pattern if you try
x0=-2, x0=0, x0=1 or x0=2
• Therefore, we have to manipulate the
function in other way as shown in the
next slide.
1) Fixed-point iteration method 40

…SOLUTION
Manipulate the function as follows;

Since the power (1/3) is odd, it can either give a +ve or -ve result.
Let us try x0 = -1
Do the following on your calculator
ଵ
DO NOT write the power as
1) Press -1 and then = ଷ
0.333. If you do, you will get a
2) Type (5ANS2 ÷ (ANS3−2))^(1÷3) Math ERROR message.
1) Fixed-point iteration method 41

…SOLUTION
3) Press = (this gives you the value of x1 = -1.185631101)
Pressing = sign afterwards displays values of x1,2,3… as shown
⸫ The root in the interval [-1,-2] is
x = -1.255937548
You will get the same final result if
you try x0=1 or x0=-2 but with
different accuracy.
If you try x0=2 will get the same final
result after 29 iterations.
2) Newton-Raphson method 42

• It is the most widely used of all root-locating methods.

• 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, xi+1.
• As shown in the Figure, the first derivative at xi is equivalent to the
slope of the tangent line at xi. That is;

which can be rearranged to yield;

This is the Newton-Raphson formula.

2) Newton-Raphson method 43

Termination Criteria and Error Estimates

• The iteration is terminated when the relative error εa is ≤ a
xi 1  xi
prespecified stopping criterion εs. a   100%
xi 1
• Assuming xr is the true root; if the true error for iteration i is
Eti=xr−xi then (based on Taylor series) the true error for the next
iteration will be (see Box 6.2 of your text book, Chapra)

• Therefore, the error is roughly proportional to the square of the

previous error. In other words, the number of significant figures
of accuracy approximately doubles with each iteration.
• Such behavior is referred to as quadratic convergence. Hence,
Newton-Raphson method has quadratically convergent.
Advantages
• It converges very fast (quadratic convergence).
2) Newton-Raphson method 44

Disadvantages
• In some cases, if a poor initial estimate is used, the procedure may
converge slowly or it may converge to an alternate solution.
• If an inflection point [i.e., f ’’(x)=0] occurs in the vicinity of a root,
it can send the method far away from the root as shown below.
Notice that iterations beginning at x0 progressively diverge from
the root. A better initial estimate can eliminate this problem.
2) Newton-Raphson method 45

Disadvantages
• If a local maximum or minimum occurs in the vicinity of a root, it
may cause oscillations in the solution as shown below.
• The oscillations may persist, or as in the figure below, a near-zero
slope is reached, and so the solution is sent far from the area of
interest. A better initial estimate can eliminate this problem.
2) Newton-Raphson method 46

Disadvantages
• In some cases where the function f(x) has a number of roots, an
initial guess that is close to one root can jump to a location several
roots away (the guess may jump and converge to some other root)
as shown below. This tendency to move away from the area of
interest is because near-zero slopes are encountered.
2) Newton-Raphson method 47

Disadvantages
• Obviously, a zero slope [f ’(x)=0] is truly a disaster because it
causes division by zero in the Newton-Raphson formula.
Graphically (see the Figure below), it means that the solution
shoots off horizontally and never hits the x axis.

• Another major shortcoming is that it requires the derivative of the

function be obtained analytically. Some functions are difficult to
differentiate analytically, and some functions cannot be
differentiated analytically at all. The remedy for this problem is to
use the secant method.
2) Newton-Raphson method 48

Algorithm for Newton-Raphson method

2) Newton-Raphson method 49

Algorithm for Newton-Raphson method

• Because of the foregoing discussion of potential problems of the
Newton- Raphson method, the program would be improved by
incorporating several additional features, such as:
3) Secant method 50

• As discussed previously, a potential problem in using the Newton-

Raphson method is the evaluation of the derivative.
• In the secant method, the derivative is approximated by a
backward finite divided difference, as in (see Figure below);

which can be substituted in the

Newton-Raphson formula to yield;

This is the formula for secant method.

3) Secant method 51

• Notice that the secant method requires two initial estimates of x.

However, because f(x) is not required to change signs between the
estimates, it is not classified as a bracketing method.
Termination Criteria and Error Estimates
• The iteration is terminated when the relative error εa is ≤ a
prespecified stopping criterion εs. xi 1  xi
a    100%
xi 1

• Convergence occurs at a rate of 1.62..., which is somewhat slower

than the quadratic convergence rate of Newton’s method.
Disadvantages and Algorithm
• Disadvantages of Newton-Raphson are also applicable here.
• The algorithm is similar to Newton-Raphson; simply modify it so
that the two initial guesses are input and by using the equation for
secant method instead of Newton-Raphson.
Root Location with software package-Excel 52
• Excel has two standard tools that can be used for root locating:
1) Goal Seek tool
2) Solver tool
• Goal Seek is expressly used to drive an equation to a value (in our
case, zero) by varying a single parameter.
• The Solver tool is more sophisticated than Goal Seek in that;
A) it can vary several cells simultaneously and
B) along with driving a target cell to a value, it can minimize and
maximize its value.