Lecture (3)

Numerical Analysis
CC413

Dr. Mourad samir

 Outline
2

Roots of equations
3. Bisection method
4. False position method
 Roots of equations
3

Given continuous function 𝑓(𝑥) and required the

value of 𝑥 such that:
𝑓 𝑥 =0

f(x)
Graphical, the root of equation Root
𝑓(𝑥)=0 is intersection point between
𝑓(𝑥) and 𝑥 − 𝑎𝑥𝑖𝑠 as shown in figure
x
 Roots of equations
4

𝐸𝑋: 𝑥2 + 1 = 0

From figure, the equation has no root x

𝑥2 + 1 = 0 𝑥 2 = −1 no solution

x
𝐸𝑥: 𝑥 2 − 1 = 0 -1 +1
𝑥 2 = 1 ⟹ 𝑥 = ±1
From figure, two roots of equation
Roots of equations
5
In Figure a) we have the case of f(xl)
and f(xu) with the same sign, and there
is no root in the interval (xl,xu).
In Figure b) we have the case of f(xl)
and f(xu) With different sign, and there
is a root in the interval (xl,xu).

In Figure c) we have the case of f(xl)

and f(xu) with the same sign, and there
are two roots.
In Figure d) we have the case of f(xl)
and f(xu) with different sign, and there
is an odd number of roots.
 Roots of equations
6

 Let f(x) be defined on the

interval [𝑥𝑙 ,𝑥𝑢 ]. f(𝑥𝑢 )

 Intermediate value theorem:

if a function is continuous
and f(𝑥𝑙 ) and f(𝑥𝑢 ) have 𝑥𝑙 𝑥𝑢
different signs then the
function has at least one zero
in the interval [𝑥𝑙 ,𝑥𝑢 ].
f(𝑥𝑙 )
 Roots of equations
7

If 𝑓 𝑥 = 4 sin 𝑥 − 𝑒 𝑥 , show that f(x) has a root in [0,1]

Solution
𝑥𝑙 = 0 𝑓 𝑥𝑙 = 4 sin 𝑥𝑙 − 𝑒 𝑥𝑙 = 4 sin 0 − 𝑒 0 = −1

𝑥𝑢 = 1 𝑓 𝑥𝑢 = 4 sin 𝑥𝑢 − 𝑒 𝑥𝑢 = 4 sin 1 − 𝑒 1 = +0.647

𝑓 𝑥 has root in the interval [0,1], because

𝑓 𝑥𝑙 and 𝑓 𝑥𝑢 are different signs

or
𝑓 𝑥𝑙 𝑓 𝑥𝑢 = −1 ∗ 0.647 = −0.647 = −ve value
 Roots of equations
8

Given: 𝑓(𝑥) = 0
Required: The root of 𝑓(𝑥) in the interval [𝑥𝑙 , 𝑥𝑢 ]
Solution
We can be solve this problem by using one of
𝑥𝑙 𝑥𝑢
 Bisection method
 False position method
 Secant method
Bisection method

Slide 9
 Bisection method
10

Step 1
Estimate the root, 𝑥𝑟 of the equation f (x) = 0 as the mid
point between xl and xu as
f(x)
xu  x l f(𝑥𝑢 )
xr 
2 𝑥𝑙 𝑥𝑟
𝑥𝑢 x

f(𝑥𝑙 )
 Bisection method
11

Step 2
Find the value of 𝑓(𝑥𝑟 ) and select the new interval [𝑥𝑙 , 𝑥𝑟 ]
Or [𝑥𝑟 , 𝑥𝑢 ] such that satisfy Intermediate value theorem
f(x)
f(𝑥𝑢 )

𝑥𝑙 𝑥𝑟
𝑥𝑢 x
f(𝑥𝑟 )
f(𝑥𝑙 )
From figure the new interval is [𝑥𝑟 , 𝑥𝑢 ]
 Bisection method
12

Step 3
Find the absolute relative approximate error
x rnew  x rold
a  new
 100
