Interval arithmetic

Interval arithmetic called in mathematics a methodology for automated error estimation based on closed intervals. It is not exactly known real quantities are considered, which can be two numbers and limited though. It can be between and or also take one of two values ​​. This range corresponds mathematically to the interval. A function that depends on such uncertain, can not be accurately evaluated. Finally, it is not known what value should be used within for actually. Instead, the smallest possible interval is determined that contains just the possible function values ​​for all. Targeted assessment of the endpoints and one obtains a new function, which in turn maps intervals to intervals.

This concept is suitable, inter alia, for the treatment of rounding errors directly during the calculation and if uncertainties in the knowledge of the exact values ​​of physical and technical parameters are available. The latter often arise from measurement errors and component tolerances. In addition, interval arithmetic can help you to obtain reliable solutions of equations and optimization problems.

As an example, the calculation of the body mass index ( BMI of Engl. Body Mass Index) should be considered here. The BMI is the body mass in kilograms divided by the square of height in meters. To illustrate the weight determination is done using a bathroom scale, in which the weight can be read accurately to one kilogram ( mass determination actually ). It intermediate values ​​are therefore never determined - about 79.6 kg or 80.3 kg - but to whole numbers rounded information. It is of course very unlikely that you really weighs exactly 80.0 kg, when indicated. In normal rounding to the nearest value of the scale provides weight 80 kg for each weight between 79.5 kg and 80.5 kg. The corresponding range of all real numbers that are greater than or equal to 79.5, and less than or equal to 80.5, can simply be written as an interval. To avoid confusion it is mostly a dot instead of a comma as a decimal separator.

For a person who weighs 80 kg and 1.80 m is large, the BMI is about 24.7. With a weight of 79.5 kg, and the same body size but only a value of 24.5 would have to be assumed, whereas 80.5 kg already correspond almost 24.9. Thus, the actual BMI is in the range. In this case, the error in practice can still be neglected, however, is that not all accounts of the case. For example, the weight varies in the course of a day, so that the BMI thoroughly between 24 (still normal weight ) and 25 ( already overweight ) may vary here. Without detailiierte bill but can not always be taken at the outset say whether an error is finally large enough to have significant influence.

In the interval arithmetic, the range of possible outcomes is explicitly calculated. Simply put, you no longer expects numbers, but with intervals that do not accurately represent known values ​​. Much like a error bars to a measurement interval expresses the degree of uncertainty about the phenomenon to be measured. For this purpose, simple computer operations, such as basic arithmetic or trigonometric functions, redefined for calculating with intervals to obtain outer limits of this range of values.

• 2.1 Rounded interval arithmetic
• 2.2 dependency problem and Einhüllungseffekt
• 2.3 Linear Interval Systems
• 2.4 Interval Newton method
• 2.5 bisection and overlaps

• 3.1 Rounding error analysis
• 3.2 Tolerance Analysis
• 3.3 Fuzzy Arithmetic

• 9.1 Literature
• 9.2 External links
• 9.3 sources

Introduction

The main focus in the interval arithmetic activities is to determine the simplest possible way upper and lower bounds for the values ​​of a function in one or more variables. In this case, these limits do not necessarily have the supremum and infimum correspond, since the exact calculation of these values ​​is often difficult. ( It can be shown that this task is generally NP-hard. )

Usually, one is limited to the treatment is complete, real intervals, ie sets of the form

Which are well and allowed. This match and the most ajar written intervals consisting of all real numbers less than or equal to or greater than or equal to. Accordingly, the interval refers to the entire real axis.

As with the classic arithmetic with numbers must first be defined once as the arithmetic operations and elementary functions are applied to intervals. More complex functions can then be composed of these basic elements ( ref: Kulish, 1989).

Basic arithmetic

For explanation is again resorted to the example from the beginning. In the determination of body mass index in addition to weight, body height plays a role. This is typically measured only in whole centimeters: an indication of the height of 1.80 meters so actually means a height somewhere between 1,795 m and 1,805 m. This inaccuracy has in addition to the variation in the weight which is between 79.5 kg and 80.5 kg, are included. For the BMI now as I said, the body mass in kilograms must be divided by the square of height in meters. Both of 79.5 kg and 1,795 m as well as 80.5 kg and 1.805 m results for approximately 24.7. It must now also be taken into account that the person in question may only 1,795 m tall with a weight of 80.5 kilograms - or 1,805 m 79.5 kg. The combinations of all possible intermediate values ​​must be included in the analysis. With the help of the below specified interval arithmetics, the intervallwertige BMI

