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

*To*: mathgroup at smc.vnet.net*Subject*: [mg112773] Re: Root Finding Methods Gaurenteed to Find All Root Between (xmin, xmax)*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Thu, 30 Sep 2010 04:50:25 -0400 (EDT)*References*: <001801cb5fd0$32430380$96c90a80$@md.metrocast.net>

Well, of course. This is a well known weakness of interval arithmetic.There are better approaches (see below) but the main point is that, as far as root finding by subdivision method any approach that returns the upper bounds of a function on a closed rectangle (interval) is sufficient to determine all roots by the subdivision method. If the bounds are poor many subdivisions will be required but (as long as there are no repeated roots) the rectangle will eventually be subdivided into smaller sub-rectangles which contain at most one root each. At this point the Newton method can be used to find all the roots. Of course if we other ways of determining the number of roots (as in the case of complex analytic functions) also find all the roots with certainty. By the way, Mathematica's implementation of interval arithmetic is the standard one as formalized by Ramon E.Moorein the 1960s. In that sense it is not any more limited than any other implementation and is quite sufficient for root finding (it is in fact used by Reduce). However, as is usually the case with methods that are half a century old, there are better and more efficient SVC (self-validated computation) models. One of them is affine arithmetic, which tries to correlation between errors (interval arithmetic assumes they are independent). An implementation of affine arithemtic in Mathemaitca was presented by Anita Uscilowska at the 2005 Mathematica Symposium. However, this implementation is slow, partly because the author was far from an expert Mathematica programmer but mostly because any such method would have to be implemented by WRI in the Kernel to be usable in practice. Nevertheless even this inefficient implementation can be applied to solve certain important problems much more efficiently than can be done with Mathematica's built in interval arithmetic. A foundational paper about affine aritmetic is: J. Stolfi and L. H. de Figueiredo, "An introduction to affine arithmetic", TEMA Tend. Mat. Appl. Comput, 4(3), 2003 pp. 297-312. Andrzej Kozlowski On 29 Sep 2010, at 14:16, Ted Ersek wrote: > It was mentioned that some of the methods to find all roots in a certain > region require interval analysis. > However, Interval arithmetic in Mathematica is limited. First of all > Mathematica only knows how to evaluate > elementary function and simple functions such as (Abs, Min) when given an > Interval as an argument. > So for example Mathematica does nothing with Gamma[ Interval[ {2,3} ] ] > even though Gamma[x] is continuous and monotonic over this interval with > Gamma[2] == 1; Gamma[3] ==2 > > Besides that Mathematica performs calculations as if each instance of > Interval[{xmin_, xmax_}] > is a value between (xmin, xmax) that is unrelated to any other instance of > Interval[{xmin_, xmax_}]. > So I present the following as a worst case example of what this can give. > > In[1]:= poly=Function[x, Evaluate[ChebyshevT[15,x]]] > Out[1]= Function[x,-15 x+560 x^3-6048 x^5+28800 x^7-70400 x^9+92160 > x^11-61440 x^13+16384 x^15] > > In[2]:= poly[Interval[{-1,1}]] > Out[2]= Interval[{-275807,275807}] > > The above interval isn't very useful when we can see from Plot[ poly[x], > {x,-1,1} ] > that poly[x] oscillates between (-1,1) over this interval. > For a general function we can approximate the interval we really want using > > NMinimize[ { f[x], xmin<x<xmax}, x ], NMaximize[ { f[x], xmin<x<xmax}, x ]. > > However, that's about as difficult as finding a root of f[x]. > Actually that may be more difficult than finding a root of f[x]. > > Ted Ersek > >