Re: A simple interval challenge
First intermediate report (Nov. 27, 2008)
Challenge:
---------
Find a cheap and good enclosure for
f := (a(w^2+x^2-y^2-z^2)+2b(xy-wz)+2c(xz+wy))/(w^2+x^2+y^2+z^2)
given the following bounds on the variables a,b,c,w,x,y,z:
a in [7,9]
b in [-1,1]
c in [-1,1]
w in [-0.9,-0.6]
x in [-0.1,0.2]
y in [0.3,0.7]
z in [-0.2,0.1]
[...]
I get the slightly inferior bounds [-3.2697,9.2222] (114% of
optimal width) with 62 effective interval operations, using
monotonicity arguments and term rearrangements.
(excesscost = 4.49e-4)
I had a mistake in my program. The corrected version gets only the
enclosure [-3.6517,9.2223] using 12 real and 54 interval operations,
hence 60 effective operations.
This is 117% of optimal width, and has excess cost 1.7e-3.
(The excess cost is very sensitive to the width.)
Raymon Moore provided a pure rearrangement evaluation
u=w^2+x^2;v=y^2+z^2;
s=b*(x*y-w*z)+c*(x*z+w*y);
f=a*(1-2/(u/v + 1)) + 2*s/(u+v);
with 24 operations, giving the enclosure [-5.8080,11.3655],
which is 157% of optimal width, and has excess cost 0.79.
Note that the rearrangements
s=(b*x+c*w)*y+(c*x-b*w)*z
s=(b*y+c*z)*x+(c*y-b*z)*w
of s lead to inferior results.
Mihaly Markot calculated the global extrema to high accuracy.
The global minimum -2.95607850118520?9 is attained at
(a,b,c)=(9,1,1), (w,x,y,z)=(-0.6,-0.04181974?8,0.7,-0.2).
The global maximum 8.00936984210601?8 is attained at
(a,b,c)=(9,1,-1), (w,x,y,z)=(-0.9,0.2,0.3,0.04115383?9).
Thus the width of the range is 10.9654483432912?2
Here the number s after the ? denotes an uncertainty of s units
in the last place.
In addition, the challenge revealed an implementation inefficiency
in the SAGE package for arbitrary-precision interval arithmetic.
As observed by Paul Zimmermann, the square function xx^2 was
implemented as xx*xx rather than optimally with lower bound 0
when 0 in xx. (This will be fixed soon.)
Arnold Neumaier