The Arithmetic on Proper & Improper Intervals

Completion of Classical Interval Arithmetic

Other Related Terms: Kaucher interval arithmetic, generalized interval arithmetic, modal interval arithmetic, directed interval arithmetic


An algebraic extension of the "classical" interval arithmetic

Sunaga, T.: Theory of Interval Algebra and its Applications to Numerical Analysis. RAAG Memoirs, 2, 1958, pp. 29-46.

Moore, R. E.: Interval Analysis. Prentice Hall, Englewood Cliffs, N. J., 1966.

has been proposed notably by E. Kaucher:

Ortolf, H. -J.: Eine Verallgemeinerung der Intervallarithmetik. Geselschaft fuer Mathematik und Datenverarbeitung, Bonn 11, 1969, pp. 1-71.

Kaucher, E.: Ueber metrische und algebraische Eigenschaften einiger beim numerischen Rechnen auftretender Raume. Dissertation, Universitaet Karlsruhe, 1973.

Kaucher, E.: Algebraische Erweiterungen der Intervallrechnung unter Erhaltung der Ordnungs und Verbandstrukturen Computing, Suppl. 1, 1977, pp. 65-79.

Kaucher, E.: Ueber Eigenschaften und en der Anwendungsmoeglichkeiten der erweiterten Intervallrechnung und des hyperbolischen Fastkoerpers ueber R Computing, Suppl. 1, 1977, pp. 81-94.

Kaucher, E.: Interval Analysis in the Extended Interval Space IR Computing, Suppl. 2, 1980, pp. 33-49.

In Kaucher interval arithmetic intervals form a group with respect to addition and a complete lattice with respect to inclusion. A variant of Kaucher arithmetic adopted to semantic problems has been proposed and developed by E. Gardenes et al. under the name "modal interval arithmetic":

Gardenes, E.; Trepat, A.: Fundamentals of SIGLA, an Interval Computing System over the Completed Set of Intervals. Computing, 24, 1980, pp. 161-179.

Gardenes, E.; Trepat, A.; Janer, J. M.: SIGLA-PL/1 Development and Applications. In: Nickel, K.: Interval Mathematics 1980, Academic Press, 1980, pp. 301-315.

Gardenes, E.; Trepat, A.; Janer, J. M.: Approaches to Simulation and to the Linear Problem in the SIGLA System. Freiburger Interval-Berichte 81/8, 1981, pp. 1-28.

Gardenes, E.; Trepat, A.; Mieglo H.: Present Perspective of the SIGLA Interval System. Freiburger Interval-Berichte 82/9, 1982, pp. 1-65.

Gardenes, E.; Mielgo, H.; Trepat, A.: Modal intervals: Reason and Ground Semantics, In: K. Nickel (ed.): Interval Mathematics 1985, Lecture Notes in Computer Science, Vol. 212, Springer-Verlag, Berlin, Heidelberg, 1986, pp. 27-35.

SIGLA/X group: Modal Intervals. Basic Tutorial, Proceedings of the MISC'99 Workshop, Girona, 1999, pp. 157-227.

E. Gardenes, M.A. Sainz, L. Jorba, R. Calm, R. Estela, H. Mielgo, A. Trepat: Modal Intervals, Reliable Computing 7, 2001, pp. 77-111.

A lot of papers applying modal interval analysis to systems and control can be found at the web site of MiceLab.

S. Markov and others investigate the relation between the operations for generalized (Kaucher) intervals and the so-called inner operations for classic intervals. This leads to an interpretation of Kaucher intervals as classic intervals plus direction, hence the name "directed interval arithmetic":

Markov, S. M.: Extended Interval Arithmetic Involving Infinite Intervals. Mathematica Balkanica, New Series, 6, 3, 1992, pp. 269-304.

Markov, S. M.: On Directed Interval Arithmetic and its Applications. J. UCS, 1, 7, 1995, pp. 510-521. http://www.jucs.org/jucs_1_7

Thus directed interval arithmetic is a fertilization between Kaucher interval arithmetic and an exended interval arithmetic for classic intervals. The term "directed" is used to emphasize that proper and improper intervals are directed elements in the sense of

Markov, S. M.: On the Foundations of Interval Arithmetic. In: Alefeld, G.; Frommer, A.; Lang, B. (Eds.): Scientific Computing and Validated Numerics Akademie Verlag, Berlin, pp. 507-513.

