complex bakeoffs and error bounds

[Kearfott R. Baker]

> Sender: prattacs.Stanford.EDU
> Status: R
> 
> 
> 	Interval arithmetic is one approach to dealing with uncertainty.
> 
> Indeed.  However the definition of "interval" as a pair [a,b], which
> works fine for the reals, makes no sense in the complex plane.  The
> right definition of "interval" is "convex set", and at dimensions
> higher than one this is still too weak to be useful.
> 
> A more robust and generally useful definition would I think be "ball"
> (in the sense of "interior of sphere").  Thus an "interval" would
> consist of a single quantity together with a radius bounding the
> error.  This works not just for the complex numbers but for any Banach
> space if just adding and subtracting, and for any Hilbert space if also
> multiplying.  The passage to these more general spaces should permit
> the integration of interval arithmetic with more traditional error
> analysis for matrix packages.
> 
Both circular arithmetic and rectangular arithmetic have been
considered in higher (but still finite) dimensional spaces.
Each has its advantages and disadvantages.

> What *doesn't* change in this passage is the real value of real-valued
> interval arithmetic.  The trouble with interval arithmetic is that it
...
> arithmetic randomly walks around the right answer and does not deviate
> anywhere near as far from it as interval arithmetic conservatively
> calculates to be possible.
> 
> The trouble with interval arithmetic is that every answer is innocent
> (= possibly the true answer) until proven guilty, in the *mathematical*
> sense of "proven".  With long computations, as with long trials, that
> gets to be an impractically tall order.
> 

This property can be construed to be both the "trouble" and the
strength of interval arithmetic.  I note that, several decades
ago, excessive claims may have been made (at least for the time)
for interval computations.  Experts in the field have since come
to realize that "naive" interval arithmetic often is not useful.
However, if one realizes where and how overestimation occurs in
interval arithmetic, algorithms can be designed to make
effective use of its verification properties.  In particular,
the computations can, many times, be arranged so that the answer
that interval arithmetic gives IS the set of solutions, or
differs from the set of solutions by an amount that is not
excessive.

For example, multivariate interval Newton methods are known to
be locally quadratically convergent in the sense that, starting
with a box in n-space of small enough initial diameter, the
diameters of the resulting boxes tend to zero quadratically.  In
this case, long computations cause the intervals to get SMALLER.

A reasonable and efficient use of interval arithmetic would be
to construct narrow and rigorous bounds around a solution (of a
linear or nonlinear system) that has been obtained via floating
point computations.  This is possible because interval Newton
methods supply computational fixed point theorems similar to the
Kantorovich theorem.  However, it has been mathematically proven
that certain interval Newton methods are sharper than
application of the Kantorovich theorem.

Another application of interval arithmetic is to obtain
variation information to take the place of e.g. Lipschitz constants.
Yes, interval evaluations do often overestimate the range of the
function.  However, they often compare favorably with other
techniques, such as ad hoc techniques for obtaining Lipschitz
constants, both in ease of use (assuming proper language
support) and sharpness of the bounds.


---------------------------------------------------------------
R. Baker Kearfott,       rbkausl.edu      (318) 482-5346 (fax)
(318) 482-5270 (work)                     (318) 981-9744 (home)
URL: ftp://interval.usl.edu/pub/interval_math/www/kearfott.html
Department of Mathematics, University of Southwestern Louisiana
---------------------------------------------------------------