NUMERICAL METHODS

Bracketing Methods
Department of Chemical Engineering
Faculty of Industrial Technology
Parahyangan Catholic University
February 2024
1

ROOTS OF EQUATIONS

Bisection method
Bracketing Methods
False Position Method

Roots of Simple fixed point iteration

Equations
Open Methods Newton Raphson

System of Nonlinear
Secant
Equations

1
 ROOTS OF EQUATIONS

Objective:
Solve for x, given that f(x) = 0
-or-
Equivalently, solve for x such that

g(x) = h(x) ==> f(x) = g(x) – h(x) = 0

ROOTS OF EQUATIONS

 b  b 2  4ac
ax  bx  c  0 
2
x
2a

ax 5  bx 4  cx 3  dx 2  ex  f  0  x  ?
sin x  x  0  x  ?
xe  x  1  0

2
 ROOTS OF EQUATIONS

Van der Waals equation; v = V/n (= volume/# moles)

) Find the molar volume v such that

a
f(v) = ( p + )(v - b) - RT = 0
v2

p = pressure,
T = temperature,
R = universal gas constant,
a & b = empirical constants

ROOTS OF EQUATIONS
Nonlinear Colebrook equation

The friction factor f for turbulent flow of an incompressible

fluid in a pipe.

3
 ROOTS OF EQUATIONS

• Non-computer methods:
- Closed form solution (not always available)
- Graphical solution (inaccurate)

• Numerical systematic methods suitable for

computers

Graphical Solution

• Plot the function f(x)

f(x)

roots

x
f(x)=0 f(x)=0

• The roots exist where f(x) crosses the x-axis.

4
 Graphical Solution: Example
c
K  t
• Given the equation : v  (1  e 68.1 )
c
• Calculate c to have v = 40 if K=667.38 and t = 10

f(c)
c
K  t
f (c)  (1  e m )  v
c
667.38
f (c )  (1  e 0.146843c )  40
c c
c=14.75 Check: F (14.75) = 0.059 ~ 0.0
v (c=14.75) = 40.06 ~ 40
9

Numerical Methods
I. Bracketing Methods
By Mean Value Theorem,
we know that if a function f(x) is
continuous in the interval [a, b]
and f(a)f(b) < 0, then the
equation f(x) = 0 has at least one
real root in the interval (a, b).

10

10

5
 Usually
• f(a)f(b) > 0 implies zero or
even number of roots
– [figure (a) and (c)]

• f(a)f(b) < 0 implies odd

number of roots
– [figure (b) and (d)]

Second Term 05/06 11

11

Exceptional Cases
• Multiple roots
– Roots that overlap at one
point.
– e.g.: f(x) = (x-1)(x-1)(x-2) has
a multiple root at x=1.

• Functions that discontinue

within the interval

Second Term 05/06 12

12

6
 Bracketing Methods (cont.)

• Two initial guesses (xl and xu) are required for the
root which bracket the root (s).
• If one root of a real and continuous function, f(x)=0,
is bounded by values xl , xu then f(xl).f(xu) <0.
(The function changes sign on opposite sides of the root)

13

Bracketing Methods
1. Bisection Method

• Generally, if f(x) is real and continuous in the interval xl to xu

and f (xl).f(xu)<0, then there is at least one real root between

xl and xu to this function.

• The interval at which the function changes sign is located.

Then the interval is divided in half with the root lies in the
midpoint of the subinterval. This process is repeated to
obtained refined estimates.

14

7
 f(x)
Step 1: Choose lower xl and upper xu xr = ( xl + xu )/2
guesses for the root such that:
f(xu)
f(xl).f(xu)<0
Step 2: The root estimate is:
xr = ( xl + xu )/2 xl xr1 xu
x