x r
where
x rold  previous estimate of root
x rnew  current estimate of root
 Bisection method
13

Step 4
Compare the absolute relative approximate error a with
the pre-specified error tolerance s (Required accuracy) .
Go to Step 1 using new
Yes upper and lower
Is a s ? guesses.

No Stop the algorithm

 Bisection method
14

If 𝑓 𝑥 = 4 sin 𝑥 − 𝑒 𝑥 , has a unique solution in [0,1]

Find the root of the equation 𝑓(𝑥) = 0 with 𝜀𝑠 = 5%
Solution
𝑥𝑙 = 0 𝑓 𝑥𝑙 = 4 sin 𝑥𝑙 − 𝑒 𝑥𝑙 = 4 sin 0 − 𝑒 0 = −1
𝑥𝑢 = 1 𝑓 𝑥𝑢 = 4 sin 𝑥𝑢 − 𝑒 𝑥𝑢 = 4 sin 1 − 𝑒 1 = 0.647

𝑓 𝑥 has root in the interval [0,1], because

𝑓 𝑥𝑙 and 𝑓 𝑥𝑢 are different signs or

𝑓 𝑥𝑙 𝑓 𝑥𝑢 = −1 ∗ 0.647 = −0.647 = −ve value

 𝑥𝑙 + 𝑥𝑢
𝑥 𝑥𝑟 = 𝜀𝑠 = 5%
𝑓 𝑥 = 4 sin 𝑥 − 𝑒 2
15

𝑥𝑙 𝑥𝑢 𝑥𝑟 f(𝑥𝑟 ) 𝜺𝒂
𝑓 𝑥𝑙 = −𝑣𝑒 𝑓 𝑥𝑢 = +𝑣𝑒

1 0 1 0.5 +ve
2 0 0.5 0.25 -ve 100%
3 0.25 0.5 +ve 33.33%
0.375
4 0.25 0.375 0.3125 -ve 20%
5 0.3125 0.375 0.34375 +ve 9.09%
6 0.3125 0.34375 0.32812 4.7%
 Bisection method
16

Thus, after the six iterations, the approximate error

falls below 5% and the computation is terminated.
The root is 𝑥 = 𝑥𝑟 =0.32812

Check: 4 sin 𝑥 − 𝑒 𝑥 = 0

4 sin 𝑥𝑟 − 𝑒 𝑥𝑟 = −0.09
 Bisection method
17

Example
Solve using the bisection method the equation
667.38
x
 
1  e0.146843 x  40  0

Using the interval xl  12 xu  16

and iterative until  a  0.5%

Solution
 Bisection method
18

f  x 
667.38
x
 
1  e0.146843 x  40  0

1 xl  12  f  xl   6.067
xu  16  f  xu   2.269

𝑓 𝑥 has a root in the interval [12,16], because

𝑓 𝑥𝑙 and 𝑓 𝑥𝑢 are different signs or

𝑓 𝑥𝑙 𝑓 𝑥𝑢 = −6.067 ∗ 2.269 = −ve value

 𝑥𝑙 + 𝑥𝑢
f  x 
667.38
x
 
1  e0.146843 x  40  0 𝑥𝑟 =
2
𝜀𝑠 = 0.5%
19

𝑥𝑙 𝑥𝑢 𝑥𝑟 f(𝑥𝑟 ) 𝜺𝒂
𝑓 𝑥𝑙 = +𝑣𝑒 𝑓 𝑥𝑢 = −𝑣𝑒

1 12 16 14 +ve
2 14 16 15 -ve 6.66%
3 14 15 14.5 +ve 3.448%
4 14.5 15 14.75 +ve 1.695%
5 14.75 15 14.875 -ve 0.84%
6 14.75 14.875 14.8125 0.422%
 Bisection method
20

Thus, after six iterations, the approximate error falls

below 0.5% and the computation is terminated.
The root is 𝑥 = 𝑥𝑟 = 14.8125
 Bisection method
