Graphics Programs Reference
In-Depth Information
EXAMPLE 4.1
Use
incrementalsearch with
x
=
0
.
2 to bracket the smallest positivezeroof
f
(
x
)
=
x
3
−
10
x
2
+
5.
Solution
Weevaluate
f
(
x
) at intervals
0, until the function
changes its sign (value of the functionisofno interest to us; onlyits sign is relevant).
This procedure yields the following results:
x
=
0
.
2,staring at
x
=
x
f
(
x
)
0
.
0
5
.
000
0
.
2
4
.
608
0
.
4
3
.
464
0
.
6
1
.
616
.
−
.
0
8
0
888
From the sign change of the functionweconcludethat the smallest positivezerolies
between
x
=
0
.
6 and
x
=
0
.
8.
4.3
Method of Bisection
Afteraroot of
f
(
x
)
x
2
), several methodscan
be used to close in onit. The method of bisectionaccomplishes this by successively
halving the interval until it becomes sufficiently small. This technique is also known
as the
interval halving method
.Bisectionis not the fastest methodavailable for com-
puting roots, but it is the most reliable. Once aroot has beenbracketed, bisectionwill
always close in onit.
The method of bisectionuses the same principle as incrementalsearch:if there is
aroot in the interval(
x
1
,
=
0has beenbracketedinthe interval(
x
1
,
·
<
x
2
), then
f
(
x
1
)
f
(
x
2
)
0. In order to halve the interval, we
1
compute
f
(
x
3
), where
x
3
=
2
(
x
1
+
x
2
) is the midpointoftheinterval. If
f
(
x
2
)
·
f
(
x
3
)
<
0, then the root must be in (
x
2
,
x
3
) and we record this by replacing the original bound
x
1
by
x
3
. Otherwise, the root lies in (
x
1
,
x
3
), inwhich case
x
2
is replacedby
x
3
. In either
case, the newinterval(
x
1
,
x
2
) ishalf the size of the original interval. The bisectionis
repeateduntil the intervalhas beenreduced to a small value
ε
,sothat
|
x
2
−
x
1
| ≤
ε
It iseasy to compute the number of bisections required to reach aprescribed
ε.
/
/
2
2
The original interval
x
is reduced to
x
2after one bisection,
x
after
2
n
2
n
two bisections and after
n
bisections it is
x
/
.
Setting
x
/
=
ε
and solving
Search WWH ::
Custom Search