Information Technology Reference
In-Depth Information
5
x
1
=3
x
2
=1.5
0
x
0
=0
−5
−10
−15
−20
0
0.5
1
1.5
2
2.5
3
3.5
x
e
x
Fig. 4.2
The graph of f.x/
D
2
C
x
and three values of f : f.x
0
/, f.x
1
/,andf.x
2
/
Since f.x
3
/>0, we know that x
3
<x
<x
2
,seeFig.
4.3
.
Now, we can continue in this way until
j
f.x
n
/
j
is sufficiently small. For each step
in this iterative procedure, we have one point a where f.a/ > 0 and another point
b where f.b/ < 0. Then, we define c
D
2
.a
C
b/. By checking the sign of f.c/,
we proceed by choosing either a and c or b and c for the next step. In algorithmic
form this reads as follows:
Algorithm 4.1
Bisection Method.
Given a, b such that f.a/
f.b/ < 0 and a tolerance "
.
Define c
D
2
.a
C
b/
.
while
j
f.c/
j
>"
do
if
f.a/
f.c/ < 0
then
b
D
c
else
a
D
c
c
WD
2
.a
C
b/
end