Bisection methods (was Re: Structured support...)

["Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>]

John,

Again, my problem is you are talking about "mathematical defintion" vs. 
"algorithm". An algorithm is an effective method expressed as a finite list 
of well-defined instructions for calculating a function.

As I explain in section 3.2.2, 3.2.3 and 3.2.4 the mathematical definition 
of Interval Newton, for example, is (13), but (13) is not an algorithm until 
some exact method of choosing x \in X is specified, e. g., (14). Same for 
centered forms, B&B, etc.

In the model you are proposing, only the mathematical definitions are 
defined at Level 1 and Level 2, but the corresponding algorithms are not; 
according to the standard, such algorithms must return NaNs.

Nate



----- Original Message ----- 
From: "John Pryce" <j.d.pryce@xxxxxxxxxxxx>
To: "Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>
Cc: "stds-1788" <stds-1788@xxxxxxxxxxxxxxxxx>
Sent: Friday, May 25, 2012 1:08 AM
Subject: Re: Structured support for both standard and modal intervals


> Nate
>
> On 24 May 2012, at 18:10, Nate Hayes wrote:
> > I only have one further comment (see below).
> >
> > John Pryce write:
> > > Nate Hayes wrote:
> > > > P1788 already voted that the midpoint of an unbounded interval is
> > > > undefined.
> > > > So if P1788 decides there will be no overflow, then these are my
> > > > lingering
> > > > and unanswered questions:
> > > >
> > > > 1. If arithmetic mean (midpoint) of an unbounded interval is undefined
> > > > at Level 1, does this mean other interval bisection methods such as
> > > > geometric mean, smedian2, etc. are also undefined at Level 1 for
> > > > unbounded
> > > > intervals?
> > >
> > > IMO it's right that "midpoint" should be defined entirely "by the
> > > mathematics", so undefined...
> > >
> > > My view of undefinedness. The Hack-Neumaier flmedian is inherently
> > > undefined at Level 1. The Pryce-Zuras smedian at Level 1 is undefined, 
> > > or
> > > infinite, for unbounded intervals. Who cares? They may be found
> > > pragmatically useful at Level 2.
> > ...
> > > > 3. If answer to (1) is "yes", then are all of these interval bisection
> > > > methods undefined for unbounded intervals at Level 2, as well?
> > >
> > > For me this a matter of mathematical honesty. If ANY numeric function is
> > > mathematically undefined for some input then say so, at Level 1; and let
> > > it return NaN at Level 2...
> > >
> > > > 5. If answer to (3) is "yes", it seems users will not be able to write
> > > > any interval bisection methods of thier own that will be conforming,
> > > > since
> > > > picking arbitrary real number will be against the Level 1 and Level 2
> > > > definitions. So how can any user develop conforming algorithms that
> > > > bisect
> > > > unbounded intervals?
> > >
> > > If you CALL IT SOMETHING DIFFERENT, you can make your pragmatic function
> > > do whatever is useful. So no contradiction...
> > > I should probably add to the Level 1 text, that other operations may be
> > > defined at lower levels for purely pragmatic reasons.
> >
> > My only problem with this idea is it means users can no longer design
> > interval algorithms (or prove them correct) at Level 1, and we feel it 
> > encourages users to ignore the Level 1 definitions. We believe overflow 
> > avoids this problem by providing the necessary mathematical framework at 
> > Level 1a.
>
> My take on this is that it is not so, because the magic word "some" 
> (arbitrary) can be and should be used in the definition of many algorithms 
> at Level 1:
>
> - In validated solution of ODE initial value problems x'=f(t,x), if I 
> remember right, one has a box X enclosing a set of solutions at time t. 
> One chooses "some" point xhat in X and expands the (point) Taylor series 
> about that point, with a remainder term to account for the size of X and 
> for rounding errors. It is usually best to take xhat as the midpoint of X, 
> but the algorithm is correct whatever xhat is chosen.
>
> - In your B&B method, one can choose "some" point (in "some" side) of a 
> box to split it at. One can prove the method converges in the sense that 
> each side of each box eventually becomes smaller than a tolerance TOL, 
> provided certain constraints are satisfied. First, I would map the real 
> line to a bounded interval by a map such as x -> y = x/(1+|x|) so as to 
> get a meaning of "small" that works at infinity as well as at finite 
> points. Then the constraint might be that, if (in this y coordinate 
> system) a side is split in the ratio c:d where 0 <= c <= d, c+d=1, then c 
> must >= some fixed c0 > 0.
>
> - Similarly, isn't interval Newton valid for an arbitrary "expansion 
> point" in the current interval?
>
> A correctness proof that is independent of any specific heuristic for the 
> "some" is often useful.
>
> John Pryce