Actually be calculated.

An operation between two intervals, which is, for example addition or multiplication, the condition must

. meet For the four basic arithmetic operations, this results in

If permitted for all and.

For practical applications, this can be further simplified:

• Addition:
• Subtraction:
• Multiplication:
• Division :, where appropriate.

For the division by an interval which includes the zero, is initially defined

For true, so you should actually put. This, however, you lose the gap and thus valuable information. Usually one expects, therefore, with the subsets individually and on.

Because within an interval arithmetic also several such splits occur, it is sometimes useful to systematize the computation with so-called multi - intervals of the form. The corresponding multi- interval arithmetic then maintains a disjoint set of intervals and then ensures, for example also in favor of uniting overlapping intervals (Lit.: Dreyer, 2005).

Since one can interpret a number as the interval immediately obtained a rule for combination of interval and real-valued variables.

Using these definitions, it is already the range of values ​​of simple functions, such as determining. If, for example, and, we obtain

Is interpreted as a function of one variable with intervallwertigen parameters and then can be the set of all zeros of this family of functions easily determined. It is then

The possible zeros lie in the interval so.

As in the above example, the multiplication of intervals can often be attributed to only the multiplication of two numbers. It is namely

The multiplication can be interpreted here as the area A rectangle with varying edge lengths. The intervallwertige result then covers all the values ​​from the smallest to largest possible area.

The same applies if one of the two intervals is entirely in the non -positive and the other entirely in the non - negative range of the real axis. Generally, it must be considered in the multiplication, the result must be released immediately if uncertain values ​​, such as occur. This occurs, for example, to the case of division, both included in the numerator and denominator to zero.

Notation

To make it easier to recognize intervallwertige sizes in mathematical formulas, misused to the brackets to the " mark".

Accordingly, called an interval and the set of all real intervals is as

Abbreviated. For a box or a vector of intervals used in addition bold style.

At such a compact notation is to be noted that is not confused with a so-called improper interval coincide with the upper and lower limits.

Elementary functions

To be able to treat functions with interval methods whose terms do not result from the basic arithmetic operations, one has to redefine even more elementary functions for intervals. This one makes use of existing monotonicity properties.

For monotonic functions in one variable, the range of values ​​can also be easily determined. Is monotonically increasing or decreasing in an interval, then for all values ​​of the inequality

The range of the interval is obtained by evaluation of the function at the end points, and:

Therefore, the following Intervallisierungen elementary functions can be easily defined:

• Exponential function: , for,
• Logarithm: for positive intervals and
• Odd powers: for odd.

It is also still important to determine the range of values ​​for even powers. In contrast to the usual numerical analysis, it is not useful here, due to the calculation of the multiplication. For example, moves to within the interval, though. But if one tries by multiplications of the form to determine, we obtain in each case as a result.

It makes more sense here to look at the parable as a composition of a monotonically decreasing ( for ) and a monotonically increasing function ( for ). It applies to just:

• If,
• If,
• , Other

Generally, one can say that it is sufficient for piecewise monotone functions, this calculate at the end points of an interval, as well as to the so-called critical points contained in. The critical points in this case correspond to the points at which to change the monotony properties.

This can be applied for example to the sine and cosine, which must be evaluated in addition to bodies and for all. These play a maximum of five points a role, as you can as a result set immediately when the input interval contains at least one full period. In addition, sine and cosine only need to be re-evaluated at the edge Punken since the corresponding values ​​at the critical points - namely -1, 0, 1 - can be stored in advance.

Interval extensions of general functions

In general, we find for any function no such simple description of the range of values. One can extend these to intervals but often. When a function is a real-valued vector which maps a real number, then it is called an interval extension, if applicable

This defines the interval extension is not unique. For example, as well as allowable expansion of the exponential function. As sharp as possible extensions are desired, ie those which approximate as closely as possible this range, you will choose in this case, rather, because they even determine the exact area.

The natural interval extension is obtained by the basic arithmetic and elementary functions are replaced in the function rule by their intervallwertigen equivalents.

The Taylor expansion interval ( of degree ) of a time differentiable function is defined by

A,

Wherein said differential -th order of the point and a Taylor expansion of the interval remainder term

Referred to.

Since the vector is between and, can also be estimated by. Is usually chosen as the center of the interval of the vector and the natural expansion of interval for the estimation of the residual limb.

