Transcript Foundations of Interval Computation

Foundations of Interval
Computation
Trong Wu
E-mail: [email protected]
Phone: 1-618-692-4027
Department of Computer Science
Southern Illinois University Edwardsville
Edwardsville, IL 62026, U.S.A.
1
Agenda
1.
2.
3.
4.
5.
6.
7.
8.
Introduction
Some Basic Algebraic Structures of Numbers
The Structure of Dyadic Numbers
The Structure of Rough Numbers
Hierarchical Classes and Computation
A Model Interval Computation
An Example
Conclusion
2
Some Terminologies of Numbers
1. Real Numbers
2.
3.
4.
5.
6.
Dyadic Numbers
Finite Dyadic Numbers
Limited Dyadic Numbers
Model Numbers
Rough Numbers
3
1. Introduction (1)
In 1982, Pawlak proposed a concept called rough sets, used in the theory of
knowledge for the classification of features of objects [Pawlak1982].
He considered X to be a set and R to be a relation over X. The pair (X, R) is
called a rough space, and R is called the rough relation.
If xRy, then one could say that x is too close to y, x and y are indiscernible,
and x and y belong to the same elementary set. This set is called a rough
set.
4
1. Introduction (2)
Later, Wu [1994, 1998] defined a new class of real numbers called
rough numbers, the definition is given in Section 4, which is a onedimensional rough set in rough set theory.
•
If z1, z2  E and (z1, z2 )  R implies z1, z2  [x, y) in the rough
space (E, R) then R is an equivalence relation on E. Equivalence
classes of the relation R are called basic model intervals, if the
smallest interval with model number endpoints. The set of all basic
model intervals in (E, R) is denoted by E/R.
5
1. Introduction (3)
Where are the problems?
(1)
(2)
(3)
The real world problem is given in the real number system.
The computation is done in the model number (see Section 4 for
definition) system for the given machine, M.
The results must be converted from model numbers into real
numbers.
6
1. Introduction (4)
Machine error? VS Human mistake?
1.
2.
3.
A problem moving from platform (1) to platform (2) for
computation can induce incorrect results and so can moving
from platform (2) to platform (3). The platform (2) can only
provide an approximated result for platform (1).
These incorrect results are not machine errors, because
the computer system performances exactly work as requested.
In fact, one can view this a human mistake by putting a real
valued problem onto a model number platform for computation.
7
2. Some Basic Algebraic Structures of
Numbers (1)
Definition 2.1 An abelian group (G; +) is a set G together with a
binary operation namely, addition, “+”, which satisfies the following
conditions [Waerden 1948, Herstein 1971]:
(1) For all a, b  G, such that a + b  G.
(2) For all a, b, c  G, then (a + b) + c  a + (b + c).
(3) There is an identity element, e in G such that a + e = e + a, for all
a  G.
(4) For all a  G, there exists an inverse, (a), such that
(a) + a = a + (a) = e.
(5) For all a, b  G, such that a + b = b + a.
Example 2.1 The set of all integers, I, with usual addition, +, (I, +), is an
abelian group.
8
2. Some Basic Algebraic Structures of
Numbers (2)
Definition 2.2 We say that (S; , ) is a ring, if (S; +) is an abelian group,
defining  as a mapping from S  S → S, which satisfying the
following conditions:
(1) For all a, b, c  S, then (a  b)  c  a  (b  c).
(2) Multiplication is distributed over addition: that is for all a, b, c 
S, the left and right distributive laws hold:
a  (b + c) = a  b + a  c, and (b + c)  a = b  a + b  c.
Example 2.2 The set of all integers I with usual addition, +, and
multiplication, , then (I, +, ) is a ring. This ring has no zero-divisor.
9
2. Some Basic Algebraic Structures of
Numbers (3)
Definition 2.3 A Field (F; , ) is a ring with commutative law and
multiplicative unity such that each non-zero element has a
multiplicative inverse that satisfies the following conditions:
(1) For all a, b  F such that a  b = b  a.
(2) There exists 1 such that a  1  1  a = a.
(3) For each non-zero element a in F there is an inverse (1/a) such
that a  (1/a) = (1/a)  a = 1.
Example 2.3
The set of all rational numbers, real numbers, and
complex numbers with usual addition, +, and multiplication, , are
fields.
10
3. The Structure of Dyadic Numbers (1)
Theorem 3.1 For each real number x and B =0, 1, we have its
dyadic expansion over a finite field (B; +, ) [kelley 1955]:
x  sign

