Numerical analysis

CIVL 3309 + CVL 3308

Lecture Ch5.1+5.2+5.3
Discussion

University of Palestine
Dr. Suhail Lubbad
 Problem solving
and
Discussion
On

Bisection, False-position methods

 Strategy dealing with Bisection

Start within a specified interval [ Xl Xu] where the root is expected

1- To be sure that the root lies in the above interval, make the
following sign change test:
f / X l 0 f /X u 0,0

2- Find the first approximated (estimated) root by interval halving:

X l +X u
X r1=
2
3- Calculate the true error if you already have the true value of the
Root by the formula :

Et =∣ /True root value0−/Estimated root value0

True root value ∣
×100 %

4- Calculate the estimate, approximate, error, except in the first

iteration, by the following formula:

∣
Et =
The recent estimated root value ∣
/The recent estimated root value0−/The second recent estimated root value0
×100 %
5- Find the subinterval where the new estimate root value lies by
interval halving using the following test sign change formula :

?
f /x r 0 f /x l 0, 0

a- If this formula is satisfied, then the new interval we look for the
root in is [X l X r ]

b- If the condition is not satisfied, check whether

?
f /xr 0 f / x u 0, 0

Then the interval we will use is [ Xr Xu]

? ?
c- Other cases, if f /x r 0 f / xl 0= 0 or f / xr 0 f /x u 0= 0, X r is the root
Repeat all the steps 2,3,4 and 5 described earlier on the new
subinterval

Keep Iterating till you reach the desired error

 Strategy dealing with False-position

The same strategy as in bisection except the formula in step 2

The first approximated (estimated) root by:

f / X 0/ X −X 0
X =X − u l u
r u
f / X 0−f /X 0
l u

Continue as in Bisection method iteration procedure

 Discussion

CHAPTER 5
2
Question 5.1 Determine the roots of f /x0=−0.6x +2.4x+5.5 :
(a) Graphically
(b) Using the Quadratic formula
(c) Using three iterations if the bisection method to determine
the higest root. Employ the initial guesses of x =5 and x =10.
i u

Compute the estimated error 3 and the true error 3 after each
a t

iteration.
(a) Graphical solution
(b) the root is computed as

−b± . b −4ac −2.4± . /2.40 −4×/−0.60×5.5

2 2

x= x=
2a 2×/−0.60
x =−1.6286
-
x =5.6286
+
Iteration 1 Iteration 3
/ x l + x u 0 /5.000000+6.2500000
xr = = 2
=5.6250002

/ x + x 0 /5.000000+10.0000000 3
2 2
x r1 = l u = =7.500000
2 2

Test=F / x l 0×F / x r 0=2.500000×−10.250000,0

0 1
Ea = 3
∣
/ x r − xr 0
xr
3
× 100=
3
2

∣
The new subinterval enclosing the root is
[ x l , x u ]=[ 5.000000 , 7.500000 ]
1 1
∣
5.625000−6.250000
5.625000
×100=11.111111 ∣
Test : F / x l 0×F / x r 0=2.500000×0.015625-0
2 3

The new subinterval enclosing the root is

[ x l , x u ]=[ 5.625000 , 6.250000 ]
3 3

Iteration 4
Iteration 2 / x l + x u 0 /5.625000+6.2500000
/ x l + x u 0 /5.000000+7.5000000 xr = = 3
=5.9375003

xr = = 1
=6.250000
1 24
2
2
2 2

Ea = 2
∣
/ x r −x r 0
xr
× 100= 2

2
1

∣ Ea = 4
∣
/ x r −x r 0
xr
4
×100=
4
3

∣
∣
6.250000−7.500000
6.250000
×100=20.000000 ∣ ∣
5.937500−5.625000
5.937500
×100=5.263158 ∣
Test : F / x l 0×F / x r 0=2.500000×−2.937500,0
1 2 Test : F / x l 0×F / x r 0=0.015625×−1.402344,0
3 4

The new subinterval enclosing the root is The new subinterval enclosing the root is
[ x l , x u ]= [ 5.000000 , 6.250000 ]
2 2
[ x l , x u ]= [ 5.625000 , 5.937500 ]
4 4
 Iteration 7
Iteration 5
/ x l + x u 0 /5.625000+5.7031250
/ x l + x u 0 /5.625000+5.9375000 xr = = 6 6
=5.664062
xr = = 4 4
=5.781250 7
2 2
5
2 2

Ea = 5
∣
/ x r −x r 0
xr
×100= 5 4

