Universiti Teknologi PETRONAS

MDB3053 Numerical Methods

ROOTS OF EQUATIONS –
BRACKETING METHOD

Reading Assignment: Chapter 5

in Textbook
Chap5/1
 Learning Outcomes

Numerical methods to find the roots of equation:

✓Bracketing Method

✓Open Method

Chap5/2
 BRACKETING METHOD

To calculate roots of equation using y

roots
Bracketing Methods:

1. Bisection Method x

2. False Position Method

- when a function is zero

- when a function crosses x-axis

Chap5/3
 TWO TYPES OF EQUATIONS

• Algebraic Equations
- A function y = f(x) is algebraic if it can be expressed in
the form
f i y n + f i−1 y n−1 +... + f1y + f 0 = 0

- Example: Quadratic equation 2x2 – x – 1= 0

• Transcendental Equations
- Non-algebraic equations
- Trigonometric (cos), exponential, logarithmic (log) are
examples of transcendental equations
- Example
ln x 2 −1 = 0

Chap5/4
 METHODS TO FIND ROOTS

7
Try this in MATLAB:
6
>> f=@(x) x^2-3*x+2
5 >> fplot(f,[0 4])
4

y 3 y = x2 – 3x +2
2

1
roots
0
0.0

0.4

0.8

1.2

1.6

2.0

2.4

2.8

3.2

3.6

4.0
-1

• plot the data points & connect them in a smooth curve

• locate the points at which the curve crosses the x-axis
• it provides rough estimate of the roots
• useful visualisation tool

Chap5/5
 Analytical Method
You have previously learned that:
To find the roots of
Method 1:

Method 2:

How about

Chap5/6
 BRACKETING METHODS
•2 types:
1. Bisection Method
2. False-Position Method

•Exploit the fact that a

function typically changes
sign in the vicinity of the root
→ f(xL)f(xU) < 0
• It is called bracketing
because two initial guesses
that ‘bracket’ the root on
either side are required Note:

Chap5/7
 BISECTION METHOD

•It is also known as Binary Chopping or Interval Halving

•In general, if there are two points xL(lower bound) and xU
(upper bound) such that f(xL)f(xU) < 0, then there is at least
one root between xL and xU

•Next, the interval is

successively bisected into
half
•After each bisection, the
upper and lower bounds Interval is bisected
are updated. into half

Chap5/9

Chap5/8
BISECTION METHOD: 3-Step ALGORITHM

STEP 1: Choose upper xU and lower xL guesses such that

f(xL)  f(xU) < 0

STEP 2 : Estimate the root, xr by dividing the interval [xL xU]

into half
xL + xU
Midpoint: xr =
2
STEP 3 : Evaluate the next sub-interval
• If f(xL)  f(xr) < 0, root lies in the lower interval, set xU=xr, return to step 2

• If f(xL)  f(xr) > 0, root lies in the upper interval, set xL=xr, return to step 2

• If f(xL)  f(xr) = 0, root equals to xr, terminate computation

Chap5/9
STEP 1: Choose upper xU and lower xL guesses such that
f(xL)  f(xU) < 0

root

Chap5/10
STEP 2 : Estimate the root, xr by dividing the
interval [xL xU] into half

xL + xU
Midpoint: xr =
2

Estimated root at
half of interval

Chap5/11
STEP 3 : Evaluate the next sub-interval
• If f(xL)  f(xr) < 0, root lies in the lower interval, set
xU=xr, return to step 2 (see shaded interval in case 1 & 2)

Case 1 Case 2

New iteration: xU = xr

Chap5/12
•If f(xL)  f(xr) > 0, root lies in the upper interval, set
xL=xr, return to step 2 (see shaded interval in case 3 & 4)

Case 3 Case 4

New iteration: xL=xr

Chap5/13
•If f(xL)  f(xr) = 0, root equals to xr, terminate
computation (see case 5 & 6)

Root = xr
Case 5 Case 6

Chap5/14
 BISECTION METHOD –
STOPPING CRITERION
• When to stop the iteration if it is hard to get f(xL) f(xr) = 0 ?
• Apply the convergence (stopping) criterion as follows:
If error |a| < stopping error |s| , then root= xrnew

xrnew − xold
a = new
r
100   s
xr
only valid for
xU − xL
or  a = 100   Bisection method (p121)
xU + xL
s

where xrnew is the root for the current iteration,

xL + xU
x new
r
=
2
Chap5/15
 CLASS ACTIVITY