i
a
2
 i , where ai  B and sign  ,
i  
y  sign
n
i
a
2
 i , where ai  B and sign  ,
i  n
Exp 127
sign  (1.M )  2
, for 32bits,
Exp  0,1,2,...,255.
Exp 1023
sign  (1.M )  2
, for 64bits
Exp  0,1,2,...,2047.
11
4. The Structure of Rough Numbers (1)
The Ada programming language [Watt 1987] calls a real number a
model number, if the real number can be stored exactly in a computer
system with a radix of power of 2. Therefore, the set of all model
numbers is a subset of dyadic numbers and we call it the set of limited
dyadic numbers with respect to a given computer system.
If a real number is a model number with respect to a given machine M,
then it is a special case rough number. Most computer systems use a
downward rounding policy to approximate a rough number with a
model number. Thus, there are infinitely many rough numbers
approximated by the same model number, such that all rough numbers
z [x, y) are approximated by the same value of the model number x
for computation [Wu 1994, 1998].
12
4.
The Structure of Rough Numbers (2)
The Ada programming language [Watt 1987] calls a real number a
model number, if the real number can be stored exactly in a computer
system with a radix of power of 2. Therefore, the set of all model
numbers is a subset of dyadic numbers and we call it the set of limited
dyadic numbers with respect to a given computer system.
For those real numbers that cannot be stored exactly in a given
computer system, we call them rough numbers with respect to the
given computer system.
13
4.
The Structure of Rough Numbers (3)
Definition 4.1 Let E be the set of all real numbers within the range of a given
computer system M, and let R be a relation on E. The pair (E, R) is called
rough space and R is called the rough relation, if x, y  E and (x, y)  R, we
say that x and y are indistinctive in the rough space (E, R) with respect to the
given computer system M. We call x and y rough numbers and they are
approximated to the same model number. If a real number is a model number
with respect to a given machine M, then it is a special case rough number.
Most computer systems use a downward rounding policy to approximate a
rough number with a model number. Thus, there are infinitely many rough
numbers approximated by the same model number, such that all rough
numbers z [x, y) are approximated by the same value of the model number x
for computation [Wu 1994, 1998]
14
5. Hierarchical structures of dyadic numbers
(1)
Real numbers
Dyadic numbers
(A field)
a b
ab

f
f (a  b)
f ( a )  f (b )
Rough numbers
Finite dyadic numbers
Limited dyadic numbers (model numbers)
(A subset of a polynomial ring)
15
5. Hierarchical structures of dyadic
numbers (2)
The set of real numbers has a field structure, while the set of finite dyadic
numbers is not a field; it is a subset of ring. f is not a one-to-one and
onto function, f does not preserve the field structure, and cannot even
be a local homomorphism between the set of real numbers within a
given range of machine M and the set of limited dyadic numbers. The
addition ‘+’ on the left hand side of the inequality (5.1) is a field
addition and the addition ‘’ on the right hand side is a ring addition
over dyadic numbers.
f(a + b)  f(a)  f(b)
(5.1)
They are two different additions. In the inequality (5.1), computations
occur over two different number systems; we need to adjust by adding
an error term, Err, to form the equality:
f(a + b)  f(a)  f(b) + Err.
(5.2)
16
6. Model Interval Computation (1)
Constructing a model interval

An algorithm for computing smallest model number eps w.r.t. 1.0:

