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