that is intervals with sign. This fact leads to numerous new relations in interval arithmetic and to a simple derivation of the nonstandard (Markov's) interval arithmetic for normal intervals from directed interval arithmetic.

It is remarkable that generalized intervals have been briefly considered as early as in the papers by M. Warmus:

Warmus, M.: Calculus of Approximations. Bull. Acad. Pol. Sci., Cl. III, 4(5): 253-259, 1956.

Warmus, M.: Approximations and Inequalities in the Calculus of Approximations: Classification of Approimate Numbers. Bull. Acad. Pol. Sci., Cl. III, 9(4): 241-245, 1961.

Other theoretical results concern:

    -   some relations and transition formulae between the arithmetic on the set of proper and improper intervals (Kaucher/modal) and the arithmetic on the set of proper intervals extended by Markov's (inner) operations.
The complete transition formulae and relations are contained in a local publication of E. Popova in Bulgarian.

Dimitrova, N.; Markov, S. M.; Popova, E.: Extended Interval Arithmetics: New Results and Applications. In Atanassova, L.; Herzberger, J. (Eds.): Computer Arithmetic and Enclosure Methods. Elsevier Sci. Publishers B. V., 1992, pp. 225-232. (Abstract, Full Text - PDF 132K, PS 266K)

    -   the distributive relations in multiplication and addition of proper and improper intervals

Popova, E. D.: Multiplication Distributivity of Proper and Improper Intervals. Reliable Computing 7, 2, 2001, pp.129-140. (Abstract, Full Text - 194K PDF)

Popova, E. D.: All about Generalized Interval Distributive Relations. I. Complete Proof of the Relations. Sofia, March 2000. (Abstract, Full Text - 326K PDF)

    -   explicit representation of the product of two intervals (conventional - proper or more general - Kaucher/modal) involving zero by the operand end-points

E. Popova: On the Efficiency of Interval Multiplication Algorithms. Proceedings of III-rd International Conference ``Real Numbers and Computers'', Paris, April 27-29, 1998, 117-132. (Full Text - 180K PDF)

    -   results on parametric AE-solution sets

Popova, E., Krämer, W.: Characterization of AE Solution Sets to a Class of Parametric Linear Systems, Comptes rendus de l'Academie bulgare des Sciences 64(3):325-332, 2011.

Popova, E.: Explicit Description of AE Solution Sets for Parametric Linear Systems, SIAM Journal on Matrix Analysis and Applications, 2012, 33(4), 1172–1189. http://dx.doi.org/10.1137/120870359 (Preprint)

Popova, E., M. Hladik: Outer enclosures to the parametric AE solution set, Soft Computing (2013) 17:1403-1414. (http://dx.doi.org/10.1007/s00500-013-1011-0) (Preprint)

Popova, E.: Inner Estimation of the Parametric Tolerable Solution Set, Computers and Mathematics with Applications, 2013, 66(9):1655-1665. (http://dx.doi.org/10.1016/j.camwa.2013.04.007) (Preprint)

Popova, E.: Inner Estimation of Linear Parametric AE-Solution Sets, Comptes rendus de l'Academie Bulgare des Sciences 67(1) 13-20, 2014.

Popova, E.: Improved Enclosure for Some Parametric Solution Sets with Linear Shape, Computers and Mathematics with Applications, 68 (2014) 994-1005. (Preprint)

Popova, E.: On the Unbounded Parametric Tolerable Solution Set, Numerical Algorithms 69(1) (2015), 169-182. (http://dx.doi.org/10.1007/s11075-014-9888-y) (Preprint)

Popova, E.: Outer bounds for the parametric controllable solution set with linear shape,in M. Nehmeier et al. (Eds.): SCAN 2014, LNCS 9553, pp. 138–147, 2016. http://dx.doi.org/10.1007/978-3-319-31769-4_12 (Preprint)


Specification and Implementation

  • Specification
  • Specification of the scalar Basic Interval Arithmetic Subroutines (BIAS):

    Knueppel, O.: BIAS - Basic Interval Arithmetic Subroutines. Bericht 93.3, Technische Universitaet Hamburg-Harburg, Hamburg, 1993.

    is generalized to support interval arithmetic on directed intervals:

    Popova, E. D.; Ullrich, C. P.: Generalising BIAS Specification. Journal of Universal Computer Science, Vol. 3, no. 1, 1997, pp. 23-41. (Abstract, Full Text - 240K PDF)

    Generalized specifications are sufficiently precise and complete to include everything a user needs such as subroutine's purpose, method of invocation, details of its behaviour and communication with the environment.
    Hierarchical consistency of interval arithmetic specification with floating-point arithmetic, specified by the IEEE Floating-Point Standard 754/854, is provided by specification of operations and functions on intervals involving Not-A-Numbers (NaNs) and a model of interval arithmetic exceptions and their handling:

    Popova, E.: Interval Operations Involving NaNs. Reliable Computing, 2 (2), 1996, pp. 161-165. (PDF)

  • PASCAL-XSC Module
  • exi_ari.p (50966 bytes ASCII file) is a self-contained PASCAL-XSC module for directed interval arithmetic. Using data type INTERVAL which is part of the language core of PASCAL-XSC, exi_ari module supplies all interval arithmetic operations, functions and procedures overloaded to produce correct results for directed intervals, too, as well as many other functions necessary for computations in extended interval arithmetic spaces.
    Short overview of the directed interval arithmetic and description of the exi_ari module is given in

    Popova, E.: Extended Interval Arithmetic in IEEE Floating-Point Environment. Interval Computations, No. 4, 1994, pp. 100-129. (FullText - 200K PDF, 385K PS)

  • Mathematica Package
  • An attractive goal is to make use of the algebraic completeness of the directed interval arithmetic embedding it in a computer algebra system and investigating how the algebraic and other properties of this arithmetic can be exploited for algebraic and symbolic manipulation of interval expressions, development of explicit algebraic interval methods, their effective implementation, as well as of studying other aspects of the symbolic-numeric computations. Mathematica package directed.m (21826 bytes ASCII file) extends Mathematica interval capabilities by providing a new data object (Directed) representing directed multi-intervals, as well as operations and functions for basic arithmetic on them. A full description of the package and many application functions are given in

    Popova, E; Ullrich, C.: Directed Interval Arithmetic in Mathematica: Implementation and Applications. Technical Report 96-3, Universitaet Basel, January 1996. tr96-3.ps (305800 bytes PostScript file)

    Y. Akyildiz, E. Popova, Ch. Ullrich: Computer Algebra Support for the Completed Set of Intervals. MISC'99: Preprints of the Workshop on Applications of Interval Analysis to Systems and Control, Girona, Spain, 1999, pp. 3-12. (Full Text - PDF)

  • Dynamic Web drawing: AE Solution Sets of Interval Linear Systems

Applications

  • Interval Model of Linear Equilibrium Equations in Mechanics
  • Popova, E.: Improved solution to the generalized Galilei’s problem with interval loads, Archive of Applied Mechanics, online Sept. 2016. The final publication is available at Springer via http://dx.doi.org/10.1007/s00419-016-1180-2. For a free full-text view-only version click here. (Preprint)

    Popova, E.: Interval Model of Equilibrium Equations in Mechanics, in: Freitag, S., Muhanna, R. L., Mullen, R. L. (eds.) Proceedings of REC’2016, Ruhr University Bochum, pp. 241–255, 2016.

  • Algebraic Manipulation of Interval Formulas
  • Popova, E. D.; Ullrich, C.: Simplification of Symbolic-Numerical Interval Expressions In O. Gloor (Ed.): Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, ACM Press, 1998, pp. 207-214.  (Full Text - 180K PS,  220K PDF)

  • Algebraic Solutions of Linear Equations
  • Markov, S. M.; Popova, E. D.; Ullrich, C.: On the Solution of Linear Algebraic Equations Involving Interval Coefficients. In S. Margenov, P. Vassilevski (Eds.): Iterative Methods in Linear Algebra, II, IMACS Series in Computational and Applied Mathematics, 3 1996, pp. 216-225. (Abstract, Full Text)

    Popova, E. D.: Algebraic Solutions to a Class of Interval Equations Journal of Universal Computer Science, Vol. 4, no. 1, 1998, pp. 48-67. (Abstract, Full Text)

  • Efficient Inner Bounds for the solution set hull of parametric and non-parametric interval linear systems
  • Popova, E. and W. Kraemer: Inner and Outer Bounds for Parametric Linear Systems. J. Computational and Applied Mathematics 199(2), 2007, 310-316. (Abstract, Full Text )

  • Parametric Gauss-Seidel Iteration
  • Popova, E. D.: On the Solution of Parametrised Linear Systems. In: W. Kraemer, J. Wolff von Gudenberg (Eds.): Scientific Computing, Validated Numerics, Interval Methods. Kluwer Acad. Publishers, 2001, pp. 127-138. (Full Text - PS 151K, PDF 200K)

  • Solving Linear Systems whose Input Data are Rational Functions of Interval Parameters
  • Popova, E.: Solving Linear Systems whose Input Data are Rational Functions of Interval Parameters. In: T. Boyanov et al. (Eds.) Numerical Methods and Applications, LNCS 4310, 2007, Springer Berlin/Heidelberg, 345-352. (Abstract)
    Expanded version in: Preprint No. 3/2005, Institute of Mathematics and Informatics, BAS, Sofia, December 2005. (Full Text - PDF 550K)

    Popova, E., R. Iankov, Z. Bonev: Bounding the Response of Mechanical Structures with Uncertainties in all the Parameters . In R.L.Muhannah, R.L.Mullen (Eds): Proceedings of the NSF Workshop on Reliable Engineering Computing (REC), Svannah, Georgia USA, Feb. 22-24, 2006, 245-265. (Full Text - PDF 352K)

  • Applications in Discrete Mechanics
  • F. Tonon, Using Extended Interval Algebra in Discrete Mechanics. NSF Workshop “Reliable Engineering Computing 2006: Modeling Errors and Uncertainty in Engineering Computations”, Rafi L. Muhanna and Robert L. Mullen eds., February 22-24, 2006, Georgia Institute of Technology, Savannah. (PDF)

  • Yan Wang's articles on
  • Uncertainty Quantification in Modeling & Simulation

  • The articles of MiceLab (Modals Intervals and Control Engineering)

Link to the Interval Computations website.


Questions/Comments

Any questions and/or comments are welcome. Please contact Evgenija D. Popova at

Created: September 10, 1996, Last modified: Sept. 2016.