Interval arithmetic

Interval arithmetic is a specific type of computer arithmetic for (mathematical) intervals.^[1]^[2]^[3] It is mainly used for the automated detection of errors. There is a value, which isn't known exactly, but which can be given by an interval: the value is known to be inside the interval. There's a function to calculate the error. This function should be given the unknown value, but instead can only be given the interval. The result is a function which will map intervals.

Interval arithmetic can be used to treat rounding errors, or to treat insecurities with measurements: Each measurement has a certain error, which cannot be determined exactly.

Definition

For real intervals (interval of real numbers), interval arithmetic is defined as follows:^[1]^[2]^[3]

Addition: $[x_{1},x_{2}]+[y_{1},y_{2}]=[x_{1}+y_{1},x_{2}+y_{2}]$
Subtraction: $[x_{1},x_{2}]-[y_{1},y_{2}]=[x_{1}-y_{2},x_{2}-y_{1}]$
Multiplication: $[x_{1},x_{2}]\cdot [y_{1},y_{2}]=[\min(x_{1}y_{1},x_{1}y_{2},x_{2}y_{1},x_{2}y_{2}),\max(x_{1}y_{1},x_{1}y_{2},x_{2}y_{1},x_{2}y_{2})]$
Division:

{\frac {[x_{1},x_{2}]}{[y_{1},y_{2}]}}=[x_{1},x_{2}]\cdot {\frac {1}{[y_{1},y_{2}]}},

where

{\begin{aligned}{\frac {1}{[y_{1},y_{2}]}}&=\left[{\tfrac {1}{y_{2}}},{\tfrac {1}{y_{1}}}\right]&&0\notin [y_{1},y_{2}]\\{\frac {1}{[y_{1},0]}}&=\left[-\infty ,{\tfrac {1}{y_{1}}}\right]\\{\frac {1}{[0,y_{2}]}}&=\left[{\tfrac {1}{y_{2}}},\infty \right]\\{\frac {1}{[y_{1},y_{2}]}}&=\left[-\infty ,{\tfrac {1}{y_{1}}}\right]\cup \left[{\tfrac {1}{y_{2}}},\infty \right]=[-\infty ,\infty ]&&0\in (y_{1},y_{2})\end{aligned}}

Applications

Interval arithmetic is mainly used in the field of validated numerics.^[4] It is also used in other technical areas.^[5]

Implementations

Since the birth of interval arithmetic, many experts have made interval arithmetic programs. The most famous works are INTLAB (made with MATLAB),^[6] arb,^[7] JuliaIntervals,^[8]^[9] and kv.^[10]

Community

There are several international conferences about interval arithmetic. One of the most largest meeting is the International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics^[11]^[12]^[13] (usually abbreviated as SCAN). There are also SWIM (Small Workshop on Interval Methods), PPAM (International Conference on Parallel Processing and Applied Mathematics), and REC (International Workshop on Reliable Engineering Computing).

References

