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.

All the relevant results on Modal Interval Analysis are collected in a book “Modal Interval Analysis — New Tools for Numerical Information”.

S. M. 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 Popova, E.D., Generalized Interval Arithmetic - Properties and Implementation, PhD thesis, Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, Sofia, 2000.

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, in Popova, E.D., Generalized Interval Arithmetic - Properties and Implementation, PhD thesis, Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, Sofia, 2000.

    -   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.: 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.: Solvability of Parametric Interval Linear Systems of Equations and Inequalities, SIAM Journal on Matrix Analysis and Applications 36 (2015) 615-633. http://dx.doi.org/10.1137/140966459

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., 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)

Popova, E.: Parameterized Outer Estimation of AE-Solution Sets to Parametric Interval Linear Systems, Applied Mathematics and Computation 311 (2017) 353–360. http://dx.doi.org/10.1016/j.amc.2017.05.042

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 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 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)

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 87 (2017) (1):115-127. http://dx.doi.org/10.1007/s00419-016-1180-2. (Preprint)

    Popova, E.D.: Equilibrium equations in interval models of structures. Int. J. Reliability and Safety, 12, 1/2, 2018, 218-235. https://doi.org/10.1504/IJRS.2018.10013814

    Popova, E.D.: Algebraic solution to interval equilibrium equations of truss structures. Applied Mathematical Modelling 65 (2019) 489-506. https://doi.org/10.1016/j.apm.2018.08.021

    Popova, E.D., Elishakoff, I.: Novel interval model applied to derived variables in static and structural problems. Archive of Applied Mechanics (2020) 90(4):869-881. https://doi.org/10.1007/s00419-019-01644-8 Read and share here: https://rdcu.be/b25i5. (Preprint)

  • 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

See also the relevant articles of S. Shary and A. Goldsztejn.
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: March 2020.