∣ Ea = 7
∣
/ x r − xr 0
xr
7
×100=
7
6

∣
∣ ∣
5

5.664062−5.703125
∣
5.781250−5.937500
5.781250
×100=2.702703 ∣ 5.664062
×100=0.689655

Test : F / x l 0×F / x r 0=0.015625×−0.155212,0

Test : F / x l 0×F / x r 0=0.015625×−0.678711,0
4 5
6 7

The new subinterval enclosing the root is

The new subinterval enclosing the root is
[ x l , x u ]=[ 5.625000 , 5.664062 ]
[ x l , x u ]=[ 5.625000 , 5.781250 ]
5 5
7 7

Iteration 6 Iteration 8
/ x l + x u 0 /5.625000+5.7812500 / x l + x u 0 /5.625000+5.6640620
xr = = 5 5
=5.703125 xr = = 7 7
=5.644531
6
2 2
8
2 2

Ea = 6
∣
/ xr − xr 0
xr
×100=
6

6
5

∣ Ea = 8
∣
/ x r −x r 0
xr
8
×100=
8
7

∣
∣
5.703125−5.781250
5.703125
×100=1.369863 ∣ ∣
5.644531−5.664062
5.644531
×100=0.346021 ∣
Test : F / x l 0× F / x r 0=0.015625×−0.327881,0 Test : F / x l 0×F / x r 0=0.015625×−0.069565,0
7 8
5 6

The new subinterval enclosing the root is The new subinterval enclosing the root is
[ x l , x u ]=[ 5.625000 , 5.703125 ] [ x l , x u ]=[ 5.625000 , 5.644531 ]
8 8
6 6
 Iteration 9 Iteration 11
/ x l + x u 0 /5.625000+5.6445310 / x l + x u 0 /5.625000+5.6298830
xr = =8
=5.634766
8
xr = 10
= =5.627441
10

9
2 2 11
2 2

Ea = 9
∣ / x r − xr 0
xr
9
×100=
9
8

∣ Ea = 11
∣
/ xr − xr 0
xr
×100=
11

11
10

∣
∣ 5.634766−5.644531
5.634766
×100=0.173310 ∣ ∣
5.627441−5.629883
5.627441
×100=0.043384 ∣
Test : F / x l 0× F / x r 0=0.015625×−0.026913,0
8 9
Test : F / x l 0×F / x r 0=0.015625×0.005001-0
10 11

The new subinterval enclosing the root is The new subinterval enclosing the root is
[ x l , x u ]=[ 5.625000 , 5.634766 ]
9 9
[ x l , x u ]=[ 5.627441 , 5.629883 ]
11 11

Iteration 10 Iteration 12
/ x l +x u 0 /5.625000+5.6347660 / x l + x u 0 /5.627441+5.6298830
xr = = 9
=5.629883
9 xr = =11
=5.628662
11

10
2 2
12
2 2

Ea = 10
xr ∣
/ x r −x r 0
×100= 10 9

∣ Ea = 12
∣
/ x r −x r 0
xr
×100=
12

12
11

∣
∣ ∣
10

5.628662−5.627441
∣
5.629883−5.634766
5.629883
×100=0.086730 ∣ 5.628662
×100=0.021687

Test : F / x l 0×F / x r 0=0.015625×−0.005630,0 Test : F / x l 0×F / x r 0=0.005001×−0.000313,0

11 12
9 10

The new subinterval enclosing the root is The new subinterval enclosing the root is
[ x l , x u ]=[ 5.625000 , 5.629883 ] [ x l , x u ]=[ 5.627441 , 5.628662 ]
12 12
10 10
 Iteration 14
Iteration 13 / x l +x u 0 /5.628052+5.6286620
/ x l +x u 0 /5.627441+5.6286620 xr = = 13
=5.628357
13

xr = = 12
=5.628052
12 14
2 2
13
2 2

Ea = 13
∣
/ x r −x r 0
xr
×100= 13 12

∣ Ea = 14
∣
/ x r −x r 0
xr
×100=
14

14
13

∣
∣
5.628357−5.628052
∣
13

∣ ∣
5.628052−5.628662 ×100=0.005422
×100=0.010845 5.628357
5.628052
Test : F / x l 0×F / x r 0=0.002344×0.001016-0
Test : F / x l 0×F / x r 0=0.005001×0.002344-0
13 14

12 13

The new subinterval enclosing the root is

The new subinterval enclosing the root is [ x l , x u ]=[ 5.628357 , 5.628662 ]
[ x l , x u ]=[ 5.628052 , 5.628662 ]
14 14