Q1. Use analytical method to determine the radius, r of a

cylindrical can so that it holds 400 cm3 of liquid. Given r =
h/3, where h is the height. ans: r = 3.49 cm

Q2. Now, use 3 iterations of the bisection method to

determine the radius of the can. Use initial guesses of rL=3
cm and rU=4 cm. Also, calculate the estimated error, a and
the true percent relative error, t after each iteration.

Chap5/16
 SOLUTION

BISECTION METHOD
Let
Iteration xL xU xr f(xL) f(xr) % ea % et
1 3 4 3.5 -145.53 4.09 0.29%
2 3 3.5 3.25 -145.53 -76.47 7.69% 6.88%
3 3.25 3.5 3.38 -76.47 -36.07 3.85% 3.15%
4 3.38 3.5 3.44 -36.07 -16.34 1.74% 1.43%
5 3.44 3.5 3.47 -16.34 -6.21 0.86% 0.57%
6 3.47 3.5 3.49 -6.21 0.63 0% 0%

Chap5/17
 You have previously learned that:

current appr. - previous appr.

a = 100%
current approx.
= approximate percent relative error (%)

for Bisection method:

Note: The above formula is valid except for the first

approximation

Chap5/18
function root =
Bisect_ID(func,xL,xu,es,maxit)
% Bisection Method
Sample M-file :
% func = name of function , output:
%root,xr = real root
Bisection
% xL, xu = lower and upper bound guesses
% es = (optional) stopping criterion (%) >>Bisect_ID(@(x) exp(-x)-x,
% maxit = (optional) maximum iterations 0,1,0.05,20)
%
iter = 0;
xrold = 0; OR
while (1)
xr = (xL + xu)/2;
>>Bisect(inline('exp(-x)-
iter = iter + 1;
x'),0,1,0.05,20)
if xr ~= 0, ea = abs((xr - xrold)/xr)* 100;
end
test = func(xL)*func(xr); ans =
if test < 0
0.5671
xu = xr;
elseif test > 0
xL = xr;
else ea = 0;
end Refer Fig.5.1 for pseudocode
if ea <= es | iter >= maxit, break, end
fprintf('\n%10.7f %10.7f',xr, ea);
xrold = xr;
end
root = xr;
CM/Chap 5/p19
 BISECTION METHOD
– PROS AND CONS

Pros Cons
• Easy and simple • Slow to converge

• Can always find a • Must know xL and xU that bound

single root the root
• Convergence is • Cannot detect multiple roots
guaranteed • No account is taken of the
magnitudes of f(xL) and f(xU). If
f(xL) is closer to zero, it is likely
that the root is closer to xL than to
xU use False-Position Method

Chap5/21
 FALSE-POSITION METHOD
• If f(xL) is closer to zero, it is likely
Upper bound
that the root xr is closer to xL
• The curve is replaced by a straight
line that crosses the x-axis & gives
‘false position’ at xr
• Based on similar triangle Lower bound
principle, we can approximate the
solution by using linear xu − xL x − xr
= u
interpolation between the lower & f ( xu ) − f ( xL ) f ( xu ) − 0
upper bounds to find the root, xr rearrange for xr :
f ( xu )( xL − xu )
xr = xu −
• Gives better estimate than f ( xL ) − f ( xu )
Bisection method
Chap5/22
FALSE-POSITION METHOD – ALGORITHM

STEP 1: Choose upper xU and lower xL guesses such that

f(xL)  f(xU) < 0

STEP 2 : Use similar triangle to interpolate the new estimate

f (xu )(xL − xu )
of the root Refer to Box 5.1
xr = xu −
f (xL ) − f (xu )
(p125)

STEP 3 : Evaluate the next sub-interval

• If f(xL)  f(xr) < 0, root lies in the lower interval, set xU=xr, return to step 2

• If f(xL)  f(xr) > 0, root lies in the upper interval, set xL=xr, return to step 2

• If f(xL)  f(xr) = 0, root equals to xr, terminate computation

Chap5/23
FALSE-POSITION METHOD – STOPPING
CRITERION
•Stopping criterion : Check for convergence criterion
whereby error, a < s . If not, go back to STEP 2.

xrnew − xrold
a = new
100 %   s
xr

Why this method ?

• converge faster than Bisection method
• always converges to a single root

Chap5/24
 CLASS ACTIVITY
Use 3 iterations of false-position method to find a root of
equation x3 + 4x2 – 10 =0. Employ initial guesses of xL=1
and xU=2. Calculate the approximate error, a and the true
error, t after each iteration. True value = 1.36523.

f (xu )(xL − xu )
xr = xu −
f (xL ) − f (xu )

Chap5/25
 SOLUTION

f (xu )(xL − xu )
xr = xu −
f(x) = x3 + 4x2 – 10 f (xL ) − f (xu )

i xL xU f(xL) f(xU) xr f(xr) ea et

1 1 2 –5 14 1.2631 –1.6022 – 7.48%

2 1.2632 2 –1.6023 14 1.3388 –0.4304 5.65% 1.93%

3 1.3389 2 –0.4304 14 1.3585 –0.1100 1.45% 0.49%

Chap5/26
function root = F_Pos(func,xL,xu,es,maxit)
% False-position Method
% func = name of function , output:
M-file : False-Position
% root,xr = real root
% xL, xu = lower and upper bound guesses
% es = (optional) stopping criterion (%)
% maxit = (optional) maximum iterations >>F_Pos(@(x) exp(-x)-x,
% 0,1,0.05,20)
iter = 0;
while (1)
??????
xr = (xL + xu)/2; ans =
iter = iter + 1; 0.5671
if xr ~= 0, ea = abs((xu -???????
xL)/(xu + xL))
* 100; end
test = func(xL)*func(xr);
if test < 0
xu = xr;
elseif test > 0 What will be the codes if
xL = xr; modified from Bisection?
else ea = 0;
end
if ea <= es | iter >= maxit, break, end
fprintf('\n%10.7f %10.7f',xr, ea);
end
root = xr

CM/Chap 5/p27
 SUMMARY (Chapter 5)

Bisection False-position
• Easy and simple • Faster than Bisection method
• Always converge to a • Always converge to a single
single root root
• Step 1: f(xL)f(xu) < 0 • Step 1: f(xL)f(xu) < 0
• Step 2: • Step 2:

xL + xU f (xu )(xL − xu )
xr = xr = xu −
f (xL ) − f (xu )
2
• Step 3: • Step 3:
If f (xL ) f (xr )  0, set xU = xr If f (xL ) f (xr )  0, set xU = xr

If f ( xL ) f ( xr )  0, set xL = xr If f ( xL ) f ( xr )  0, set xL = xr
 MDB3053 Numerical Methods

ROOTS OF EQUATIONS –
OPEN METHOD

Reading Assignment: Chapter 6 in Textbook

Chap5/29
 OPEN METHODS

To calculate roots of equation using y

roots
Open Methods:

1. Newton-Raphson Method x

2. Secant Method
3. Fixed-point Iteration - when a function is zero
- when a function crosses x-axis

Chap6/30
 OPEN METHODS : INTRODUCTION

•Open methods are based on

formulas that require only one
single or two starting value(s)
of x that do not need to
bracket the root.
•Not always work as
sometimes it can diverge,
depending on the initial guess
• When it converges, it
reaches solution much more
faster than Bracketing Bisection Open method
method.

Chap6/31
NEWTON-RAPHSON (NR) METHOD

•Also called as Newton’s method, it is a powerful and

MOST widely used method.
•Based on Taylor series expansion; truncate the series after
1st order derivative term:

f ( xi +1 ) = f ( xi ) + f ( xi )x + ... + Rn
The root is the value of xi +1 when f ( xi +1 ) = 0
Re arranging, solve for xi+1
 i )( xi +1 − xi )
0 = f(xi ) + f (x
f ( xi )
xi +1 = xi − Newton-Raphson formula
f ( xi )

Chap6/32
 NEWTON-RAPHSON METHOD

•Convenient method for functions

whose derivatives can be evaluated
analytically.
•Not suitable for functions whose
derivatives cannot be evaluated
analytically
Fig. 6.5
•It converges very fast as it is
“quadratically convergent” (see f ( xi )
xi +1 = xi −
book in Box 6.2, p141) f ( xi )

Pitfalls: can’t find multiple roots, may not

converge if guess is near zero slope !

Chap5/33
NEWTON-RAPHSON METHOD

Tangent of curve :
f ( xi ) − 0
f ( xi ) =
xi − xi +1
f ( xi )
 xi +1 = xi −
f ( xi )

Root is estimated by
extending a tangent at x1
down to x-axis

Chap5/34
 NR METHOD – ALGORITHM

STEP 1 : Assume initial value for xi = x0

STEP 2 : Calculate the value of xi+1 usingequation
f (xi )
xi +1 = xi − i = 0,1,2,3,…
f (xi )

STEP 3 : Calculate the approx. error |a|

xi +1 − xi
a =  100
xi +1

STEP 4 : Repeat STEP 2 until a < s pre-specified value,

then root = xi+1

Chap6/35
NR method – Poor Convergence Cases

Inflection point, f '' = 0

in the vicinity of a root

Oscillation of slopes

Guess is near zero slope

Zero slope is encountered

Chap6/36
 CLASS ACTIVITY

Determine the highest real root of f(x) = x3 – 6x2 + 11x – 6.1

using Newton-Raphson Method. Consider three iterations with
guess xo=3.5. Also calculate the estimated error, ea after each
iteration. Ans: 3.0473

f (xi ) xi +1 − xi
xi +1 = xi − a =  100
f (xi ) xi +1

Chap6/37
 SOLUTION

f ( x) = x 3 − 6 x 2 + 11x − 6.1
f ' ( x) = 3x 2 − 12 x + 11

f (xi )
xi +1 = xi −
f (xi )

i x(i+1) xi f(xi) f '(xi) a %

0 3.5 -

1 3.1913 3.5000 1.7750 5.7500 9.7

2 3.0687 3.1913 0.3994 3.2576 4.00

3 3.0473 3.0687 0.0519 2.4264 0.70

Chap6/38
function root = NR_ID(fx,dfunc, xr,es,maxit)
% N_R(func, dfunc, xr,es,maxit): M-file : Newton-
% uses NR method to find the root of function
% input:
% func, dfunc = name of function, derivative
Raphson
% xr = 1 initial guess
% es = (optional) stopping criterion (%)
% maxit = (optional) maximum iterations Go to command window
% output: root = real root
% if necessary, assign default values >>NR_ID(@(x) exp(-x)-x,
if nargin<5, maxit=50; end @(x)-exp(-x)-1,0, 0.05,20)
%if maxit blank set to 50
if nargin<4, es=0.001; end
%if es blank set to 0.001 OR
% NR method
iter = 0; >>NR_ID(inline('exp(-x)-
while (1)
xrold = xr;
x'),inline('-exp(-x)-1'),0,
xr = xr - fx(xr)/dfunc(xr); 0.05,20)
iter = iter + 1;
if xr ~= 0, ea = abs((xr - xrold)/xr) * 100;
end ans =
if ea <= es | iter >= maxit, break, end
end 0.5671
root = xr;
fprintf('The root is %6.4f',xr);

CM/Chap 5/p39
 SECANT METHOD

For functions whose derivatives are difficult to evaluate,

the derivatives f '(x) can be approximated by Backward
Finite-Divided Differencing scheme :

f ( xi ) − f ( xi −1 )
f ( xi ) 
xi − xi −1

f (xi )
Newton − Raphson : xi +1 = xi −
f (xi )

f ( xi )( xi − xi −1 )
Secant method : xi +1 = xi −
f ( xi ) − f ( xi −1 )

Chap5/40
 SECANT METHOD

Requires 2 initial guesses: xi and Definition: Secant is a

xi-1 that do not necessarily straight line that intercepts a
bracket the root. Hence, NOT a curve at 2 or more points
bracketing method !
Fig. 6.7
f ( xi )( xi −1 − xi )
xi +1 = xi −
f ( xi −1 ) − f ( xi )

Similar to False-position
method:
f (xu )(xL − xu )
xr = xu −
f (xL ) − f (xu ) 2 initial guesses of xi and xi-1

Chap5/41
SECANT METHOD

Chord / Secant

Secant method requires

TWO guesses: x1 andx2

Chap5/42
SECANT METHOD – ALGORITHM

STEP 1 : Assume 2 initial guesses for xi and xi-1 at i=0

STEP 2 : Calculate the value of xi+1 using
f ( xi )( xi −1 − xi )
xi +1 = xi − i = 0,1,2,3,…
f ( xi −1 ) − f ( xi )

STEP 3 : Calculate the error |a|

xi +1 − xi
a =  100
xi +1

STEP 4 : Repeat STEP 2 until a < pre-specified value, then

set root = xi+1

NOTE: Convergence is not guaranteed for all xo

Chap5/43
 CLASS ACTIVITY
Use three iterations to determine the root of f(x) = e−x – x by using
Secant Method with initial estimate of x-1=0 and x0=1.0. Also
calculate the estimated error, ea after each iteration.
Ans: 0.5672

f ( xi )( xi −1 − xi ) xi +1 − xi
xi +1 = xi − a =  100
f ( xi −1 ) − f ( xi ) xi +1

Chap6/44
 SOLUTION

f(x) = e−x – x f ( xi )( xi −1 − xi )
xi +1 = xi −
f ( xi −1 ) − f ( xi )
x-1=0 and x0=1.0

iter x(i+1) x(i) x(i-1) f(xi) f(i-1) a (%)

0 1 0

1 0.6127 1 0 -0.6321 1.0000 63.2

2 0.5638 0.6127 1 -0.0708 -0.6321 8.67

3 0.5672 0.5638 0.6127 0.0052 -0.0708 0.59

Chap6/45
 ???????
function root = Secant(func,dfunc xr,es,maxit)
% Secant(func, dfunc, xr,es,maxit):
??????? M-file : Secant
% uses secant method to find the root
% input name:
% func, = name of a function
% xrold, xr = 2 initial guesses
% es = (optional) stopping criterion (%) >>Secant(@(x) exp(-x)-x,. . )
% maxit = (optional) maximum iterations
% output: root = real root
% if necessary, assign default values
ans =
if nargin<5, maxit=50; end 0.5671
%if maxit blank set to 50
if nargin<4, es=0.001; end
%if es blank set to 0.001
% NR method
Try to modify the NR codes for
iter = 0;
while (1) Secant method.
xrold = xr;?????
???????
xr = xr - fx(xr)/dfunc(xr);
iter = iter + 1;
if xr ~= 0, ea = abs((xr - xrold)/xr) * 100;
end
if ea <= es | iter >= maxit, break, end
end
root = xr;
fprintf('The root is %6.4f',xr);

CM/Chap 5/p46
 FIXED-POINT ITERATION

• Rearrange the function so that x is on the left side of the

equation: x = g(x)
• For example: x2 − x − 2 = 0 can be manipulated to yield
x = x2 − 2
or x = (x + 2)1/2 To obtain x = g(x)
or x = (x + 2)/x
• From an initial estimate of xi, the next estimate, xi+1 can be
ITERATIVELY computed by the function of xi+1 = g(xi)
• The approximate percent error:
xi +1 − xi
a = 100 %
xi +1
Chap5/47
EXAMPLE

Chap5/48
 CLASS ACTIVITY

Use fixed-point iteration to find the root of x2 - 3x+2 = 0

Chap5/49
 SOLUTION

Function x = ( x2 + 2 ) / 3
i xi a %
1 0.0000
2 0.6667 100.00
3 0.8148 18.18
4 0.8880 8.24
5 0.9295 4.47
6 0.9547 2.64
7 0.9705 1.63
8 0.9806 1.03
9 0.9872 0.67

Chap5/50
 FIXED-POINT ITERATION –
CONVERGENCE
• x =g(x) can be expressed as a
pair of equations:
f1(x) = x and
f2(x) = g(x)

• Plot these two equations

separately  the intersection
of the two curves will be the
root !

• The method is slower to

converge because it is
linearly convergent Figure 6.2 Chap6/54

Chap5/51
 FIXED-POINT ITERATION –
CONVERGENCE
• Fixed-point methods may sometime “diverge”, depending
on the starting point (initial guess) and how the function
behaves (see Sec 6.1.1).

• It will converge if the absolute slope

g (x)  1  the absolute slope of y = g(x) is less

than the slope of y = x, see Fig 6.3 (p137)

• When the method converges, the error is roughly

proportional to the error of the previous step, therefore it
is called “linearly convergent.”

Chap6/52
 FIXED-POINT ITERATION –
CONVERGENCE CASeS
|g’(x)|<1 |g’(x)|<1
converge converge

|g’(x)|>1 |g’(x)|>1
diverge diverge

Chap6/53
BRACKETING VS OPEN METHOD

BRACKETING Method OPEN Method

• Bracketing methods • Open method might
can always converge to diverge or move away
a root. from the true root
depending on the initial
• Bracketing method is
guess (see pitfalls)
slow to converge
• When it converges, it
reaches results faster
than the bracketing
methods.

Chap6/54
 ROOTS OF EQUATION
➢Bracketing Methods – Bisection, False-position
➢Open Methods – NR, Secant, Fixed-Point Iteration

✓ We have covered Chapter 5 and 6 in textbook.

Chap6/55