Interval arithmetic

Last updated

Tolerance function (turquoise) and interval-valued approximation (red) Set of curves Outer approximation.png
Tolerance function (turquoise) and interval-valued approximation (red)

Interval arithmetic (also known as interval mathematics, interval analysis, or interval computation) is a mathematical technique used to put bounds on rounding errors and measurement errors in mathematical computation. Numerical methods using interval arithmetic can guarantee reliable, mathematically correct results. Instead of representing a value as a single number, interval arithmetic represents each value as a range of possibilities. For example, instead of estimating the height of someone as exactly 2.0 metres, using interval arithmetic one might be certain that that person is somewhere between 1.97 and 2.03 metres.

Contents

Mathematically, instead of working with an uncertain real , one works with the ends of an interval that contains . In interval arithmetic, any variable lies in the closed interval between and . A function , when applied to , yields an uncertain result; produces an interval which includes all the possible values for for all .

Interval arithmetic is suitable for a variety of purposes. The most common use is in software, to keep track of rounding errors in calculations and of uncertainties in the knowledge of the exact values of physical and technical parameters. The latter often arise from measurement errors and tolerances for components or due to limits on computational accuracy. Interval arithmetic also helps find guaranteed solutions to equations (such as differential equations) and optimization problems.

Introduction

The main objective of interval arithmetic is a simple way to calculate upper and lower bounds for the range of a function in one or more variables. These endpoints are not necessarily the true supremum or infimum, since the precise calculation of those values can be difficult or impossible; the bounds need only contain the function's range as a subset.

This treatment is typically limited to real intervals, so quantities of form

where and are allowed. With one of , infinite, the interval would be an unbounded interval; with both infinite, the interval would be the extended real number line. Since a real number can be interpreted as the interval intervals and real numbers can be freely combined.

As with traditional calculations with real numbers, simple arithmetic operations and functions on elementary intervals must first be defined. [1] More complicated functions can be calculated from these basic elements. [1]

Example

Body mass index for a person 1.80 m tall in relation to body weight m (in kilograms) Interval BMI Simple Example.png
Body mass index for a person 1.80 m tall in relation to body weight m (in kilograms)

As an example, consider the calculation of body mass index (BMI) and assessing whether a person is overweight. BMI is calculated as a person's body weight in kilograms divided by the square of their height in metres. A bathroom scale may have a resolution of one kilogram. Intermediate values cannot be discerned—79.6 kg and 80.3 kg are indistinguishable, for example—but the true weight is rounded to the nearest whole number. It is unlikely that when the scale reads 80 kg, the person weighs exactly 80.0 kg. In normal rounding to the nearest value, the scale's showing 80 kg indicates a weight between 79.5 kg and 80.5 kg. This corresponds with the interval .

For a man who weighs 80 kg and is 1.80 m tall, the BMI is approximately 24.7. A weight of 79.5 kg and the same height yields approx. 24.537, while a weight of 80.5 kg yields approx. 24.846. Since the function is monotonically increasing, we conclude that the true BMI is in the range . Since the entire range is less than 25, which is the cutoff between normal and excessive weight, we conclude that the man is of normal weight.

The error in this case does not affect the conclusion (normal weight), but this is not always the case. If the man was slightly heavier, the BMI's range may include the cutoff value of 25. In that case, the scale's precision was insufficient to make a definitive conclusion.

Also, note that the range of BMI examples could be reported as , since this interval is a superset of the calculated interval. The range could not, however, be reported as , as now the interval does not contain possible BMI values.

Interval arithmetic states the range of possible outcomes explicitly. Results are no longer stated as numbers, but as intervals that represent imprecise values. The size of the intervals are similar to error bars in expressing the extent of uncertainty.

Multiple intervals

Body mass index for different weights in relation to height L (in metres) Interval BMI Example.png
Body mass index for different weights in relation to height L (in metres)

Height and body weight both affect the value of the BMI. We have already treated weight as an uncertain measurement, but height is also subject to uncertainty. Height measurements in metres are usually rounded to the nearest centimeter: a recorded measurement of 1.79 metres actually means a height in the interval . Now, all four combinations of possible height/weight values must be considered. Using the interval methods described below, the BMI lies in the interval

In this case, the man may have a normal weight or be overweight; the weight and height measurements were insufficiently precise to make a definitive conclusion. This demonstrates interval arithmetic's ability to correctly track and propagate error.

Interval operators