The special case of the Taylor expansion of the degree interval is also referred to as the average interval extension. For an interval extension of the Jacobian matrix is obtained here

A non-linear function can be limited by linear functions.

Interval method

The methods of classical numerical analysis can not be implemented directly for interval arithmetic, as this dependencies are usually not taken into account.

Rounded interval arithmetic

In order to efficiently anticipate intervals, a concrete implementation must be compatible to calculations with floating point numbers. The operations defined above are based on exact arithmetic, which is not available in fast numerical solution method. The range of values ​​of the function and for example, would be. Performs to the same invoice with single digit precision through, the result would normally be rounded. However, since this approach would contradict the basic principles of interval arithmetic, since part of the value range of lost. Instead, here the rounded outwards solution is preferable.

The IEEE 754 standard defines both standard representations of binary floating-point numbers and exact procedures for the implementation of roundings. Therefore, it must conform to IEEE 754, a system programmer in addition to the mathematical rounding ( to the nearest floating-point number ), further rounding modes provide: always round up, always round and rounding to 0 (earnings reduce its value).

The required outward rounds so can be done by appropriately switching the rounding settings of the processor when calculating upper and lower limits. Alternatively, this can be achieved by adding small addition of a suitable interval.

Dependency problem and Einhüllungseffekt

The so-called dependence problem is a major impediment to the application of interval arithmetic. Although the range of values ​​of the elementary arithmetic operations and functions with interval methods can be determined very accurately, this is no longer true for composite functions. If multiple intervallwertiger a parameter occurs in an invoice, each occurrence is treated independently. This leads to an undesired inflation of the resulting intervals.

To illustrate a function is given by the expression. The range of values ​​of this function over the interval is actually. To receive the natural interval extension, but is expected, resulting in a slightly larger area. In fact, you actually calculated over infimum and supremum of the function. Here one would therefore use a better alternative formulation that uses the variable only once. In this case one can transform by completing the square the expression simple.

Then delivers the appropriate interval arithmetic

Also the correct range of values.

In general, it can be shown that you can actually receive the exact range of values, when each variable appears only once. However, not every function can be suitable to dissolve.

The dependency problem caused by the overestimation of the value range can go so far that the result covers such a large area that does not allow meaningful conclusions more.

An additional enlargement of the range of values ​​resulting from the enveloping of areas which do not have the form of an interval vector. The solution set of the linear system

Is exactly the line between the points and. Interval methods provide here but in the best case, the square that encloses the actual solution ( Einhüllungs or "wrapping " effect).

Linear interval systems

A linear interval of system consists of a matrix and an interval intervallwertigen vector. Is then searched for a possible small box that contains all the vectors for which there are a pair, and that equation

Met.

For square systems - in other words - could such interval vector containing all the possible solutions, and easily determine the interval Gauss method. To this end, we replace the numerical operations that appear in the Gaussian elimination method known from linear algebra, by their interval versions. However, since received during the execution of this method, the intervallwertigen entries and more than once in the bill, this approach suffers from very strong to the dependency problem. Consequently, the interval Gauss provides only rough estimates at first, although they include the entire amount of solution, but also a very large area outside of it.

A rough solution can often be improved by a Intervallisierung the Gauss- Seidel method. This is motivated as follows: the - th row of the intervallwertigen linear equation

Can be determined by the variables dissolve, if the division is allowed. There is therefore simultaneously

So you can now by

Replace, and so improve the vector element-wise. Since the process is more efficient for diagonal dominant matrix, attempts often takes the system, the resultant by multiplying with a suitable real matrix matrix equation

To solve. Is chosen, for example, the center matrix, as is an outer approximation of the unit matrix.

However, applies to the above methods, that they only work well if the width of the intervals occurring is sufficiently small. For wider intervals, it may be useful to a finite (albeit large ) number of real-valued linear systems due to an interval linear system. For, if all matrices invertible, then it is perfectly adequate to consider all possible combinations of ( upper and lower ) endpoints of the intervals occurring. The resulting sub-problems can be solved by conventional numerical methods. Interval arithmetic is only still used to determine rounding error.

This approach is only possible for systems of smaller dimension as a fully occupied matrix has real matrices must be inverted, each with vectors for the right side. This approach has been continued and improved by Jiří Rohn.

Interval Newton method