eps  1.0
epsp1  eps  1.0
pass = 0
while (epsp1 > 1.0)
pass = pass + 1
– eps  0.5  eps
– epsp1  eps  1.0
end while






For a given real number x, then the smallest model number w.r.t. x is
eps(x) and the smallest model interval containing x is
[x-eps(x), x+eps(x)].
******* Computatation of Epsilon w.r.t. 1.0 *******
Pass
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Machine Epsilon
Epsp1
5.000000000000000e-001
2.500000000000000e-001
1.250000000000000e-001
6.250000000000000e-002
3.125000000000000e-002
1.562500000000000e-002
7.812500000000000e-003
3.906250000000000e-003
1.953125000000000e-003
9.765625000000000e-004
4.882812500000000e-004
2.441406250000000e-004
1.220703125000000e-004
6.103515625000000e-005
3.051757812500000e-005
1.525878906250000e-005
7.629394531250000e-006
3.814697265625000e-006
1.907348632812500e-006
9.536743164062500e-007
4.768371582031250e-007
2.384185791015625e-007
1.192092895507813e-007
5.960464477539063e-008
2.980232238769531e-008
1.490116119384766e-008
7.450580596923828e-009
1.500000000000000e+000
1.250000000000000e+000
1.125000000000000e+000
1.062500000000000e+000
1.031250000000000e+000
1.015625000000000e+000
1.007812500000000e+000
1.003906250000000e+000
1.001953125000000e+000
1.000976562500000e+000
1.000488281250000e+000
1.000244140625000e+000
1.000122070312500e+000
1.000061035156250e+000
1.000030517578125e+000
1.000015258789063e+000
1.000007629394531e+000
1.000003814697266e+000
1.000001907348633e+000
1.000000953674316e+000
1.000000476837158e+000
1.000000238418579e+000
1.000000119209290e+000
1.000000059604645e+000
1.000000029802322e+000
1.000000014901161e+000
1.000000007450581e+000
Pass
Machine Epsilon
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
3.725290298461914e-009
1.862645149230957e-009
9.313225746154785e-010
4.656612873077393e-010
2.328306436538696e-010
1.164153218269348e-010
5.820766091346741e-011
2.910383045673370e-011
1.455191522836685e-011
7.275957614183426e-012
3.637978807091713e-012
1.818989403545857e-012
9.094947017729282e-013
4.547473508864641e-013
2.273736754432321e-013
1.136868377216160e-013
5.684341886080802e-014
2.842170943040401e-014
1.421085471520200e-014
7.105427357601002e-015
3.552713678800501e-015
1.776356839400251e-015
8.881784197001252e-016
4.440892098500626e-016
2.220446049250313e-016
1.110223024625157e-016
Epsp1
1.000000003725290e+000
1.000000001862645e+000
1.000000000931323e+000
1.000000000465661e+000
1.000000000232831e+000
1.000000000116415e+000
1.000000000058208e+000
1.000000000029104e+000
1.000000000014552e+000
1.000000000007276e+000
1.000000000003638e+000
1.000000000001819e+000
1.000000000000910e+000
1.000000000000455e+000
1.000000000000227e+000
1.000000000000114e+000
1.000000000000057e+000
1.000000000000028e+000
1.000000000000014e+000
1.000000000000007e+000
1.000000000000004e+000
1.000000000000002e+000
1.000000000000001e+000
1.000000000000000e+000
1.000000000000000e+000
1.000000000000000e+000
The final Eps = 1.110223024625157e-016
6.
Model Interval Computation (2)
Definition: For any real numbers x and y, there exist basic model
intervals X  [a1, b1] and Y [a2, b2] such that x [a1, b1) and y[a2, b2)
where a1, b1, a2, and b2 are model numbers.
Interval arithmetic:
Addition
x + y  [[a1, b1] + [a2, b2] ) = [a1 + a2,, b1 + b2).
Subtraction
x  y  [[a1, b1]  [a2, b2] ) = [a1  b2,, b1 a2).
(6.1)
(6.2)
19
6.
Model Interval Computation (3)
Multiplication
x  y [ min(a1a2, a1b2, b1a2, b1b2), max(a1a2, a1b2, b1a2, b1b2)).
(6.3)
Division
1/y  [1/b2, 1/a2), if 0  B, then we define
x/y  [min(a1/b2, a1/a2, b1/b2, b1/a2), max(a1/b2, a1/a2, b1/b2, b1/a2))
(6.4)
20
6.
Model Interval Computation (4)
Since the product of two model numbers or the inverse of a model number might
not be a model number, we round the result outward to the nearest model
numbers. Let m(x) be the greatest model number less than x for the lower
bound and m(y) be the smallest model number greater than y for the upper
bound. Therefore, we redefine multiplication and division as follows:
Multiplication
x  y [m(min(a1a2, a1b2, b1a2, b1b2)), m(max(a1a2, a1b2, b1a2, b1b2))).
(6.3)’
Division
1/y  [1/b2, 1/a2), if 0  B, then we define
x/y  [m(min(a1/b2, a1/a2, b1/b2, b1/a2)), m(max(a1/b2, a1/a2, b1/b2, b1/a2))).
(6.4)’
21
6. Model Interval Computation (5)
Theorem 6.1 The Fundamental Theorem of Interval Computation:
Let f(x1, x2, . . . , xn) be a rational function of n variables. Consider
any sequence of arithmetic steps which serve to evaluate f with given
arguments x1, x2, . . . , xn. Suppose we replace the arguments xi by the
corresponding closed interval Xi (i  1, 2, . . . , n) and replace the
arithmetic steps in the sequence used to evaluate f by the
corresponding interval arithmetic steps. The result will be an interval
f(X1, X2, . . . , Xn). This interval contains the value of f(x1, x2, . . . , xn),
for all xi  Xi (i= 1, 2, . . . , n) [Moore 1966].
22
7. Example (Newton Method) (1)
An example in solving non-linear equations by using interval computation is
given. The Newton method is used for demonstration. The computation is
done with an Ada Interval Mathematics Package.
This program uses interval method (Interval_Math package) and Newton
method to solve equation:

