Re: [boost] Boost.Interval

From: Jens Maurer (Jens.Maurer_at_[hidden])
Date: 2001-04-24 12:54:29

Matthew Austern wrote:
> 
> "Peter Schmitteckert (boost)" wrote:

> > You will need just one function call to check if x has a
> > zero in the interval -1..1:
> > if  f( interval<double>(-1,1) ) contains no zero then it is proven that there
> > is no zero.
> 
> But isn't that just a matter of redefining the problem away?
> When you write f(interval<double>(-1, 1)), what you really mean
> is "the ordered pair (a, b) such that a is less than or equal
> to f(x) for all x in [-1, 1] and b is greater than or equal to
> f(x) for all x in [-1, 1]".

The assumption is that f() is continuous and composed of arithmetic
operations, constants and "simple" functions such as sin, cos, tan
only.  Then, you're redefining (overloading) each of the operations
and functions for interval type arguments.  Then, computing
f(interval<double>(-1,1)) is (in C++) as easy as computing
f((double)1.0), provided that you've only used "allowed" operations
and functions and you've defined f() as   template<class T> T f(T x) .

So, instead of taking f(double x) as your starting point, you're
actually taking advantage of the inner structure of f().

In the root-finding case, you've either proven that there are no
roots within [-1, 1] or that there is at least one.  If the latter,
you're subdividing your interval into two, e.g. [-1, 0] and [0, 1]
and continue searching in both of these.  Eventually, you'll
be finding intervals without roots (which you can disregard) and
the rest gives enclosures for all of the roots of the function.

If there's interest, I can give a short introduction at the
Copenhagen boost meeting.

Jens Maurer