An interval version of Newton's method for the determination of the zeros in an interval vector can be easily derived from the average extension ( ref: Hansen, 1992). For an unknown vector applies to a solid that

For a zero, and thus must

Be satisfied. Is thus obtained. An external assessment of this case can be determined by a linear method.

In each Newton step, a rough start value is replaced and iteratively improved. In contrast to the classical method, this method approaches from outside the zeros. Therefore, it is guaranteed that the result always contains all zeros in the start value. Conversely, it has been proven that there is no zero point is in when the Newton step returns the empty set.

The method converges to a set containing all zeros ( within the start region). By existing in this case, divide by zero, often results in several interval vectors that separate the zeros of each other. This separation is not always complete, and can then be pushed through bisection.

As an example, consider the function of the start value and the point. One has then and the first Newton step is given by

It applies to a zero. Newton more steps are then used, respectively, and separated. These converge to arbitrarily small intervals around and.

The interval -Newton method can also be readily applied in thick functions, ie functions such that already then return intervals, if one uses real numbers. The solution then consists of several intervals.

Bisection and overlaps

The various interval methods provide only extremely conservative estimates of each desired region, because of dependencies among the intervallwertigen sizes are not sufficiently considered. However, the dependency problem plays a more minor role, the thinner the intervals.

About Cover to an interval vector by smaller boxes so that then applies to the range of values ​​for the interval above extensions then applies. As often is a proper superset of the right side, is thus obtained usually an improved estimate.

Such coverage can be generated by bisection by dividing particularly thick elements of the interval vector, for example, in the middle and two intervals and replaced the one. If the result of the action is still not suitable, it can be further decomposed successively. Here, however, be noted that by split vector elements at a surplus of interval vectors arises, which of course greatly increases the computational effort.

With very wide intervals, it may even be advisable to disassemble all intervals equal in several subintervals with (small ) constant width ( " Mincing "). This eliminates the intermediate calculation for each Bisektionsschritte. Both approaches, however, are only suitable for problems of low dimension.

Application

The interval arithmetic comes in various fields used to treat sizes for which no exact numerical values ​​can be specified (Ref.: .. Jaulin et al, 2001).

Rounding error analysis

The interval arithmetic is used in the error analysis in order to get control over the rounding errors occurring in each calculation. The advantage of interval arithmetic is that one obtains an interval after each operation, which includes the result of safely. From the distance of the interval bounds can read the current calculation error directly:

Interval analysis here offers no substitute for the classical methods of error reduction, as Pivoting, but complements only.

Tolerance analysis

In the simulation, technical and physical processes often occur on parameters to which no exact numbers can be assigned. Thus, subject to the production process of technical components to specific tolerances can vary so certain parameters within certain intervals. In addition, many physical constants can not be measured with any degree of accuracy ( ref: Dreyer, 2005).

If the behavior of such a system of tolerances, for example, by an equation described for and unknown, then the set of all possible solutions

Be estimated by interval methods. This present here an alternative to the classical error analysis dar. In contrast to point-based methods, such as Monte Carlo simulation, presents the methodology used ensures that no parts of the solution domain be overlooked. However, the result is always a worst case analysis for uniformly distributed errors, other probability distributions are not possible.

Fuzzy arithmetic

Interval arithmetic can be used to approach as used in the fuzzy logic membership functions for fuzzy sets arbitrary. In addition to the strict statements and also intermediate values ​​are possible that are given real numbers. This corresponds to the safe belonging and non-belonging. A distribution function assigns to each of these values ​​to a certain range of variation, which can be regarded as interval.

Only many discrete membership levels are considered for the fuzzy arithmetic finite. The shape of such a distribution for a fuzzy value can be by a number of intervals,

Be approximated. In this case, the interval exactly corresponds to the fluctuation range for the stage.

The corresponding distribution for a function with respect to fuzzy values ​​and the corresponding sequences can then be approximated by the interval sequence. The values ​​are given by and can be estimated by interval method. This corresponds to the result of interval arithmetic.

History

Interval arithmetic is not a completely new phenomenon in mathematics and dived repeatedly under different names throughout history on. How Archimedes calculated already in the 3rd century BC, upper and lower bounds on the circle of pi However, the actual calculation with intervals was never as popular as other numerical techniques, but was never completely forgotten.

