next up previous notation contents
Next: 2.9.4 Constant Intervals Up: 2.9 Generalized Interval Arithmetic Previous: 2.9.2 Three Valued Logic

2.9.3 Linear Intervals

The transformational operator tex2html_wrap_inline32671 will be extended to further generalize interval arithmetic.

We envision numbers as a tool used to describe things. Many of the things described by numbers are parameterized. For example, we may be using a number to describe the mass of an iron ball. The iron ball can be parameterized by its radius. We will bring these parameters into our number system. This integration of parameters into numbers will give us hints as to how numbers depend on the parameters. These hints will enable the new interval routines to return much tighter results.

To start, we will consider a number system with a single parameter   tex2html_wrap_inline32761 . The parameter can vary from zero to one, and is a real number. Again, as a starting point we will consider only linear relationships between the parameter and the value's bounds. This new number system, using real numbers as the underlying number system, is denoted by tex2html_wrap_inline32763 or tex2html_wrap_inline32765 . The subscript, tex2html_wrap_inline32767 , states that a linear relationship is used; the greek letter tex2html_wrap_inline32761 signifies the parameter tex2html_wrap_inline32761 of the linear function, while the latin letters p and q signify coefficients of the linear function.

A linear interval is described by a lower and upper endpoint, each of which is a linear function of tex2html_wrap_inline32761 . The coefficients of the linear functions must be numbers of the underlying system tex2html_wrap_inline32451 .

figure6841

The semantics of the interval   tex2html_wrap_inline32781 is: when parameter tex2html_wrap_inline32761 has value k, the interval represents a fixed real number between a+bk and c+dk. This can be stated formally as:

math6862

for real number x. Although the upper and lower endpoints of interval tex2html_wrap_inline32793 are linear functions of tex2html_wrap_inline32761 , the real number represented by the interval may not be a linear function of the parameter tex2html_wrap_inline32761 . The intervals cannot collapse. The interval between the lower and upper bound must be well-defined:

math6870

This follows from the original statement that intervals must have non-negative width:

math6877

The upper and lower functions must both be well-defined over [0,1]:

math6889

A picture may soothe the intuition. Associate the interval tex2html_wrap_inline32017 with the closed set [a,b], of extended real numbers. The free variable tex2html_wrap_inline32761 may be accommodated by introducing a new dimension. The interval tex2html_wrap_inline32017 does not interact with this new dimension, although the interval tex2html_wrap_inline32809 does. The earlier intervals may now be regarded as ``constant intervals''.

figure6901

An example is appropriate. Consider the problem of determining the range of an arbitrary function tex2html_wrap_inline32831 over the domain [0,1]. The parameter tex2html_wrap_inline32761 in this case is the argument to the function. The range may be computed by simply evaluating the function with x being a number representing the domain of interest, [0,1].

Since tex2html_wrap_inline32761 varies over [0,1], the linear function tex2html_wrap_inline32845 represents the domain completely: every element of the domain [0,1] is represented by tex2html_wrap_inline32845 , for some value of tex2html_wrap_inline32851 . It follows that the linear interval tex2html_wrap_inline32853 represents the domain: every element of the domain is contained in the interval tex2html_wrap_inline32853 . The constant interval tex2html_wrap_inline32111 represents the domain since every element of the domain is represented by an element of tex2html_wrap_inline32111 .

Consider the simple function g(x) = x - x. So, with tex2html_wrap_inline32765 , this proceeds as follows:

math8034

The resulting bound for the range is [0,0], which is the actual range. Using tex2html_wrap_inline32653 this would proceed as follows:

math8046

The resulting bound for the range is [-1,1], which is valid, but definitely not optimal. To determine the range of g over the domain [a,b], the domain would be represented by the linear interval tex2html_wrap_inline32875 , or the constant interval tex2html_wrap_inline32017 . The domain may also be represented by the linear interval tex2html_wrap_inline32879 . Any valid linear interval representative of the domain [a,b] must contain either tex2html_wrap_inline32875 or tex2html_wrap_inline32879 ; unless it also represents a larger domain D, tex2html_wrap_inline32889 .

The linear real interval number system may be denoted by   tex2html_wrap_inline32891 . The notation follows from the denotation   tex2html_wrap_inline32893 for the linear floating point interval number system:

math8077

A linear interval model tex2html_wrap_inline31401 of an n-ary function tex2html_wrap_inline32577 satistfies the inclusion property if  

math8084

Since tex2html_wrap_inline32905 is a function of tex2html_wrap_inline32761 , tex2html_wrap_inline32909 is well defined as a closed real interval:

math8089

The linear interval extension of the n-ary function g is defined as follows:

math8095

The lower and upper bounds l and u are functions of tex2html_wrap_inline32761 . The lower bound tex2html_wrap_inline32921 bounds tex2html_wrap_inline32923 from below; the range of tex2html_wrap_inline32213 is tex2html_wrap_inline32927 , and is therefore a function of tex2html_wrap_inline32761 . Although l is a function of tex2html_wrap_inline32761 it is not guaranteed to be linear, or even continuous. The demotion from an arbitrary function to a linear function is significant. The demoted tex2html_wrap_inline32935 bounds tex2html_wrap_inline32921 from below while the demoted tex2html_wrap_inline32939 bounds tex2html_wrap_inline32941 from above. In both cases, tex2html_wrap_inline32761 varies from zero to one.  

The demotions tex2html_wrap_inline32945 and tex2html_wrap_inline32947 are significant in the definition of interval extension because there is no best demotion available. This is drastically different from the demotions tex2html_wrap_inline32421 and tex2html_wrap_inline32419 used in the definition of floating point interval extensions. When demoting an extended real to a float, there is a particular floating point number which is the best choice. When rounding down, the largest floating point number less than or equal to the extended real is chosen. The best choice when demoting an arbitrary extended real function l to a linear extended real function tex2html_wrap_inline32955 depends on how tex2html_wrap_inline32955 will be used. This significantly changes the character of the interval extension. It can no longer be used to show an interval model is optimal in general, although it may be used to show that an interval method is suboptimal.


next up previous notation contents
Next: 2.9.4 Constant Intervals Up: 2.9 Generalized Interval Arithmetic Previous: 2.9.2 Three Valued Logic
Jeff TupperMarch 1996