f(xr1) f(xu)
Step 3: Subdivide the interval according to:
– If (f(xl).f(xr)<0) the root lies in the f(x)
(f(xl).f(xr)<0): xu = xr
lower subinterval; xu = xr and go to xr = ( xl + xu )/2
step 2.
f(xu)
– If (f(xl).f(xr)>0) the root lies in the
upper subinterval; xl = xr and go to f(xr2)
step 2. xl xu
x
– If (f(xl).f(xr)=0) the root is xr and stop xr2
f(xu)

15

Implementation Issues

• The condition f(xl)f(xr) = 0 (in step 3) is difficult to

achieve due to errors.

• We should repeat until xr is close enough to the root,

but we don't know what the root is!

• Therefore, we have to define error criteria !

16

16

8
 Bisection Method - Termination Criteria

True relative Error :

X true  X approximate
et   100%
X true

• For the Bisection Method ea > et

• Practically, ea is commonly used.
• The computation is terminated when ea
becomes less than a certain criterion (ea < es)

17

Bisection method: Example

c
K  t
• Consider again : v  (1  e 68.1 )
c
• Calculate c to have v = 40 if K=667.38 and t = 10

(True root: α=14.7802)

f(c)
c
K  t
f (c)  (1  e 68.1 )  v
c
667.38
f (c )  (1  e 0.146843c )  40
c
c

18

9
 f(x)
1. Assume xl =12 and xu=16
f(xl)=6.067 and f(xu)=-2.269
6.067

2. The root: xr=(xl+xu)/2= 14

1.569
3. Check f(12).f(14) = 6.067•1.569=9.517 >0;
x
the root lies between 14 and 16. 12 14 16
-2.269

4. Set xl = 14 and xu=16, thus the new root

f(x)
xr=(14+ 16)/2= 15 (f(12).f(14)>0): xl = 14

5. Check f(14).f(15) = 1.569•-0.425= -0.666 <0;

the root lies bet. 14 and 15.

1.569
6. Set xl = 14 and xu=15, thus the new root 15
x
xr=(14+ 15)/2= 14.5 14 16
-0.425 -2.269
and so on…...
19

Bisection method: Example

In the previous example, if the stopping criterion is e =
0.5%; what is the root?

Iter Xl Xu Xr f(Xl) f(Xu) f(Xr) εt εa

1 12 16 14 6,06695 -2,2688 1,56871 5,27868

2 14 16 15 1,56871 -2,2688 -0,4248 1,48712 6,6667

3 14 15 14,5 1,56871 -0,4248 0,55233 1,89578 3,4483

4 14,5 15 14,75 0,55233 -0,4248 0,05896 0,20433 1,6949

5 14,75 15 14,875 0,05896 -0,4248 -0,1841 0,6414 0,8403

6 14,75 14,875 14,8125 0,05896 -0,1841 -0,0629 0,21854 0,4219

20

10
 Bisection method: Example

εa

εt

21

21

Bisection method

22

11
 Comments on Bisection Method
• The method is simple and guaranteed to
converge.
• However, the convergence is slow as we gain
only one binary digit in accuracy in each
iteration.
• Requires two good initial estimates which define
an interval around root:
 use graph of function,
 incremental search, or
 trial & error 23

23

Bracketing Methods
2. False-position Method
• The bisection method divides the interval xl to xu in
half not accounting for the magnitudes of f(xl) and
f(xu). For example if f(xl) is closer to zero than f(xu),
then it is more likely that the root will be closer to
f(xl).
• False position method is an alternative approach
where f(xl) and f(xu) are joined by a straight line; the
intersection of which with the x-axis represents and
improved estimate of the root.

24

12
 2. False-position Method

• False position method is an

alternative approach where
f(xl) and f(xu) are joined by
a straight line; the
intersection of which with
the x-axis represents and
improved estimate of the
root.

25

False-position Method -Procedure

f(x)

f(xu)

xl xr xu
x
f(xl) f(xr)

f ( x )  f ( xu ) x  xu

f ( xl )  f ( xu ) xl  xu
Define : f ( xr )  0, so
f ( xu )( xl  xu )
xr  xu 
f ( xl )  f ( xu )

26

13
 False-position Method -Procedure
