Root Finding Methods Gaurenteed to Find All Root Between (xmin, xmax)
- To: mathgroup at smc.vnet.net
- Subject: [mg112575] Root Finding Methods Gaurenteed to Find All Root Between (xmin, xmax)
- From: "Ted Ersek" <ersekt at md.metrocast.net>
- Date: Mon, 20 Sep 2010 05:44:52 -0400 (EDT)
In [1] I gave a long response to the thread [FindRoots]
It seems in [2] Andrzej Kozlowski was saying there are ways to
obtain the complete set of roots (provably complete) over a
closed and bounded set provided the function is C2 continuous
and does not have multiple roots in the domain of definition.
I suppose he is talking about numeric methods to find all the roots.
If that is the case I would expect these methods to have practical
limitations in what they can do? I mean a function could be very
ill-behaved and still meet the conditions above. Consider f[x] below.
pnts=Table[ {x,Log[x]}, {x,3.0,250.0,0.01}];
Part[ pnts, 16000, 2] = -0.05;
f=Interpolation[ pnts, Method:>Spline ];
>From the output of Plot[f[x], {x,3,250}] it looks like f[x] is monotonic,
well behaved and having no roots between (3, 250). In fact it is
C2 continuous, but it does have two root close to 18.99. It actually is
well behaved except for the small interval between (18.992, 19.006).
Suppose we wanted to find all the roots between (3,250) of a function
defined as SomeNumericalAlgorithm[x] and the function always evaluated to
the same value as the InterpolatingFunction above. How can a numeric
RootFinding
algorithm be gaurenteed to find these roots near 18.99 if it doesn't have
the
good furtune of taking one or more sample between (18.992, 19.006), or
sampling higher order derivatives in a interval a bit larger than (18.992,
19.006)?
(******* References ********)
[1] http://forums.wolfram.com/mathgroup/archive/2010/Sep/msg00255.html
[2] http://forums.wolfram.com/mathgroup/archive/2010/Sep/msg00262.html