21

One important advantage of this method is that one can

calculate the maximum number of required iterations for a
given error 𝜀.
𝐥𝐧 𝒙𝒖 −𝒙𝒍 −𝐥𝐧(𝜺)
N>
𝐥𝐧 𝟐
where
𝑁: maximum number of required iterations
𝜺: the required accuracy
If required the result is correct to at least n decimal places,
then:
𝜺 = 𝟎. 𝟓 × 𝟏𝟎−𝒏
 Bisection method
22

If 𝑓 𝑥 = 4 sin 𝑥 − 𝑒 𝑥 = 0, has a unique solution in [0,1]

Find
The maximum number of iterations necessary to obtain
solution of 𝑓(𝑥) = 0 correct to 4 decimal places

Solution
𝐥𝐧 𝒙𝒖 − 𝒙𝒍 − 𝐥𝐧(𝜺) 𝒙𝒖 = 𝟏
𝑵>
𝐥𝐧 𝟐 𝒙𝒍 = 𝟎 4
𝐥𝐧 𝟏−𝟎 −𝐥𝐧(𝟎.𝟎𝟎𝟎𝟓)
N> 𝜺 = 𝟎. 𝟓 × 𝟏𝟎−𝒏
𝐥𝐧 𝟐

N> 𝟏𝟒. 𝟐𝟖 N= 𝟏𝟓 𝒊𝒕𝒆𝒓𝒂𝒕𝒊𝒐𝒏𝒔 𝜺 =0.00005

 Bisection method
23

+ + -

+ - -

+ + -
 Define xL, and xu

Flow chart Bisection method No f(xL)f(xu) <

0

Yes

𝑥𝑙 + 𝑥𝑢
𝑥𝑟 = Calculate xr
2
Yes
No
f(xL)f(xr) < 0

xL = xr xu = xr

No 𝜖𝑎 <
ϵs
Yes

End 24
False position method

Slide 25
False position method
26

Step 1
Estimate the root, 𝑥𝑟 of the equation f (x) = 0 by

f(x)
𝑓(𝑥𝑢 )(𝑥𝑙 − 𝑥𝑢 )
𝑥𝑟 = 𝑥𝑢 − f(𝑥𝑢 )
𝑓 𝑥𝑙 − 𝑓(𝑥𝑢 )
𝑥𝑙 𝑥𝑟
𝑥𝑢 x

f(𝑥𝑙 )
 False position method 27

Step 2
Find the value of 𝑓(𝑥𝑟 ) and select the new interval [𝑥𝑙 , 𝑥𝑟 ]
Or [𝑥𝑟 , 𝑥𝑢 ] such that satisfy Intermediate value theorem
f(x)
f(𝑥𝑢 )

𝑥𝑙 𝑥𝑟
𝑥𝑢 x
f(𝑥𝑟 )
f(𝑥𝑙 )
From figure the new interval is [𝑥𝑟 , 𝑥𝑢 ]
False position method
28

Step 3
Find the absolute relative approximate error
x rnew  x rold
a  new
 100
x r
where
x rold  previous estimate of root
x rnew  current estimate of root
False position method 29

Step 4
Compare the absolute relative approximate error a with
the pre-specified error tolerance s (Required accuracy) .
Go to Step 1 using new
Yes upper and lower
Is a s ? guesses.

No Stop the algorithm

False position method
30
 False position method
31
The equation of the straight line joining x l , f  x l   and
 x u , f  x u  is
f x u   y 
f x u   f x l 
xu  x xu x l

For the intersection with x-axis  y  0 and x  xr

f x u  
f x u   f x l 
xu  x r xu  x l
 False position method
