Theories of
INTERVAL ARITHMETIC Mathematical Foundations and Applications
HEND DAWOOD Department of Mathematics Cairo University
Theories of Interval Arithmetic Mathematical Foundations and Applications
Hend Dawood Cairo University
Hend Dawood Department of Mathematics Faculty of Science Cairo University Giza, Egypt
c LAP LAMBERT Academic Publishing, 2011 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without the prior permission of the copyright owner.
ISBN: 978-3-8465-0154-2
Publisher: LAP LAMBERT Academic Publishing GmbH & Co. KG Dudweiler Landstr. 99 66123 Saarbrücken Germany Register court/number: Handelsregister Amtsgericht Saarbrücken HRA 10752 Identi…cation Number (Verkehrsnummer): 12917 Partner with unlimited liability/Persönlich haftende Gesellschafterin: VDM Management GmbH Register court/number: Handelsregister Amtsgericht Saarbrücken HRB 18918 Managing directors/Geschäftsführer: Thorsten Ohm (CEO), Dr. Wolfgang Philipp Müller, Esther von Krosigk, Christoph Schulligen Responsible in accordance with Art. 10 par. 3 MDStV (German Interstate Agreement on Media Services): Dr. Wolfgang Philipp Müller
“This new book by Hend Dawood is a fresh introduction to some of the basics of interval computation. It stops short of discussing the more complicated subdivision methods for converging to ranges of values, however it provides a bit of perspective about complex interval arithmetic, constraint intervals, and modal intervals, and it does go into the design of hardware operations for interval arithmetic, which is something still to be done by computer manufacturers.”
-Ramon E. Moore The Founder of Interval Computations Professor Emeritus of Computer and Information Science, Department of Mathematics, The Ohio State University, Columbus, U.S.A.
Dedicated to my family.
h
Contents
1 Prologue: A Weapon Against Uncertainty
1
1.1 What Interval Arithmetic is and Why it is Considered . . . . . . . . . . . . . . .
1
1.2 A History Against Uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2 The Classical Theory of Interval Arithmetic 2.1 Algebraic Operations for Interval Numbers . . . . . . . . . . . . . . . . . . . . .
7 7
2.2 Point Operations for Interval Numbers . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Algebraic Properties of Interval Arithmetic . . . . . . . . . . . . . . . . . . . . . 15 3 Complex Interval Arithmetic
25
3.1 Algebraic Operations for Complex Interval Numbers . . . . . . . . . . . . . . . . 26 3.2 Point Operations for Complex Interval Numbers . . . . . . . . . . . . . . . . . . 30 3.3 Algebraic Properties of Complex Interval Arithmetic . . . . . . . . . . . . . . . 31 4 Alternate Theories of Interval Arithmetic
33
4.1 The Interval Dependency Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.2 Constraint Interval Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.3 Modal Interval Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5 Computational Applications of Interval Arithmetic
47
5.1 Estimates of the Image of Real Functions . . . . . . . . . . . . . . . . . . . . . . 48 5.2 Bounding the Error Term in Taylor’s Series . . . . . . . . . . . . . . . . . . . . . 53 5.3 Estimates of De…nite Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 i
CONTENTS 6 Hardware Implementation of Interval Arithmetic
61
6.1 Machine Interval Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 6.1.1
Rounded-Outward Interval Arithmetic . . . . . . . . . . . . . . . . . . . . 62
6.1.2
Rounded-Upward Interval Arithmetic . . . . . . . . . . . . . . . . . . . . 66
6.2 An Interval Adder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 6.3 An Interval Squarrer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7 Epilogue: What is Next?
71
7.1 A View to the Future of Interval Computations . . . . . . . . . . . . . . . . . . 71 7.2 More Scienti…c Applications of Interval Arithmetic
. . . . . . . . . . . . . . . . 72
7.3 Current and Future Research in Interval Arithmetic . . . . . . . . . . . . . . . . 73 7.4 Suggestions for Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 A A Verilog Description for the 4-by-4 Bit Multiplier
77
A.1 Verilog Description of the 4-by-4 Bit Multiplier Circuitry . . . . . . . . . . . . . 78 A.1.1 Verilog Description of the Half Adder . . . . . . . . . . . . . . . . . . . . 78 A.1.2 Verilog Description of the Full Adder . . . . . . . . . . . . . . . . . . . . 78 A.1.3 Verilog Description of the 4 -by-4 Bit Multiplier . . . . . . . . . . . . . . 79 A.2 Verilog Description of the 4-by-4 Bit Multiplier Simulation . . . . . . . . . . . . 85 B A Verilog Description for the Interval Squarrer
91
B.1 Verilog Description of the Interval Squarrer Circuitry . . . . . . . . . . . . . . . 91 B.1.1 Verilog Description of the 8-Bit Comparator . . . . . . . . . . . . . . . . 92 B.1.2 Verilog Description of the Interval Squarrer . . . . . . . . . . . . . . . . 92 B.2 Verilog Description of the Interval Squarrer Simulation . . . . . . . . . . . . . . 94
ii
Preface
Scientists are, all the time, in a struggle with uncertainty which is always a threat to a trustworthy scienti…c knowledge. A very simple and natural idea, to defeat uncertainty, is that of enclosing uncertain measured values in real closed intervals. On the basis of this idea, interval arithmetic is constructed. The idea of calculating with intervals is not completely new in mathematics: the concept has been known since the third century BC, when Archimedes used guaranteed lower and upper bounds to compute his constant . Interval arithmetic is now a broad …eld in which rigorous mathematics is associated with scienti…c computing. This connection makes it possible to solve uncertainty problems that cannot be e¢ ciently solved by ‡oating-point arithmetic. Today, application areas of interval methods include electrical engineering, control theory, remote sensing, experimental and computational physics, chaotic systems, celestial mechanics, signal processing, computer graphics, robotics, and computer-assisted proofs. The purpose of this monograph is to be a concise but informative introduction to the theories of interval arithmetic as well as to some of their computational and scienti…c applications, for undergraduates and early graduates. It is primarily intended for students of mathematics, computer science, and engineering. The book tries to represent a reasonable portion of the theory of intervals, but still contains only a fraction of the results and applications. So, I believe that it may help to introduce students to the elementary concepts of the interval theory without exhaustively analyzing every single aspect or delving into more advanced topics of the theory. The book is a greatly expanded edition of my earlier graduate report entitled “Interval Arithmetic: An Accurate Self-Validating Arithmetic for Digital Computing”. This edition is completely rewritten for improved clarity and readability. With the various additions and improvements, some stylistic changes, and the corrections of some minor errors I have made to my original account, I iii
PREFACE
could not resist a change in the original title. The new title, therefore, is more truly representative of the expanded contents of this text.
Outline of the Book The book opens with a brief prologue intended to provide a bit of motivation and perspective about the …eld of interval arithmetic, its history, and how it is a potential weapon against uncertainty in science and technology. Chapter 2 introduces the key concepts of the classical interval theory and then de…nes the algebraic and point operations for interval numbers. In section 2.3, we carefully construct the algebraic system of classical interval arithmetic and deduce its fundamental properties. The …rst extension of the classical interval theory appears in chapter 3. Here we introduce how the use of classical interval arithmetic can be extended, via complex interval numbers, to determine regions of uncertainty in computing with complex numbers. We start with the key concepts of complex interval arithmetic and then move on to carefully construct the algebraic system of complex interval arithmetic and deduce its fundamental properties. Chapter 4, after describing the interval dependency problem, is intended to provide a bit of perspective about two important alternate theories of interval arithmetic: constraint interval arithmetic, and modal interval arithmetic. In chapter 5, we delve into some computational applications of the interval theory. Here we explain, in some detail, the interval estimates of the images of continuous real functions on closed intervals, how interval methods are used to bound the error term in Taylor’s theorem, and how interval arithmetic is applied to evaluate de…nite integrals. In chapter 6, we begin with some key concepts of machine real arithmetic, and then carefully construct the algebraic system of machine interval arithmetic and deduce its fundamental properties. In section 6.2, we design a simple circuitry that shows how to realize interval addition on a machine. The …nal section of this chapter introduces how to use a ‡oating-point multiplier and a comparator to design a simple interval squarrer circuitry. The book closes with a brief epilogue intended to provide a view to the future of the interval theory. Here we provide a concluding look ahead and further information resources. Appendix A introduces how to use four half adders and eight full adders to iv
PREFACE
design a 4-by-4 bit multiplier circuitry. We provide detailed Verilog descriptions of the circuitry and simulation process of the 4-by-4 bit multiplier. Appendix B introduces how to use two 4-by-4 bit multipliers and one 8-bit comparator to design an interval squarrer circuitry. We provide detailed Verilog descriptions of the circuitry and simulation process of the interval squarrer.
Acknowledgments I owe great thanks to Assoc. Prof. Dr. Hossam A. H. Fahmy, Department of Electronics and Communication Engineering, Faculty of Engineering, Cairo University, for encouraging my early interests in interval arithmetic and for his fruitful discussions and valuable suggestions. Dr. Hossam spent a lot of his time introducing me to the concepts of the interval theory. I am deeply indebted to my teacher Assoc. Prof. Dr. Hassan A. M. Aly, Department of Mathematics, Faculty of Science, Cairo University, for his continual support and wise advice and for so many most fruitful discussions. My discussions with Dr. Hassan inspired me to think in a radically new way that permeated the present work. Finally it is a pleasure to acknowledge the courtesy and substantial help which I have received from Hannah Olsen, my editor, and the sta¤ of the LAP Lambert Academic Publishing at all stages in the production of the book. Hend Dawood Cairo University, Cairo, September, 2011.
[email protected]
v
Notations and Conventions
Most of our notation is standard but, for the purpose of legibility, we give here a consolidated list of symbols for the entire text.
Logical Symbols Symbol
Meaning
:
Logical Negation (not).
)
, ^ _ 8 9
=
Implication (if ..., then ...). Equivalence (if, and only if ). Conjunction (and ). Inclusive disjunction (or ). Universal quanti…er (for all ). Existential quanti…er (there exists). Identity (equality).
Non-logical Symbols Symbol
Meaning
?
The empty set.
R
The set of real numbers.
x; y; z
Real variable symbols (with or without subscripts, and with or without lower or upper hyphens).
vii
NOTATIONS AND CONVENTIONS
Symbol
Meaning
a; b; c
Real constant symbols (with or without subscripts, and with or without lower or upper hyphens).
2 f+; g 2f ;
} (S)
1
g
A binary algebraic operator. A unary algebraic operator. The powerset of a set
S.
[R]
The set of real interval numbers.
[R]p
The set of point (singleton) interval numbers
[R]s
The set of symmetric interval numbers
[R]e0
The set of interval numbers that do not contain 0.
X; Y; Z
Interval variable symbols (with or without subscripts).
A; B; C
Interval constant symbols (with or without subscripts).
C
The set of ordinary complex numbers.
i=
p
1
[x; x].
[ x; x].
The ordinary imaginary unit.
x; y; z
Complex variable symbols (with or without subscripts).
a; b; c
Complex constant symbols (with or without subscripts).
[C]
The set of complex interval numbers.
[C]e0
The set of nonzero complex interval numbers.
[C]p
The set of point complex interval numbers.
i = [i; i]
The interval imaginary unit.
X; Y ; Z
Complex interval variable symbols (with or without subscripts).
A; B; C
Complex interval constant symbols (with or without subscripts).
c X M
The conjugate of a complex interval number
R
The set of machine-representable real numbers.
Mn
The set of machine real numbers with
[M]
The set of machine interval numbers.
5
Downward rounding operator.
4
X.
Upward rounding operator. Outward rounding operator.
viii
n signi…cant digits.
NOTATIONS AND CONVENTIONS
Symbol
Meaning
c
[R]
The set of constraint interval numbers.
c
[R]e0
The set of nonzero constraint interval numbers.
c
[R]p
M
M9 M8
The set of point constraint interval numbers. The set of modal intervals. The set of existential (proper) modal intervals. The set of universal (improper) modal intervals.
m
X;m Y;m Z
Modal interval variable symbols (with or without subscripts).
m
A;m B;m C
Modal interval constant symbols (with or without subscripts).
ix
Chapter
1
Prologue: A Weapon Against Uncertainty You cannot be certain about uncertainty. –Frank Knight (1885-1972) Scientists are, all the time, in a struggle with error and uncertainty. Uncertainty is the quantitative estimation of errors present in measured data; all measurements contain some uncertainty generated through many types of error. Error (“mistaken result”, or “mistaken outcome”) is common in all scienti…c practice, and is always a serious threat to the search for a trustworthy scienti…c knowledge and to certain epistemic foundations of science. This brief chapter is intended to provide a bit of motivation and perspective about the …eld of interval arithmetic, its history, and how it is a potential weapon against uncertainty in science and technology (For further background, the reader can consult, e.g., [Allchin2000], [Allchin2007], [Kline1982], and [Pedrycz2008]).
1.1 What Interval Arithmetic is and Why it is Considered In real-life computations, uncertainty naturally arises because we process values which come from measurements and from expert estimations. From both the epistemological and physical viewpoints, neither measurements nor expert estimations can be exact for the following reasons: The actual value of the measured quantity is a real number; so, in general, we need in…nitely many bits to describe the exact value, while after every measurement, we gain only a …nite number of bits of information (e.g., a …nite number of binary digits in the binary expansion of the number). 1
CHAPTER 1. PROLOGUE: A WEAPON AGAINST UNCERTAINTY
There is always some di¢ cult-to-delete noise which is mixed with the measurement results. Expert estimates cannot be absolutely exact, because an expert generates only a …nite amount of information. Experts are usually even less accurate than are measuring instruments. So, there are usually three sources of error while performing numerical computations with real numbers; rounding, truncation and input errors. A mistaken outcome is always a concern in scienti…c research because errors inevitably accumulate during calculations. Interval arithmetic keeps track of all error types simultaneously, because an interval arithmetic operation produces a closed interval within which the true real-valued result is guaranteed to lie. Interval arithmetic (also known as “interval mathematics”, “interval analysis”, and “interval computation”) is an arithmetic de…ned on sets of real intervals, rather than sets of real numbers. It speci…es a precise method for performing arithmetic operations on closed intervals (interval numbers). The concept is simple: in the interval number system, each interval number represents some …xed real number between the lower and upper endpoints of the closed interval. So, an interval arithmetic operation produces two values for each result. The two values correspond to the lower and upper endpoints of the resulting interval such that the true result certainly lies within this interval, and the accuracy of the result is indicated by the width of the resulting interval. As a result of error, we all the time have to face situations in which scienti…c measurements give uncertain values. Let x be a real number whose value is uncertain, and assume a measurement gives adequate information about an acceptable range, x x x, in which the true value of x is estimated to lie. The closed interval (interval number), [x; x] = fx 2 Rjx
x
xg,
is called the “interval of certainty”(or the “interval of con…dence”) about the value of x. That is, we are certain that the true value of x lies within the interval [x; x]. ! = hx ; x ; :::; x i is a multidimensional quantity (realIf it is the case that x n
1
2
n
valued vector) such that for each xi there is an interval of certainty Xi = [xi ; xi ], ! has an “n-dimensional parallelotope of certainty”, X , then the quantity x n n which is the Cartesian product of the intervals X1 ; X2 ; :::; Xn . 2
CHAPTER 1. PROLOGUE: A WEAPON AGAINST UNCERTAINTY
Figure 1.1 illustrates the case n = 2; with ! x2 = hx1 ; x2 i, x1 2 [x1 ; x1 ], x2 2 [x2 ; x2 ], and X2 is a rectangle of certainty.
Figure 1.1: A 2-dimensional parallelotope of certainty.
To illustrate this, we give two numerical examples. Example 1.1 The Archimedes’s constant, , is an irrational number, which means that its value cannot be expressed exactly as a fraction. Consequently, it has no certain decimal representation because its decimal representation never ends or repeats. Since 314 10 2 315 10 2 , the number can be represented as the interval number [ ; ] = 314
10 2 ; 315
10
2
.
That is, we are certain that the true value of lies within the interval [ ; ] whose width indicates the maximum possible error, Error = width([ ; ]) = = 315 10 2 314 = 10 2 .
10
2
Example 1.2 Suppose two independent scienti…c measurements give di¤erent uncertain results for the same quantity q. One measurement gives q = 1:4 0:2. The other gives q = 1:5 0:2. These uncertain values of q can be represented 3
CHAPTER 1. PROLOGUE: A WEAPON AGAINST UNCERTAINTY
as the interval numbers X = [1:2; 1:6] and Y = [1:3; 1:7], respectively. Since q lies in both, it certainly lies in their intersection X \ Y = [1:3; 1:6]. So, if X \ Y 6= ?, we can get a better (tighter) “interval of certainty”. If not, we can be certain that at least one of the two measurements is wrong. After we present a rigorous construction of the theoretical foundations of interval arithmetic in chapters 2, 3, and 4, more advanced examples and applications shall be discussed, in detail, in chapter 5.
1.2 A History Against Uncertainty The term “interval arithmetic” is reasonably recent: it dates from the 1950s, when the works of Paul S. Dwyer, R. E. Moore, R. E. Boche, S. Shayer, and others made the term popular (see, [Dwyer1951], [Moore1959], [Boche1963], and [Shayer1965]). But the notion of calculating with intervals is not completely new in mathematics: in the course of history, it has been invented and reinvented several times, under di¤erent names, and never been abandoned or forgotten. The concept has been known since the third century BC, when Archimedes used guaranteed lower and upper bounds to compute his constant, (see [Archimedes2002]). Early in the twentieth century, the idea seemed to be rediscovered. A form of interval arithmetic perhaps …rst appeared in 1924 by J. C. Burkill in his paper “Functions of Intervals”([Burkill1924]), and in 1931 by R. C. Young in his paper “The Algebra of Many-Valued Quantities”([Young1931]) that gives rules for calculating with intervals and other sets of real numbers; then later in 1951 by Paul S. Dwyer in his book “Linear computations” ([Dwyer1951]) that discusses, in a heuristic manner, certain methods for performing basic arithmetic operations on real intervals, and in 1958 by T. Sunaga in his book “Theory of an Interval Algebra and its Application to Numerical Analysis”([Sunaga1958]). However, it was not until 1959 that new formulations of interval arithmetic were presented. Modern developments of the interval theory began in 1959 with R. E. Moore’s technical report “Automatic Error Analysis in Digital Computation”([Moore1959]) in which he developed a number system and an arithmetic dealing with closed real intervals. He called the numbers “range numbers” and the arithmetic “range arithmetic” to be the …rst synonyms of “interval numbers” and “interval arithmetic”. Then later in 1962, Moore developed a theory for exact or in…nite precision interval arithmetic in his very in‡uential dissertation titled “Interval Arithmetic and Automatic Error Analysis in Digital Computing” ([Moore1962]) in which he used a modi…ed digital (rounded) 4
CHAPTER 1. PROLOGUE: A WEAPON AGAINST UNCERTAINTY
interval arithmetic as the basis for automatic analysis of total error in a digital computation. Since then, thousands of research papers and numerous books have appeared on the subject. Interval arithmetic is now a broad …eld in which rigorous mathematics is associated with scienti…c computing. The connection between computing and mathematics provided by intervals makes it possible to solve problems that cannot be e¢ ciently solved using ‡oating-point arithmetic and traditional numerical approximation methods. Today, the interval methods are becoming rapidly popular as a prospective weapon against uncertainties in measurements and errors of numerical computations. Nowadays, interval arithmetic is widely used and has numerous applications in scienti…c and engineering disciplines that deal intensely with uncertain data (or range data). Practical application areas include electrical engineering, structure engineering, control theory, remote sensing, quality control, experimental and computational physics, dynamical and chaotic systems, celestial mechanics, signal processing, computer graphics, robotics, and computer-assisted proofs (In chapter 5, we shall discuss, in some detail, a number of the computational applications of interval arithmetic).
5
Chapter
2
The Classical Theory of Interval Arithmetic Algebra is the metaphysics of arithmetic. –John Ray (1627-1705) A very simple and natural idea is that of enclosing real numbers in real closed intervals. Based on this idea, this chapter is devoted to rigorously de…ning and constructing the number system of classical interval arithmetic and developing the most fundamental tools for classical interval analysis (For a brief overview of some alternate theories of interval arithmetic, see chapter 4). The chapter opens with the key concepts of the classical interval theory and then introduces the algebraic and point operations for interval numbers. In section 2.3, we carefully construct the algebraic system of classical interval arithmetic and deduce its fundamental properties (For other constructions of the classical interval theory, the reader may consult, e.g., [Jaulin2001], [Moore1962], [Moore2009], and [Shayer1965]).
2.1 Algebraic Operations for Interval Numbers The basic algebraic operations for real numbers can be extended to interval numbers. In this section, we shall formulate the basic relations and algebraic operations on interval numbers. We …rst de…ne what an interval number is. De…nition 2.1 Let x; x 2 R such that x x. An interval number [x; x] is a closed and bounded nonempty real interval, that is [x; x] = fx 2 Rjx 7
x
xg,
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
where x = min ([x; x]) and x = max ([x; x]) are called, respectively, the lower and upper bounds (endpoints) of [x; x]. De…nition 2.2 The set [R] of interval numbers is a subset of the powerset of R such that [R] = fX 2 } (R) j (9x 2 R) (9x 2 R) (X = [x; x])g. Since, corresponding to each pair of real constants x; x (x a closed interval [x; x], the set of interval numbers is in…nite.
x) there exists
In order to be able easily to speak of di¤erent types of interval numbers, it is convenient to introduce some notational conventions. Notation 2.1 The set of all interval numbers that do not contain the real number 0 is denoted by [R]e0 , that is [R]e0 = fX 2 [R] j0 2 = Xg.
Notation 2.2 The set of all symmetric interval numbers is denoted by [R]s , that is [R]s = fX 2 [R] j(9x 2 R)(0 x ^ X = [ x; x])g. Notation 2.3 The set of all singleton (point) interval numbers is denoted by [R]p , that is [R]p = fX 2 [R] j(9x 2 R)(X = [x; x])g. The set [R]p is an in…nite subset of [R] and is isomorphically equivalent to the set R of real numbers (see theorem 2.5). That is, every element [x; x] 2 [R]p is an isomorphic copy of an element x 2 R. By convention, and being less pedantic, we agree to identify a point interval number [x; x] with its real isomorphic copy x. In this sense, throughout the text, we may write x = [x; x]. Hereafter, the upper-case Roman letters X, Y , and Z (with or without subscripts), or equivalently [x; x], y; y , and [z; z], shall be employed as variable symbols to denote elements of [R]. The equality relation on [R] is characterized in the following de…nition. De…nition 2.3 (Equality on [R]). The equality relation for interval numbers is de…ned as [x; x] = y; y , x = y ^ x = y. 8
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
Thus equality in [R] is de…ned in terms of equality in R. This de…nition is a special case of the axiom of extensionality1 of axiomatic set theory, from the fact that every interval number is an ordered set. Only a partial order (can only compare certain elements) can be de…ned on [R] as follows. De…nition 2.4 (Ordering on [R]). A strict partial order on [R] with respect to the inequality, <, is de…ned as [x; x] < y; y , x < y. Thus the ordering on [R] is de…ned in terms of the ordering on R. The relation < is irre‡exive, asymmetric, and transitive on [R]. We observe that not every two elements of [R] can be compared by the relation < (if X \ Y 6= ?): this is why the ordering by < is strictly partial 2 on [R]. If S is a subset of [R] such that for every two elements X and Y of S, it is the case that either X = Y or X \ Y = ?; then we have a total order 3 on S with respect to the relation , that is, X Y or Y X. 1
The axiom of extensionality asserts that two sets are equal if, and only if they have precisely the same elements (see, e.g., [Causey1994], [Devlin1993], and [Kleene1952]), that is (8X) (8Y ) (X = Y , (8z) (z 2 X , z 2 Y )) . 2
A relation
is a strict partial ordering on a set S i¤
irre‡exive: (8x 2 S) (: (x
is
x)),
asymmetric: (8x 2 S) (8y 2 S) (x
y ) : (y
transitive: (8x 2 S) (8y 2 S) (8z 2 S) (x
x)), and
y^y
z)x
z).
If a relation is a strict partial ordering on a set S, then S has at least one pair which is non-comparable (see, e.g, [Causey1994], [Devlin1993], and [Gleason1992]), in symbols (9x 2 S) (9y 2 S) (: (x 3
A relation
y) ^ : (y
is a total ordering on a set S i¤
re‡exive: (8x 2 S) (x
x)) .
is
x),
antisymmetric: (8x 2 S) (8y 2 S) (x
y^y
transitive: (8x 2 S) (8y 2 S) (8z 2 S) (x
x ) x = y),
y^y
connected (total): (8x 2 S) (8y 2 S) (x 6= y ) x 9
z)x y_y
z), and x).
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
Example 2.1 For three given interval numbers A = [1; 2], B = [1; 2], and C = [4; 7], we have A = B < C. We now proceed to de…ne the basic algebraic operations for interval numbers: two binary operations, namely addition (“+”) and multiplication (“ ”), and two unary operations, namely negation (“ ”) and reciprocal (“ 1 ”). According to the fact that interval numbers are sets, the binary and unary algebraic operations for interval numbers can be characterized, respectively, in the following two set-theoretic de…nitions. De…nition 2.5 (Binary Interval Operations). For any two interval numbers X and Y , the binary algebraic operations are de…ned by X where
Y = fz 2 Rj (9x 2 X) (9y 2 Y ) (z = x y)g,
2 f+; g.
De…nition 2.6 (Unary Interval Operations). For any interval number X, the unary algebraic operations are de…ned by X = fz 2 Rj (9x 2 X) (z = x)g, where
2f ;
1
g and 0 2 = X if
is “ 1 ”.
By means of the above set-theoretic de…nitions and from the fact that interval numbers are ordered sets of real numbers, the following four theorems are immediate. Theorem 2.1 (Interval Addition). For any two interval numbers [x; x] and y; y , interval addition is formulated in terms of the intervals’endpoints as [x; x] + y; y = x + y; x + y . If a relation is a total ordering on a set S, then S has no non-comparable pairs (see, e.g, [Causey1994], [Devlin1993], and [Gleason1992]), in symbols (8x 2 S) (8y 2 S) (x
10
y_y
x) .
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
Theorem 2.2 (Interval Multiplication). For any two interval numbers [x; x] and y; y , interval multiplication is formulated in terms of the intervals’ endpoints as [x; x]
y; y = minfxy; xy; xy; xyg; maxfxy; xy; xy; xyg .
Theorem 2.3 (Interval Negation). For any interval number [x; x], interval negation is formulated in terms of the interval endpoints as [x; x] = [ x; x] . Theorem 2.4 (Interval Reciprocal). For any interval number [x; x] 2 [R]e0 (that is, 0 2 = [x; x]), interval reciprocal is formulated in terms of the interval endpoints as h 1 1i 1 [x; x] = x ; x . In accordance with the above theorems, we can now de…ne subtraction, division, and exponentiation for interval numbers. De…nition 2.7 (Interval Subtraction). For any two interval numbers X and Y , interval subtraction is de…ned by Y = X + ( Y ).
X
De…nition 2.8 (Interval Division). For any X 2 [R] and any Y 2 [R]e0 , interval division is de…ned by X
Y =X
Y
1
.
De…nition 2.9 (Interval Exponentiation). For any interval number X and any integer n, the integer exponents of X are recursively de…ned by: (i)
X 0 = [1; 1],
(ii)
0 < n ) Xn = Xn
(iii) 0 2 = X ^0
1
n)X
X, n
= X
1 n
.
Since the interval algebraic operations are de…ned in terms of the real algebraic operations, and as long as division by zero is disallowed; it follows that the result of an interval algebraic operation is always an interval number. 11
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
Example 2.2 For three given interval numbers [1; 2], [3; 4], and [ 2; 2], we have (i)
[1; 2] + [3; 4] = [4; 6],
(ii)
[1; 2]
[3; 4] = [3; 8], 2
(iii) [ 2; 2] = [ 2; 2]
[ 2; 2] = [ 4; 4]. 2
The result [ 4; 4] of [ 2; 2] , in the above example, is not natural in the sense that a square is always nonnegative. Generally, for any non-point interval number [x; x], with 0 2 [x; x], the square of [x; x] is given by 2
[x; x]
= [x; x] [x; x] h i 2 2 2 2 = minfx ; xx; x g; maxfx ; xx; x g h i 2 2 = xx; maxfx ; x g ,
which is consistent with interval multiplication (theorem 2.2), but it is not consistent with the fact that a square is always nonnegative, for the case when xx < 0. However, if we changed it to be 2
[x; x]
2
= fz 2 Rj (9x 2 [x; x]) z = x g h i 2 2 = 0; maxfx ; x g ,
then it would be inconsistent with interval multiplication. This is not a problem if interval arithmetic is regarded as a numerical approximation method, for real-valued problems, such that the result of an interval operation contains all possible solutions. But if interval arithmetic is regarded as a de…nitional extension 4 of the theory of real numbers (this is the case in almost all interval literature), in the logical sense; then the theory of interval arithmetic is not 4
A theory TE is called a de…nitional extension of a theory T i¤ TE is obtained from T by adding new relation symbols and function symbols de…ned in terms of symbols of T (see, e.g., [Kleene1952], [Rasiowa1963] and [Tarski1965]). De…ning relation symbols. Let ' (x1 ; :::; xn ) be a formula of T such that x1 ; :::; xn occur free in '. A new theory TE can be obtained from T by adding a new n-ary relation symbol R, the logical axioms featuring R, and the new de…nitional axiom of R (8x1 ) ::: (8xn ) (R (x1 ; :::; xn ) , ' (x1 ; :::; xn )) . An example of such a de…nition of relation symbols is the de…nition of a closed interval in terms of the order relation of the theory of real numbers. De…ning function symbols. Let ' (y; x1 ; :::; xn ) be a formula of T such that y; x1 ; :::; xn 12
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
consistent. In this book, we shall regard interval arithmetic as a numerical approximation tool of guaranteed e¢ ciency against computation errors, in the sense we discussed in chapter 1.
2.2 Point Operations for Interval Numbers A point (or scalar) interval operation is an operation whose operands are interval numbers, and whose result is a point interval (or, equivalently, a real number). This is made precise in the following de…nition. De…nition 2.10 (Point Interval Operations). Let [R]hni be the n-th Cartesian power of [R]. An n-ary point interval operation, ! n , is a function that maps elements of [R]hni to the set [R]p of point interval numbers, that is ! n : [R]hni 7 ! [R]p . Several point interval operations can be de…ned. Next we de…ne some unary and binary point interval operations. De…nition 2.11 (Interval In…mum). The in…mum of an interval number [x; x] is de…ned to be inf ([x; x]) = min ([x; x]) = x. De…nition 2.12 (Interval Supremum). The supremum of an interval number [x; x] is de…ned to be sup ([x; x]) = max ([x; x]) = x. occur free in '. Assume that the sentence (8x1 ) ::: (8xn ) (9!y) (' (y; x1 ; :::; xn )) , is provable in T ; that is, for all x1 ; :::; xn , there exists a unique y such that ' (y; x1 ; :::; xn ). A new theory TE can be obtained from T by adding a new n-ary relation symbol F , the logical axioms featuring F , and the new de…nitional axiom of F (8x1 ) ::: (8xn ) (' (F (x1 ; :::; xn ) ; x1 ; :::; xn )) . An example of such a de…nition of function symbols is the de…nition of the interval algebraic operations in terms of the algebraic operations of the theory of real numbers. If TE is a consistent de…nitional extension of T , then for any formula of TE we can form a formula ' of T , called a translation of into T , such that , ' is provable in TE . Such a formula is not unique, but any two formulas '1 and '2 can be proved to be equivalent in T . That is, for TE to be a consistent de…nitional extension of T ; if 1 , '1 , 2 , '2 , and '1 , '2 , then 1 , 2 . 13
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
De…nition 2.13 (Interval Width). The width of an interval number [x; x] is de…ned to be w ([x; x]) = x x. Thus, the width of a point interval number is zero, that is (8x 2 R) (w ([x; x]) = x
x = 0) .
De…nition 2.14 (Interval Radius). The radius of an interval number [x; x] is de…ned to be r ([x; x]) = w ([x; x]) =2 = (x x) =2. De…nition 2.15 (Interval Midpoint). The midpoint (or mean) of an interval number [x; x] is de…ned to be m ([x; x]) = (x + x) =2. Hence, the midpoint of a point interval number is its real isomorphic copy, that is (8x 2 R) (m ([x; x]) = (x + x) =2 = x) . We observe that any interval number X can be expressed, in terms of its width and its midpoint, as the sum of its midpoint and a corresponding symmetric interval, that is X = m (X) + [ w (X) =2; w (X) =2] , where, by convention, m (X) = [m (X) ; m (X)]. De…nition 2.16 (Interval Absolute Value). The absolute value of an interval number [x; x] is de…ned, in terms of the absolute values of its real endpoints, to be j[x; x]j = max (fjxj ; jxjg) . Thus, the absolute value of a point interval number is the usual absolute value of its real isomorphic copy, that is (8x 2 R) (j[x; x]j = max (fjxj ; jxjg) = jxj) . All the above point interval operations are unary operations. An important de…nition of a binary point interval operation is that of the interval metric (or the distance between two interval numbers). 14
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
De…nition 2.17 (Interval Distance). The distance (or metric) between two interval numbers [x; x] and y; y is de…ned to be d [x; x] ; y; y
= max f x
y ; jx
yjg .
The importance of this de…nition is that starting from the distance function for interval numbers, we can verify that it induces a Hausdor¤ metric space 5 for interval numbers which is a generalization of the usual metric space of real numbers. Thus, the notions of a sequence, convergence, continuity, and a limit can be de…ned for interval numbers in the standard way. These notions give rise to what we may call a “measure theory for interval numbers”. An interval measure theory is beyond the scope of this book. Example 2.3 For three given interval numbers [1; 2], [3; 4], and [ 5; 3], we have (i)
w ([1; 2]) = w ([3; 4]) = 1,
(ii)
m ([1; 2]) = 3=2, m ([3; 4]) = 7=2,
(iii) j[ 5; 3]j = max (fj 5j ; j3jg) = 5, (iv) d ([1; 2] ; [3; 4]) = max (fj1
3j ; j2
4jg) = 2.
2.3 Algebraic Properties of Interval Arithmetic By means of the notions prescribed in sections 2.1 and 2.2, we shall now inquire into some fundamental theorems concerning interval arithmetic. By virtue of our de…nition of an interval number, the properties of real numbers are naturally assumed priori. A …rst important theorem we shall now prove is the isomorphism theorem for interval arithmetic. 5
A metric space is an ordered pair (S; d), where S is a set and d is a metric on S, that is d : S h2i 7 ! R,
such that for any x; y; z 2 S, the following holds: x = y , d (x; y) = 0,
d (x; y) = d (y; x), d (x; z)
d (x; y) + d (y; z).
A Hausdor¤ space is a metric space in which distinct points have disjoint neighbourhoods (see [Bryant1985]). 15
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
D
Theorem 2.5 The ordered structure [R]p ; +[R] ; [R] ; <[R] equivalent to the …eld hR; +R ; R ;
E
is isomorphically
Proof. Let { : R ,! [R]p be a mapping from R to [R]p such that (8x 2 R) 9{ (x) 2 [R]p ({ (x) = [x; x]) . The following conditions for { are satis…ed: { is a bijection from R onto [R]p since, by de…nitions 2.2 and 2.3, the range of { is [R]p , and (8x 2 R) (8y 2 R) ({ (x) = { (y) ) x = y) . { is function-preserving for “+”since, by theorem 2.1, we have { (x +R y) = [x +R y; x +R y] = [x; x] +[R] [y; y] = { (x) +[R] { (y) . { is function-preserving for “ ”since, by theorem 2.2, we have { (x
R
y) = [x R y; x R y] = [x; x] [R] [y; y] = { (x) [R] { (y) .
{ is relation-preserving for “<”since, by de…nition 2.4, we have x
R ;
That is, up to isomorphism, the sets R and [R]p are equivalent, and each element of [R]p is an isomorphic copy of an element of R. In other words, everything that is true for real numbers is certainly true for point interval numbers. 16
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
The properties of the interval operations are similar to, but not the same as, those of the real operations. The algebraic properties of the interval operations are prescribed by the following theorems. Theorem 2.6 (Absorbing Element). The interval number [0; 0] is an absorbing element for interval multiplication, that is (8X 2 [R]) ([0; 0]
X=X
[0; 0] = [0; 0]) .
Proof. For any interval number X, according to de…nition 2.5 and assuming the properties of real multiplication, we have [0; 0]
X = = = =
fr 2 Rj (9x 2 X) (9y 2 [0; 0]) (r = y fr 2 Rj (9x 2 X) (9y 2 [0; 0]) (r = x fr 2 Rj (9x 2 X) (r = x 0)g X [0; 0] = [0; 0] ,
x)g y)g
and therefore, the point interval number [0; 0] absorbs any interval number X by interval multiplication. Theorem 2.7 (Identity for Addition). The interval number [0; 0] is both a left and right identity for interval addition, that is (8X 2 [R]) ([0; 0] + X = X + [0; 0] = X) . Proof. For any interval number X, according to de…nition 2.5 and assuming the properties of real addition, we have [0; 0] + X = = = =
fr 2 Rj (9x 2 X) (9y 2 [0; 0]) (r = y + x)g fr 2 Rj (9x 2 X) (9y 2 [0; 0]) (r = x + y)g fr 2 Rj (9x 2 X) (r = x + 0)g X + [0; 0] = X,
and therefore, [0; 0] is both a left and right identity for interval addition. Theorem 2.8 (Identity for Multiplication). The interval number [1; 1] is both a left and right identity for interval multiplication, that is (8X 2 [R]) ([1; 1]
X=X
17
[1; 1] = X) .
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
Proof. For any interval number X, according to de…nition 2.5 and assuming the properties of real multiplication, we have [1; 1]
X = = = =
fr 2 Rj (9x 2 X) (9y 2 [1; 1]) (r = y fr 2 Rj (9x 2 X) (9y 2 [1; 1]) (r = x fr 2 Rj (9x 2 X) (r = x 1)g X [1; 1] = X,
x)g y)g
and therefore, it is shown that [1; 1] is both a left and right identity for interval multiplication. Theorem 2.9 (Commutativity). Both interval addition and multiplication are commutative, that is (i)
(8X; Y 2 [R]) (X + Y = Y + X),
(ii) (8X; Y 2 [R]) (X
Y =Y
X).
Proof. (i) For any two interval numbers X and Y , according to de…nition 2.5 and assuming the properties of real addition, we have X + Y = fr 2 Rj (9x 2 X) (9y 2 Y ) (r = x + y)g = fr 2 Rj (9x 2 X) (9y 2 Y ) (r = y + x)g = Y + X. (ii) In a manner analogous to (i), assuming the properties of real multiplication, we have X
Y = fr 2 Rj (9x 2 X) (9y 2 Y ) (r = x = fr 2 Rj (9x 2 X) (9y 2 Y ) (r = y = Y X.
y)g x)g
Therefore, both addition and multiplication are commutative in [R]. Theorem 2.10 (Associativity). Both interval addition and multiplication are associative, that is (i)
(8X; Y; Z 2 [R]) (X + (Y + Z) = (X + Y ) + Z),
(ii) (8X; Y; Z 2 [R]) (X
(Y
Z) = (X
18
Y)
Z).
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
Proof. (i) For any three interval numbers X, Y , and Z, according to de…nition 2.5 and assuming the properties of real addition, we have X + (Y + Z) = = = = =
fr 2 Rj (9x 2 X) (9s 2 (Y + Z)) (r = x + s)g fr 2 Rj (9x 2 X) (9y 2 Y ) (9z 2 Z) (r = x + (y + z))g fr 2 Rj (9x 2 X) (9y 2 Y ) (9z 2 Z) (r = (x + y) + z)g fr 2 Rj (9t 2 (X + Y )) (9z 2 Z) (r = t + z)g (X + Y ) + Z.
(ii) In a manner analogous to (i), assuming the properties of real multiplication, we have X
(Y
Z) = = = = =
fr 2 Rj (9x 2 X) (9s 2 (Y Z)) (r = x s)g fr 2 Rj (9x 2 X) (9y 2 Y ) (9z 2 Z) (r = x (y z))g fr 2 Rj (9x 2 X) (9y 2 Y ) (9z 2 Z) (r = (x y) z)g fr 2 Rj (9t 2 (X Y )) (9z 2 Z) (r = t z)g (X Y ) Z.
Therefore, both addition and multiplication are associative in [R]. Theorem 2.11 (Inverses). Additive and multiplicative inverses do not always exist for interval numbers except for point interval numbers, that is (i) (ii)
(9X 2 [R]) (X + ( X) 6= [0; 0]),
(9X 2 [R]) 0 2 = X ^X
1
X
6= [1; 1] ,
(iii)
8X 2 [R]p (X + ( X) = [0; 0]),
(iv)
8X 2 [R]p
02 =X)X
X
1
= [1; 1] .
Proof. For (i) and (ii), let X = [x; x] be a nonpoint interval, that is x 6= x. According to theorems 2.1 and 2.2, we have [x; x] + ( [x; x]) = [x; x] + [ x; x] = [x x; x x] 6= [0; 0] ,
19
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
and, if 0 2 = [x; x], we have [x; x]
[x; x]
1
= [x; x]
[1=x; 1=x]
= [x=x; x=x] 6 [1; 1] . = (iii) and (iv) are immediate from the fact that [R]p and R are isomorphically equivalent (theorem 2.5). The result formulated in the following theorem is an important property of interval arithmetic. Theorem 2.12 (Subdistributivity). The distributive law does not always hold in interval arithmetic, that is (9X; Y; Z 2 [R]) (Z
(X + Y ) 6= Z
X +Z
Y ),
except when (i)
Z is a point interval number, or
(ii)
X = Y = [0; 0], or
(iii) (8x 2 X) (8y 2 Y ) (xy
0).
In general, interval arithmetic only has the subdistributive law: (8X; Y; Z 2 [R]) (Z
(X + Y )
Z
X +Z
Y ).
Proof. Let [z; z], [x; x], and [ x; x] be in [R]. First adding and then multiplying, we have [z; z]
([x; x] + [ x; x]) = [z; z]
[0; 0] = [0; 0] .
But if we …rst multiply and then add, we get ([z; z] [x; x]) + ([z; z] [ x; x]) = [min (zx; zx) ; max (zx; zx)] + [min ( zx; zx) ; max ( zx; zx)] 6= [0; 0] , unless z = z, or x =
x = 0, or both.
Thus, there are some interval numbers for which the distributive law does not hold. 20
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
(i) Let Z = [a; a] be a point interval number, for some real constant a. According to de…nition 2.5, we have Z
fr fr fr fr fr Z
(X + Y ) = = = = = =
2 Rj (9z 2 [a; a]) (9s 2 (X + Y )) (r = z s)g 2 Rj (9s 2 (X + Y )) (r = a s)g 2 Rj (9x 2 X) (9y 2 Y ) (r = a (x + y))g 2 Rj (9x 2 X) (9y 2 Y ) (r = a x + a y)g 2 Rj (9t 2 (Z X)) (9u 2 (Z Y )) (r = t + u)g X +Z Y.
(ii) By theorems 2.6 and 2.7, we immediately have Z
([0; 0] + [0; 0]) = Z [0; 0] = [0; 0] = Z [0; 0] + Z
[0; 0] .
(iii) Let X = [x; x] and Y = [y; y]. Without loss of generality, we consider only the case when x 0 and y 0. We have three cases for Z = [z; z]. Case 1. If z
0, then we have Z
(X + Y ) =
z x + y ; z (x + y)
= [zx; zx] + zy; zy = Z X +Z Y. Case 2. If z
0, we obtain the same result by considering
Z.
Case 3. If zz < 0, then we have Z
(X + Y ) = [z (x + y) ; z (x + y)] = [zx; zx] + [zy; zy] = Z X +Z Y,
and the last case is thus proved. Now let r 2 (Z we have
(X + Y )). From the distributive property of real numbers, r = z(x + y) = zx + zy,
for some x 2 X, y 2 Y , and z 2 Z. 21
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
Thus r 2 (Z
X +Z
Y ), and therefore
(8X; Y; Z 2 [R]) (Z
(X + Y )
Z
X +Z
Y ),
which completes the proof. It should be borne in mind that interval arithmetic does not even have the distributive law Z
([x; x] + [y; y]) = Z
[x; x] + Z
[y; y] ,
for point interval numbers [x; x] and [y; y]. An important and more general result we shall next prove is the inclusion monotonicity of interval arithmetic. Theorem 2.13 (Inclusion Monotonicity). Let X1 , X2 , Y1 , and Y2 be interval numbers such that X1 Y1 and X2 Y2 . Then for any interval operation 2 f+; g, we have X1 X2 Y1 Y2 . Proof. By hypothesis, we have X1 de…nition 2.5, we have
Y1 and X2
Y2 . Then, according to
X1 X2 = fr 2 Rj (9x1 2 X1 ) (9x2 2 X2 ) (r = x1 x2 )g fs 2 Rj (9y1 2 Y1 ) (9y2 2 Y2 ) (s = y1 y2 )g = Y1 Y2 , and the theorem follows. An immediate consequence is the following important special case. Corollary 2.1 Let X and Y be interval numbers with x 2 X and y 2 Y . Then for any interval operation 2 f+; g, we have x y2X
Y.
Finally, we prove the following result about the algebraic system of interval arithmetic. Theorem 2.14 Let h[R] ; i be the algebraic system of interval numbers. Then for any interval operation 2 f+; g, the system h[R] ; i is an abelian monoid. 22
CHAPTER 2. THE CLASSICAL THEORY OF INTERVAL ARITHMETIC
Proof. For
2 f+; g, the following four criteria are satis…ed.
Closure. By de…nition, the set [R] is closed under both addition and multiplication. Associativity. Both addition and multiplication are associative, by theorem 2.10. Commutativity. Both addition and multiplication are commutative, by theorem 2.9. Identity Elements. The interval numbers [0; 0] and [1; 1] are identity elements respectively for addition and multiplication, by theorems 2.7 and 2.8. Therefore, the set [R] of interval numbers forms an abelian monoid under both addition and multiplication. Two important properties, peculiar to the classical theory of interval arithmetic, …gure in the theorems of this section: additive and multiplicative inverses do not always exist for interval numbers, and there is no distributivity between addition and multiplication except for certain special cases. Then, we have to sacri…ce some useful properties of ordinary arithmetic, if we want to use the interval weapon against uncertainty.
23
Chapter
3
Complex Interval Arithmetic The shortest route between two truths in the real domain passes through the complex domain. –Jacques Hadamard (1865-1963) A great extension of number systems is that to the complex numbers. The need for complex numbers in mathematics far transcends the existence of imaginary roots of polynomial equations: there is scarcely a scienti…c theory which does not involve the notion of a complex number. As it is the case with computing with real numbers, computing with complex numbers involves uncertain data. So, given the fact that an interval number is a real closed interval and a complex number is an ordered pair of real numbers, there is no reason to limit the application of interval arithmetic to the measure of uncertainties in computations with real numbers. The purpose of this chapter is to introduce how the use of classical interval arithmetic can be extended, via complex interval numbers, to determine regions of uncertainty in computing with complex numbers. The chapter opens with the key concepts of complex interval arithmetic and then introduces the algebraic and point operations for complex interval numbers. In section 3.3, we carefully construct the algebraic system of complex interval arithmetic and deduce its fundamental properties (For other constructions of complex interval arithmetic, the reader may consult, e.g., [Boche1966], and [Petkovic1998]).
25
CHAPTER 3. COMPLEX INTERVAL ARITHMETIC
3.1 Algebraic Operations for Complex Interval Numbers The basic algebraic operations for real interval numbers (described in section 2.1) can be extended to complex numbers. It is therefore not surprising that complex interval arithmetic is similar to, but not the same as, ordinary complex arithmetic. In this section, we shall formulate the basic operations and relations on complex interval numbers. Hereafter, the boldface small letters x, y, and z (with or without subscripts) shall be employed as variable symbols to denote elements of the set C of ordinary complex numbers, and the boldface capital letters X, Y , and Z (with or without subscripts) shall be employed as variable symbols to denote elements of the set of complex interval numbers. We …rst de…ne what a complex interval number is. De…nition 3.1 Let X and X be real interval numbers. A complex interval number X is the set of all ordinary complex numbers x + ix for all x 2 X and x 2 X , that is X = fx 2 Cj (9x 2 X ) (9x 2 X ) (x = x + ix )g = X + iX , where X and X are called, respectively, the interval and imaginary parts of X, and i = [i; i] is the interval imaginary unit. The set of complex interval numbers shall be denoted by [C]. In order to be able easily to speak of di¤erent types of complex interval numbers, it is convenient to introduce some notational conventions. Notation 3.1 A complex interval number X + iX with X = [0; 0] is called a pure interval. The set of all pure intervals shall be denoted by [C]I . Notation 3.2 A complex interval number X + iX with X = [0; 0] is called a pure imaginary. The set of all pure imaginaries shall be denoted by [C]G . Notation 3.3 A complex interval number X + iX with 0 2 = X 2 + X 2 is called a nonzero complex interval number. The set of all nonzero complex interval numbers shall be denoted by [C]e0 . 26
CHAPTER 3. COMPLEX INTERVAL ARITHMETIC
Notation 3.4 A complex interval number X + iX with X and X are real point interval numbers is called a point complex interval number. The set of all point complex interval numbers shall be denoted by [C]p . The set [C]p is isomorphically equivalent to the set C of ordinary complex numbers (see theorem 3.7). That is, every element ([x ; x ] + i [x ; x ]) 2 [C]p is an isomorphic copy of an element (x + ix ) 2 C. By convention, and being again less pedantic, we agree to identify a point complex interval number [x ; x ] + i [x ; x ] with its isomorphic copy x + ix . In this sense, throughout the text, we may write x + ix = [x ; x ] + i [x ; x ] . Geometrically, a complex interval number may be conceived as a rectangle in the complex plane with sides parallel to the coordinate axes, that is, a complex interval number is a rectangle of certainty (see Figure 3.1). If it is the case of a point complex interval number, the geometric representation shall be a point in the complex plane, which is the same as that of the corresponding ordinary complex number.
Figure 3.1: Geometric representation of a complex interval number.
27
CHAPTER 3. COMPLEX INTERVAL ARITHMETIC
As it is the case with ordinary complex numbers, complex interval numbers cannot be ordered with respect to the inequality relation <, in a way compatible 1 with the algebraic operations. The equality relation on [C] is characterized in the following de…nition. De…nition 3.2 (Equality on [C]). The equality relation for complex interval numbers is de…ned as (X + iX ) = (Y + iY ) , X = Y ^ X = Y . In a way similar to how ordinary complex arithmetic is de…ned in terms of real arithmetic, complex interval arithmetic is de…ned in terms of real interval arithmetic. The binary and unary algebraic operations for complex interval numbers can be characterized, respectively, in the following two set-theoretic de…nitions. De…nition 3.3 (Binary Complex Interval Operations). For any two complex interval numbers X and Y , the binary algebraic operations are de…ned by X where
Y = fz 2 Cj (9x 2 X) (9y 2 Y ) (z = x y)g,
2 f+; g.
De…nition 3.4 (Unary Complex Interval Operations). For any complex interval number X, the unary algebraic operations are de…ned by X = fz 2 Cj (9x 2 X) (z = x)g, where
2f ;
1
g and X 2 = [C]e0 if
is “ 1 ”.
By means of the above set-theoretic de…nitions and from theorems 2.1, 2.2, 2.3, and 2.4 for the real interval operations, the following four theorems are immediate. Theorem 3.1 (Complex Interval Addition). For any two complex interval numbers X = X + iX and Y = Y + iY , complex interval addition is formulated as X + Y = (X + Y ) + i (X + Y ) . 1
Let
be a binary operation on a set S. A relation (8x1 ; x2 ; y1 ; y2 2 S) (x1
x 2 ^ y1
28
on S is compatible with
y2 ) (x1 y1 )
(x2 y2 )) .
i¤
CHAPTER 3. COMPLEX INTERVAL ARITHMETIC
Theorem 3.2 (Complex Interval Multiplication). For any two complex interval numbers X = X + iX and Y = Y + iY , complex interval multiplication is formulated as X
Y = (X Y
X Y ) + i (X Y + X Y ) .
Theorem 3.3 (Complex Interval Negation). For any complex interval number X = X + iX , complex interval negation is formulated as X = ( X ) + i( X ) =
X
iX .
Theorem 3.4 (Complex Interval Reciprocal). For any nonzero complex interval number X = X + iX , complex interval reciprocal is formulated as X iX 1 . = 2 X X + X2 An important unary operation peculiar to complex arithmetic is the conjugate operation. The conjugate of a complex interval number, X, is that complex interval number which determines a region symmetric to the region determined by X with respect to the axis of the reals. This is made precise in the following theorem. Theorem 3.5 The conjugate of a complex interval number X = X + iX is formulated as c = X + i( X ) = X X iX .
In accordance with the above theorems, we can now de…ne subtraction and division for complex interval numbers, as usual. De…nition 3.5 (Complex Interval Subtraction). For any two complex interval numbers X and Y , complex interval subtraction is de…ned by X
Y = X + ( Y ).
De…nition 3.6 (Complex Interval Division). For any complex interval number X and any nonzero complex interval number Y , complex interval division is de…ned by X 1 =X . Y Y 29
CHAPTER 3. COMPLEX INTERVAL ARITHMETIC
3.2 Point Operations for Complex Interval Numbers By analogy with point operations for real interval numbers, a point operation for complex interval numbers is an operation whose operands are complex interval numbers, and whose result is a point complex interval number (or, equivalently, an ordinary complex number). This is made precise in the following de…nition. De…nition 3.7 (Point Complex Interval Operations). Let [C]hni be the n-th Cartesian power of [C]. An n-ary point complex interval operation, ! n , is a function that maps elements of [C]hni to the set [C]p of point complex interval numbers, that is ! n : [C]hni 7 ! [C]p . Next we de…ne some point complex interval operations. De…nition 3.8 (Complex Interval In…mum). The in…mum of a complex interval number [x ; x ] + i x ; x is de…ned to be inf [x ; x ] + i x ; x
= inf ([x ; x ]) + i inf = x + ix .
x ;x
De…nition 3.9 (Complex Interval Supremum). The supremum of a complex interval number [x ; x ] + i x ; x is de…ned to be sup [x ; x ] + i x ; x
= sup ([x ; x ]) + i sup = x + ix .
x ;x
De…nition 3.10 (Complex Interval Width). The width of a complex interval number [x ; x ] + i x ; x is de…ned to be w [x ; x ] + i x ; x
= w ([x ; x ]) + iw = (x x )+i x
x ;x x .
Thus, the width of a point complex interval number is zero, that is (8x ; x 2 R) (w ([x ; x ] + i [x ; x ]) = 0 + i (0) = 0) .
30
CHAPTER 3. COMPLEX INTERVAL ARITHMETIC
De…nition 3.11 (Complex Interval Radius). The radius of a complex interval number [x ; x ] + i x ; x is de…ned to be r [x ; x ] + i x ; x
w [x ; x ] + i x ; x 2 x x (x x ) = +i 2 2 =
.
De…nition 3.12 (Complex Interval Midpoint). The midpoint (or mean) of a complex interval number [x ; x ] + i x ; x is de…ned to be m [x ; x ] + i x ; x
= m ([x ; x ]) + im x ; x x +x x +x +i = 2 2
.
Hence, the midpoint of a point complex interval number is its ordinary complex isomorphic copy, that is (8x ; x 2 R) (m ([x ; x ] + i [x ; x ]) = x + ix ) . We observe that for a complex interval number X +iX with X = [0; 0], the point operations for complex interval numbers are reduced to the corresponding point operations for real interval numbers.
3.3 Algebraic Properties of Complex Interval Arithmetic By means of the notions prescribed in the preceding two sections, we shall now inquire into some fundamental results concerning complex interval arithmetic. In a manner analogous to the proof of theorem 2.5, the following two theorems and their corollary are derivable. Theorem 3.6 Let 2 f+; g. The structure [C]I ; [C] is isomorphically equivalent to the abelian monoid [R] ; [R] of interval numbers. D
E
Theorem 3.7 The structure [C]p ; +[C] ; [C] is isomorphically equivalent to the …eld hC; +C ; C i of ordinary complex numbers. Corollary 3.1 Let [C]r = [C]I \ [C]p . The structure [C]r ; +[C] ; morphically equivalent to the …eld hR; +R ; R i of real numbers. 31
[C]
is iso-
CHAPTER 3. COMPLEX INTERVAL ARITHMETIC
That is, up to isomorphism, the set of complex interval numbers includes, as proper subsets, isomorphic copies of the sets of real numbers and interval numbers. With the help of the results of section 2.3, it can be shown that, as it is the case with real interval arithmetic, there is no distributivity between addition and multiplication of complex interval numbers except for certain special cases, and inverse elements do not always exist for complex interval numbers. Two other useful properties of ordinary complex arithmetic fail to hold in complex interval arithmetic. The following two theorems show that the additive and multiplicative properties, of ordinary complex conjugates, do not hold for complex interval conjugates. Theorem 3.8 The additive property of complex conjugates does not always hold for complex interval numbers, that is, for some complex interval number X = X + iX (X + iX ) + (X iX ) 6= 2X . Proof. By theorem 3.1, we have (X + iX ) + (X
iX ) = 2X + i (X
X ),
which, due to lack of additive inverse elements (by theorem 2.11), is not equal to 2X unless X is a point interval number. Theorem 3.9 The multiplicative property of complex conjugates does not always hold for complex interval numbers, that is, for some complex interval number X = X + iX (X + iX )
(X
iX ) 6= X 2
X2 .
Proof. By theorem 3.2, we have (X + iX )
(X
iX ) = X 2
X 2 + i (X X
which, by theorem 2.11, is not equal to X 2 interval number.
X X ),
X 2 unless X X is a point
Finally, it should be noted that interval arithmetic can be extended, in an analogous manner, to other multidimensional number systems such as quaternions and octonions, but with the expense that we have to sacri…ce other useful properties of ordinary arithmetic. 32
Chapter
4
Alternate Theories of Interval Arithmetic Can you do division? Divide a loaf by a knife: what’s the answer to that? –Lewis Carroll (1832-1898) It is not easy to perform arithmetic and solve equations in an algebraic system which is only a monoid. The algebraic system of classical interval arithmetic is only an abelian monoid, under both addition and multiplication (see theorem 2.14, on page 22), which is a poor algebraic structure, if compared to the …eld of real numbers. Two useful properties of ordinary real arithmetic fail to hold in classical interval arithmetic: additive and multiplicative inverses do not always exist for interval numbers, and there is no distributivity between addition and multiplication except for certain special cases. For instance, the solutions of the algebraic interval equations [x; x] + [a; a] =
b; b ,
y; y
b; b ,
[a; a] =
are not generally expressable in terms of the interval operations, due to the lack of inverse elements. Another main drawback of the classical interval theory is that when estimating the image of real functions using classical interval arithmetic, we usually get overestimations that inevitably produces meaningless results, if the variables are functionally dependent. This persisting problem is known as the “interval dependency problem”. A considerable scienti…c e¤ort is put into developing special methods and algorithms that try to overcome the di¢ culties imposed by the algebraic disadvantages of the classical interval arithmetic structure. Various proposals for 33
CHAPTER 4. ALTERNATE THEORIES OF INTERVAL ARITHMETIC
possible alternate theories of interval arithmetic were introduced to reduce the dependency e¤ect or to enrich the algebraic structure of interval numbers. This chapter, after describing the dependency problem, is intended to provide a bit of perspective about two important alternate theories of interval arithmetic: constraint interval arithmetic, and modal interval arithmetic (For further details, the reader can consult, e.g., [Gardenyes1985], [Hansen1975], [Hayes2009], [Kulisch2008], [Lodwick1999], and [Markov1995]).
4.1 The Interval Dependency Problem The notion of dependency comes from the notion of a function. There is scarcely a mathematical theory which does not involve the notion of a function. In ancient mathematics the idea of functional dependence was not expressed explicitly and was not an independent object of research, although a wide range of speci…c functional relations were known and were studied systematically. The concept of a function appears in a rudimentary form in the works of scholars in the Middle Ages, but only in the work of mathematicians in the 17th century, and primarily in those of P. Fermat, R. Descartes, I. Newton, and G. Leibniz, did it begin to take shape as an independent concept. Later, in the 18th century, Euler had a more general approach to the concept of a function as “dependence of one variable quantity on another”[Euler2000]. By 1834, Lobachevskii was writing: “The general concept of a function requires that a function of x is a number which is given for each x and gradually changes with x. The value of a function can be given either by an analytic expression or by a condition which gives a means of testing all numbers and choosing one of them; or …nally a dependence can exist and remain unknown”[Lobach1951]. In the theory of real closed intervals, the notion of interval dependency naturally comes from the idea of functional dependence of real variables. Despite the fact that dependency is an essential and useful notion of real variables, interval dependency is the main unsolved problem of the classical theory of interval arithmetic and its modern generalizations. The interval dependency problem can be formulated in the following theorem. Theorem 4.1 (Interval Dependency). Let Xi be real closed intervals and let y = f (x1 ; :::; xn ) be a real-valued function with xi 2 Xi . Evaluating the accurate image Y = f (X1 ; :::; Xn ) of f for the interval numbers Xi , using interval arithmetic, is not always possible if some xi are functionally dependent. Proof. Let [ z; z] be a symmetric interval number. The image of [ z; z] under 34
CHAPTER 4. ALTERNATE THEORIES OF INTERVAL ARITHMETIC
the real-valued function f (x) = x2 , is 0; z 2 . If we evaluate the image of [ z; z] using classical interval arithmetic, by theorem 2.2, we obtain, f ([ z; z]) = [ z; z] [ z; z] = z2; z2 , which is not the actual image of [ z; z] under f , and therefore evaluating the accurate image of real-valued functions is not always possible, using interval arithmetic. Obviously, the result has an overestimation of w
z 2 ; z 2 , obtained using classical interval arithmetic, z2; z2
w
0; z 2
= z2.
This overestimated result is due to the fact that the classical interval theory assumes independence of all interval variables, even when dependencies exist. A numerical example is shown below. Example 4.1 Consider the real-valued function f (x) = x (x
1) ,
with x 2 [0; 1]. The actual image of [0; 1] under f is [ 1=4; 0]. Evaluating the image using classical interval arithmetic, we get f ([0; 1]) = [0; 1]
([0; 1]
1) = [ 1; 0] ,
which has an overestimation of jw ([ 1; 0])
w ([ 1=4; 0])j = 3=4.
35
CHAPTER 4. ALTERNATE THEORIES OF INTERVAL ARITHMETIC
4.2 Constraint Interval Arithmetic A non-constructive important theory of interval arithmetic is the theory of constraint intervals. Although it is scarcely mentioned in the interval literature, if at all, constraint interval arithmetic has widespread applications in many scienti…c …elds such as arti…cial intelligence, fuzzy systems, and granular computing, which require more accuracy and compatibility with the semantic (meaning) of real arithmetic and fuzzy set theory (see, e.g., [Chen2000], [Kahraman2008], [Pedrycz2008], [Pichler2007], and [Yu2004]). The theory of constraint intervals was introduced by Weldon Lodwick in [Lodwick1999], but it has an earlier root in Cleary’s “logical arithmetic”which is a logical technique, for real arithmetic in Prolog, that uses constraints over real intervals (see [Cleary1987] and [Cleary1993]). In the sequel, we provide a brief introduction to constraint interval arithmetic. A constraint interval number is de…ned as follows. De…nition 4.1 Let x; x 2 R such that x de…ned to be [x; x] = fx 2 Rj (9
x
x. A constraint interval number is
2 [0; 1]) (x = (x
x)
x
+ x)g,
where min (x) = x and max (x) = x are, respectively, the lower and upper x
x
bounds (endpoints) of [x; x]. Obviously, de…nition 4.1 is equivalent to de…nition 2.1, and a constraint interval number is a closed and bounded nonempty real interval. However, to simplify the exposition, we shall denote the set of constraint interval numbers by c [R], and the upper-case Roman letters X, Y , and Z (with or without subscripts), or equivalently [x; x], y; y , and [z; z], shall be still employed as variable symbols to denote elements of c [R]. The sets of point and nonzero constraint interval numbers shall be denoted, as usual, by the right-subscripted symbols c [R]p and c [R]e0 , respectively.
In de…nition 4.1, a constraint interval number is de…ned as the image of a continuous real-valued function x of one variable x 2 [0; 1] and two constants x and x. The endpoints, x and x, are respectively the minimum and maximum
36
CHAPTER 4. ALTERNATE THEORIES OF INTERVAL ARITHMETIC
of x (see Figure 4.1) with the constraint 0
x
1 , 0 , x , x
(x x) (x x) x x.
(x x) x x+x
x
Figure 4.1: A constraint interval number as the image of a continuous real function.
Three arguments (x; x; x ) are necessary to deal with dependencies. Since the numbers x and x are known inputs, they are parameters whereas x is varying and hence a variable that is constrained between 0 and 1, hence the name “constraint interval arithmetic”. The binary constraint interval operations can be guranteed to be continuous by introducing two constrained variables x ; y 2 [0; 1]. From the fact that x 2 [x; x] and y 2 y; y are continuous real-valued functions of x and y respectively, the result of a constraint interval operation shall be the image of the continuous function x y = ((x with
x;
y
x)
x
+ x)
y
y
y
+y ,
2 [0; 1].
According to the functional dependence of real variables, we then have two types of constraint interval operations, namely “dependent operations”and “independent operations”. The dependent and independent constraint interval operations are characterized in the following two de…nitions.
37
CHAPTER 4. ALTERNATE THEORIES OF INTERVAL ARITHMETIC
De…nition 4.2 (Constraint Dependent Operations). For any constraint interval number [x; x], there exists a constraint interval number [z; z] such that [z; z] = [x; x] [x; x] = fz 2 Rj (9x 2 [x; x]) (z = x x)g = fz 2 Rj (9 x 2 [0; 1]) (z = ((x x)
x
+ x) ((x
x)
x
+ x))g,
where z = min (z) = min (x x) , z
x
z = max (z) = max (x x) , z
and
x
2 f+; ; ; g such that 0 2 = [x; x] if
is “ ”.
De…nition 4.3 (Constraint Independent Operations). For any two constraint interval numbers [x; x] and y; y , there exists a constraint interval number [z; z] such that [z; z] = [x; x]
y; y
= fz 2 Rj (9x 2 [x; x]) 9y 2 y; y (z = x y)g = fz 2 Rj (9 x 2 [0; 1]) (9 y 2 [0; 1]) z = ((x x) x + x) y y y + y g, where z = min (z) = min (x y) , x; y
z
z = max (z) = max (x y) , x; y
z
and
2 f+; ; ; g such that 0 2 = y; y if
is “ ”.
It is obvious, from de…nitions 4.2 and 4.3, that constraint interval arithmetic is a mathematical programming problem, and therefore constraint interval operations can be easily performed by any constraint solver such as GeCode1 , HalPPC2 , and MINION3 . The minimization and maximization are well-de…ned, attained, and the resultant [z; z] is in turn a constraint interval number. 1
http://www.gecode.org/
2
http://sourceforge.net/projects/halppc
3
http://minion.sourceforge.net/ 38
CHAPTER 4. ALTERNATE THEORIES OF INTERVAL ARITHMETIC
If there is no dependency between interval numbers, using constraint independent operations, we have the same results as in classical interval arithmetic. When dependencies exist, using constraint dependent operations, we have di¤erent results. Thus, constraint interval arithmetic has algebraic properties di¤erent than those of the classical interval theory. Some of the algebraic properties of constrained interval arithmetic are formulated in the following theorems. Theorem 4.2 For any constraint interval number [x; x], we have [x; x] + [x; x] = [2x; 2x] . Proof. By de…nitions 4.1 and 4.2, we have [z; z] = [x; x] + [x; x] = fz 2 Rj (9x 2 [x; x]) (z = 2x)g = fz 2 Rj (9 x 2 [0; 1]) (z = 2 ((x
x)
Optimizing z, with respect to the constraint variable [2x; 2x].
x x,
+ x))g.
we thus get [z; z] =
Theorem 4.3 For any constraint interval number [x; x] with x < x, we have h i 2 2 2 2 [x; x] [x; x] = minfx ; x ; 0g; maxfx ; x ; 0g . Proof. By de…nitions 4.1 and 4.2, we have [z; z] = [x; x] [x; x] = fz 2 Rj (9x 2 [x; x]) z = x2 g = fz 2 Rj (9
x
2 [0; 1]) z = ((x
x)
z, with respect ito the constraint variable h Optimizing 2 2 2 2 minfx ; x ; 0g; maxfx ; x ; 0g .
x
x,
+ x)2 g. we thus get [z; z] =
In a manner analogous to the proofs of the above theorems, the following three important results are derivable. Theorem 4.4 (8X 2
c
[R]) (X
X = [0; 0]). 39
CHAPTER 4. ALTERNATE THEORIES OF INTERVAL ARITHMETIC
Theorem 4.5 8X 2
c
[R]e0 (X
Theorem 4.6 (8X; Y; Z 2
c
X = [1; 1]).
[R]) (Z
(X + Y ) = Z
X +Z
Y ).
Thus, unlike classical interval arithmetic, constraint interval arithmetic has an additive inverse, a multiplicative inverse and satis…es the distributive law. Point operations, for a constraint interval number [x; x], are also min-max optimization problems with respect to the constraint variable x 2 [0; 1], and have the same results as in classical interval arithmetic. Some of the point operations for constraint interval numbers are listed below. De…nition 4.4 (Constraint Width). The width of a constraint interval number [x; x] is de…ned to be w ([x; x]) = max (x)
min (x)
x
x
= x
x.
De…nition 4.5 (Constraint Radius). The radius of a constraint interval number [x; x] is de…ned to be w ([x; x]) 2 (x x) = . 2
r ([x; x]) =
De…nition 4.6 (Constraint Midpoint). The midpoint (or mean) of a constraint interval number [x; x] is de…ned to be max (x) + min (x) m ([x; x]) = =
x
x
2 (x + x) . 2
De…nition 4.7 (Constraint Absolute Value). The absolute value of a constraint interval number [x; x] is de…ned to be j[x; x]j = max f min (x) ; max (x) g x
= max (fjxj ; jxjg) . 40
x
CHAPTER 4. ALTERNATE THEORIES OF INTERVAL ARITHMETIC
Finally, it should be mentioned that the main advantage of constraint interval arithmetic, over all other theories of intervals, is that; the theory of constraint intervals is completely compatible with the semantic of real arithmetic. That is, any sentence of real arithmetic can be translated to a semantically equivalent sentence of constraint interval arithmetic. Furthermore, the min-max constraint interval operations produce the accurate result, if there is a way to keep the dependency information during a long series of calculations, which is not always possible.
4.3 Modal Interval Arithmetic The theory of modal intervals, constructed by Ernest Gardenyes in 1985 (see [Gardenyes1985]), is a de…nitional extension 4 of the classical interval theory that provides a set of interval arithmetic sentences which is semantically equivalent to a larger subset of the sentences of real arithmetic. A basic problem of the classical interval theory is that the semantic of quanti…cation over real variables is lost in classical interval arithmetic. To illustrate this, let real arithmetic
2 f+; g and consider the following two sentences of
(8x 2 [x; x]) 8y 2 y; y
(8x 2 [x; x]) 9y 2 y; y
(9z 2 R) (z = x y) , (9z 2 R) (z = x y) .
The classical interval theory has the following single translation for the above two real sentences, (9Z 2 [R]) Z = [x; x] y; y ,
which is semantically equivalent to the …rst real sentence. The meaning of the second sentence is lost in classical interval arithmetic, because the semantic of the existential quanti…cation over y; y is not kept by the set-theoretic de…nition of classical interval operations (de…nition 2.5). Modal interval arithmetic, which is based entirely on predicate logic and set theory, is conceived to solve this problem.
In the sequel, the basic concepts of the modal theory of interval arithmetic are brie‡y introduced. Next we de…ne what a modal interval is. 4
See footnote 4, on page 12.
41
CHAPTER 4. ALTERNATE THEORIES OF INTERVAL ARITHMETIC
De…nition 4.8 Let [x; x] be a classical (set-theoretic) interval number, and let QX 2 f8; 9g be a logical quanti…er. A modal interval m X is an ordered pair such that m i¤ QX is 9, [x; x] m X = ([x; x] ; QX ) = m [x; x] i¤ QX is 8, such that
m
[x; x] = f'j' , (9x 2 [x; x]) (P (x))g, m [x; x] = f'j' , (8x 2 [x; x]) (R (x))g,
where P (x) and R (x) are some real predicates for which the existential and universal sentences are true respectively. That is, a modal interval (the term “modal pair” or “modal set” is better) is not a set-theoretical interval. In a manner analogous to how a real number x can be represented as a pair (jxj ; ) whose …rst element is the absolute value of x and whose second element is a negative or positive sign, a modal interval can be represented as a pair of a set-theoretical interval and a logical quanti…er. Thus, a modal interval ([x; x] ; QX ) is the set of all true real sentences with respect to the quanti…cation QX x 2 [x; x]. For example, ([2; 3] ; 9) = ([2; 3] ; 8) =
m m
[2; 3] = f'j' , (9x 2 [2; 3]) (P (x))g, [3; 2] = f'j' , (8x 2 [2; 3]) (R (x))g,
where the sentences (9x 2 [2; 3]) (x > 2) , (8x 2 [2; 3]) (x 2) , are, respectively, elements of ([2; 3] ; 9) and ([2; 3] ; 8). The set M of modal intervals is characterized as follows. De…nition 4.9 M = f(X; QX ) jX 2 [R] ^ QX 2 f8; 9gg. Hereafter, the left-superscripted Roman letters m X, m Y , and m Z (with or without subscripts), or equivalently m [x; x], m y; y , and m [z; z], shall be employed as variable symbols to denote elements of M. Classical interval numbers shall be denoted as usual. To further simplify the exposition, it is convenient to introduce the following notational conventions. 42
CHAPTER 4. ALTERNATE THEORIES OF INTERVAL ARITHMETIC
Notation 4.1 A modal interval (X; 8) is called a universal (or improper) modal interval. The set of all universal modal intervals shall be denoted by M8 . Notation 4.2 A modal interval (X; 9) is called an existential (or proper) modal interval. The set of all existential modal intervals shall be denoted by M9 . Notation 4.3 A modal interval (X; Q) with X 2 [R]p is called a point modal interval. The set of all point modal intervals shall be denoted by Mp . Next we de…ne the M ode, Set, Dual, inf, and sup operators for modal intervals. m
De…nition 4.10 The mode of a modal interval 9 8
M ode (m [x; x]) =
i¤ i¤ m
De…nition 4.11 The set of a modal interval
[x; x] is de…ned to be x x
x, x.
[x; x] is de…ned to be
Set (m [x; x]) = [minfx; xg; maxfx; xg] . De…nition 4.12 The dual of a modal interval Dual (m [x; x]) =
m
m
[x; x] is de…ned to be
[x; x] .
De…nition 4.13 The in…mum of a modal interval m X is de…ned to be inf (m X) =
min (Set (m X)) max (Set (m X))
i¤ i¤
M ode (m X) = 9, M ode (m X) = 8.
De…nition 4.14 The supremum of a modal interval m X is de…ned to be sup (m X) =
max (Set (m X)) min (Set (m X))
i¤ i¤
M ode (m X) = 9, M ode (m X) = 8.
It should be noted that the inf and sup operators of a modal interval m X are canonical, that is, they are not necessarily the in…mum and supremum of the corresponding set-theoretical interval X. Some numerical examples are shown below. 43
CHAPTER 4. ALTERNATE THEORIES OF INTERVAL ARITHMETIC
Example 4.2 For two given modal intervals (i)
m
[1; 2] = ([1; 2] ; 9),
m
m
[1; 2] and
m
[4; 3], we have
[4; 3] = ([3; 4] ; 8);
(ii) M ode (m [1; 2]) = 9, M ode (m [4; 3]) = 8; (iii) Set (m [1; 2]) = [1; 2], Set (m [4; 3]) = [3; 4]; (iv) Dual (m [1; 2]) =
m
[2; 1] = ([1; 2] ; 8);
(v) Dual (m [4; 3]) =
m
[3; 4] = ([3; 4] ; 9);
(vi) inf (m [1; 2]) = 1, inf (m [4; 3]) = 4; (vii) sup (m [1; 2]) = 2, sup (m [4; 3]) = 3. The result of a modal algebraic operation is a set of true real arithmetic sentences. The algebraic operations for modal intervals are characterized in the following de…nition. De…nition 4.15 (Modal Algebraic Operations). Let m X = (X; QX ), m Y = (Y; QY ), and m Z = (Z; QZ ) be modal intervals. For any algebraic operator , let P (x; y; z) , z = x y be a true real predicate with respect to the quanti…cations QX x 2 X, QY y 2 Y , and QZ z 2 Z, where QX ; QY ; QZ 2 f8; 9g. Then the modal algebraic operations are de…ned as m
Z = mX mY = f'j' , (QX x 2 X) (QY y 2 Y ) (QZ z 2 Z) (z = x y)g.
Providing the details for all the ensuing cases, with 2 f+; ; ; g, is beyond the scope of this introductory text. However, we state, without proofs, the following two important results. Theorem 4.7 For any modal interval m X, we have m
X
Dual (m X) =
m
[0; 0] .
Theorem 4.8 For any modal interval m X with 0 2 = Set (m X), we have m
X
Dual (m X) = 44
m
[1; 1] .
CHAPTER 4. ALTERNATE THEORIES OF INTERVAL ARITHMETIC
That is, additive and multiplicative inverses exist in modal interval arithmetic. Unlike the theory of constraint intervals, not every sentence of real arithmetic can be translated to a semantically equivalent sentence of modal arithmetic, without loss of dependency information. Furthermore, in spite of the promising applications of modal intervals, its complicated construction is often misunderstood, which is a drawback for it to have widespread applications.
45
Chapter
5
Computational Applications of Interval Arithmetic An error does not become truth by reason of multiplied propagation, nor does truth become error because nobody sees it. –Mahatma Gandhi (1869-1948) It was realized that interval arithmetic has the potential of solving many computational problems that are inaccessible to conventional approaches. The interval theory provides several powerful tools that make it possible to attack problems that were previously intractable. With its self-validation nature, interval arithmetic is promising in bounding the e¤ects of round-o¤ errors and solving uncertainty problems that cannot be e¢ ciently solved by ‡oating-point arithmetic. In this chapter, we delve into some computational applications of the interval theory. Here we explain, in some detail, the interval estimates of the images of continuous real functions on closed intervals, how interval methods are used to bound the error term in Taylor’s theorem, and how interval arithmetic is applied to evaluate de…nite integrals (For further computational applications of the interval theory, the interested reader my consult, e.g., [Hales2005], [Hansen2003], [Jaulin2001], [Moore2009], and [Pedrycz2008]).
47
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
5.1 Estimates of the Image of Real Functions Interval arithmetic could be used to obtain bounds on the image of a continuous function de…ned on a closed interval number X as its preimage. We use the fact that, since interval numbers are the connected subsets of R, the image of an interval number by any continuous function is also an interval number. We …rst de…ne the image set of a real-valued function f . De…nition 5.1 (Image of a Function). Let f : D 7 ! R be a real-valued function whose domain is D and whose range is R. The image of a subset A D, under f , is de…ned to be f (A) = fy 2 Rj (9x 2 A) (y = f (x))g
R.
We can prove easily that, if f is continuous on the interval number X = [x; x] D, then by de…nition 5.1 the image set f (X) is given by f (X) = minf (x) ; maxf (x) , x2X
x2X
(5.1)
as a result of equation 5.1, if the function f is monotonic on X, then the image f (X) can be computed easily by applying the function to the endpoints x and x as follows f (X) = [min ff (x) ; f (x)g ; max ff (x) ; f (x)g], hence, we get, for non-decreasing f , f (X) = [f (x) ; f (x)] ,
(5.2)
f (X) = [f (x) ; f (x)] .
(5.3)
and for non-increasing f ,
Next, we give some examples illustrating the use of interval arithmetic to estimate the images of some elementary real functions. p Example 5.1 Consider the functions f1 (x) = ex , f2 (x) = log x, f3 (x) = x, and f4 (x) = xn where n is an odd positive integer and x 2 X = [x; x] (with x > 0 in case of f2 and f3 ). These functions are all non-decreasing on X. So, by equation 5.2, we can easily get their images as an interval number whose lower 48
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
Figure 5.1: A continuous non-decreasing function f .
and upper endpoints are simply the function applied to x and x, respectively. For example, the image of f2 is given by f2 (X) = log X = [log x; log x] . Example 5.2 The function f (x) = e x with x 2 X = [x; x] is a non-increasing function on X. So, by equation 5.3, we can get its image as an interval number whose lower and upper endpoints are the function applied to x and x, respectively. Hence the image of f is given by f (X) = e
X
= e x; e
x
.
The following example illustrates the case with piecewise monotonic functions. Example 5.3 The function f (x) = xn where n is an even positive integer and x 2 X = [x; x]. This is a non-increasing function for x < 0 and a nondecreasing function for x > 0. So, by equations 5.2, 5.3, and 5.1, the image of f is given by 8 n n x 0, < [x ; x ] n n n x < 0, [x ; x ] f (X) = X = : n n [0; max fx ; x g] otherwise. 49
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
Figure 5.2: A continuous non-increasing function f .
So, for piecewise monotonic functions, it is su¢ cient to consider the endpoints x, x of the interval number X together with the critical points, the points where the monotonicity of the function changes direction, within X. It should be noted that the exponentiation X n , de…ned in the above example, is not consistent with interval multiplication. As we mentioned before (see example 2.2, on page 12), this is not a problem if interval arithmetic is regarded as a numerical approximation method for real-valued problems, but not as a de…nitional extension, in the logical sense, of the theory of real numbers (see footnote 4, on page 12). The next example shows that even if the function is not monotonic, some restrictions on its domain could be monotonic, and we could use the previous tools to easily estimate its image. Example 5.4 The function f (x) = sin x with x 2 R. Here f is not monotonic on R, but its restriction to the interval number 2 ; 2 is non-decreasing. Hence, by equation 5.2, the image of any interval number X = [x; x] 2 ; 2 under f is given by f (X) = sin X = [sin x; sin x] . The previous examples show how we could estimate the images of elementary functions using interval arithmetic tools with the help of the monotonicity properties of these functions. 50
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
Next, we give more general examples for many types of functions and show how we could estimate their images. Example 5.5 Consider the continuous function f (x) = x + 3 with x 2 X = [x; x]. To estimate its image, simply we replace each occurrence of x by the interval number in which it lies, X, and each real elementary operation by the corresponding interval elementary operation. So, the image of f is estimated as follows f (X) = X + 3 = [x; x] + [3; 3] = [x + 3; x + 3] . For instance, if X = [x; x] = [2; 5], then the image is [2 + 3; 5 + 3] = [5; 8]. Example 5.6 Consider the continuous function f (x) = x2 + x + 5 with x 2 X = [x; x]. To estimate its image, as before, we replace each occurrence of x by the interval number in which it lies, X, and each real elementary operation by the corresponding interval elementary operation. So, we get f (X) = X 2 + X + 5 = [x; x]2 + [x; x] + [5; 5] , Hence, to estimate the image we should know the signs of x and x to be able to determine the value of [x; x]2 , as in example 5.3. For instance, if X = [x; x] = [ 3; 1], then the image is estimated as f (X) = = = =
[ 3; 1]2 + [ 3; 1] + [5; 5] [1; 9] + [ 3; 1] + [5; 5] [ 2; 8] + [5; 5] [3; 13] .
Here, we notice that the result is not the exact image of f , which is [5; 11], but instead an inclusion of it. That is, the exact image of f is an interval number which is a subset of the resulting interval number [3; 13]. This means that applying interval arithmetic, despite its simplicity, gives an inevitable overestimated results. This is because the so called dependency problem, see section 4.1, on page 34. Example 5.7 Consider the continuous function f (x) = x (x 1) with x 2 X = [x; x]. By the same techniques as before, the image of f is estimated as 51
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
follows f (X) = X (X 1) = [x; x] ([x; x] [1; 1]) = [x; x] [x 1; x 1] . For instance, if X = [x; x] = [0; 1], then the image is estimated as f (X) = [0; 1] [0 1; 1 = [0; 1] [ 1; 0] = [ 1; 0] .
1]
The resulting interval number is an overestimated result, it is an inclusion of 1 the exact image of f which is 4; 0 . Next we give a more complicated example. Example 5.8 Consider the continuous function f (x) = ex + x2 + x with x 2 X = [x; x]. The image is estimated as follows f (X) = eX + X 2 + X = e[x;x] + [x; x]2 + [x; x] , The value of e[x;x] could be easily evaluated as in example 5.1 since it is nondecreasing on X. But determining the value of [x; x]2 needs us to know the signs of x and x as we mentioned in example 5.3. For instance, if X = [x; x] = [ 2; 5], then the image could be estimated as oi h n 2 2 2 5 + [ 2; 5] f (X) = e ; e + 0; max ( 2) ; (5) = = =
e 2 ; e5 + [0; 25] + [ 2; 5] e 2 ; e5 + 25 + [ 2; 5] e 2 2; e5 + 30 .
Again, we get an inclusion of the exact image, which is e 2 + 2; e5 + 30 , due to the dependency e¤ect. But the important point is that the exact image is always included in the resulting interval number. So, the inevitable overestimation caused by the dependency problem does not a¤ect the important information. Instead, it introduces additional unneeded information.
52
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
5.2 Bounding the Error Term in Taylor’s Series Taylor’s series, introduced by the English mathematician Brook Taylor (16851731) in 1715, is an expansion of a function as an in…nite sum of terms. It is a common practice, especially in digital computing, to approximate a function by using a …nite number of terms of its Taylor’s series. Taylor’s theorem, one of the elementary theorems in mathematical analysis, gives quantitative estimates on the error in this approximation. In this section, we shall discuss, in some detail, how interval arithmetic can be applied to obtain bounds on the remainder term in Taylor’s series. Our objective is to obtain an interval number in which the exact value of the remainder is guaranteed to lie. We begin …rst by stating the statement of Taylor’s Theorem. Theorem 5.1 (Taylor’s Theorem). Let n be an integer such that n 1 and let the function f : R 7 ! R be such that its (n 1)-th derivative, namely f (n 1) (x), is continuous on the closed interval number [a; b] and the n-th derivative f (n) (x) exists on the open interval ]a; b[. Then for each x 2 [a; b] we have f (x) = pn (x) + rn (x) , (5.4) where pn (x) =
n 1 X
f
(k)
(a)
a)k
(x k!
k=0
, rn (x) =
(x
a)n (n) f ( ), n!
(5.5)
and a < < x. The polynomial pn (x) is called the (n 1)-th degree Taylor polynomial approximation of f , and the term rn (x) is called the Lagrange form of the remainder. If we set a = 0 in equations 5.4 and 5.5, we get the so called Maclaurin’s series with remainder: f (x) =
n 1 X
f
(k)
k=0
xk (0) + rn (x) , k!
(5.6)
where the remainder rn (x) in this case is given as rn (x) = with 0 <
xn (n) f ( ), n!
< x. 53
(5.7)
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
The importance of the Lagrange form of the remainder term rn (x) of Taylor’s series, equation 5.5, is that, starting from the fact that is known to lie somewhere between a and x, we can obtain a closed interval number which will contain the exact value of this remainder. Given that the n-th derivative of the function f is either monotonically increasing or decreasing in the interval a to x, we can construct a closed interval number such that the function can be approximated by Taylor’s series with rigorous error bounds. The desired interval number will contain all possible values of rn (x) for a < < x. Obviously, if takes on every possible value between a and x, then rn (x) is bounded. To simplify the exposition, we simply write rn instead of rn (x) to refer to the Lagrange form of the remainder of Taylor’s series in equation 5.5, also let rn;a = and rn;x = It is clear that either rn;a
(x
a)n (n) f (a) , n!
(5.8)
(x
a)n (n) f (x) . n!
(5.9)
rn
rn;x or rn;x
rn
rn;a .
A …rst important result, concerning the desired interval number which contains rn , is formulated in the next theorem. Theorem 5.2 The interval number Rn;i = [min frn;a ; rn;x g ; max frn;a ; rn;x g] ,
(5.10)
contains rn . Proof. The proof is immediate from equations 5.5, 5.8, and 5.9. In an analogous manner, we can construct the interval number which contains the remainder term of Maclaurin’s series, equation 5.7, by setting a = 0 in equation 5.10 as follows Rn;i = [min frn;0 ; rn;x g ; max frn;0 ; rn;x g] .
(5.11)
An immediate consequence, for the interval number Rn;i , is the following.
54
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
Theorem 5.3 (Taylor’s Theorem with Interval Remainder). Let n be an integer such that n 1 and let f be a real-valued function which meets the conditions of Taylor’s theorem and its n-th derivative is monotonically increasing or decreasing between a and x. Then f (x) 2 pn (x) + Rn;i , where pn (x) is given as in equation 5.5 and Rn;i is given by equation 5.10. In practice, we often start a computation with an inexact value of x, say, x " for some " 2 R. Taking into account this inaccuracy of the parameter x, we can obtain a Taylor expansion of the function f with precise error bounds. Hereafter, let the conditions of theorem 5.3 be met by the function f . Suppose x is not precisely known, but rather, we have x " for some " 2 R. What follows, is a procedure for simultaneously doing the initial computation of the value of the function f for x and the error analysis, thus obtaining an interval number in which the exact value of the function is known to lie. Let f (x + ") and f (x ") be the values of f at x + " and x ", respectively. Then f (x + ") and f (x ") can both be computed by Taylor’s theorem with the remainder as an interval number, theorem 5.3. Hence f (x + ") can be computed as follows f (x + ") 2 pn (x + ") + Rn; , (5.12) where Rn; is computed by replacing x by x + " in Rn;i (equation 5.10), that is Rn; = [min frn;a ; rn;x+" g ; max frn;a ; rn;x+" g] , where the condition on the remainder term is now a < In an analogous manner, f (x f (x
(5.13)
< x + ".
") can be computed as
") 2 pn (x
where Rn; is computed by replacing x by x
") + Rn; ,
(5.14)
" in Rn;i (equation 5.10), that is
Rn; = [min frn;a ; rn;x " g ; max frn;a ; rn;x " g] , and the condition on the remainder term is a <
<x
(5.15)
".
Applying theorems 2.5 and 2.1, equation 5.12 becomes f (x + ") 2 [pn (x + ") + min (Rn; ) ; pn (x + ") + max (Rn; )] ,
(5.16)
where min (Rn; ) and max (Rn; ) are respectively the lower and upper bounds 55
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
of Rn; . Similarly, equation 5.14 becomes f (x
") 2 [pn (x
") + min (Rn; ) ; pn (x
") + max (Rn; )] .
(5.17)
In accordance with equations 5.16 and 5.17, we get the following important result, for computing an interval number which contains all values of the function f at x ", and which also contains the upper and lower error bounds, f (x
") 2 f ; f ,
(5.18)
where f = min fpn (x
") + min (Rn; ) ; pn (x + ") + min (Rn; )g ,
f = max fpn (x
") + max (Rn; ) ; pn (x + ") + max (Rn; )g .
and
If a is everywhere replaced by 0, we obtain an interval number which contains all values of f (x ") expanded by Maclaurin’s series. As a conclusion, it has been shown that, by using interval arithmetic, we can obtain explicit interval numbers containing the exact solution and the error bounds for any function satisfying the conditions of theorem 5.3. The following example makes this clear. Example 5.9 Using the Maclaurin’s series to calculate sin (x "), it is assumed that x lies in the interval number 0; 2 . We notice that the conditions of theorem 5.3 are satis…ed. We shall now …nd an interval number which contains sin (1 0:01) to …ve decimal places accuracy. The error bound will then be in the sixth place. By means of equations 5.16 and 5.17, we get sin (1 + 0:01) = sin (1:01) 2 [0:846831; 0:846832] , and sin (1
0:01) = sin (0:99) 2 [0:836025; 0:836026] ,
while the values of sin (1:01) and sin (0:99), using traditional numerical methods, approximated to seven decimal places are respectively 0:8468318 and 0:8360259. Now, applying equation 5.18, we get sin (1
0:01) 2 [0:836025; 0:846832] .
Obviously, all values of sin x for 0:99 interval number.
x 56
1:01 are included in the resulting
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
5.3 Estimates of De…nite Integrals The de…nite integral is an elementary and important operation in calculus, which can be used to …nd the area under a curve. It is a basic tool in the signi…cance of geometic quantities such as area, volume, and arc length, in addition to many other applications involving the calculation of quantities like mass, ‡uid pressure, etc. This section is intended to provide a brief discussion of how interval arithmetic can be applied to estimate the values of de…nite integrals. That is, to compute enclosures for the de…nite integrals of real-valued functions. In what follows, Let f be a continuous real function on the interval number X = [a; b]. We shall use the following notation to express the de…nite integral of f from a to b, Z Z f (x) dx =
X
f (x) dx.
[a;b]
Figure 5.3: The de…nite integral of a function f .
We begin …rst by the following important lemma. Lemma 5.1 Let f (X) be the image of X under f , then Z f (x) dx 2 f (X) w (X) , X
where w (X) is the width of the interval number X. 57
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
Proof. By the mean value theorem for de…nite integrals, there exists some real number s 2 [a; b] such that Z Z f (x) dx = f (x) dx = f (s) (b a) , X
[a;b]
but, by equation 5.1, we conclude that f (s) 2 f (X), and, by de…nition 2.13, we have b a = w (X) , hence the lemma follows. We next prove the basic theorem of this section. Theorem 5.4
R
X
f (x) dx 2 w (X) minf (x) ; w (X) maxf (x) . Moreover, if x2X
x2X
the function f is non-decreasing on X, then Z f (x) dx 2 [w (X) f (a) ; w (X) f (b)] , X
and if f is non-increasing on X, then Z f (x) dx 2 [w (X) f (b) ; w (X) f (a)] . X
Proof. By lemma 5.1, we have Z f (x) dx 2 f (X)
w (X) ,
X
and, by equation 5.1, the image f (X) is given by f (X) = minf (x) ; maxf (x) , x2X
x2X
hence, with the help of theorems 2.5 and 2.2, we get Z f (x) dx 2 f (X) w (X) = minf (x) ; maxf (x) x2X
X
=
x2X
[w (X) ; w (X)]
w (X) minf (x) ; w (X) maxf (x) . x2X
The last result clearly holds since w (X)
58
x2X
0. If the function f is non-decreasing
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
on X, then by means of equation 5.2, we get Z f (x) dx 2 [w (X) f (a) ; w (X) f (b)] . X
In an analogous manner, if f is non-increasing on X, then by equation 5.3, we get Z f (x) dx 2 [w (X) f (b) ; w (X) f (a)] , X
which completes the proof.
For piecewise monotonic functions, one can estimate the de…nite integral on the interval number X = [a; b] by dividing X into n-subinterval numbers X1 = [a; a1 ], X2 = [a1 ; a2 ],..., Xn = [an ; b] such that the function is either monotonically increasing or decreasing. That is, using the additive properties of de…nite integrals, Z Z f (x) dx = f (x) dx X [a;b] Z Z Z = f (x) dx + f (x) dx + ::: + f (x) dx [an ;b] Z[a;a1 ] Z [a1 ;a2 ] Z = f (x) dx + f (x) dx + ::: + f (x) dx =
X1 n XZ i=1
X2
Xn
f (x) dx.
Xi
Examples are shown below. Example 5.10 Estimate
R
[0;2] x
2
dx.
The function f (x) = x2 is an increasing function on the interval number [0; 2], hence Z [0;2]
x2 dx 2 [(2) (0) ; (2) (4)] = [0; 8] .
The exact value of this de…nite integral is
8 3
2 [0; 8].
We notice in the previous example that the width of the resulting interval number is relatively not small. In fact, if we divide the interval number [0; 2] into two subinterval numbers [0; 1] and [1; 2] and repeat the computation using 59
CHAPTER 5. COMPUTATIONAL APPLICATIONS OF INTERVAL ARITHMETIC
the additive properties of de…nite integrals, we get Z Z Z x2 dx = x2 dx + x2 dx 2 [1; 5] [0;2]
[0;1]
[0; 8] ,
[1;2]
which has half the width and thus is more accurate than the result obtained by direct estimation. This is due to the fact that, when the width of the interval number decreases, it tends to be a point interval number which su¤ers less of the overestimation caused by the dependency e¤ect. The following example illustrates the case with piecewise monotonic functions. Example 5.11 Estimate
R
[0; ] sin xdx.
The function f (x) = sin x is increasing on the interval number 0; 2 and decreasing on the interval number 2 ; . Hence Z Z Z sin xdx = sin xdx + sin xdx [0; ] 0; ; [ ] [ ] i 2 h 2i h + 0; = [0; ] . 2 0; 2 2 The exact value of this de…nite integral is 2 2 [0; ].
60
Chapter
6
Hardware Implementation of Interval Arithmetic I am ashamed to tell you to how many …gures I carried these calculations, having no other business at the time. –Isaac Newton (1642-1727) There are numerous software implementations for interval arithmetic, which are usually provided as class libraries. Interval class libraries and language extensions are available for many numeric and symbolic programming languages such as C++, Java, Fortran, Mathematica, Maple, Lisp, Macsyma, and Coq (For further details, see, e.g., [Fateman2009], [Hansen2003], [Jaulin2001], and [Keene1988]). However, existing software packages for interval arithmetic, in which interval calculations is simulated with ‡oating-point routines, are often too slow for numerically intensive calculations. Therefore, interval arithmetic is about …ve times slower than ‡oating-point arithmetic, if no special hardware implementations are provided such that interval arithmetic is directly supported on the machine level. Fortunately, computers are getting faster and most existing parallel processors provide a tremendous computing power. So, with little extra hardware, it is very possible to make interval computations as fast as ‡oating point computations. In this chapter, we begin with some key concepts of machine real arithmetic, and then carefully construct the algebraic system of machine interval arithmetic and deduce its fundamental properties. In section 6.2, we design a simple circuitry that shows how to realize interval addition on a machine. The …nal section of this chapter introduces how to use a ‡oating-point multiplier and 61
CHAPTER 6. HARDWARE IMPLEMENTATION OF INTERVAL ARITHMETIC
a comparator to design a simple interval squarrer circuitry (For further reading about the hardware support for interval arithmetic, see, e.g., [Kolev1993], [Muller2009], and [Neumaier1991]).
6.1 Machine Interval Arithmetic The arithmetics of intervals de…ned in the preceding chapters are called exact interval arithmetics. However, when interval arithmetic is realized on a computer, we get some loss of accuracy due to round-o¤ errors. Therefore, due to the fact that there is only a …nite subset M R of machine-representable numbers, special care has to be taken to guarantee a proper hardware implementation of interval arithmetic. Thus, we need a machine interval arithmetic in which interval numbers have to be rounded so that the interval result computed by a machine always contains the exact interval result. 6.1.1 Rounded-Outward Interval Arithmetic The algebraic operations of the classical theory of interval arithmetic are de…ned in such a way that they satisfy the property of inclusion monotonicity (see theorem 2.13, on page 22). An important immediate consequence of the inclusion monotonicity is that given two interval numbers [x; x] and y; y with x 2 [x; x] and y 2 y; y , then for any unary operation 2 f ; 1 g or binary operation 2 f+; g, the real and interval results shall satisfy x 2 [x; x] , x y 2 [x; x] y; y .
(6.1)
That is, guaranteed enclosures of the real-valued results can be obtained easily by computing on interval numbers. The following formulas can be deduced immediately from formulas 6.1. x 2 [ x; x] , h 1 1i 1 x 2 x ; x , if 0 2 = [x; x] ,
x+y 2
x
y 2
x + y; x + y ,
(6.2)
minfxy; xy; xy; xyg; maxfxy; xy; xy; xyg .
Formulas 6.2 use the arithmetic of real numbers that are not machinerepresentable. However, using outward rounding for interval numbers, we can obtain alternate formulas that use ‡oating-point arithmetic, and still satisfy the 62
CHAPTER 6. HARDWARE IMPLEMENTATION OF INTERVAL ARITHMETIC
property of inclusion monotonicity. Two de…nitions we shall need are those of the downward and upward rounding operators. De…nition 6.1 (Downward Rounding). Let x be any real number and let xm denote a machine-representable real number. Then there exists a machinerepresentable real number 5x such that 5x = supfxm 2 Mjxm
xg,
where 5 is called the downward rounding operator. De…nition 6.2 (Upward Rounding). Let x be any real number and let xm denote a machine-representable real number. Then there exists a machinerepresentable real number 4x such that 4x = inffxm 2 Mjx
xm g,
where 4 is called the upward rounding operator. On the basis of these de…nitions, we can obtain a …nite set [M] machine interval numbers by rounding interval numbers outward.
[R] of
De…nition 6.3 (Outward Rounding). Let [x; x] be any interval number. Then there exists a machine-representable interval number [x; x] such that [x; x] = [5x; 4x] , where
is called the outward rounding operator.
With outward rounding, a machine interval arithmetic can be de…ned such that the result of a machine interval operation is a machine interval number which is guaranteed to contain the exact result of an interval operation. In this manner, the interval algebraic operations can be rede…ned, in the language of machine interval arithmetic, as follows. De…nition 6.4 (Machine Interval Operations). Let [x; x] and y; y be interval
63
CHAPTER 6. HARDWARE IMPLEMENTATION OF INTERVAL ARITHMETIC
numbers. The unary and binary machine interval operations are de…ned as ( [x; x]) = [5 ( x) ; 4 ( x)] , h i 1 1 1 = 5 x ;4 x , [x; x]
[x; x] + y; y
=
[x; x]
=
y; y
if 0 2 = [x; x] ,
5 x + y ; 4 (x + y) ,
5 minfxy; xy; xy; xyg ; 4 maxfxy; xy; xy; xyg
.
With the help of the above de…nitions, it is not di¢ cult to prove the following two theorems and their corollary. Theorem 6.1 For any two real numbers x and y, we have (i)
y ) 5x
x
(ii) x
5y,
y ) 4x
4y.
Theorem 6.2 For any two interval numbers X and Y , we have (i)
X
(ii)
X
(iii)
Y ) X
Y
X
(X
Y, Y ),
( X).
Corollary 6.1 For any two interval numbers X and Y with x 2 X and y 2 Y , we have (i)
x2
(ii) x y 2
( X), (X
Y ).
Thus, outward rounding provides an e¢ cient implementation of interval arithmetic, with the property of inclusion monotonicity still satis…ed. To illustrate this, we give two numerical examples. Example 6.1 Let M3 be the set of machine-representable real numbers with three signi…cant digits. (i) We have 3 ([1; 2]
[2; 3]) = [53 (1=3) ; 43 (1)] = [0:333; 1] , 64
CHAPTER 6. HARDWARE IMPLEMENTATION OF INTERVAL ARITHMETIC
and ([1; 2]
[2; 3])
[0:333; 1] .
(ii) We have 3 ([0; 1]
+ [2:7182; 3:3841]) = [53 (2:7182) ; 43 (4:3841)] = [2:718; 4:385] ,
and ([0; 1] + [2:7182; 3:3841])
[2:718; 4:385] .
Unlike the sets R and [R], the sets M and [M], of machine real numbers and machine interval numbers, are obviously countable 1 . Moreover, the sets M and [M] are not dense, as is proved by the following theorem and its corollary. Theorem 6.3 Let Mn be the set of machine real numbers with n signi…cant digits. The set Mn is not dense with respect to the order relation <, that is (9xm 2 Mn ) (9ym 2 Mn ) (xm < ym ^ : ((9zm 2 Mn ) (xm < zm ^ zm < ym ))) . Proof. Let xm be an element of Mn . Then xm can be written as n
X xk x2 xn x1 + 2 + ::: + n = , xm = x0 + 10 10 10 10k k=0
where x0 ; x1 ; x2 ; :::; xn are nonnegative integers. Accordingly, if ym is an element of Mn such that n
X xk x1 x2 xn + 1 1 + 2 + ::: + = + , ym = x0 + 10 10 10n 10n 10k k=0
then ym is the element of Mn exactly next to xm , and therefore, there is no zm 2 Mn such that xm < zm ^ zm < ym . Corollary 6.2 Let [Mn ] be the set of machine interval numbers with n signi…cant digits. The set [Mn ] is not dense with respect to the order relation <. 1
A set S is countable if there is an injective mapping from S to the set N = f0; 1; 2; 3; :::g of natural numbers. Otherwise, S is uncountable.
65
CHAPTER 6. HARDWARE IMPLEMENTATION OF INTERVAL ARITHMETIC
Let, for instance, M1 be the set of machine real numbers with one signi…cant digit. Obviously, there is no zm 2 M1 such that 1:1 < zm < 1:2, and there is no Zm 2 [M1 ] such that [1:1; 1:1] < Zm < [1:2; 1:2]. Thus, we can easily determine the number of machine interval numbers between any two elements of M. This is made precise in the following easyprovable theorem. Theorem 6.4 Let Mn be the set of machine real numbers with n signi…cant digits, and let xm and ym be elements of Mn such that xm ym . Then the count of machine interval numbers between xm and ym is given by CM(xm ;ym )
C[M](xm ;ym ) =
X
k=
2 CM(x + CM(xm ;ym ) m ;ym )
2
k=1
,
where CM(xm ;ym ) = 10n
(ym
xm ) + 1,
is the count of machine real numbers between xm and ym . The following example makes this clear. Example 6.2 Let M2 be the set of machine real numbers with two signi…cant digits. The count of machine real numbers between 1:23 and 1:32 is CM(1:23;1:32) = 102 = 10,
(1:32
1:23) + 1
and the count of machine interval numbers between 1:23 and 1:32 is C[M](1:23;1:32) =
102 + 10 = 55. 2
6.1.2 Rounded-Upward Interval Arithmetic Outward rounding of interval numbers involves performing computations with two rounding modes (upward and downward). This can be much costlier than performing the computations with one single rounding direction. If, as usual, we have (8xm ) (xm 2 M ) ( xm ) 2 M) , 66
CHAPTER 6. HARDWARE IMPLEMENTATION OF INTERVAL ARITHMETIC
then the relation (8x 2 R) (5 ( x) =
4 (x)) ,
which then holds, makes it possible to use upward rounding as one single rounding mode. In this manner, for instance, machine interval addition can be reformulated as [x; x] + y; y
=
4 ( x)
y ; 4 (x + y) .
Similar optimal roundings can be applied to other interval operations so that we get more e¢ cient implementations of interval arithmetic.
6.2 An Interval Adder The idea of realizing interval addition on a machine is very simple: according to the formula of machine interval addition, [x; x] + y; y
= 5 x + y ; 4 (x + y) ,
the hardware implementation is simply consists of two ‡oating-point adders to produce the sums x + y and x + y of the lower and upper endpoints of the operand interval numbers [x; x] and y; y . The lower and upper sums are rounded downward and upward respectively. Figure 6.1 shows the block diagram of a simple interval adder.
Figure 6.1: A block diagram of an interval adder.
67
CHAPTER 6. HARDWARE IMPLEMENTATION OF INTERVAL ARITHMETIC
6.3 An Interval Squarrer To simplify the implementation of the interval squaring circuit, we consider only a special case. Let [x; x] be an interval number with x 0 or x 0. According to theorem 2.2 of interval multiplication, the square of [x; x] is given by 2
[x; x]
= [x; x] [x; x] h i 2 2 2 2 = minfx ; xx; x g; maxfx ; xx; x g i h 2 2 2 2 = minfx ; x g; maxfx ; x g .
(6.3)
2
To realize [x; x] on a computer, under the prescribed conditions, we reformulate 6.3, in the language of machine interval arithmetic, as h i 2 2 2 2 2 [x; x] = 5 minfx ; x g ; 4 maxfx ; x g . (6.4) According to 6.4, the implementation idea is that: if x and x are two n-bit numbers, we need two (n n)-bit multipliers and one (2n 2n)-bit comarator. Let us consider the case that x and x are two 4-bit numbers. We then need two 4-by-4 bit multipliers and one 8-by-8 bit comparator. Figure 6.2 shows the block diagram of this simple interval squarrer.
Figure 6.2: A block diagram of an interval squarrer 68
CHAPTER 6. HARDWARE IMPLEMENTATION OF INTERVAL ARITHMETIC
A combinational circuit for implementing the 4-by-4 bit multiplier can be constructed using a simple method called “partial product accumulation”. Let the two numbers involved in a multiplication be called the multiplicand and the multiplier. Let the multiplicand bits be A0 ; A1 ; A2 ; A3 and the multiplier bits be B0 ; B1 ; B2 ; B3 . Then the multiplication process can be formulated as follows.
A3 ^ B3 S6
A3 ^ B2 A2 ^ B3 S5
A3 ^ B1 A2 ^ B2 A1 ^ B3 S4
A3 A2 A1 A0 B3 B2 B1 B0 A3 ^ B0 A2 ^ B0 A1 ^ B0 A0 ^ B0 A2 ^ B1 A1 ^ B1 A0 ^ B1 A1 ^ B2 A0 ^ B2 A0 ^ B3 S3 S2 S1 S0
Each of the bitwise ANDed terms is called a partial product. The resulting 8-bit product is formed by accumulating down the columns of partial products, propagating the carries from the rightmost columns to the left. So, the multiplier employs a shifter and an accumulator to sum each partial product. Figure 6.3 shows the schematic diagram of the 4-by-4 bit multiplier. In Figure 6.3, The …rst level of the sixteen AND gates computes the individual partial products. The second and third levels of the logic blocks accumulate the products, column by column. The columns’sums are produced by four half adders and eight full adders. In the …gure, inputs to the adders from the left are the bits to be added and the carry-in. The output from the right is the sum and the carry-out. The Verilog descriptions, of the circuitries and simulations of the 4-by-4 bit multiplier and the interval squarrer, are provided in appendices A and B respectively.
69
CHAPTER 6. HARDWARE IMPLEMENTATION OF INTERVAL ARITHMETIC
Figure 6.3: A schematic diagram of the 4-by-4 bit multiplier. 70
Chapter
7
Epilogue: What is Next? It is not once nor twice but times without number that the same ideas make their appearance in the world. –Aristotle (384 BC–322 BC) A fascinating story of struggling against uncertainty is that of interval arithmetic. In the preceding chapters, we provided a concise introduction to the theories of interval arithmetic as well as to some of their computational and scienti…c applications. This …nal chapter o¤ers a view to the future of interval computations, brief selections of some application areas of interval arithmetic, an overview of the current research topics in the interval theory, and some suggestions for further reading about the topics that we either barely touched on or omitted.
7.1 A View to the Future of Interval Computations What is the future of interval computations? Fortunately, computers are getting faster and most existing parallel processors provide a tremendous computing power. So, with little extra hardware, it is very possible to make interval computations as fast as ‡oating-point computations. The interval theory is likely to have more widespread applications in the future, for many reasons: Interval algorithms are naturally parallel, because they progress by deleting regions where solutions are proved not to exist. Intervals provide the only known general algorithms that achieve linear speedup, as the number of processors increases in parallel computing systems.
71
CHAPTER 7. EPILOGUE: WHAT IS NEXT?
Interval arithmetic is, arguably, the best and most e¢ cient way to safely translate ever-increasing computer speed into mission-critical problem solutions that are otherwise impractical or impossible to obtain. By using interval algorithms to solve nonlinear problems, more accurate mathematical models of physical phenomena become practical. With interval arithmetic, it is possible to automatically perform rigorous error analysis, and solve nonlinear problems that were previously thought to be impossible to solve. Speed is not all-important anymore. We can get worthwhile accurate results by sacri…cing some speed.
7.2 More Scienti…c Applications of Interval Arithmetic Despite the persisting interval dependency problem and other implementation drawbacks, interval methods are becoming a mainstream. Interval arithmetic is still more accurate and reliable than ‡oating-point arithmetic and traditional numerical approximation methods. Today, the interval theory has numerous applications in scienti…c and engineering disciplines that deal intensely with uncertain data. Brief selections of some application areas of interval arithmetic are listed below (For further details, see, e.g, [Hansen2003], [Jaulin2001], and [Moore2009]). Electrical Engineering. Interval computations, besides providing validated results, are hundreds of times faster than a Monte Carlo method for solving AC network equations. Moreover, interval computations are applied in quality control in the manufacture of radioelectric devices. Control Theory. Interval computations are used to analyze Hurwitz stability in control theory applications. Remote Sensing and GISs. Interval computations are used to bound errors in decisions based on remote sensing. Furthermore, interval methods are used in sensitivity analysis in geographic information systems (GISs). Quality Control. Interval computations are used for quality control in manufacturing processes in which the factors ‡uctuate within bounds. Economics: Linear interval methods are used in modeling economic systems to determine the e¤ects of uncertainties in input parameters, and to include the e¤ects of forecast uncertainties. 72
CHAPTER 7. EPILOGUE: WHAT IS NEXT?
Experimental Physics. Interval computations are used to handle the gathered uncertain data about observed physical phenomena. Computational Physics. Interval algorithms are used to solve physical problems that arise from experimental and theoretical physics. Dynamical and Chaotic Systems: Interval computations are used to verify that computed numerical solutions to chaotic dynamical systems are close to the actual solutions. Furthermore, cell-mapping methods based on interval arithmetic are used to robustly visualize strange attractors (SAs) in discrete chaotic systems. Computer Graphics and Computational Geometry: Interval computations are used to handle many problems in computer graphics and computational geometry. Operations on geometric objects such as rendering, surface intersection, and hidden line removal require robustness in nonlinear equation solvers that can be provided by interval computations. A set of tools and techniques, based on interval arithmetic and a¢ ne geometry, has been developed to improve robustness in such operations.
7.3 Current and Future Research in Interval Arithmetic In the early stages, classical interval arithmetic was preoccupied with the e¤ect of rounding errors on the accuracy of expression evaluation. Later, it was realized that the interval theory has the potential of going beyond expression evaluation and on to solving problems that are inaccessible to conventional approaches. For example, interval analysis has been used, by Thomas Hales of the university of Michigan, in computational parts of a proof of Kepler’s conjecture on the densest packing of spheres. Making use of classical interval mathematics, Hales introduced a de…nitive proof of a conjecture that perplexed mathematicians for nearly 400 years (see, e.g., [Hales2005] and [Moore2009]). Current and future research e¤orts in interval mathematics can be classi…ed mainly into three categories; interval standardizations, interval implementations, and generalizations of the mathematical theory of intervals. A considerable scienti…c e¤ort is put into developing special methods and algorithms that try to overcome the di¢ culties imposed by the algebraic disadvantages of the classical interval arithmetic structure. Various proposals for possible alternate theories of interval arithmetic were introduced to reduce the dependency e¤ect or to enrich the algebraic structure of interval numbers (For further details, see, e.g., [Gardenyes1985], [Hansen1975], [Hayes2009], [Kulisch2008], [Lodwick1999], and [Markov1995]).. 73
CHAPTER 7. EPILOGUE: WHAT IS NEXT?
Now, the subject of interval mathematics concerns numerous scienti…c journals and publishers. The journal “Interval Computations” started as a joint Soviet-Western enterprise in 1991, and continues as the journal “Reliable Computing”. Besides that, “Computing” commonly publishes material related to interval computations, as well as the journal “Global Optimization”. Traditional numerical analysis journals such as “BIT ”, the “SIAM Journal on Numerical Analysis”, the “SIAM Journal on Scienti…c and Statistical Computing”, and the “ACM Transactions on Mathematical Software” contain articles on interval computations (For further resources, see, e.g., [Hansen2003], [Jaulin2001], [Kearfott1996], and [Moore2009]).
7.4 Suggestions for Further Reading There are some advanced topics of the interval theory that we either barely touched on or omitted completely. We list some suggested references that cover such topics in more detail. Applications of the Interval Theory. Gilles Chabert and Luc Jaulin; Computing the Pessimism of Inclusion Functions; Reliable Computing; Volume 13, Number 6; 2007; pp. 489-504. Eldon Hansen; Global Optimization Using Interval Analysis: Revised And Expanded; Second Edition; CRC Press; 2003. Luc Jaulin et al.; Applied Interval Analysis; First Edition; Springer; 2001. L. V. Kolev; Interval Methods for Circuit Analysis; World Scienti…c Publishing Company; 1993. R. E. Moore and R. B. Kearfott; Introduction to Interval Analysis; SIAM; 2009. Jean-Michel Muller et al.; Handbook of Floating-Point Arithmetic; First Edition; Birkhauser Boston; 2009. Arnold Neumaier; Interval Methods for Systems of Equations; Cambridge University Press; 1991. Witold Pedrycz (ed.), Andrzej Skowron (ed.), and Vladik Kreinovich (ed.); Handbook of Granular Computing; First Edition; Wiley-Interscience; 2008.
74
CHAPTER 7. EPILOGUE: WHAT IS NEXT?
Implementations of Interval Arithmetic. Luc Jaulin et al.; Applied Interval Analysis; First Edition; Springer; 2001. Ulrich W. Kulisch; Complete Interval Arithmetic and its Implementation; in “Numerical Validation in Current Hardware Architectures”; Internationales Begegnungs; 2008. Svetoslav M. Markov; On Directed Interval Arithmetic and its Applications; Journal of Universal Computer Science; Volume 1, Number 7; 1995; pp. 514-526. R. E. Moore and R. B. Kearfott; Introduction to Interval Analysis; SIAM; 2009. Arnold Neumaier; Interval Methods for Systems of Equations; Cambridge University Press; 1991. Generalizations of the Classical Interval Theory. E. Gardenyes, H. Mielgo, and A. Trepat; Modal Intervals: Reason and Ground Semantics; in “Interval Mathematics”; LNCS, 212:27-35; Springer Verlag; 1985. Eldon Hansen; A Generalized Interval Arithmetic; in “Interval Mathematics”; Lecture Notes in Computer Science; Volume 29; pp. 7-18; SpringerVerlag; 1975. Nathan T. Hayes; Introduction to Modal Intervals; IEEE 1788 Working Group; March 2009. Ulrich W. Kulisch; Complete Interval Arithmetic and its Implementation; in “Numerical Validation in Current Hardware Architectures”; Internationales Begegnungs; 2008. Svetoslav M. Markov; On Directed Interval Arithmetic and its Applications; Journal of Universal Computer Science; Volume 1, Number 7; 1995; pp. 514-526.
75
Appendix
A
A Verilog Description for the 4-by-4 Bit Multiplier The purpose of this appendix is to introduce how to use four half adders and eight full adders to design a 4-by-4 bit multiplier circuitry. We provide detailed Verilog descriptions of the circuitry and simulation process of the 4-by-4 bit multiplier. The circuitries in this appendix, and its successor, are compliled and simulated using Active-HDL1 version 7:1. Figure A.1 shows the main screen and the design browser window of the Active-HDL workspace.
Figure A.1: The Active-HDL workspace. Active-HDL is a trademark of Aldec, Inc. All other trademarks or registered trademarks are property of their respective owners. 1
77
A. THE 4-BY-4 BIT MULTIPLIER
A.1 Verilog Description of the 4-by-4 Bit Multiplier Circuitry The circuitry of the 4-by-4 bit multiplier consists of three levels of half and full adders (see Figure 6.3, on page 70): Level 1: three half adders and one full adder. Level 2: four full adders. Level 3: three full adders, and one half adder. The Verilog descriptions of the half adder, the full adder, and the 4-by-4 bit multiplier are listed below. A.1.1 Verilog Description of the Half Adder //------- The Half Adder ------------// // ---- Author: Hend Dawood ---- // //--------------------------------------// // ----- A halfadder module. module halfadder (S, C, x, y); input x, y; output S,C; // Instantiate Primitive Gates xor (S,x,y); and (C,x,y); endmodule A.1.2 Verilog Description of the Full Adder //------- The Full Adder ------------// // ---- Author: Hend Dawood ---- // //------------------------------------- // // ----- A Half Adder module. module halfadder (S,C,x,y); input x,y; output S,C; // Instantiate Primitive Gates xor (S,x,y); 78
A. THE 4-BY-4 BIT MULTIPLIER
and (C,x,y); endmodule //----- Description of Full Adder. module fulladder (S,C,x,y,z); input x, y, z; output S,C; wire S1,D1,D2; //Outputs of first XOR and two And Gates // Instantiate the halfadder halfadder HA1 (S1,D1,x,y), HA2(S,D2,S1,z); or g1(C,D2,D1); endmodule A.1.3 Verilog Description of the 4 -by-4 Bit Multiplier //-------------------------------------------------------// // Title : The 4-by-4 Bit Multiplier // Author : Hend Dawood //------------------------------------------------------// ‘ifdef _VCP ‘else ‘define library ‘endif
// ---------- Design Unit Header ---------- // ‘timescale 1ps / 1ps module Multiplier4Bit (A,B,S) ; // ------------ Port declarations --------- // input [3:0] A; wire [3:0] A; input [3:0] B; wire [3:0] B; output [7:0] S; wire [7:0] S;
79
A. THE 4-BY-4 BIT MULTIPLIER
// ----------- Signal declarations -------- // wire NET1017; wire NET1025; wire NET1033; wire NET1041; wire NET1049; wire NET1057; wire NET1111; wire NET1115; wire NET1123; wire NET1204; wire NET1212; wire NET1224; wire NET1266; wire NET1274; wire NET1282; wire NET1359; wire NET1367; wire NET1375; wire NET1460; wire NET1480; wire NET1488; wire NET1643; wire NET1651; wire NET1663; wire NET4304; wire NET4308; wire NET4357; wire NET4361; wire NET4369; wire NET4508; wire NET4516; wire NET4524; // -------- Component instantiations -------// // synopsys translate_off ‘library("FA1","FA") // synopsys translate_on fulladder FA1 80
A. THE 4-BY-4 BIT MULTIPLIER
( .C(NET1488), .S(NET1359), .x(NET1111), .y(NET1115), .z(NET1123) );
// synopsys translate_off ‘library("FA2","FA") // synopsys translate_on fulladder FA2 ( .C(NET1663), .S(S[2]), .x(NET1204), .y(NET1212), .z(NET1224) );
// synopsys translate_off ‘library("FA3","FA") // synopsys translate_on fulladder FA3 ( .C(NET1375), .S(NET1643), .x(NET1266), .y(NET1274), .z(NET1282) );
// synopsys translate_off ‘library("FA4","FA") // synopsys translate_on fulladder FA4 ( 81
A. THE 4-BY-4 BIT MULTIPLIER
.C(NET4361), .S(NET4304), .x(NET1359), .y(NET1367), .z(NET1375) );
// synopsys translate_off ‘library("FA5","FA") // synopsys translate_on fulladder FA5 ( .C(NET4516), .S(NET4357), .x(NET1460), .y(NET1480), .z(NET1488) );
// synopsys translate_off ‘library("FA6","FA") // synopsys translate_on fulladder FA6 ( .C(NET4308), .S(S[3]), .x(NET1643), .y(NET1651), .z(NET1663) );
// synopsys translate_off ‘library("FA7","FA") // synopsys translate_on fulladder FA7 ( .C(NET4524), 82
A. THE 4-BY-4 BIT MULTIPLIER
.S(S[5]), .x(NET4357), .y(NET4361), .z(NET4369) );
// synopsys translate_off ‘library("FA8","FA") // synopsys translate_on fulladder FA8 ( .C(S[7]), .S(S[6]), .x(NET4508), .y(NET4516), .z(NET4524) );
// synopsys translate_off ‘library("HA1","HA") // synopsys translate_on halfadder HA1 ( .C(NET1224), .S(S[1]), .x(NET1017), .y(NET1025) );
// synopsys translate_off ‘library("HA2","HA") // synopsys translate_on halfadder HA2 ( .C(NET1282), .S(NET1204), .x(NET1033), 83
A. THE 4-BY-4 BIT MULTIPLIER
.y(NET1041) );
// synopsys translate_off ‘library("HA3","HA") // synopsys translate_on halfadder HA3 ( .C(NET1123), .S(NET1266), .x(NET1049), .y(NET1057) );
// synopsys translate_off ‘library("HA4","HA") // synopsys translate_on halfadder HA4 ( .C(NET4369), .S(S[4]), .x(NET4304), .y(NET4308) );
assign assign assign assign assign assign assign assign assign assign assign assign
S[0] = B[0] & A[0]; NET1651 = B[3] & A[0]; NET1111 = B[1] & A[3]; NET1115 = B[2] & A[2]; NET1367 = B[3] & A[1]; NET1460 = B[2] & A[3]; NET1480 = B[3] & A[2]; NET4508 = B[3] & A[3]; NET1017 = B[0] & A[1]; NET1025 = B[1] & A[0]; NET1033 = A[2] & B[0]; NET1041 = B[1] & A[1]; 84
A. THE 4-BY-4 BIT MULTIPLIER
assign assign assign assign
NET1212 NET1049 NET1057 NET1274
= = = =
B[2] B[0] B[1] B[2]
& & & &
A[0]; A[3]; A[2]; A[1];
endmodule
A.2 Verilog Description of the 4-by-4 Bit Multiplier Simulation This section describes the testing and simulation process of the 4-by-4 bit multiplier. We provide here the waveform simulation view, the tabled-text simulation view, and the Verilog description of the simulation process. The input-output properties used to produce the simulation views are as follows. Inputs: –A(3 : 0): a random exponential input at period 10 ns. –B(3 : 0): a random Poisson input at period 20 ns. Output: –S(7 : 0): the multiplication product. Figures A.2 and A.3 show, respectively, the waveform simulation view and the tabled-text simulation view of the 4-by-4 bit multiplier.
Figure A.2: The waveform simulation view of the 4-by-4 bit multiplier.
85
A. THE 4-BY-4 BIT MULTIPLIER
Figure A.3: The tabled-text simulation view of the 4-by-4 bit multiplier.
The Verilog description of the simulation process of the 4-by-4 bit multiplier is shown below. //----------------------------------------------------------// // Title : 4-by-4 Bit Multiplier Test Bench // Author : Hend Dawood //---------------------------------------------------------// ‘timescale 1ps / 1ps module Multiplier4Bit_tb;
//Internal signals declarations: reg [3:0]B; reg [3:0]A; wire [7:0]S;
86
A. THE 4-BY-4 BIT MULTIPLIER
// Unit Under Test port map Multiplier4Bit UUT ( .B(B), .A(A), .S(S)); initial $monitor($realtime,,"ps %h %h %h ",B,A,S); //The Waveform Simulation initial begin : STIMUL // begin of stimulus process #0 A = 4’b0001; B = 4’b0001; #20000; //0 A = 4’b0100; B = 4’b0000; #10000; //20000 A = 4’b0010; #10000; //30000 A = 4’b0001; #10000; //40000 A = 4’b0000; #10000; //50000 A = 4’b0010; B = 4’b0010; #10000; //60000 A = 4’b0011; #10000; //70000 A = 4’b0001; B = 4’b0000; #20000; //80000 A = 4’b0000; B = 4’b0001; #20000; //100000 B = 4’b0011; #20000; //120000 B = 4’b0010; 87
A. THE 4-BY-4 BIT MULTIPLIER
#10000; //140000 A = 4’b0001; #10000; //150000 B = 4’b0000; #20000; //160000 A = 4’b0000; B = 4’b0001; #10000; //180000 A = 4’b0001; #10000; //190000 A = 4’b0011; B = 4’b0000; #10000; //200000 A = 4’b0000; #10000; //210000 B = 4’b0010; #10000; //220000 A = 4’b0001; #10000; //230000 B = 4’b0001; #20000; //240000 A = 4’b0000; #10000; //260000 A = 4’b0001; #10000; //270000 A = 4’b0010; B = 4’b0000; #30000; //280000 A = 4’b0001; #30000; //310000 A = 4’b0000; B = 4’b0001; #10000; //340000 A = 4’b0001; #10000; //350000 B = 4’b0010; #10000; //360000 A = 4’b0011; #10000; //370000 A = 4’b0100; 88
A. THE 4-BY-4 BIT MULTIPLIER
B = 4’b0000; #10000; //380000 A = 4’b0010; #10000; //390000 A = 4’b0000; #10000; //400000 A = 4’b0001; #10000; //410000 A = 4’b0101; #10000; //420000 A = 4’b0001; #30000; //430000 B = 4’b0001; #20000; //460000 B = 4’b0000; #10000; //480000 A = 4’b0010; #10000; //490000 A = 4’b0000; #20000; //500000 B = 4’b0001; #10000; //520000 A = 4’b0001; #10000; //530000 A = 4’b0000; #10000; //540000 A = 4’b0001; #10000; //550000 A = 4’b0000; #20000; //560000 B = 4’b0011; #20000; //580000 A = 4’b0001; B = 4’b0001; #20000; //600000 A = 4’b0100; B = 4’b0100; #10000; //620000 A = 4’b0010; #10000; //630000 89
A. THE 4-BY-4 BIT MULTIPLIER
A = 4’b0000; B = 4’b0001; #20000; //640000 A = 4’b0010; B = 4’b0000; #10000; //660000 A = 4’b0000; #10000; //670000 A = 4’b0001; B = 4’b0010; #20000; //680000 A = 4’b0000; B = 4’b0001; end // end of stimulus process endmodule
90
Appendix
B
A Verilog Description for the Interval Squarrer The purpose of this appendix is to introduce how to use two 4-by-4 bit multipliers and one 8-bit comparator to design an interval squarrer circuitry. We provide detailed Verilog descriptions of the circuitry and simulation process of the interval squarrer.
B.1 Verilog Description of the Interval Squarrer Circuitry The circuitry of the interval squarrer consists of two levels (see Figure 6.2, on page 68): Level 1: two 4-by-4 bit multipliers to produce, in parallel, the squares of the lower and upper endpoints of an interval number [x; x]. Level 2: one 8-bit comparator to compare the two 8-bit squares and produce one true-false binary bit for each of the following three comparison cases: 2
2
2
2
2
2
–Case 1. x = x , –Case 2. x < x , –Case 3. x > x . The Verilog descriptions of the 8-bit comparator and the interval squarrer are listed below.
91
B. THE INTERVAL SQUARRER
B.1.1 Verilog Description of the 8-Bit Comparator //------- 8-Bit Comparator ------------// // ----- Author: Hend Dawood ------ // //-----------------------------------------// // ----- 8-Bit Comparator Module module comparator8bit (A,B,AltB,AgtB,AeqB); input [7:0] A,B; output AltB,AgtB,AeqB; assign AltB=(A
B), AeqB=(A==B); endmodule B.1.2 Verilog Description of the Interval Squarrer //-----------------------------------------------// // Title : Interval Squaring Circuit // Author : Hend Dawood //---------------------------------------------// ‘ifdef _VCP ‘else ‘define library ‘endif
// ---------- Design Unit Header ---------- // ‘timescale 1ps / 1ps module IntervalSqrCircuit (Xl,Xu,XlSqr_Equal_XuSqr, XlSqr_Greater_XuSqr,XlSqr_Little_XuSqr,Xl_Squared,Xu_Squared) ; // ------------ Port declarations --------- // input [3:0] Xl; wire [3:0] Xl; 92
B. THE INTERVAL SQUARRER
input [3:0] Xu; wire [3:0] Xu; output [0:0] XlSqr_Equal_XuSqr; wire [0:0] XlSqr_Equal_XuSqr; output [0:0] XlSqr_Greater_XuSqr; wire [0:0] XlSqr_Greater_XuSqr; output [0:0] XlSqr_Little_XuSqr; wire [0:0] XlSqr_Little_XuSqr; output [7:0] Xl_Squared; wire [7:0] Xl_Squared; output [7:0] Xu_Squared; wire [7:0] Xu_Squared; // -------- Component instantiations -------// // synopsys translate_off ‘library("U1","Multiplier4Bit") // synopsys translate_on Multiplier4Bit U1 ( .A(Xl), .B(Xl), .S(Xl_Squared) );
// synopsys translate_off ‘library("U2","Multiplier4Bit") // synopsys translate_on Multiplier4Bit U2 ( .A(Xu), .B(Xu), .S(Xu_Squared) );
comparator8bit U3 ( .A(Xl_Squared), 93
B. THE INTERVAL SQUARRER
.AeqB(XlSqr_Equal_XuSqr[0]), .AgtB(XlSqr_Little_XuSqr[0]), .AltB(XlSqr_Greater_XuSqr[0]), .B(Xu_Squared) );
endmodule
B.2 Verilog Description of the Interval Squarrer Simulation This section describes the testing and simulation process of the interval squarrer. We provide here the waveform simulation view, the tabled-text simulation view, and the Verilog description of the simulation process. The input-output properties used to produce the simulation views are as follows. Inputs: –Xl(3 : 0): a random exponential input at period 5 ns. –Xu(3 : 0): a random Poisson input at period 10 ns. Outputs: 2
–Xl_Squared(7 : 0): the lower bound squared, x . 2
–Xu_Squared(7 : 0): the upper bound squared, x . 2
2
2
2
–XlSqr_Equal_XuSqr(0 : 0): a comparison bit for the case x = x . –XlSqr_Little_XuSqr(0 : 0): a comparison bit for the case x < x . 2
2
–XlSqr_Greater_XuSqr(0 : 0): a comparison bit for the case x > x .
Figures B.1 and B.2 show, respectively, the waveform simulation view and the tabled-text simulation view of the interval squarrer.
94
B. THE INTERVAL SQUARRER
Figure B.1: The waveform simulation view of the interval squarrer.
Figure B.2: The tabled-text simulation view of the interval squarrer.
The Verilog description of the simulation process of the interval squarrer is shown below. //-------------------------------------------------------------// // Title : Interval Squaring Circuit Test Bench // Author : Hend Dawood //------------------------------------------------------------// ‘timescale 1ps / 1ps module IntervalSqrCircuit_tb;
//Internal signals declarations: reg [3:0]Xl; reg [3:0]Xu; 95
B. THE INTERVAL SQUARRER
wire wire wire wire wire
[0:0]XlSqr_Equal_XuSqr; [0:0]XlSqr_Greater_XuSqr; [0:0]XlSqr_Little_XuSqr; [7:0]Xl_Squared; [7:0]Xu_Squared;
// Unit Under Test port map IntervalSqrCircuit UUT ( .Xl(Xl), .Xu(Xu), .XlSqr_Equal_XuSqr(XlSqr_Equal_XuSqr), .XlSqr_Greater_XuSqr(XlSqr_Greater_XuSqr), .XlSqr_Little_XuSqr(XlSqr_Little_XuSqr), .Xl_Squared(Xl_Squared), .Xu_Squared(Xu_Squared)); initial $monitor($realtime,,"ps %h %h %h %h %h %h %h ", Xl,Xu,XlSqr_Equal_XuSqr,XlSqr_Greater_XuSqr,XlSqr_Little_XuSqr, Xl_Squared,Xu_Squared); //The Waveform Simulation initial begin : STIMUL // begin of stimulus process #0 Xl = 4’b0001; Xu = 4’b0001; #10000; //0 Xl = 4’b0100; Xu = 4’b0000; #5000; //10000 Xl = 4’b0010; #5000; //15000 Xl = 4’b0001; #5000; //20000 Xl = 4’b0000; #5000; //25000 Xl = 4’b0010; 96
B. THE INTERVAL SQUARRER
Xu = 4’b0010; #5000; //30000 Xl = 4’b0011; #5000; //35000 Xl = 4’b0001; Xu = 4’b0000; #10000; //40000 Xl = 4’b0000; Xu = 4’b0001; #10000; //50000 Xu = 4’b0011; #10000; //60000 Xu = 4’b0010; #5000; //70000 Xl = 4’b0001; #5000; //75000 Xu = 4’b0000; #10000; //80000 Xl = 4’b0000; Xu = 4’b0001; #5000; //90000 Xl = 4’b0001; #5000; //95000 Xl = 4’b0011; Xu = 4’b0000; #5000; //100000 Xl = 4’b0000; #5000; //105000 Xu = 4’b0010; #5000; //110000 Xl = 4’b0001; #5000; //115000 Xu = 4’b0001; #10000; //120000 Xl = 4’b0000; #5000; //130000 Xl = 4’b0001; #5000; //135000 Xl = 4’b0010; Xu = 4’b0000; 97
B. THE INTERVAL SQUARRER
#15000; //140000 Xl = 4’b0001; #15000; //155000 Xl = 4’b0000; Xu = 4’b0001; #5000; //170000 Xl = 4’b0001; #5000; //175000 Xu = 4’b0010; #5000; //180000 Xl = 4’b0011; #5000; //185000 Xl = 4’b0100; Xu = 4’b0000; #5000; //190000 Xl = 4’b0010; #5000; //195000 Xl = 4’b0000; #5000; //200000 Xl = 4’b0001; #5000; //205000 Xl = 4’b0101; #5000; //210000 Xl = 4’b0001; #15000; //215000 Xu = 4’b0001; #10000; //230000 Xu = 4’b0000; #5000; //240000 Xl = 4’b0010; #5000; //245000 Xl = 4’b0000; #10000; //250000 Xu = 4’b0001; #5000; //260000 Xl = 4’b0001; #5000; //265000 Xl = 4’b0000; #5000; //270000 Xl = 4’b0001; 98
B. THE INTERVAL SQUARRER
#5000; //275000 Xl = 4’b0000; #10000; //280000 Xu = 4’b0011; #10000; //290000 Xl = 4’b0001; Xu = 4’b0001; #10000; //300000 Xl = 4’b0100; Xu = 4’b0100; #5000; //310000 Xl = 4’b0010; #5000; //315000 Xl = 4’b0000; Xu = 4’b0001; #10000; //320000 Xl = 4’b0010; Xu = 4’b0000; #5000; //330000 Xl = 4’b0000; #5000; //335000 Xl = 4’b0001; Xu = 4’b0010; #10000; //340000 Xl = 4’b0000; Xu = 4’b0001; #10000; //350000 Xu = 4’b0011; #10000; //360000 Xu = 4’b0100; #10000; //370000 Xu = 4’b0000; #5000; //380000 Xl = 4’b0001; #10000; //385000 Xl = 4’b0010; #10000; //395000 Xl = 4’b0000; #5000; //405000 Xl = 4’b0010; 99
B. THE INTERVAL SQUARRER
Xu = 4’b0001; #5000; //410000 Xl = 4’b0001; #10000; //415000 Xl = 4’b0010; #5000; //425000 Xl = 4’b0000; Xu = 4’b0000; #5000; //430000 Xl = 4’b0001; #5000; //435000 Xu = 4’b0010; #5000; //440000 Xl = 4’b0000; #5000; //445000 Xl = 4’b0001; Xu = 4’b0001; #5000; //450000 Xl = 4’b0000; #5000; //455000 Xl = 4’b0001; #10000; //460000 Xl = 4’b0000; Xu = 4’b0000; #10000; //470000 Xl = 4’b0001; Xu = 4’b0010; #10000; //480000 Xl = 4’b0000; Xu = 4’b0001; #5000; //490000 Xl = 4’b0001; #5000; //495000 Xl = 4’b0000; Xu = 4’b0000; #10000; //500000 Xl = 4’b0010; Xu = 4’b0010; #5000; //510000 Xl = 4’b0001; 100
B. THE INTERVAL SQUARRER
#5000; //515000 Xl = 4’b0000; #5000; //520000 Xl = 4’b0001; #5000; //525000 Xu = 4’b0000; #10000; //530000 Xl = 4’b0000; #5000; //540000 Xl = 4’b0011; #5000; //545000 Xl = 4’b0000; Xu = 4’b0001; #5000; //550000 Xl = 4’b0001; #5000; //555000 Xl = 4’b0010; #5000; //560000 Xl = 4’b0001; #5000; //565000 Xl = 4’b0010; Xu = 4’b0000; #5000; //570000 Xl = 4’b0000; #10000; //575000 Xl = 4’b0001; #10000; //585000 Xl = 4’b0000; #5000; //595000 Xl = 4’b0001; Xu = 4’b0010; #10000; //600000 Xu = 4’b0001; #5000; //610000 Xl = 4’b0010; #5000; //615000 Xl = 4’b0001; #10000; //620000 Xl = 4’b0000; #10000; //630000 101
B. THE INTERVAL SQUARRER
Xl = 4’b0001; Xu = 4’b0000; #10000; //640000 Xl = 4’b0000; Xu = 4’b0001; #5000; //650000 Xl = 4’b0001; #5000; //655000 Xl = 4’b0000; #5000; //660000 Xl = 4’b0001; #5000; //665000 Xu = 4’b0010; #10000; //670000 Xl = 4’b0000; Xu = 4’b0001; #10000; //680000 Xl = 4’b0010; #5000; //690000 Xl = 4’b0100; #5000; //695000 Xl = 4’b0000; Xu = 4’b0010; end // end of stimulus process
endmodule
102
Bibliography
[Allchin2000]
Douglas Allchin; The Epistemology of Error; Philosophy of Science Association Meeting; 2000.
[Allchin2007]
Douglas Allchin; Thinking about Technology and the Technology of “Thinking About”; Techné; Volume 11, Number 1; 2007.
[Archimedes2002] Archimedes; The Works of Archimedes; translated with introduction and commentary by Sir Thomas L. Heath; Dover Publications, 2002. [Boche1963]
R. E. Boche; An Operational Interval Arithmetic; University of Illinois National Electronics Conference; August 1963.
[Boche1966]
R. E. Boche; Complex Interval Arithmetic with Some Applications; Technical Report Number LMSC4-22-66-1; Lockheed General Research Program, 1966.
[Bryant1985]
Victor Bryant; Metric Spaces: Iteration and Application; Cambridge University Press; 1985.
[Burkill1924]
J. C. Burkill; Functions of Intervals; Proceedings of the London Mathematical Society; Volume 22, 1924; pp. 275-310.
[Causey1994]
Robert L. Causey; Logic, Sets, and Recursion; Jones and Bartlett Publishers; Boston; 1994.
[Chabert2007]
Gilles Chabert and Luc Jaulin; Computing the Pessimism of Inclusion Functions; Reliable Computing; Volume 13, Number 6; 2007; pp. 489-504.
[Chen2000]
Guanrong Chen and Trung Tat Pham; Introduction to Fuzzy Sets, Fuzzy Logic, and Fuzzy Control Systems; First Edition; CRC Press; 2000. 103
BIBLIOGRAPHY
[Cleary1987]
John G. Cleary; Logical Arithmetic; Future Computing Systems; Volume 2, Number 2; 1987; pp. 125-149.
[Cleary1993]
John G. Cleary; Proving the Existence of Solutions in Logical Arithmetic; Constraint Programming; NATO Advanced Study Institute; Estonia; 1993; pp. 52-63.
[Devlin1993]
Keith Devlin; The Joy of Sets: Fundamentals of Contemporary Set Theory; Springer Verlag; 1993.
[Dwyer1951]
Paul S. Dwyer; Linear computations; Chapman & Hall; New York; 1951.
[Euler2000]
Leonhard Euler; Foundations of Di¤erential Calculus; Springer Verlag; 2000.
[Fateman2009]
Richard J. Fateman; Interval Arithmetic, Extended Numbers and Computer Algebra Systems; University of California at Berkeley; 2009.
[Gardenyes1985] E. Gardenyes, H. Mielgo, and A. Trepat; Modal Intervals: Reason and Ground Semantics; in “Interval Mathematics”; LNCS, 212:27-35; Springer Verlag; 1985. [Gleason1992]
Andrew Gleason; Fundamentals of Abstract Analysis; CRC Press; 1992.
[Hales2005]
Thomas C. Hales; A Proof of the Kepler Conjecture; The Annals of Mathematics; Volume 162, Number 3; 2005; pp. 1065-1185.
[Hansen1975]
Eldon Hansen; A Generalized Interval Arithmetic; in “Interval Mathematics”; Lecture Notes in Computer Science; Volume 29; pp. 7-18; Springer-Verlag; 1975.
[Hansen2003]
Eldon Hansen; Global Optimization Using Interval Analysis: Revised And Expanded; Second Edition; CRC Press; 2003.
[Hayes2009]
Nathan T. Hayes; Introduction to Modal Intervals; IEEE 1788 Working Group; March 2009.
[Jaulin2001]
Luc Jaulin et al.; Applied Interval Analysis; First Edition; Springer; 2001.
[Kahraman2008] Cengiz Kahraman; Fuzzy Engineering Economics with Applications; Springer; 2008. 104
BIBLIOGRAPHY
[Kearfott1996]
R. B. Kearfott; Interval computations: Introduction, uses, and resources; Euromath Bulletin; Volume 2, Number 1; 1996; pp. 95-112.
[Keene1988]
Sonya Keene; Object-Oriented Programming in Common Lisp: A Programmer’s Guide to CLOS ; Addison-Wesley; 1988.
[Kleene1952]
Stephen Kleene; Introduction to Metamathematics; NorthHolland Publishing Company; Amsterdam; 1952.
[Kline1982]
Morris Kline; Mathematics: The Loss of Certainty; Oxford University Press; 1982.
[Kolev1993]
L. V. Kolev; Interval Methods for Circuit Analysis; World Scienti…c Publishing Company; 1993.
[Kreinovich1995] Vladik Kreinovich; Interval Rational = Algebraic; ACM SIGNUM Newsletter; Volume 30, Issue 4; New York; 1995; pp. 2-13. [Kulisch2008]
Ulrich W. Kulisch; Complete Interval Arithmetic and its Implementation; in “Numerical Validation in Current Hardware Architectures”; Internationales Begegnungs; 2008.
[Lobach1951]
Nikolai Ivanovich Lobachevskii; Complete works 5 ; MoscowLeningrad; 1951.
[Lodwick1999]
Weldon A. Lodwick; Constrained Interval Arithmetic; CCM Report 138; February 1999.
[Markov1995]
Svetoslav M. Markov; On Directed Interval Arithmetic and its Applications; Journal of Universal Computer Science; Volume 1, Number 7; 1995; pp. 514-526.
[Moore1959]
R. E. Moore; Automatic Error Analysis in Digital Computation; Technical Report Number LMSD84821; Lockheed General Research Program; 1959.
[Moore1962]
R. E. Moore; Interval Arithmetic and Automatic Error Analysis in Digital Computing; Ph.D. Thesis; Stanford University; 1962.
[Moore2009]
R. E. Moore and R. B. Kearfott; Introduction to Interval Analysis; SIAM; 2009. 105
BIBLIOGRAPHY
[Muller2009]
Jean-Michel Muller et al.; Handbook of Floating-Point Arithmetic; First Edition; Birkhauser Boston; 2009.
[Neumaier1991]
Arnold Neumaier; Interval Methods for Systems of Equations; Cambridge University Press; 1991.
[Pedrycz2008]
Witold Pedrycz (ed.), Andrzej Skowron (ed.), and Vladik Kreinovich (ed.); Handbook of Granular Computing; First Edition; Wiley-Interscience; 2008.
[Petkovic1998]
Miodrag S. Petkovic, Ljiljana D. Petkovic, L. D. Petkovic; Complex Interval Arithmetic and Its Applications; First Edition; Wiley-VCH; 1998.
[Pichler2007]
Franz Pichler; Computer Aided Systems Theory; Springer; 2007.
[Rasiowa1963]
Helena Rasiowa and Roman Sikorski; The Mathematics of Metamathematics; Panstwowe Wydawnictwo Naukowe; Warszawa; 1963.
[Shayer1965]
S. Shayer; Interval Arithmetic with Some Applications for Digital Computers; Technical Report Number LMSD5-1365-12; Lockheed General Research Program; 1965.
[Sunaga1958]
T. Sunaga; Theory of an Interval Algebra and its Application to Numerical Analysis; RAAG Memoirs; Volume 2; 1958; pp. 29-46.
[Tarski1965]
Alfred Tarski; Logic, Semantics, Metamathematics; translated by J. H. Woodger; Oxford At the Clarendon Press; 1965.
[Young1931]
R. C. Young; The Algebra of Many-Valued Quantities; Mathematische Annalen; Volume 104; 1931; pp. 260-290.
[Yu2004]
Xing Huo Yu; Advances in Arti…cial Intelligence; Proceedings of 17th Australian Joint Conference on Arti…cial Intelligence; Australia; 2004.
106