Rules for calculating with intervals and other subsets of the real numbers eventually find themselves in a work published in 1931 by Rosalind Cicely Young, a doctoral student at the University of Cambridge. Working for a range arithmetic of numbers ("Area Numbers") in order to improve and reliability of digital systems are then found in a textbook published in 1951, linear algebra by Paul S. Dwyer ( University of Michigan ). Here intervals are actually used for estimating the rounding errors in floating point numbers.

(Lit.: Moore) as the birth of modern interval arithmetic the publication of the book Interval Analysis by Ramon E. Moore in 1966 is considered. The idea he had in the spring of 1958, and already nearly a year later, he published an article on computer-assisted interval arithmetic. Its merit is that a universal method for automated error analysis was made ​​of a simple principle that will help not only the influence of rounding could be determined.

Regardless of Mieczyslaw Warmus had proposed as early as 1956 formulas for calculating with intervals, but at Moore were found along with implementation notes also the first non-trivial applications.

In the following twenty years, German research groups afford to Götz Alefeld (Lit.: Alefeld and Herzberger ) and Ulrich Kulish (Lit.: Kulish ) at the University of Karlsruhe and later at the University of Wuppertal pioneering work. For example, explored Karl Nickel efficient implementations while owes improved containment procedures for the solution set of systems of equations, among others, Arnold Neumaier. Eldon R. Hansen also initially dealt in the 60s with intervallwertigen linear equations and then delivered later decisive contributions to global optimization (Lit.: Hansen). In this area, an attempt is made to tackle with intervals, the problem is that with the classical numerics often the largest (or smallest ) function value can not be determined, but only a so-called local optimum in a place in their environment no better values ​​are assumed. For this purpose, transferred Ratschek and Rokne the branch-and- bound algorithm, which was originally defined only for integer values ​​using interval method to continuous quantities. In 1988, Rudolf Lohner developed a Fortran -based software for secure solutions for initial value problems in ordinary differential equations.

Since the 90s the journal Reliable Computing (formerly Interval Computations ) is issued, the reliability of computer-assisted calculations devoted to. As a senior editor R. Baker Kearfott has contributed significantly in addition to his work on global optimization to unify the notation and terminology of interval arithmetic (web: Kearfott ).

More recently, in particular the work on the assessment of the archetype of parameterized functions and robust control of the coprine working group of the INRIA in Sophia Antipolis be mentioned ( Web: INRIA ).

Patents

One of the main sponsors of the interval arithmetic, G. William Walster of Sun Microsystems, in the years 2003/ 04 - filed several patents in the field of interval arithmetic in the U.S. Patent and Trademark Office - partly together with Ramon E. Moore and Eldon R. Hansen. However, the validity of these claims is highly controversial in the interval arithmetic research community, since it may merely reflect the prior art.

Implementations

There are many software packages that allow the development of numerical applications using the interval arithmetic. These are usually implemented in the form of program libraries. However, there are also C - and Fortran translator which possess interval data types and corresponding appropriate operations as a language extension so that interval arithmetic is supported directly.

Since 1967, we initially developed at the University of Karlsruhe XSC - extensions for scientific computing ( " Extensions for Scientific Computation" ) for various programming languages, including C , Fortran and Pascal. Platform was initially a Zuse Z 23, for which a new interval data type with corresponding elementary operators was provided.

In 1976, with Pascal -SC, a Pascal variant on a Zilog Z80, which made it possible to create complex routines for automated verification result quickly. It was followed by the Fortran 77 -based ACRITH -XSC for the System/370, which is later delivered by IBM. From 1991 onwards, you can then generate code for C compiler with Pascal -XSC, and a year later, the C class library C -XSC already supports many different computer systems. 1997, all XSC variants are placed under the General Public License and are thus freely available. Beginning of the 2000s was 2.0 redesigned under the auspices of the Working Group for Scientific Computing at the University of Wuppertal in order to meet the now adopted C standard better C- XSC.

Another C class library is created at the Technical University Hamburg -Harburg 1993 Profile / BIAS ( "Programmer's Runtime Optimized Fast Interval Library, Basic Interval Arithmetic" ), which is the usual interval operations user-friendly available. Here, special emphasis was placed on the efficient utilization of the hardware, portability and independence from a specific interval representation.

The boost set of C libraries also includes a template class intervals. Their authors are currently seeking to a recording of interval arithmetic in the C language standard.

Today, in addition to the popular computer algebra systems such as Mathematica, Maple and MuPAD, handle intervals. There is also the extension for Matlab Intlab, based on the BLAS routines, as well as the B4M Toolbox, which provides a profile / BIAS interface.