A binary operation on two intervals, such as addition or multiplication, is defined by

In other words, it is the set of all possible values of , where and are in their corresponding intervals. If is monotone in each operand on the intervals, which is the case for the four basic arithmetic operations (except division when the denominator contains ), the extreme values occur at the endpoints of the operand intervals. Writing out all combinations, one way of stating this is

provided that is defined for all and .

For practical applications this can be simplified further:

where

The last case loses useful information about the exclusion of . Thus, it is common to work with and as separate intervals. More generally, when working with discontinuous functions, it is sometimes useful to do the calculation with so-called multi-intervals of the form The corresponding multi-interval arithmetic maintains a set of (usually disjoint) intervals and also provides for overlapping intervals to unite. [2]

Multiplication of positive intervals Interval multiplication.png
Multiplication of positive intervals

Interval multiplication often only requires two multiplications. If , are nonnegative,

The multiplication can be interpreted as the area of a rectangle with varying edges. The result interval covers all possible areas, from smallest to the largest.

With the help of these definitions, it is already possible to calculate the range of simple functions, such as For example, if , and :

.

Notation

To make the notation of intervals smaller in formulae, brackets can be used.

can be used to represent an interval. Note that in such a compact notation, should not be confused between a single-point interval and a general interval. For the set of all intervals, we can use

as an abbreviation. For a vector of intervals we can use a bold font: .

Elementary functions

Values of a monotonic function Value domain of monotonic function.png
Values of a monotonic function

Interval functions beyond the four basic operators may also be defined.

For monotonic functions in one variable, the range of values is simple to compute. If is monotonically increasing (resp. decreasing) in the interval then for all such that (resp. ).

The range corresponding to the interval can be therefore calculated by applying the function to its endpoints:

From this, the following basic features for interval functions can easily be defined:

For even powers, the range of values being considered is important, and needs to be dealt with before doing any multiplication. For example, for should produce the interval when But if is taken by repeating interval multiplication of form then the result is wider than necessary.

More generally one can say that, for piecewise monotonic functions, it is sufficient to consider the endpoints , of an interval, together with the so-called critical points within the interval, being those points where the monotonicity of the function changes direction. For the sine and cosine functions, the critical points are at or for , respectively. Thus, only up to five points within an interval need to be considered, as the resulting interval is if the interval includes at least two extrema. For sine and cosine, only the endpoints need full evaluation, as the critical points lead to easily pre-calculated values—namely -1, 0, and 1.

Interval extensions of general functions

In general, it may not be easy to find such a simple description of the output interval for many functions. But it may still be possible to extend functions to interval arithmetic. If is a function from a real vector to a real number, then   is called an interval extension of if

.

This definition of the interval extension does not give a precise result. For example, both and are allowable extensions of the exponential function. Tighter extensions are desirable, though the relative costs of calculation and imprecision should be considered; in this case, should be chosen as it gives the tightest possible result.

Given a real expression, its natural interval extension is achieved by using the interval extensions of each of its subexpressions, functions and operators.

The Taylor interval extension (of degree ) is a times differentiable function defined by

,

for some , where is the th order differential of at the point and is an interval extension of the Taylor remainder

Mean value form Meanvalue extension.png
Mean value form

The vector lies between and with , is protected by . Usually one chooses to be the midpoint of the interval and uses the natural interval extension to assess the remainder.

The special case of the Taylor interval extension of degree is also referred to as the mean value form.

Complex interval arithmetic

An interval can also be defined as a locus of points at a given distance from the centre,[ clarification needed ] and this definition can be extended from real numbers to complex numbers. [3] 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. [4] Interval arithmetic can thus be extended, via complex interval numbers, to determine regions of uncertainty in computing with complex numbers. [4]

The basic algebraic operations for real interval numbers (real closed intervals) 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. [4] 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. [4] Two other useful properties of ordinary complex arithmetic fail to hold in complex interval arithmetic: the additive and multiplicative properties, of ordinary complex conjugates, do not hold for complex interval conjugates. [4]

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 sacrifice other useful properties of ordinary arithmetic. [4]

Interval methods

The methods of classical numerical analysis can not be transferred one-to-one into interval-valued algorithms, as dependencies between numerical values are usually not taken into account.

Rounded interval arithmetic

Outer bounds at different level of rounding Illustration of outward rounding.png
Outer bounds at different level of rounding

