Re: Interval comparisons
Maarten and P1788
On 24 Aug 2009, at 23:05, Maarten van Emden wrote:
According to Motion 2 on process structure we should settle issues
at level 1 of that motion before descending ...
I have written about my view on that.
What we have so far are the relational operators in the Vienna
Proposal
section 5.4 (henceforth "Vienna 5.4").
We, qua P1788, don't yet HAVE anything on this issue. I believe what
we eventually create will be functionally very similar to Vienna, but
we need to vote each issue in turn.
...
This problem can be avoided. The remedy that I propose has the
additional
advantage that it explains the backward definitions in Vienna 3.11.
I think Arnold explained that well already in his email of 3 June
2008, which essentially covers the distinction you make between
evaluation and solving.
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.
In numerical analysis one can only solve by iterated evaluation.
In interval arithmetic one can make solving the basic step.
Evaluation becomes available as a special case of solving:
Proposal: given expression E for computing function f, xx, and yy,
define IA as solving
E(xx) = yy
in the sense of making xx or yy or both as narrow as the equation
allows.
With respect, Maarten, this is not devoid of ambiguities. Let's take
E(xx) relop yy
where "relop" is some relational operator. There are several ways to
quantify this in order to get a precise meaning:
(Q1 x in xx) (Q2 y in yy) E(x) relop y, (eqn1)
where Q1 is either "all" or "exist", and Q2 similarly. (I assume xx
and yy are atomic. Presumably they are vectors in general, and if one
were allowed to quantify each component separately, one would have
2^N possibilities where N is the number of components.) Oh dear: more
than that, because an "all" phrase doesn't commute with an "exist"
phrase in general.
Properties:
(1) Interval arithmetic is the special case where yy = [-oo,+oo].
In that case xx stays unchanged and yy narrows to the result of E(xx)
according to interval arithmetic as traditionally understood.
That is specified by
(all x in xx) (exist y in yy) E(x) = y,
which is the definition of: yy is an enclosure of range(f,xx).
(2) If yy = hull(y) for some real y, then xx narrows to the hull of
the set of solutions to f(x) = y. The SIVIA algorithm, for example,
computes this hull. It solves, for example, algebraic equations
this way.
SIVIA (Set Inversion Via Interval Analysis) looks an important
algorithm, but I don't think "computes this hull" is accurate. It
computes an _enclosure_ of the set of solutions, and such an
enclosure may be specified by another variant on these quantifications:
(all x not in xx) E(x) \neq y.
What SIVIA computes is a union of intervals in general, isn't it? So
not a hull. And, I don't see how the more specific set "the hull of
the set of solutions to f(x) = y" can be described by
E(xx) = hull(y), (eqn2)
no matter how it is quantified. Suppose E(x) is x*x, and y is 4. Then
- The equation is x^2 = 4.
- The set of solutions is {-2,2}.
- The hull thereof is [-2,2].
And you are saying the task of finding this hull can be described by
writing
xx*xx = [4,4]
which is what (eqn2) becomes in this case. No matter how I quantify
it as in (eqn1):
(Q1 x in [-2,2]) (Q2 y in [4,4]) x*x = y
(or with the Q1 and Q2 phrases swapped) I don't see how this makes
sense. Well, it's true that
(all y in [4,4]) (exist x in [-2,2]) x*x = y
but that doesn't capture what you are saying.
Maarten, please elucidate.
Regards
John