13 13

Root=5.6284

Root = 5.6250 Ea = 11.1111 Iter = 3

Root = 5.6641 Ea = 0.6897 Iter = 7

Root = 5.6284 Ea = 0.0054 Iter = 14

What is the true error?

Example: similar to Exercise 5.3

Determine the real root of the function

2 3 4 5
f /x0=−25+82x−90x +44x −8x +0.7x

(a) Use Bisection to determine the root to Es = 10 %.

Employ initial Guesses of Xl = 0.5 and Xu=1.0.

(b) Perform the same computation as above using the false-position

method and Es = 0.2 %
Part b Bisection Method

Iteration 1
/ X l +X u 0 / 0.500000+1.000000 0
X r1= = =0.750000
2 2

The new subinterval enclosing the root is

[ X l1 , X u1 ]=[ 0.500000 , 0.750000 ]

Ea can't be computed this round, WHY?

Et can't be computed in any round in this question WHY?

Iteration 2

/ X l1+X u1 0 /0.500000+0.7500000
X r2= = =0.625000
2 2

Ea 2 =∣ / X r2−X r10
X r2 ∣
×100 %= ∣0.625000−0.750000
0.625000 ∣
×100 %=20.000000

The new subinterval enclosing the root is

[ X l2 , Xu2 ]= [ 0.500000 , 0.625000 ]
Iteration 3

/ X l2+Xu2 0 / 0.500000+0.6250000
X r3= = =0.562500
2 2

∣ ∣ ∣ ∣
/ X r3−X r2 0 0.562500−0.625000
Ea3= ×100 %= ×100 %=11.111111
Xr3 0.562500

The new subinterval enclosing the root is

[ X l3 , Xu3 ] =[ 0.562500 , 0.625000 ]
Iteration 4

/X l3+X u3 0 /0.562500+0.6250000
X r4= = =0.593750
2 2

∣
Ea 4 =
X r4 ∣
/ Xr4 −X r3 0
×100 %= ∣ 0.593750−0.562500
0.593750 ∣
×100 %=5.263158

Since Ea ,10 % , Stop here

Root =0.5938
Part c False-position method

Iteration 1

F / X u0∗/X l −X u 0
X r1=X u− =
/F /X l 0−F / X u 00
3.700000∗/0.500000−1.0000000
1.000000− =0.642728
−5.178125

The new subinterval enclosing the root is

[ X l1 , Xu1 ]= [ 0.500000 , 0.642728 ]
Iteration 2

F /X u10∗/X l1−X u1 0
X r2 =X u1 − =
/F /X l10−F / X u100
0.918789∗/0.500000−0.6427280
0.642728− =0.588017
−2.396914

Ea 2= ∣ /X r2−X r1 0
X r2 ∣ ×100= ∣0.588017−0.642728
0.588017 ∣
×100=9.304260

The new subinterval enclosing the root is

[X l2 , X u2 ]= [ 0.500000 , 0.588017 ]
Iteration 3

F /X u20∗/X l2−X u2 0
X r3 =X u2 − =
/F /X l20−F / X u200
0.137289∗/0.500000−0.5880170
0.588017− =0.580537
−1.615414

∣
Ea 3 =
X r3 ∣
/ X r3 −X r2 0
∣
×100=
0.580537−0.588017
0.580537 ∣
×100=1.288519

The new subinterval enclosing the root is

[X l3 , X u3 ]= [ 0.500000 , 0.580537 ]
Iteration 4

F / X u3 0∗/ X l3−X u3 0
X r4=X u3− =
/F /X l30−F /X u3 00
0.018219∗/0.500000−0.5805370
0.580537− =0.579556
−1.496344

∣
Ea 4 =
X r4 ∣
/ X r4 −X r3 0
×100= ∣ 0.579556−0.580537
0.579556 ∣
×100=0.169198,Es=0.2

Since Ea ,10 % , Stop here

Root=0.5796
 Error Analysis and number of iteration
IN
Bisection method only

1x
Ea , n = n
where Ea , n is the absolute error = Ea , n × xr
2 n

rewrite

log / 0
1X
1X
/ 0
1X Ea , n
n log /20= log
n
2= ⇒ ⇒ n=
Ea , n Ea , n log /2 0

Use it to estimate the number of iteration needed when performing bisection

method

Would any explain how?

 As applying the last mentioned relation to
the last solved example

Ea , 4 =5.263158 % and the Root = 0.5938