To work effectively in a real-life implementation, intervals must be compatible with floating point computing. The earlier operations were based on exact arithmetic, but in general fast numerical solution methods may not be available. The range of values of the function for and are for example . Where the same calculation is done with single digit precision, the result would normally be . But , so this approach would contradict the basic principles of interval arithmetic, as a part of the domain of would be lost. Instead, the outward rounded solution is used.

The standard IEEE 754 for binary floating-point arithmetic also sets out procedures for the implementation of rounding. An IEEE 754 compliant system allows programmers to round to the nearest floating point number; alternatives are rounding towards 0 (truncating), rounding toward positive infinity (i.e. up), or rounding towards negative infinity (i.e. down).

The required external rounding for interval arithmetic can thus be achieved by changing the rounding settings of the processor in the calculation of the upper limit (up) and lower limit (down). Alternatively, an appropriate small interval can be added.

Dependency problem

Approximate estimate of the value range Interval-dependence problem-front view.png
Approximate estimate of the value range

The so-called dependency problem is a major obstacle to the application of interval arithmetic. Although interval methods can determine the range of elementary arithmetic operations and functions very accurately, this is not always true with more complicated functions. If an interval occurs several times in a calculation using parameters, and each occurrence is taken independently then this can lead to an unwanted expansion of the resulting intervals.

Treating each occurrence of a variable independently Interval-dependence problem.png
Treating each occurrence of a variable independently

As an illustration, take the function defined by The values of this function over the interval are As the natural interval extension, it is calculated as:

which is slightly larger; we have instead calculated the infimum and supremum of the function over There is a better expression of in which the variable only appears once, namely by rewriting as addition and squaring in the quadratic

So the suitable interval calculation is

and gives the correct values.

In general, it can be shown that the exact range of values can be achieved, if each variable appears only once and if is continuous inside the box. However, not every function can be rewritten this way.

Wrapping effect Interval-wrapping effect.png
Wrapping effect

The dependency of the problem causing over-estimation of the value range can go as far as covering a large range, preventing more meaningful conclusions.

An additional increase in the range stems from the solution of areas that do not take the form of an interval vector. The solution set of the linear system

is precisely the line between the points and Using interval methods results in the unit square, This is known as the wrapping effect .

Linear interval systems

A linear interval system consists of a matrix interval extension and an interval vector . We want the smallest cuboid , for all vectors which there is a pair with and satisfying

.

For quadratic systems in other words, for there can be such an interval vector , which covers all possible solutions, found simply with the interval Gauss method. This replaces the numerical operations, in that the linear algebra method known as Gaussian elimination becomes its interval version. However, since this method uses the interval entities and repeatedly in the calculation, it can produce poor results for some problems. Hence using the result of the interval-valued Gauss only provides first rough estimates, since although it contains the entire solution set, it also has a large area outside it.

A rough solution can often be improved by an interval version of the Gauss–Seidel method. The motivation for this is that the -th row of the interval extension of the linear equation

can be determined by the variable if the division is allowed. It is therefore simultaneously

and .

So we can now replace by

,

and so the vector by each element. Since the procedure is more efficient for a diagonally dominant matrix, instead of the system one can often try multiplying it by an appropriate rational matrix with the resulting matrix equation

left to solve. If one chooses, for example, for the central matrix , then is outer extension of the identity matrix.

These methods only work well if the widths of the intervals occurring are sufficiently small. For wider intervals it can be useful to use an interval-linear system on finite (albeit large) real number equivalent linear systems. If all the matrices are invertible, it is sufficient to consider all possible combinations (upper and lower) of the endpoints occurring in the intervals. The resulting problems can be resolved using conventional numerical methods. Interval arithmetic is still used to determine rounding errors.

This is only suitable for systems of smaller dimension, since with a fully occupied matrix, real matrices need to be inverted, with vectors for the right hand side. This approach was developed by Jiri Rohn and is still being developed. [5]

Interval Newton method

Reduction of the search area in the interval Newton step in "thick" functions Interval Newton step.png
Reduction of the search area in the interval Newton step in "thick" functions

An interval variant of Newton's method for finding the zeros in an interval vector can be derived from the average value extension. [6] For an unknown vector applied to , gives

.

For a zero , that is , and thus must satisfy

.

This is equivalent to . An outer estimate of can be determined using linear methods.

In each step of the interval Newton method, an approximate starting value is replaced by and so the result can be improved iteratively. In contrast to traditional methods, the interval method approaches the result by containing the zeros. This guarantees that the result produces all zeros in the initial range. Conversely, it proves that no zeros of were in the initial range if a Newton step produces the empty set.

