[ Marquette | MSCS | Corliss | Vladik's Intervals ]
Interval FAQ: [ Entry page | Contents | Search ]
About Sun's f95 with Interval Support

Interval FAQ
Eugene Zima -- Inner interval arithmetic?

From Eugene Zima (ezima@daisy.uwaterloo.ca), Symbolic Computation Group, University of Waterloo:

Have you ever heard about "inner" interval analysis?

Response by Eugene Zima:

(ezima@daisy.uwaterloo.ca), Symbolic Computation Group, University of Waterloo.

The idea is simple. When you do some interval computations, you return an interval [a, b] such that "real (exact) interval value" of an expression [ar, br] is guaranteed to be included in [a, b]. Sometimes when we have good luck [a, b] = [ar, br]; sometimes [a, b] is very pessimistic, but refinement is a very time consuming problem.

Suppose we reverse the problem a little bit, and look for an "inner" interval value, i.e. such an interval value [ai, bi] of the same expression which is

  1. not trivial (ai <> bi), and
  2. guaranteed to be subinterval of [ar, br].
Again when we have good luck [ai, bi] = [ar, br]; when we have bad luck, [ai, bi] is trivial. However, sometimes neither of these situations occurs, and we have a good source of refinement.

The point is that [ai, bi] is as easy to compute as [a, b] (much easier than exact interval [ar, br]), and having both [a, b] and [ai, bi] it is sometimes an easy task to get a good refinement for [ar, br].

Have you ever heard something like this? I would appreciate any information or references.

Eugene Zima

Response by Rob Corless:

(Rob.Corless@uwo.ca), Department of Applied Mathematics, University of Western Ontario.

You explain it very clearly. I had heard of it before but never really used it.

Rob Corless

Response by George Corliss:

(georgec@mscs.mu.edu), Department of Mathematics, Statistics, and Computer Science, Marquette University.

I can point you to authors, but not to specific papers.

  1. Linear systems. Sergey Shary (shary@ict.nsc.ru) has written several articles applying and generalizing the concept of inner enclosures to systems of linear equations. I am not familiar with all his papers on the topic, but I think at least a couple have appeared in Interval Computations / Reliable Computing. Sergey distinguishes "for all" from "there exists".
  2. Variants of interval arithmetic. Svetoslav Markov (smarkov@iph.bio.acad.bg) has written many papers about various extensions of interval arithmetic. If I remember correctly, one of his applications was doing computations that could result in inner enclosures.
  3. Ordinary differential equations. Rudolf Lohner (Rudolf.Lohner@math.uni-karlsruhe.de) in his thesis, and I think in some articles, applied similar ideas to enclosure methods for ordinary differential equations. One of his ideas was to use the difference between the inner and the outer enclosure as a possible step size control.

    Martin Berz (berz@pilot.msu.edu ) may have used similar ideas, too.

There are probably others, but those are three I know.

George Corliss

Response by Sergey P. Shary:


Yes, these are the following papers:

S.P. Shary, Algebraic approach to the interval linear static identification, tolerance and control problems, or One more application of Kaucher arithmetic, Reliable Computing, Vol. 2 (1996), # 1, pp. 3--33.

S.P. Shary, Algebraic solutions to interval linear equations and their applications, in: Numerical Methods and Error Bounds, G. Alefeld and J. Herzberger, eds. Berlin, Akademie Verlag, 1996, pp.224--233.

S.P. Shary, A new approach to the analysis of static systems under interval uncertainty, in: Scientific Computing and Validated Numerics, G. Alefeld, A. Frommer, and B. Lang, eds., Berlin: Akademie Verlag, 1996, pp. 118--132.

In the last paper, I attempted to generalize my approach to a subclass of nonlinear algebraic systems as well.

For interval linear systems my software is "public domain".

Sergey Shary

Response by Svetoslav Markov:

(smarkov@iph.bio.bas.bg), Section "Biomathematics", Inst. of Mathematics and Computer Sci., Bulgarian Academy of Sciences.

I agree with all explanations. Inner interval operations are part of interval arithmetic. For instance, inner subtraction X = A-^-B is either the solution X of B + X = A, or MINUS the solution X of A - X = B, whichever has a solution). Another definition of inner subtraction is : Y = A-_i B is the solution of B + X = A or the solution of A - X = B. In this form it is a special case of the Minkowski subtraction (introduced by Hadwiger for convex bodies) or of so-called Hukuhara difference. Indeed, inner operations are important for finding tight ranges (inner but also outer). In fact many authors use them tacitly (instead of A-^-B one can say "the solution of B + X = A"). There exists a vast literature on related topics.

I can give more details if I know what is needed.

Svetoslav Markov

[ Marquette | MSCS | Corliss | Vladik's Intervals ]
Interval FAQ: [ Entry page | Contents | Search ]
About Sun's f95 with Interval Support

If you have a question related to validated computing, interval analysis, or related matters, I recommend

This page URL: http://www.mscs.mu.edu/~georgec/IFAQ/zima1.html
Last modified June 8, 1999. Send comments to (georgec@mscs.mu.edu)
Access count since 20 Apr 1999 : Graphical counter