Graphics Programs Reference
In-Depth Information
Ingeneral, an equation may have any number of (real) roots, orno roots at all.
For example,
sin x
x
=
0
has a single root, namely x
=
0, whereas
tan x
x
=
0
has an infinite number of roots ( x
).
All methodsoffinding roots are iterative procedures that require a starting point,
i.e., an estimate of the root. This estimate can becrucial; a bad starting value may
failtoconverge, orit may converge to the “wrong” root (aroot differentfrom the one
sought). There is no universal recipefor estimating the valueofaroot. If the equationis
associatedwith aphysical problem, then the contextoftheproblem (physical insight)
might suggest the approximate location of the root. Otherwise, the functionmust be
plotted,orasystematic numericalsearch for the roots can becarried out. Onesuch
search methodis describedinthe next article.
It ishighly advisable to go a step further and bracket the root (determine its lower
and upperbounds) before passing the problem to aroot-finding algorithm. Prior
bracketing is, in fact, mandatory in the methods describedinthischapter.
=
0
, ±
4
.
493
, ±
7
.
725
,...
4.2
Incremental Search Method
The approximate locations of the roots are best determinedbyplotting the function.
Oftenaveryroughplot,basedonafewpoints, issufficienttogiveus reasonable starting
values.Anotheruseful tool fordetectingandbracketing roots is the incrementalsearch
method. It can also be adapted for computing roots, but the effort wouldnot be
worthwhile, since othermethods describedinthischapterare moreefficientfor that.
The basic ideabehind the incrementalsearch methodissimple:if f ( x 1 ) and
f ( x 2 )haveopposite signs, then there is atleast one root in the interval( x 1 ,
x 2 ). If the
interval issmall enough, it islikely to contain a single root. Thus the zeroes of f ( x )can
be detectedbyevaluating the functionat intervals
x and looking for change in sign.
There areseveral potential problems with the incrementalsearch method:
It is possible to miss two closely spacedroots if the search increment
x islarger
than the spacing of the roots.
Adouble root (two roots thatcoincide) will not be detected.
Certain singularities of f ( x )can be mistaken forroots.For example,
f ( x )
=
tan x
1
changes sign at x
, as shown in Fig. 4.1. However, these
locations are not truezeroes, since the functiondoes not cross the x -axis.
2 n
π,
n
=
1
,
3
,
5
,...
Search WWH ::




Custom Search