Interval comparisons
Revision of my August 24 message "Interval Comparisons". John, Arnold,
Nate: thanks for your comments. Indeed, my notion of "solving" E(xx) = yy
is unclear. Also, I should not have referred to "interval extensions of
relations". Please see below for a revision to remedy these defects.
==========================================================
According to Motion 2 on process structure we should settle issues at
level 1 of that motion before descending into the details of the lower
levels. An outstanding issue at level 1 is the definition of interval
comparisons.
What we have so far are the relational operators in the Vienna Proposal
section 5.4 (henceforth "Vienna 5.4"). Here == is the name given to the
equality relation among intervals. Is this satisfactory?
A consequence of Vienna 5.4:
if E computes f and if x in xx, then E(xx) == hull(f(x)) is not
necessarily true.
This problem can be avoided by a suitable definition of relational
comparisons. The remedy that I propose has the additional advantage that
it explains the backward definitions in Vienna 3.11. This is necessary
because the backward definition of interval division is not universally
agreed to (see, e.g. Motion 5).
The cause of the difficulty is that IA focuses exclusively on EVALUATION,
whereas numerical analysis (which is the intended application of interval
arithmetic) is concerned with SOLVING.
Given expression E for computing function f and floating-point intervals
xx0 and yy0, define solving E(xx) <rel> yy as follows, where <rel> is any
of =, <=, >=.
find least floating-point intervals xx and yy such that:
for all real x, y it is the case that
f(x) <rel> y and x in xx0 and y in yy0
imply
x in xx and y in yy.
This definition extends <rel> among reals to <rel> among intervals.
Proposal: Generalize interval arithmetic to the solving of E(xx) <rel> yy
in the above sense.
In this way the comparison operators for intervals follow. But first check
out properties of solving when <rel> is equality:
(1) Interval arithmetic in the traditional sense is the special case where
yy is [-oo,+oo] with <rel> is =. In that case solving results in xx and
yy such that xx is xx0 and yy is the result of E(xx0) according to
interval arithmetic as traditionally understood.
(2) If yy0 is hull(y) for some real y, then xx is the floating-point hull
of the set of solutions to f(x) = y. The SIVIA algorithm, for example,
computes this hull in the sense of producing a set of xx's whose hull is
the floating-point hull of the set of solutions to f(x) = y. It solves,
for example, algebraic equations this way.
(3) The above are extremes for yy0. Solving E(xx) = yy makes sense for any
combination of widths of the intervals xx0 and yy0, thus making the
problem a common generalization of evaluation and solving. Such generality
can be standard interval arithmetic according to this proposal. It seems
beyond conventional numerical analysis. In this general case SIVIA works
unchanged.
As final property:
It makes just as much sense to solve E(xx) <rel> yy with >= or <= for
<rel>. SIVIA works unchanged.
In the special case of E(t) being t we have, e.g.
xx <= yy
In this case we don't need SIVIA for solving. But then we have, at
variance with Vienna 5.4, that the comparison evaluates to true except
when xx0 and yy0 are disjoint with xx0 to the right of yy0.
--
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.