Thus, the absolute error = 5.263158 % × 0.5938=0.0313

n=
log / 1 X = 0.5
Ea , n = 0.0313 0 = 3.9977
log /20

Taking the ceiling of the last evaluated number, gives n = 4

Since we usually don't know the Xrn, we may use as an approximation,

relative error Ean instead of the absolute error which equals to Ena*Xrn
This latest approximation will lead us to underestimate n
Exercise 5.03 at the blackboard
Exercise 5.17 at the blackboard
Next slides
The independent parameter is h

f /h0=30−2∗h2∗/9−h0/3

LowerLimit = 0
UpperLimit = 3
StopError = 0
MaxIteration = 3
 Bisection

Iteration 1
/hl +hu 0 /0.000000+3.0000000
hr1= = =1.500000
2 2

Test=F /hl 0×F /h r 0=30.000000∗12.328541-0

0 1

The new subinterval enclosing the root is

[ hl , hu ]=[ 1.500000 , 3.000000 ]
1 1
Iteration 2
/hl +hu 0 /1.500000+3.0000000
hr = = 1
=2.250000
1

2
2 2

Ea = 2
hr ∣
/hr −hr 0
×100= 2

2
1

∣
∣
2.250000−1.500000
2.250000
×100=33.333333 ∣
Test : F /hl 0×F /hr 0=12.328541×−5.784704,0
1 2

The new subinterval enclosing the root is

[hl , hu ]=[ 1.500000 , 2.250000 ]
2 2
Iteration 3
/hl +hu 0 /1.500000+2.2500000
hr = = 2
=1.875000
2

3
2 2

Ea = 3
hr ∣
/hr −h r 0
×100= 3

3
2

∣
∣
1.875000−2.250000
1.875000
×100=20.000000 ∣
Test : F /hl 0×F /h r 0=12.328541×3.768929-0
2 3

The new subinterval enclosing the root is

[hl , hu ]= [ 1.875000 , 2.250000 ]
3 3

Root =1.8750
After so many iterations you will get close to what false position gives in only 3 iterations

Iteration 20
/hl +hu 0 /2.026903+2.0269090
hr = =19
=2.026906
19

20
2 2

Ea =20
∣
/hr −hr 0 20

hr 20
19

∣
×100=

∣2.026906−2.026903
2.026906
×100=0.000141 ∣
Test : F / hl 0× F /hr 0=0.000065×−0.000007,0
19 20

The new subinterval enclosing the root is

[hl , hu ]= [ 2.026903 , 2.026906 ]
20 20

Root =2.0269
 False Position

Iteration 1
F /h u 0×/hl −hu 0
hr =hu − =
1
/ F /hl 0−F /hu 00
−26.548668×/0.000000−3.0000000
3.000000− =1.591549
56.548668

Test=F /hl 0× F /h r 0=30.000000∗10.348475-0

0 1

The new subinterval enclosing the root is

[ hl , hu ] =[ 1.591549 , 3.000000 ]
1 1
Iteration 2
F /hu 0×/hl −h u 0
hr =hu − 1
= 1 1

2
/ F /hl 0−F /hu 00
1
1 1

−26.548668×/1.591549−3.0000000
3.000000− =1.986575
36.897142

Ea = 2 ∣
/hr2 −hr1 0
hr2
×100=
∣ ∣
1.986575−1.591549
1.986575 ∣
×100=19.884755

Test : F /hl 0×F /hr 0=10.348475×1.015307-0

1 2

The new subinterval enclosing the root is

[ hl , hu ] =[ 1.986575 , 3.000000 ]
2 2
Iteration 3
F /hu 0×/hl −hu 0
hr =hu − 2
= 2 2

3
/ F /hl 0−F /hu 00
2
2 2

−26.548668×/1.986575−3.0000000
3.000000− =2.023904
27.563975

Ea = 3 ∣
/hr3 −hr2 0
hr3
×100=
∣ ∣
2.023904−1.986575
2.023904 ∣
×100=1.844409

Test : F /hl 0×F /hr 0=1.015307×0.075913-0

2 3

The new subinterval enclosing the root is

[ hl , hu ]=[ 2.023904 , 3.000000 ]
3 3

Root=2.0239
 Final word on Bracketing methods

Bracketing methods, Bisection and false-position methods,

search for a root within an interval in the domain
[ a lower bound , upper bound]

Repetition, iteration, always results in closer estimates of the true

value of the root

Those methods are convergent because they move closer to the true
value of the root as the computation progresses