32
Use false position method to find the root of the equation
𝑥𝑒 𝑥 − 3 = 0 in the interval [1,1.5] with 𝜀𝑠 = 0.09%
Solution
𝑥𝑙 = 1 𝑓 𝑥𝑙 = 𝑥𝑙 𝑒 𝑥𝑙 − 3 = 𝑒 1 − 3 = −0.28171
𝑥𝑢 = 1.5 𝑓 𝑥𝑢 = 𝑥𝑢 𝑒 𝑥𝑢 − 3 = 1.5𝑒 1.5 − 3 = 3.72253
𝑓 𝑥 has a root in the interval [1,1.5], because
𝑓 𝑥𝑙 and 𝑓 𝑥𝑢 are different signs
𝑓(𝑥𝑢 )(𝑥𝑙 − 𝑥𝑢 )
𝑥𝑟 = 𝑥𝑢 −
𝑓 𝑥𝑙 − 𝑓(𝑥𝑢 )
3.72253 1 − 1.5
𝑥𝑟 = 1.5 − = 1.03518
−0.28171 − 3.72253
 𝑓(𝑥𝑢 )(𝑥𝑙 − 𝑥𝑢 )
𝑓 𝑥 = 𝑥𝑒 𝑥 −3 𝑥𝑟 = 𝑥𝑢 − 𝜀𝑠 = 0.09%
𝑓 𝑥𝑙 − 𝑓(𝑥𝑢 )
33

𝑥𝑙 𝑥𝑢 𝑥𝑟 f(𝑥𝑟 ) 𝜺𝒂
𝑓 𝑥𝑙 = −𝑣𝑒 𝑓 𝑥𝑢 = +𝑣𝑒

1 1 1.5 1.03518 −0.08637

2 1.03518 1.5 1.04572 -0.02446 1.0079%
3 1.04572 1.5 0.28%
1.04869 -0.00713
4 1.04869 1.5 1.04955 0.082%
Thus, after four iterations, the approximate error falls
below 0.09% and the computation is terminated.
The root is 𝑥 = 𝑥𝑟 = 1.04955
 Example
34

Solve using the false position method the equation

667.38
x
 
1  e0.146843 x  40  0

xl  12 xu  16

 a  0.5%
Solution
 False position method
667.38 35 0.146843 x
f  x 
x

1 e  40  0
1 xl  12  f  xl   6.0669

x u  16  f  x u   2.2688

𝑓(𝑥𝑢 )(𝑥𝑙 − 𝑥𝑢 )
𝑥𝑟 = 𝑥𝑢 −
𝑓 𝑥𝑙 − 𝑓(𝑥𝑢 )
−2.2688 12 − 16
𝑥𝑟 = 16 − = 14.9113
6.0669 − −2.2688
 𝑓(𝑥𝑢 )(𝑥𝑙 − 𝑥𝑢 )
f  x 
667.38
x
1 e 
0.146843 x
 40  0 𝑥𝑟 = 𝑥𝑢 − 𝑓 𝑥 − 𝑓(𝑥 )
36
𝑙 𝑢

Iteration xl xu xr f  xr  a %
1 12 16 14.9113 -0.2543
2 12 14.9113 14.7942 -0.0273 0.79%
3 12 14.7942 14.7817 0.08%

It is clear that the error for false position decreases much

faster than for bisection method because of the more
efficient scheme for root location in the false position
method
 Try to solve
37

1- For 𝑥 10 − 1 = 0, apply the bisection method to obtain a

solution in [0,1.3] and with stopping criterion 𝜀𝑠 = 5%

2- For 𝑥 3 − 2𝑥 − 5 = 0, apply the false position method

to obtain a solution in [2,3] and with stopping criterion 𝜀𝑠
= 0.2%
 Tutorial problems
38

1. Show that the equation (𝑥 − 2)2 − ln 𝑥 = 0 has a root in the