x**3 + 2(x**2) - 7 = 0
Let f(x) = x**3 + 2(x**2) - 7 = 0
x |
-3
-2
-1
0
1
2
_____|___________________________________________________
f(x) |
-16
-7
-6
-7
-4
9
From the above table: f(1) = -4
f(2) = 9
For f(x) = 0,
1 < x < 2 , x lies in (1,2)
7. Example (Newton Method) (2)
Since,
f(2) > 0
To obtain c that lies in (a, b)
f"(x) = 6x + 4 > 0
therefore,
b = 2
c = b - f(b)/f'(b)
Approximated interval for x
(Lower_bound, Upper_bound)
(1.549999999999998046007476659724E+00,
(1.435968674249482601723570951435E+00,
(1.428844709398426893187661335105E+00,
(1.428817702168641678994731591956E+00,
(1.428817701781343041389504833205E+00,
1.550000000000002042810365310288E+00)
1.435968674249491705552372877719E+00)
1.428844709398445989023684887798E+00)
1.428817702168680536800593472435E+00)
1.428817701781421423135043369257E+00)
The final interval length = 0.00000 00000 00078 37174 55385 32052
8. Conclusion
1.
2.
3.
4.
5.
We have studied some basic algebraic structures
Groups, Abelian groups, Rings, and Fields
We also have learned systems of numbers
Real numbers, Dyadic numbers, Finite dyadic numbers,
Limit dyadic numbers, Rough numbers, and Model number
We have seen that the “Ring Computation” is not the same of
“Field Computation”
A mapping f from a “field” into a “subset of ring” is not an
isomorphism. This mapping does not preserve the the structure.
Interval computation is studied, example is presented, and model
interval computation is introduced. By this way, numerical
computation problem from an un-decidable turns to a decidable
problem.
25
Questions?
Thank You !!!
26