Re: Root Finding Methods Gaurenteed to Find All Root Between (xmin, xmax)

*To*: mathgroup at smc.vnet.net*Subject*: [mg112561] Re: Root Finding Methods Gaurenteed to Find All Root Between (xmin, xmax)*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Mon, 20 Sep 2010 05:42:17 -0400 (EDT)*References*: <000601cb5809$fb6d8600$f2489200$@md.metrocast.net>

The method that I referred to does have a practical limitation in that it relies on an implementation of interval arithmetic or some equivalent method of finding upper bounds of the function(s) involved in our equations and their derivatives (or generalised jacobians in the multi-dimensional case). In other words, method will work as long as we can compute f[Interval{{a,b}]], f'[Interval[{a,b}]] etc. The algorithm works as follows. It subdivides the interval (or rectangle) in which we are looking for roots into a finite number of sub-rectangles. It them performs two tests on them, let's call them T1 and T2. If a rectangle passes the testT1 we no for sure that there are no roots in it and we eliminate it from further search. If a rectangle fails test T1 we apply to it test T2. If the rectangle passes T2 we know with certainty that there is at most a single root in the rectangle. We then apply Newton's method to the rectangle - it will either find the required root or will not converge. This will always determine whether there is a root in the rectangle or not. If a rectangle fails both tests it is subdivided further into smaller and smaller rectangles. As there are only finitely many roots in the original rectangle they will all be separated and we will now for sure that we have found all the roots. Since the process goes on until all roots have been found the example described below does not contradict the method. A problem occurs when there is a multiple root. A rectangle containing such a root will always fail both tests and the algorithm will never complete. We can of course always decide to stop search when the rectangle containing possibly multiple roots is sufficiently small. We will then know that there is possibly a multiple root in the remaining rectangle. If we wish we can of course let the method run longer. If the roots are really distinct the process will stop for sure, but if they are multiple it can go on for ever. Here may be the right place to add that Daniel Lichtblau has noticed that the method given by Semenov in the case systems with 2 or more equations and variables contains a mistake (it is fine for the one dimensional case). There is a mistake in the application of the mean value theorem for vector valued functions in Semenev's published article, which causes the algorithm to miss certain roots. However, we have been able to find the correct version of Semenev's method based on the concept of generalized jacobian. I am now writing up our corrected version of Semenev's method and will soon implement it in Mathematica. Eventually I will replace my demonstrations on the Demosntrations site with new ones using the new version, which we believe to be correct. Andrzej Kozlowski On 19 Sep 2010, at 16:50, Ted Ersek wrote: > 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 ]; > > =46rom 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 > >