interval [2.5, 3.5], and then use the (a) false position method and (b)
bisection method to find this root with 𝜀𝑠 = 1 % .
2. Use the false position method to find a root of the following Kepler's
Equation of Elliptical Motion: 𝑥 − 𝑎 𝑠𝑖𝑛𝑥 − 𝑏 = 0 which can be used
to describe the motion of planets around the Sun, given that 𝑎 = 0.5, 𝑏
= 1 with the interval [1,2]and. 𝜀𝑠 = 0.2%.
3. Use bisection method to find the root of the equation 𝑒 𝑥 + 𝑥 − 10
= 0 in the interval [2,3] with 𝜀𝑠 = 5%
4 Show that the equation 2𝑥 − 𝑒 −𝑥 = 0 has a root in the interval [0,
1.6], and then use the (a) false position method and (b) bisection
method to find this root with 𝜀𝑠 = 3 % .
 Tutorial problems
39
5- Find the maximum number of iterations necessary to obtain
solution of 𝑓(𝑥) = 0 correct to 4 decimal places by bisection method
and the interval [0,1]

6- Find the maximum number of iterations necessary to obtain solution

of 𝑓(𝑥) = 0 so that the accuracy 𝜀𝑠 = 0.00001% by bisection method
and the interval [0,1]
 Try to solve
40

1- Solve the equation 𝑥 3 − 20𝑥 + 5 − 4𝑒 𝑥 = 0using fixed

point iteration method with initial guess x0 = 0 and
stopping criterion 𝜀𝑠 = 5%
2- Use Newton-Raphson method to find the root of the
equation 𝑥 3 − 9𝑥 2 + 3.8197 = 0 start with initial guess
x0 = 1 and stopping criterion 𝜀𝑠 = 0.5%
 Try to solve
41

1. Solve the equation 𝑥 3 − 20𝑥 + 5 − 4𝑒 𝑥 = 0 using fixed

point iteration method with initial guess x0 = 0 and
stopping criterion 𝜀𝑠 = 5%
Solution
Fixed point iteration method: 1
𝑔′ 𝑥 = (3𝑥 2 − 4𝑒 𝑥 )
1 3 0
20
𝑥= (𝑥 + 5 − 4𝑒 𝑥 )
20 1 −1
′
𝑔 (0) = 0
−4𝑒 =
1 3
𝑔 𝑥 = (𝑥 + 5 − 4𝑒 ) 𝑥 20 5
20 ′
1
1 𝑔 (0) = < 1
𝑔′ 𝑥 = (3𝑥 2 − 4𝑒 𝑥 ) 5
20 The form is convergent
 42

1 3
𝑥𝑖+1 = (𝑥𝑖 + 5 − 4𝑒 𝑥𝑖 )
20 x0 = 0
𝒊 𝒙𝒊 𝜺𝒂
0 0.05 100%
1 0.03975 25.78%
2 0.04189 5.10%
3 0.04145 1.061% < 𝜀𝑠 = 5%

The root is 𝑥 = 𝑥4 = 0.04145

 Try to solve
43

2- Use Newton-Raphson method to find the root of the

equation 𝑥 3 − 9𝑥 2 + 3.8197 = 0 start with initial guess
x0 = 1 and stopping criterion 𝜀𝑠 = 0.5%
Solution
f  xi 
Newton-Raphson method xi 1  xi 
f   xi 
𝑓 𝑥 = 𝑥3 − 9𝑥 2 + 3.8197
𝑓′ 𝑥 = 3𝑥 2 − 18𝑥
3 2
𝑓 𝑥𝑖 = 𝑥𝑖 − 9𝑥𝑖 + 3.8197
2
𝑓′ 𝑥𝑖 = 3𝑥𝑖 − 18𝑥𝑖
 Try to solve
44
3 2
𝑥𝑖 − 9𝑥𝑖 + 3.8197
𝑥𝑖+1 = 𝑥𝑖 − 2 x0 = 1
3𝑥𝑖 − 18𝑥𝑖

𝒊 𝒙𝒊 𝜺𝒂
0 0.72131 38.6%
1 0.67862 6.29%
2 0.67747 0.1708% < 𝜀𝑠 = 0.5%

The root is 𝑥 = 𝑥3 = 0.67747