Re: Motion 11
> Date: Tue, 16 Feb 2010 10:11:46 +0100
> From: =?ISO-8859-1?Q?Fr=E9d=E9ric_Goualard?=
> <Frederic.Goualard@xxxxxxxxxxxxxx>
> To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
> CC: stds-1788@xxxxxxxxxxxxxxxxx
> Subject: Re: Motion 11
>
>
> Dear Dan,
>
> Dan Zuras Intervals wrote:
> > I believe your observation about Corollary 1 & arguments
> > for the need for reverse operations both contribute to an
> > approach along the lines George has suggested.
> >
> > For example, Nate has pointed out the the lack of inverse
> > operators within ordinary intervals can be repaired by the
> > use of the Dual() operator. Where
> >
> > Dual([a,b]) = [b,a].
> >
> > Thus, you can solve for yy in xx + yy = zz by
> >
> > xx + yy = zz
> > (xx - Dual(xx)) + yy = zz - Dual(xx)
> > [0,0] + yy = zz - Dual(xx)
> > yy = zz - Dual(xx)
> >
> > All 4 basic operations may be inverted in this way. (I
> > will leave it to Nate to discuss the details on grounds
> > of incompetence on my part. :-)
>
> I do not know enough about modal interval arithmetic to have any
> definitive argument about that. However, I doubt you can easily obtain
> the same results as with reverse division. Once again, consider my example:
>
> A=[0,2]
> B=[-1,1]
> C=[1,1]
>
> with \circ=\times
>
> and compute \times_1^-(B,C,A) = hull({x\in[0,2]\mid\exists b\in[-1,1],
> x\times b\in[1,1]})
>
> Can you obtain [1, 2] as a result? The n+1-ary reverse division will.
Ah, yes. We have discussed this before.
Still, I believe that the answer is that such a result
CAN be obtained with the proper inverse of B. But I'll
let Nate describe the details.
Nate?
>
> > Further, it is my understanding that inverse operations
> > (for example, in Newton steps) can lead to tighter
> > intervals than those defined in Motion 11. Of course,
> > one must intersect it with the original guess interval
> > just as in Motion 11.
>
> I am lost here. What do you call inverse operations?
When I first came to intervals I was puzzled by something.
You see, the intervals contain the reals by the obvious
mapping of r --> [r,r] for all r in R but the standard
intervals are not a field. They DO have identity elements,
[0,0] for add & [1,1] for multiply. But they do not, in
general have inverses. That is, for any xx = [a,b] with
a < b there is no -xx such that xx + (-xx) = [0,0]. Nor
a xx^-1 such that xx*(xx^-1) = [1,1].
One CAN find such an additive inverse element in the form
of [-a,-b] but this is not a standard interval as -a > -b.
Still, for -xx = [-a,-b] = -Dual(xx) we have xx + (-xx) =
[0,0].
Similarly, Nate help me here if I make a mistake, we
have that xx^-1 = 1/Dual(xx) = Dual(1/xx) = [1/a,1/b]
to obtain xx*(xx^-1) = [1,1].
We need these things. We can't solve equations without
inverses.
Thus we are forced to consider at least getting our toes
wet in the modal world if for no other reason than solving
equations in the standard world.
So it is these operations I am calling inverse operations.
Indeed, it was *I* that was confused on first reading of
the reverse operations in Motion 11. I came to it thinking
that it was the inverse operations being defined when it was
something slightly different but to be used for the same
purposes.
>
> > So I guess I'm suggesting the addition of the Dual()
> > operator as something out of which the needed operators
> > can be constructed.
> >
> > Does this work?
> > Would this be a simpler approach along the lines George
> > has mentioned?
> > Is anything else needed?
>
> As I said, there is more to reverse operations than division. How would
> reverse cosine be implemented with Dual (see example of use below)?
Good. Dual will not do it then. At least, not all by
itself.
>
>
> > In particular, are the 3-op forms needed given that we
> > can just intersect the 2-op form with the original guess?
> >
> > Anyone? - Dan
>
> No, because Corollary 1 is false.
> You just have to consider the example above. Another one, taken from the
> first paper I referred you to in a previous mail:
>
> Say you know that x\in[20,26], and you have the *relation*: y=cos x,
> with y\in[-0.3,0.2].
>
> What can you infer about x from that? If you use some unary reverse
> cosine, you cannot obtain anything useful for x. You have to use a
> binary reverse cosine to take into account x's original domain *inside*
> the operator. You will then be able to infer that x\in[6\pi+acos 0.2,
> 8\pi-acos 0.2]\approx[20.22,23.77].
>
> F.
> - --
> Frédéric Goualard LINA - UMR CNRS 6241
Yes. You have mentioned this before.
So the obvious generalization to Motion 11 to solve this
problem would be a 2-op form of inverse cosine like
RevCos(xx,yy) which is defined as
hull(cos^-1(xx) \intersect yy) where cos^-1 returns all
the countably infinite intervals whose cosines map into
the operand interval xx.
Given that this (conceptually) infinite intermediate
result is immediately intersected with yy & turned into
an ordinary interval by hull, I'm with you & this seems
to be the correct definition.
Still, Motion 11 as it was most recently written, contains
things that return pairs of intervals. This really only
works for the similar (finite) intermediate form of the
inverse of divide & does not generalize well to functions
that have anything other than a simple pole. Square root
(actually, inverse square) would work but not much else.
It's not the pole, you see, it's the fact that the inverse
function sits on exactly two manifolds in the complex plane.
Not many functions have inverses that fit that description.
Pairs of intervals will not play well with expressions.
Nor with a parsimony of datatypes. Nor 1788 definitions,
for that matter. So George's principles of simplicity of
definitions would be out the window.
If we were dealing with only the 3-op forms I'd be OK
with it. As you point out, Corollary 1 is false because
hull & intersect do not commute.
But things that return pairs of intervals exposes this
to the outside world in a way that cannot be generalized
easily. We will not be defining triplets & quadruplets of
intervals & things that return infinitely many intervals
cannot be implemented.
Wouldn't it be better in both cases to keep this
particular sin under the covers so to speak & use hull to
protect the outside world from this notion altogether?
Just a suggestion... - Dan
P.S. - Actually, a subtle thing about floating-point means
that there would be only finitely many intervals to
something like an inverse cosine. Beyond some point, the
sparsity of floating-point numbers means that there would
be a last representable interval [r,oo) that contains all
the remaining results. So an inverse cosine would return
only finitely many intervals after all. But the number
would be large & related to the precision more than the
exponent range. I don't know why I mention it. There is
no possibility of implementing such a thing. It is just
the nerd in me I guess. Ah well... :-)