The method converges on all zeros in the starting region. Division by zero can lead to separation of distinct zeros, though the separation may not be complete; it can be complemented by the bisection method.

As an example, consider the function , the starting range , and the point . We then have and the first Newton step gives

.

More Newton steps are used separately on and . These converge to arbitrarily small intervals around and .

The Interval Newton method can also be used with thick functions such as , which would in any case have interval results. The result then produces intervals containing .

Bisection and covers

Rough estimate (turquoise) and improved estimates through "mincing" (red) Illustration of interval mincing.png
Rough estimate (turquoise) and improved estimates through "mincing" (red)

The various interval methods deliver conservative results as dependencies between the sizes of different intervals extensions are not taken into account. However the dependency problem becomes less significant for narrower intervals.

Covering an interval vector by smaller boxes so that

is then valid for the range of values

So for the interval extensions described above the following holds:

Since is often a genuine superset of the right-hand side, this usually leads to an improved estimate.

Such a cover can be generated by the bisection method such as thick elements of the interval vector by splitting in the centre into the two intervals and If the result is still not suitable then further gradual subdivision is possible. A cover of intervals results from divisions of vector elements, substantially increasing the computation costs.

With very wide intervals, it can be helpful to split all intervals into several subintervals with a constant (and smaller) width, a method known as mincing. This then avoids the calculations for intermediate bisection steps. Both methods are only suitable for problems of low dimension.

Application

Interval arithmetic can be used in various areas (such as set inversion, motion planning, set estimation or stability analysis) to treat estimates with no exact numerical value. [7]

Rounding error analysis

Interval arithmetic is used with error analysis, to control rounding errors arising from each calculation. The advantage of interval arithmetic is that after each operation there is an interval that reliably includes the true result. The distance between the interval boundaries gives the current calculation of rounding errors directly:

Error = for a given interval .

Interval analysis adds to rather than substituting for traditional methods for error reduction, such as pivoting.

Tolerance analysis

Parameters for which no exact figures can be allocated often arise during the simulation of technical and physical processes. The production process of technical components allows certain tolerances, so some parameters fluctuate within intervals. In addition, many fundamental constants are not known precisely. [2]

If the behavior of such a system affected by tolerances satisfies, for example, , for and unknown then the set of possible solutions

,

can be found by interval methods. This provides an alternative to traditional propagation of error analysis. Unlike point methods, such as Monte Carlo simulation, interval arithmetic methodology ensures that no part of the solution area can be overlooked. However, the result is always a worst-case analysis for the distribution of error, as other probability-based distributions are not considered.

Fuzzy interval arithmetic

Approximation of the normal distribution by a sequence of intervals Fuzzy arithmetic.png
Approximation of the normal distribution by a sequence of intervals

Interval arithmetic can also be used with affiliation functions for fuzzy quantities as they are used in fuzzy logic. Apart from the strict statements and , intermediate values are also possible, to which real numbers are assigned. corresponds to definite membership while is non-membership. A distribution function assigns uncertainty, which can be understood as a further interval.

For fuzzy arithmetic [8] only a finite number of discrete affiliation stages are considered. The form of such a distribution for an indistinct value can then represented by a sequence of intervals

The interval corresponds exactly to the fluctuation range for the stage

The appropriate distribution for a function concerning indistinct values and the corresponding sequences

can be approximated by the sequence

where

and can be calculated by interval methods. The value corresponds to the result of an interval calculation.

Computer-assisted proof

Warwick Tucker used interval arithmetic in order to solve the 14th of Smale's problems, that is, to show that the Lorenz attractor is a strange attractor. [9] Thomas Hales used interval arithmetic in order to solve the Kepler conjecture.

History

Interval arithmetic is not a completely new phenomenon in mathematics; it has appeared several times under different names in the course of history. For example, Archimedes calculated lower and upper bounds 223/71 < π < 22/7 in the 3rd century BC. Actual calculation with intervals has neither been as popular as other numerical techniques nor been completely forgotten.

Rules for calculating with intervals and other subsets of the real numbers were published in a 1931 work by Rosalind Cicely Young. [10] Arithmetic work on range numbers to improve the reliability of digital systems were then published in a 1951 textbook on linear algebra by Paul S. Dwyer  [ de ]; [11] intervals were used to measure rounding errors associated with floating-point numbers. A comprehensive paper on interval algebra in numerical analysis was published by Teruo Sunaga (1958). [12]

