Re: Interval comparisons
John Pryce wrote:
>> (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.
John, remember that SIVIA is a branch-and-bound process. So it recursively
bisects xx to find solutions for xx^2=[4,4]. If xx is initialized to
(-oo,+oo), it would therefore produce the two solutions xx_1 = [-2,-2] and
xx_2 = [2,2], each which satisfies the proposition
(all x in xx_i)(exists y in [4,4]) x^2 = y.
The hull of xx_1 and xx_2 is [-2,2], but I think it misses Maarten's point
that SIVIA computes xx_1 and xx_2 as unique solutions (correct me, Maarten,
if I'm wrong).
Nate Hayes