Step 1: Choose lower xl and upper xu guesses for the
root such that: f(xl).f(xu)<0
Step 2: The root estimate is:
f ( xu )( xl  xu )
xr  xu 
f ( xl )  f ( xu )
Step 3: Subdivide the interval according to:
– If (f(xl).f(xr)<0) the root lies in the lower
subinterval; xu = xr and go to step 2.
– If (f(xl).f(xr)>0) the root lies in the upper
subinterval; xl = xr and go to step 2.
– If (f(xl).f(xr)=0) the root is xr and stop

27

False Position method: Example

c
K  t
• Consider again : v  (1  e 68.1 )
c
• Calculate c to have v = 40 if K=667.38 and t = 10

f(c)
c
K  t
f (c)  (1  e 68.1 )  v
c
667.38
f (c )  (1  e 0.146843c )  40
c
c

28

14
 False position method: Example f(x)
1. Assume xl = 12 and xu=16
6.067
f(xl)= 6.067 and f(xu)= -2.269

2. The root: xr=14.9113 14.91

x
12 16
f(12) . f(14.9113) = -1.5426 < 0;
-2.269

3. The root lies bet. 12 and 14.9113.

4. Assume xl = 12 and xu=14.9113, f(xl)=6.067 and
f(xu)=-0.2543
5. The new root xr= 14.7942
6. This has an approximate error of 0.79%

29

False position method: Example

In the previous example, if the stopping criterion is e =
0.5%; what is the root?

Iter. Xl Xu Xr f(Xl) f(Xu) f(Xr) εa (%)

1 12 16 14.9113 6.0669 -2.2688 -0.2543

2 12 14.9113 14.7942 6.0669 -0.2543 -0.0273 0.791600841

3 12 14.7942 14.7817 6.0669 -0.0273 -0.0029 0.084539415

4 12 14.7817 14.7804 6.0669 -0.0029 -0.0003 0.009017166

5 12 14.7804 14.7802 6.0669 -0.0004 -4E-05 0.000937706

6 12 14.7802 14.7802 6.0669 1.7E-05 2E-06 0.000144261

30

15
 False position method: Example

31

31

Comparison between two methods : Example

32

16
 False-position vs Bisection
• False position in general performs better than
bisection method.
• Exceptional Cases:
– (Usually) When the deviation of f'(x) is high and
the end points of the interval are selected poorly.
– For example,

f ( x )  x10  1
with xl  0, xu  1.3
33

33

False Position Method - Example 2

34

17
 Bisection Method (Converge quicker)
Iteration xl xu xr εa (%) εt (%)
1 0 1.3 0.65 35
2 0.65 1.3 0.975 33.3 25
3 0.975 1.3 1.1375 14.3 13.8
4 0.975 1.1375 1.05625 7.7 5.6
5 0.975 1.05625 1.015625 4.0 1.6

False-position Method
Iteration xl xu xr εa (%) εt (%)
1 0 1.3 0.09430 90.6
2 0.09430 1.3 0.18176 48.1 81.8
3 0.18176 1.3 0.26287 30.9 73.7
4 0.26287 1.3 0.33811 22.3 66.2
5 0.33811 1.3 0.40788 17.1 59.2
35

35

Summary of False-Position Method:

Advantages:
1. Simple
2. Brackets the Root

Disadvantages:
1. Can be VERY slow
2. Like Bisection, need an initial interval
around the root.

36

18
 Summary
• Bracketing Methods
– f(x) has the be continuous in the interval [xl, xu] and
f(xl)f(xu) < 0
– Always converge
– Usually slower than open methods

• Bisection Method
– Slow but guarantee the best worst-case convergent rate.

• False-position method
– In general performs better than bisection method (with
some exceptions).

37

37

Exercises

1. Find the root of:

f ( x)  x 3  3 x  1 in the interval : [0,1]

Please use : a) Bisection method
b) Regula Falsi Method
Perform iterations until the relative error
less than 0,1%

38

38

19
 Exercises

39

Exercises

40

20