The birth of modern interval arithmetic was marked by the appearance of the book Interval Analysis by Ramon E. Moore in 1966. [13] [14] He had the idea in spring 1958, and a year later he published an article about computer interval arithmetic. [15] Its merit was that starting with a simple principle, it provided a general method for automated error analysis, not just errors resulting from rounding.

Independently in 1956, Mieczyslaw Warmus suggested formulae for calculations with intervals, [16] though Moore found the first non-trivial applications.

In the following twenty years, German groups of researchers carried out pioneering work around Ulrich W. Kulisch [1] [17] and Götz Alefeld  [ de ] [18] at the University of Karlsruhe and later also at the Bergische University of Wuppertal. For example, Karl Nickel  [ de ] explored more effective implementations, while improved containment procedures for the solution set of systems of equations were due to Arnold Neumaier among others. In the 1960s, Eldon R. Hansen dealt with interval extensions for linear equations and then provided crucial contributions to global optimisation, including what is now known as Hansen's method, perhaps the most widely used interval algorithm. [6] Classical methods in this often have the problem of determining the largest (or smallest) global value, but could only find a local optimum and could not find better values; Helmut Ratschek and Jon George Rokne developed branch and bound methods, which until then had only applied to integer values, by using intervals to provide applications for continuous values.

In 1988, Rudolf Lohner developed Fortran-based software for reliable solutions for initial value problems using ordinary differential equations. [19]

The journal Reliable Computing (originally Interval Computations) has been published since the 1990s, dedicated to the reliability of computer-aided computations. As lead editor, R. Baker Kearfott, in addition to his work on global optimisation, has contributed significantly to the unification of notation and terminology used in interval arithmetic. [20]

In recent years work has concentrated in particular on the estimation of preimages of parameterised functions and to robust control theory by the COPRIN working group of INRIA in Sophia Antipolis in France. [21]

Implementations

There are many software packages that permit the development of numerical applications using interval arithmetic. [22] These are usually provided in the form of program libraries. There are also C++ and Fortran compilers that handle interval data types and suitable operations as a language extension, so interval arithmetic is supported directly.

Since 1967, Extensions for Scientific Computation (XSC) have been developed in the University of Karlsruhe for various programming languages, such as C++, Fortran and Pascal. [23] The first platform was a Zuse Z23, for which a new interval data type with appropriate elementary operators was made available. There followed in 1976, Pascal-SC, a Pascal variant on a Zilog Z80 that it made possible to create fast, complicated routines for automated result verification. Then came the Fortran 77-based ACRITH-XSC for the System/370 architecture (FORTRAN-SC), which was later delivered by IBM. Starting from 1991 one could produce code for C compilers with Pascal-XSC; a year later the C++ class library supported C-XSC on many different computer systems. In 1997, all XSC variants were made available under the GNU General Public License. At the beginning of 2000 C-XSC 2.0 was released under the leadership of the working group for scientific computation at the Bergische University of Wuppertal to correspond to the improved C++ standard.