↑ ^1.0 ^1.1 Mayer, G. (2017). Interval analysis: and automatic result verification. Walter de Gruyter GmbH & Co KG.
↑ ^2.0 ^2.1 Moore, R. E., Kearfott, R. B., & Cloud, M. J. (2009). Introduction to Interval Analysis. Society for Industrial and Applied Mathematics.
↑ ^3.0 ^3.1 Alefeld, G., & Mayer, G. (2000). Interval analysis: theory and applications. Journal of Computational and Applied Mathematics, 121(1-2), 421-464.
↑ Tucker, W. (2011). Validated Numerics: A Short Introduction to Rigorous Computations. Princeton University Press.
↑ Jaulin, L. Kieffer, M., Didrit, O. Walter, E. (2001). Applied Interval Analysis. Berlin: Springer.
↑ S.M. Rump: INTLAB - INTerval LABoratory. In Tibor Csendes, editor, Developments in Reliable Computing, pages 77-104. Kluwer Academic Publishers, Dordrecht, 1999.
↑ Johansson, F. (2017). Arb: efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Transactions on Computers, 66(8), 1281-1292.
↑ Sanders, D. P., Benet, L., & Kryukov, N. (2016). The julia package ValidatedNumerics. jl and its application to the rigorous characterization of open billiard models. SCAN 2016, 124.
↑ ValidatedNumerics.jl: a new framework in Julia, David P. Sanders and Luis Benet, SCAN 2018.
↑ Overview of kv – a C++ library for verified numerical computation, Masahide Kashiwagi, SCAN 2018.
↑ Scientific Computing, Computer Arithmetic, and Validated Numerics 16th International Symposium, SCAN 2014, Würzburg, Germany, September 21-26, 2014. Revised Selected Papers. Editors: Marco Nehmeier, Jürgen Wolff von Gudenberg, Warwick Tucker. Published by Springer.
↑ 13th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Verified Numerical Computations (SCAN'2008), Proceedings of a meeting held 29 September - 3 October 2008, El Paso, Texas, USA. Special volume devoted to materials presented at SCAN 2012. Published by the Institute of Computational Technologies
↑ 12th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (SCAN 2006), Proceedings of a meeting held 26-29 September 2006, Duisburg, Germany. Published by the Institute of Electrical and Electronics Engineers (IEEE)

Other websites

Interval arithmetic (Wolfram Mathworld)
Interval Methods from Arnold Neumaier Archived 2020-12-02 at the Wayback Machine, University of Vienna

Workshops

Libraries

INTLAB, Institute for Reliable Computing Archived 2020-01-30 at the Wayback Machine
Ball arithmetic by Joris van der Hoeven
kv - a C++ Library for Verified Numerical Computation
Arb - a C library for arbitrary-precision ball arithmetic
Interval and related software Archived 2020-05-13 at the Wayback Machine

This short article about technology can be made longer. You can help Wikipedia by adding to it.

[mayer-1] 1.0 ^1.1 Mayer, G. (2017). Interval analysis: and automatic result verification. Walter de Gruyter GmbH & Co KG.

[mkc-2] 2.0 ^2.1 Moore, R. E., Kearfott, R. B., & Cloud, M. J. (2009). Introduction to Interval Analysis. Society for Industrial and Applied Mathematics.

[am-3] 3.0 ^3.1 Alefeld, G., & Mayer, G. (2000). Interval analysis: theory and applications. Journal of Computational and Applied Mathematics, 121(1-2), 421-464.

[4] Tucker, W. (2011). Validated Numerics: A Short Introduction to Rigorous Computations. Princeton University Press.

[5] Jaulin, L. Kieffer, M., Didrit, O. Walter, E. (2001). Applied Interval Analysis. Berlin: Springer.

[6] S.M. Rump: INTLAB - INTerval LABoratory. In Tibor Csendes, editor, Developments in Reliable Computing, pages 77-104. Kluwer Academic Publishers, Dordrecht, 1999.

[7] Johansson, F. (2017). Arb: efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Transactions on Computers, 66(8), 1281-1292.

[8] Sanders, D. P., Benet, L., & Kryukov, N. (2016). The julia package ValidatedNumerics. jl and its application to the rigorous characterization of open billiard models. SCAN 2016, 124.

[9] ValidatedNumerics.jl: a new framework in Julia, David P. Sanders and Luis Benet, SCAN 2018.

[10] Overview of kv – a C++ library for verified numerical computation, Masahide Kashiwagi, SCAN 2018.

[scan2014-11] Scientific Computing, Computer Arithmetic, and Validated Numerics 16th International Symposium, SCAN 2014, Würzburg, Germany, September 21-26, 2014. Revised Selected Papers. Editors: Marco Nehmeier, Jürgen Wolff von Gudenberg, Warwick Tucker. Published by Springer.

[scan2008-12] 13th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Verified Numerical Computations (SCAN'2008), Proceedings of a meeting held 29 September - 3 October 2008, El Paso, Texas, USA. Special volume devoted to materials presented at SCAN 2012. Published by the Institute of Computational Technologies

[scan2006-13] 12th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (SCAN 2006), Proceedings of a meeting held 26-29 September 2006, Duisburg, Germany. Published by the Institute of Electrical and Electronics Engineers (IEEE)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]