MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

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
>
>



  • Prev by Date: Re: Why Row does not format 2 plots in one row when ImageSize->Full?
  • Next by Date: Re: New Version 3 Presentations
  • Previous by thread: Root Finding Methods Gaurenteed to Find All Root Between (xmin, xmax)
  • Next by thread: Re: Root Finding Methods Gaurenteed to Find All Root Between (xmin, xmax)