Another C++-class library was created in 1993 at the Hamburg University of Technology called Profil/BIAS (Programmer's Runtime Optimized Fast Interval Library, Basic Interval Arithmetic), which made the usual interval operations more user friendly. It emphasized the efficient use of hardware, portability and independence of a particular presentation of intervals.

The Boost collection of C++ libraries contains a template class for intervals. Its authors are aiming to have interval arithmetic in the standard C++ language. [24]

The Frink programming language has an implementation of interval arithmetic that handles arbitrary-precision numbers. Programs written in Frink can use intervals without rewriting or recompilation.

Gaol [25] is another C++ interval arithmetic library that is unique in that it offers the relational interval operators used in interval constraint programming.

The Moore library [26] is an efficient implementation of interval arithmetic in C++. It provides intervals with endpoints of arbitrary precision and is based on the ``concepts´´ feature of C++.

The Julia programming language [27] has an implementation of interval arithmetics along with high-level features, such as root-finding (for both real and complex-valued functions) and interval constraint programming, via the ValidatedNumerics.jl package. [28]

In addition computer algebra systems, such as FriCAS, Mathematica, Maple, Maxima (software) [29] and MuPAD, can handle intervals. A Matlab extension Intlab [30] builds on BLAS routines, and the Toolbox b4m makes a Profil/BIAS interface. [30] [31] Moreover, the Software Euler Math Toolbox includes an interval arithmetic.

A library for the functional language OCaml was written in assembly language and C. [32]

IEEE 1788 standard

A standard for interval arithmetic, IEEE Std 1788-2015, has been approved in June 2015. [33] Two reference implementations are freely available. [34] These have been developed by members of the standard's working group: The libieeep1788 [35] library for C++, and the interval package [36] for GNU Octave.

A minimal subset of the standard, IEEE Std 1788.1-2017, has been approved in December 2017 and published in February 2018. It should be easier to implement and may speed production of implementations. [37]

Conferences and workshops

Several international conferences or workshop take place every year in the world. The main conference is probably SCAN (International Symposium on Scientific Computing, Computer Arithmetic, and Verified Numerical Computation), but there is also SWIM (Small Workshop on Interval Methods), PPAM (International Conference on Parallel Processing and Applied Mathematics), REC (International Workshop on Reliable Engineering Computing).

See also

Related Research Articles

Discrete Fourier transform

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be a frequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous, and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle.

In probability theory, the expected value of a random variable , denoted or , is a generalization of the weighted average, and is intuitively the arithmetic mean of a large number of independent realizations of . The expected value is also known as the expectation, mathematical expectation, mean, average, or first moment. Expected value is a key concept in economics, finance, and many other subjects.

In mathematics, a product is the result of multiplication, or an expression that identifies factors to be multiplied. For example, 30 is the product of 6 and 5, and is the product of and .

Taylor series Expression of a function as an infinite sum

In mathematics, the Taylor series of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor series are equal near this point. Taylor's series are named after Brook Taylor who introduced them in 1715.

In probability theory, the central limit theorem (CLT) establishes that, in many situations, when independent random variables are added, their properly normalized sum tends toward a normal distribution even if the original variables themselves are not normally distributed. The theorem is a key concept in probability theory because it implies that probabilistic and statistical methods that work for normal distributions can be applicable to many problems involving other types of distributions.

Probability density function Function whose integral over a region describes the probability of an event occurring in that region

In probability theory, a probability density function (PDF), or density of a continuous random variable, is a function whose value at any given sample in the sample space can be interpreted as providing a relative likelihood that the value of the random variable would equal that sample. In other words, while the absolute likelihood for a continuous random variable to take on any particular value is 0, the value of the PDF at two different samples can be used to infer, in any particular draw of the random variable, how much more likely it is that the random variable would equal one sample compared to the other sample.

In mathematics, the affinely extended real number system is obtained from the real number system by adding two infinity elements: and where the infinities are treated as actual numbers. It is useful in describing the algebra on infinities and the various limiting behaviors in calculus and mathematical analysis, especially in the theory of measure and integration. The affinely extended real number system is denoted or or

Fourier series Decomposition of periodic functions into sums of simpler sinusoidal forms

In mathematics, a Fourier series is a periodic function composed of harmonically related sinusoids, combined by a weighted summation. With appropriate weights, one cycle of the summation can be made to approximate an arbitrary function in that interval. As such, the summation is a synthesis of another function. The discrete-time Fourier transform is an example of Fourier series. The process of deriving weights that describe a given function is a form of Fourier analysis. For functions on unbounded intervals, the analysis and synthesis analogies are Fourier transform and inverse transform.

In calculus, and more generally in mathematical analysis, integration by parts or partial integration is a process that finds the integral of a product of functions in terms of the integral of the product of their derivative and antiderivative. It is frequently used to transform the antiderivative of a product of functions into an antiderivative for which a solution can be more easily found. The rule can be thought of as an integral version of the product rule of differentiation.

Fokker–Planck equation Partial differential equation

In statistical mechanics, the Fokker–Planck equation is a partial differential equation that describes the time evolution of the probability density function of the velocity of a particle under the influence of drag forces and random forces, as in Brownian motion. The equation can be generalized to other observables as well. It is named after Adriaan Fokker and Max Planck, and is also known as the Kolmogorov forward equation, after Andrey Kolmogorov, who independently discovered the concept in 1931. When applied to particle position distributions, it is better known as the Smoluchowski equation, and in this context it is equivalent to the convection–diffusion equation. The case with zero diffusion is known in statistical mechanics as the Liouville equation. The Fokker–Planck equation is obtained from the master equation through Kramers–Moyal expansion.

In probability theory and statistics, the moment-generating function of a real-valued random variable is an alternative specification of its probability distribution. Thus, it provides the basis of an alternative route to analytical results compared with working directly with probability density functions or cumulative distribution functions. There are particularly simple results for the moment-generating functions of distributions defined by the weighted sums of random variables. However, not all random variables have moment-generating functions.

Radon transform

In mathematics, the Radon transform is the integral transform which takes a function f defined on the plane to a function Rf defined on the (two-dimensional) space of lines in the plane, whose value at a particular line is equal to the line integral of the function over that line. The transform was introduced in 1917 by Johann Radon, who also provided a formula for the inverse transform. Radon further included formulas for the transform in three dimensions, in which the integral is taken over planes. It was later generalized to higher-dimensional Euclidean spaces, and more broadly in the context of integral geometry. The complex analogue of the Radon transform is known as the Penrose transform. The Radon transform is widely applicable to tomography, the creation of an image from the projection data associated with cross-sectional scans of an object.

In mathematics, more specifically in multivariable calculus, the implicit function theorem is a tool that allows relations to be converted to functions of several real variables. It does so by representing the relation as the graph of a function. There may not be a single function whose graph can represent the entire relation, but there may be such a function on a restriction of the domain of the relation. The implicit function theorem gives a sufficient condition to ensure that there is such a function.

Cross-correlation

In signal processing, cross-correlation is a measure of similarity of two series as a function of the displacement of one relative to the other. This is also known as a sliding dot product or sliding inner-product. It is commonly used for searching a long signal for a shorter, known feature. It has applications in pattern recognition, single particle analysis, electron tomography, averaging, cryptanalysis, and neurophysiology. The cross-correlation is similar in nature to the convolution of two functions. In an autocorrelation, which is the cross-correlation of a signal with itself, there will always be a peak at a lag of zero, and its size will be the signal energy.

In mathematics, a norm is a function from a real or complex vector space to the nonnegative real numbers that behaves in certain ways like the distance from the origin: it commutes with scaling, obeys a form of the triangle inequality, and is zero only at the origin. In particular, the Euclidean distance of a vector from the origin is a norm, called the Euclidean norm, or 2-norm, which may also be defined as the square root of the inner product of a vector with itself.

Projectively extended real line

In real analysis, the projectively extended real line, is the extension of the set of the real numbers, by a point denoted . It is thus the set with the standard arithmetic operations extended where possible, and is sometimes denoted by The added point is called the point at infinity, because it is considered as a neighbour of both ends of the real line. More precisely, the point at infinity is the limit of every sequence of real numbers whose absolute values are increasing and unbounded.

In mathematical analysis, and applications in geometry, applied mathematics, engineering, and natural sciences, a function of a real variable is a function whose domain is the real numbers , or a subset of that contains an interval of positive length. Most real functions that are considered and studied are differentiable in some interval. The most widely considered such functions are the real functions, which are the real-valued functions of a real variable, that is, the functions of a real variable whose codomain is the set of real numbers.

Dyadic transformation

The dyadic transformation is the mapping

In mathematics, a stiff equation is a differential equation for which certain numerical methods for solving the equation are numerically unstable, unless the step size is taken to be extremely small. It has proven difficult to formulate a precise definition of stiffness, but the main idea is that the equation includes some terms that can lead to rapid variation in the solution.

In mathematics, a line integral is an integral where the function to be integrated is evaluated along a curve. The terms path integral, curve integral, and curvilinear integral are also used; contour integral is used as well, although that is typically reserved for line integrals in the complex plane.

References

  1. 1 2 3 Kulisch, Ulrich W. (1989). Wissenschaftliches Rechnen mit Ergebnisverifikation. Eine Einführung (in German). Wiesbaden: Vieweg-Verlag. ISBN   3-528-08943-1.
  2. 1 2 Dreyer, Alexander (2003). Interval Analysis of Analog Circuits with Component Tolerances. Aachen, Germany: Shaker Verlag. p. 15. ISBN   3-8322-4555-3.
  3. Complex interval arithmetic and its applications, Miodrag S. Petković, Ljiljana D. Petković, Wiley-VCH, 1998, ISBN   978-3-527-40134-5
  4. 1 2 3 4 5 6 Hend Dawood (2011). Theories of Interval Arithmetic: Mathematical Foundations and Applications. Saarbrücken: LAP LAMBERT Academic Publishing. ISBN   978-3-8465-0154-2.
  5. "Jiri Rohn, List of publications". Archived from the original on 2008-11-23. Retrieved 2008-05-26.
  6. 1 2 Walster, G. William; Hansen, Eldon Robert (2004). Global Optimization using Interval Analysis (2nd ed.). New York, USA: Marcel Dekker. ISBN   0-8247-4059-9.
  7. Jaulin, Luc; Kieffer, Michel; Didrit, Olivier; Walter, Eric (2001). Applied Interval Analysis. Berlin: Springer. ISBN   1-85233-219-0.
  8. Application of Fuzzy Arithmetic to Quantifying the Effects of Uncertain Model Parameters, Michael Hanss, University of Stuttgart
  9. Tucker, Warwick (1999). The Lorenz attractor exists. Comptes Rendus de l'Académie des Sciences-Series I-Mathematics, 328(12), 1197-1202.
  10. Young, Rosalind Cicely (1931). The algebra of many-valued quantities. Mathematische Annalen, 104(1), 260-290. (NB. A doctoral candidate at the University of Cambridge.)
  11. Dwyer, Paul Sumner (1951). Linear computations. Oxford, England: Wiley. (University of Michigan)
  12. Sunaga, Teruo (1958). "Theory of interval algebra and its application to numerical analysis". RAAG Memoirs (2): 29–46.
  13. Moore, Ramon Edgar (1966). Interval Analysis. Englewood Cliff, New Jersey, USA: Prentice-Hall. ISBN   0-13-476853-1.
  14. Cloud, Michael J.; Moore, Ramon Edgar; Kearfott, R. Baker (2009). Introduction to Interval Analysis. Philadelphia: Society for Industrial and Applied Mathematics (SIAM). ISBN   978-0-89871-669-6.
  15. Hansen, Eldon Robert (2001-08-13). "Publications Related to Early Interval Work of R. E. Moore". University of Louisiana at Lafayette Press. Retrieved 2015-06-29.
  16. Precursory papers on interval analysis by Mieczyslaw Warmus Archived 2008-04-18 at the Wayback Machine
  17. Kulisch, Ulrich W. (1969). "Grundzüge der Intervallrechnung". In Laugwitz, Detlef (ed.). Jahrbuch Überblicke Mathematik (in German). 2. Mannheim, Germany: Bibliographisches Institut. pp. 51–98.
  18. Alefeld, Götz; Herzberger, Jürgen. Einführung in die Intervallrechnung. Reihe Informatik (in German). 12. Mannheim, Wien, Zürich: B.I.-Wissenschaftsverlag. ISBN   3-411-01466-0.
  19. Bounds for ordinary differential equations of Rudolf Lohner Archived 11 May 2018 at the Wayback Machine (in German)
  20. Bibliography of R. Baker Kearfott, University of Louisiana at Lafayette
  21. Introductory Film (mpeg) of the COPRIN teams of INRIA, Sophia Antipolis
  22. Software for Interval Computations collected by Vladik Kreinovich], University of Texas at El Paso.
  23. History of XSC-Languages Archived 2007-09-29 at the Wayback Machine
  24. A Proposal to add Interval Arithmetic to the C++ Standard Library
  25. Gaol is Not Just Another Interval Arithmetic Library
  26. Moore: Interval Arithmetic in Modern C++
  27. The Julia programming language
  28. ValidatedNumerics.jl
  29. Interval Arithmetic for Maxima: A Brief Summary by Richard J. Fateman.]
  30. 1 2 Intlab INTerval LABoratory
  31. b4m
  32. Alliot, Jean-Marc; Gotteland, Jean-Baptiste; Vanaret, Charlie; Durand, Nicolas; Gianazza, David (2012). Implementing an interval computation library for OCaml on x86/amd64 architectures. 17th ACM SIGPLAN International Conference on Functional Programming.
  33. IEEE Standard for Interval Arithmetic
  34. Nathalie Revol (2015). The (near-)future IEEE 1788 standard for interval arithmetic, slides // SWIM 2015: 8th Small Workshop in Interval Methods. Prague, 9-11 June 2015
  35. C++ implementation of the preliminary IEEE P1788 standard for interval arithmetic
  36. GNU Octave interval package
  37. "IEEE Std 1788.1-2017 - IEEE Standard for Interval Arithmetic (Simplified)". IEEE Standard. IEEE Standards Association. 2017. Retrieved 2018-02-06.

Further reading

Workshops

Libraries