Interval arithmetic

Journal of the ACM - Tập 48 Số 5 - Trang 1038-1068 - 2001
Timothy J. Hickey1, Qun Ju1, M. H. van Emden2
1Brandeis University, Waltham, Massachusetts
2University of Victoria, Victoria, B.C., Canada

Tóm tắt

We start with a mathematical definition of a real interval as a closed, connected set of reals. Interval arithmetic operations (addition, subtraction, multiplication, and division) are likewise defined mathematically and we provide algorithms for computing these operations assuming exact real arithmetic. Next, we define interval arithmetic operations on intervals with IEEE 754 floating point endpoints to be sound and optimal approximations of the real interval operations and we show that the IEEE standard's specification of operations involving the signed infinities, signed zeros, and the exact/inexact flag are such as to make a correct and optimal implementation more efficient. From the resulting theorems, we derive data that are sufficiently detailed to convert directly to a program for efficiently implementing the interval operations. Finally, we extend these results to the case of general intervals, which are defined as connected sets of reals that are not necessarily closed.

Từ khóa


Tài liệu tham khảo

ALEFELD , G. , AND HERZBERGER , J. 1983. Introduction to Interval Computations . Academic Press , Orlando, Fla .]] ALEFELD, G., AND HERZBERGER, J. 1983. Introduction to Interval Computations. Academic Press, Orlando, Fla.]]

BENHAMOU , F. , AND OLDER , W. J. 1997 . Applying interval arithmetic to real, integer, and Boolean constraints . J. Logic Prog. 32 , 1 - 24 .]] BENHAMOU,F.,AND OLDER, W. J. 1997. Applying interval arithmetic to real, integer, and Boolean constraints. J. Logic Prog. 32, 1-24.]]

FORSYTHE , G. E. 1970 . Pitfalls of computation, or why a math book isn't enough . Amer. Math. Monthly 77 , 931 - 956 .]] FORSYTHE, G. E. 1970. Pitfalls of computation, or why a math book isn't enough. Amer. Math. Monthly 77, 931-956.]]

HAMMER , R. , HOCKS , M. , KULISCH , U. , AND RATZ , D. 1993. Numerical Toolbox for Verified Computing I . Springer-Verlag , New York .]] HAMMER, R., HOCKS, M., KULISCH, U., AND RATZ, D. 1993. Numerical Toolbox for Verified Computing I. Springer-Verlag, New York.]]

HANSEN , E. 1992. Global Optimization Using Interval Analysis . Marcel Dekker .]] HANSEN, E. 1992. Global Optimization Using Interval Analysis. Marcel Dekker.]]

HICKEY , T. J. 2000 a. CLIP: A CLP(Intervals) Dialect for Metalevel Constraint Solving. In Proceedings of PADL'00 . Lecture Notes in Computer Science , vol. 1753 . Springer-Verlag , New York .]] HICKEY, T. J. 2000a. CLIP: A CLP(Intervals) Dialect for Metalevel Constraint Solving. In Proceedings of PADL'00. Lecture Notes in Computer Science, vol. 1753. Springer-Verlag, New York.]]

HICKEY , T. J. 2000 b. Analytic constraint solving and interval arithmetic . In Proceedings of the 27th Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (Jan.). ACM , New York.]] 10.1145/325694.325738 HICKEY, T. J. 2000b. Analytic constraint solving and interval arithmetic. In Proceedings of the 27th Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (Jan.). ACM, New York.]] 10.1145/325694.325738

HICKEY , T. J. , QIU , Z. , AND VAN EMDEN , M. H. 2000 . Interval constraint plotting for interactive visual exploration of implicitly defined relations. Special issue on Reliable Geometric Computations . Rel. Comput. 6 , 1 .]] HICKEY, T. J., QIU, Z., AND VAN EMDEN, M. H. 2000. Interval constraint plotting for interactive visual exploration of implicitly defined relations. Special issue on Reliable Geometric Computations. Rel. Comput. 6,1.]]

KAHAN , W. M. 1968. A more complete interval arithmetic. Tech. rep. Univ . Toronto, Toronto , Ont., Canada .]] KAHAN, W. M. 1968. A more complete interval arithmetic. Tech. rep. Univ. Toronto, Toronto, Ont., Canada.]]

LIPSCHUTZ S. 1965. General Topology. Schaum's Outline Series.]] LIPSCHUTZ S. 1965. General Topology. Schaum's Outline Series.]]

MOORE , R. E. 1966. Interval Analysis . Prentice-Hall , Englewood Cliffs , N.J.]] MOORE, R. E. 1966. Interval Analysis. Prentice-Hall, Englewood Cliffs, N.J.]]

NOVOA M. 1993. Theory of preconditioners for the interval Gauss-Seidel method and exis-tence/ uniqueness theory with interval Newton methods. Dept. Mathematics , Univ. Southwestern Louisiana .]] NOVOA M. 1993. Theory of preconditioners for the interval Gauss-Seidel method and exis-tence/ uniqueness theory with interval Newton methods. Dept. Mathematics, Univ. Southwestern Louisiana.]]

OLDER W. J. 1989. Interval arithmetic specification. Tech. rep. Bell-Northern Research Computing Research Laboratory.]] OLDER W. J. 1989. Interval arithmetic specification. Tech. rep. Bell-Northern Research Computing Research Laboratory.]]

RALL , L. B. 1969. Computational solution of nonlinear operator equations . Wiley , New York .]] RALL, L. B. 1969. Computational solution of nonlinear operator equations. Wiley, New York.]]

RATZ , D. 1996. On extended interval arithmetic and inclusion isotonicity . Institut fur Angewandte Mathematik, Universit~t Karlsruhe .]] RATZ, D. 1996. On extended interval arithmetic and inclusion isotonicity. Institut fur Angewandte Mathematik, Universit~t Karlsruhe.]]

STOLFI J. AND DE FIGUEIREDO L. 1997. Self-Validated Numerical Methods and Applications. IMPA Rio de Janiero Brazil.]] STOLFI J. AND DE FIGUEIREDO L. 1997. Self-Validated Numerical Methods and Applications. IMPA Rio de Janiero Brazil.]]

VAN HENTENRYCK , P. , MICHEL , L. , AND DEVILLE , Y. 1997 . Numerica: A Modeling Language for Global Optimization . MIT Press , Cambridge, Mass .]] VAN HENTENRYCK, P., MICHEL, L., AND DEVILLE, Y. 1997. Numerica: A Modeling Language for Global Optimization. MIT Press, Cambridge, Mass.]]

WALSTER G. W. 1996. The extended real interval system. Available on the internet http://www.mscs.mu.edu / globsol / readings.html.]] WALSTER G. W. 1996. The extended real interval system. Available on the internet http://www.mscs.mu.edu / globsol / readings.html.]]

WALSTER G.W. AND HANSEN E. R. 1998. Interval Algebra Composite Functions and Dependence in Compilers. Available on the internet http://www.mscs.mu.edu /globsol /readings.html.]] WALSTER G.W. AND HANSEN E. R. 1998. Interval Algebra Composite Functions and Dependence in Compilers. Available on the internet http://www.mscs.mu.edu /globsol /readings.html.]]

Thông tin
Thông tin xuất bản

Journal of the ACM

Tập 48 Số 5

1038-1068

Thông tin tác giả