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
  • Subject: [mg112773] Re: Root Finding Methods Gaurenteed to Find All Root Between (xmin, xmax)
  • From: Andrzej Kozlowski <akoz at>
  • Date: Thu, 30 Sep 2010 04:50:25 -0400 (EDT)
  • References: <001801cb5fd0$32430380$96c90a80$>

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

  • Prev by Date: Re: Mathematica calculates RSquared wrongly?
  • Next by Date: Re: Interpolate in polar coordinates or cartesian
  • Previous by thread: Re: Root Finding Methods Gaurenteed to Find All Root Between (xmin, xmax)
  • Next by thread: Mutual package imports in Mathematica