Re: Unification of motion 25 and 27
On Sun, July 10, 2011 20:00, Jürgen Wolff von Gudenberg wrote:
> Nate, Marco and myself have unified motions 25 and 27.
==================================================================
The new Motion 25+27 is indeed much simpler than Motion 26, but it
violates a basic principle commonly attributed to Albert Einstein
(http://rescomp.stanford.edu/~cheshire/EinsteinQuotes.html):
''Everything should be made as simple as possible,
but not simpler.''
Indeed, in the interest of maximal simplicity, Version 1.5 of
Motion 25+27 became far too sloppy. It does not address necessary
results about nontrivial uses of the decorations.
Instead, the main results claimed (Theorem 3) is in fact false
(see below), leading to wrong conclusions and violating the safety
requirement for interval methods.
Arnold Neumaier
=====================================================================
Detailed critique:
Section 1.1.
There is no discernible difference between functions and elementary
operations, so that the semantics remains unclear. In particular, the
semantics of Definition 1 is appropriate only for decorations of a
single elementary operation. E.g., f(x)=\sqrt(x-x) is everywhere
defined and continuous but f([-1,1]_saf) has the decoration con only.
Definition 1 does not explain the semantics of all decorations. What is
the difference between Empty_saf, Empty_def, and Empty_ndf?
Section 1.3.1.
Definition 6 would give the decoration saf to an ill-formed literal
constant. Thus ill-formed stuff would become legitimated....
Definition 7 is not properly formulated, as the formulation given
does not say anything about how to compose subtrees but only how to
compose leaves. Moreover, it is not clear whether the tree contains
symbolic information about the expression or only decorated intervals
reflecting the history of evaluating an expression.
The propagation rule (1) in Definition 8 is identical to the one used
in Motion 26. Thus the substance of the motion is contained in that
of the (much more carefully formulated) Motion 26, except that only a
subset of the decorations treated there is part of the above motion.
Theorem 3 is not obvious but false since for f(x)=sqrt(x-x-1), which
is nowhere defined, we get
f([0,2])=sqrt([0,2]-[0,2]-1)=sqrt([-3,1])=[0,1]
with computed decoration con, which is above the true decoratio ndf.
The containment order discussed in Motion 26 is necessary to cover the
correct propagation behavior.
Also, the theorem does not cover the content one would like
to extract from a decorated computation. Relying only on the statement
of the theorem, one could not conclude anything from a computed
decoration ndf, since the true decoration could have been anything
above it. This would make the decoration ndf useless in branch and
bound algorithms. Thus the theory is incomplete and myust be augmented
to a full set of statements that one can rely on after having computed
a decorated result.
Section 1.3.2.
The semantics stated is appropriate only for decorations of a
single elementary operation. E.g., f(x)=\sqrt(x-x) is everywhere
defined and continuous but f([-1,1]_saf) has the decoration con only.
It is not clear how lines 3-6 on p.5 imply (as claimed on line 7)
line 8-10. In fact, the latter lines are meaningless as stated since
(unlike in Motion 26) containment is not defined for decorated
intervals.
Section 1.3.3.
The treatment of intersections and unions is inconsistent.
Remark 1 refers to intersections of decorated intervals although the
introduction before Definition 1 says that decorations are associated
with functions. Intersection is not a function like sqrt.
Trees involving both arithmetical operations and intersections may be
meaningless, e.g., f(x)= x/((x+1) intersect x^2). Definition 7 does
not catch the bug but will give a safe answer for f([1,3]).
It is not clear why the motion distinguishes between hull and union.
Unlike claimed on line 6 of the section, the set-theoretic union is
not defined everywhere in any useful sense since the union of real
numbers is undefined, and the union of disjoint intervals is not an
interval.
It does not make sense that according to Definition 8,
Empty_ndf union [1,2]_saf = [1,2]_ndf
rather than
Empty_ndf union [1,2]_saf = [1,2]_saf.
Section 1.4.
Definition 9 lacks a condition on the decorations. It would allow
F(xx_d):=sqrt(xx)_saf for every decoration d and every interval xx
to define a decorated interval extension of f(x)=sqrt(x), which loses
decoration information and thus may giver too optimistic results.
Theorem 4 while valid is irrelevant for actual computations.
The isotonicity of a range englosure is nice if one happens to have it
but is not essential. For example, centered forms using slopes are not
isotone but very useful for good range enclosures. Most likely,
isotonicity also fails on efficient outward rounding implementations of
multiprecision intervals.
Theorem 5 has empty content since it says nothing about decorations,
and hence is not a FTDIA.
A true FTDIA must allow to conclude from favorable decorations that
the function has on the input interval certain guaranteed properties,
such as definedness or continuity.
The statement about comparisons in the last paragraph of the section
is meaningless. Indeed, comparisons are treated inadequately,
the function defined by
f(x)=1-x if x<0, f(x)=x otherwise
is not covered by Definition 7 for an expression tree.
No matter how the comparisons are interpreted, an interval evaluation
will give the wrong decoration saf although the function is
discontinuous. (In Motion 26, this can be handled correctly using the
case function.)
Section 2.1.
Line 2 says that a decoration is a pair of a function and an interval,
but according to Section 1 it isn't.