Interval Arithmetics and Interval Newton Method

Interval Arithmetics

Interval arithmetic, interval mathematics, interval analysis, or interval computation, is a method developed by mathematicians since the 1950s and 1960s as an approach to putting bounds on rounding errors and measurement errors in mathematical computation and thus developing numerical methods that yield reliable results. Very simply put, it represents each value as a range of possibilities. For example, instead of estimating the height of someone using standard arithmetic as 2.0 meters, using interval arithmetic we might be certain that that person is somewhere between 1.97 and 2.03 meters.

Whereas classical arithmetic defines operations on individual numbers, interval arithmetic defines a set of operations on intervals:

T · S = { x | there is some y in T, and some z in S, such that x = y · z }.

The basic operations of interval arithmetic are, for two intervals [a, b] and [c, d] that are subsets of the real line (-∞, ∞),

  • [a, b] + [c, d] = [min (a + c, a + d, b + c, b + d), max (a + c, a + d, b + c, b + d)] = [a + c, b + d]
  • [a, b] − [c, d] = [min (ac, ad, bc, bd), max (ac, ad, bc, bd)] = [ad, bc]
  • [a, b] × [c, d] = [min (a × c, a × d, b × c, b × d), max (a × c, a × d, b × c, b × d)]
  • [a, b] ÷ [c, d] = [min (a ÷ c, a ÷ d, b ÷ c, b ÷ d), max (a ÷ c, a ÷ d, b ÷ c, b ÷ d)] when 0 is not in [c, d].

Division by an interval containing zero is not defined under the basic interval arithmetic. The addition and multiplication operations are commutative, associative and sub-distributive: the set X ( Y + Z ) is a subset of XY + XZ.

Instead of working with an uncertain real x we work with the two ends of the interval [a,b] which contains x: x lies between a and b, or could be one of them. Similarly a function f when applied to x is also uncertain. Instead, in interval arithmetic f produces an interval [c,d] which is all the possible values for f(x) for all x \in [a,b].

This concept is suitable for a variety of purposes. The most common use is to keep track of and handle rounding errors directly during the calculation 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 reliable and guaranteed solutions to equations and optimization problems.

Interval Newton method

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 [\mathbf{x}] can be derived from the average value extension.[6] For an unknown vector \mathbf{z}\in [\mathbf{x}] applied to \mathbf{y}\in [\mathbf{x}], gives

f(\mathbf{z}) \in  f(\mathbf{y}) + [J_f](\mathbf{[x]}) \cdot (\mathbf{z} - \mathbf{y}).

For a zero \mathbf{z}, that is f(z) = 0, and thus must satisfy

 f(\mathbf{y}) + [J_f](\mathbf{[x]}) \cdot (\mathbf{z} - \mathbf{y})=0 .

This is equivalent to  \mathbf{z} \in \mathbf{y} - [J_f](\mathbf{[x]})^{-1}\cdot f(\mathbf{y}). An outer estimate of [J_f](\mathbf{[x]})^{-1}\cdot f(\mathbf{y})) can be determined using linear methods.

In each step of the interval Newton method, an approximate starting value [\mathbf{x}]\in [\mathbb{R}]^n is replaced by [\mathbf{x}]\cap \left(\mathbf{y} - [J_f](\mathbf{[x]})^{-1}\cdot f(\mathbf{y})\right) 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 will produce all the zeros in the initial range. Conversely, it will prove that no zeros of f were in the initial range [\mathbf{x}] 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 f(x) = x2 − 2, the starting range [x] = [ − 2,2], and the point y = 0. We then have  J_f(x) = 2\, x and the first Newton step gives

[-2,2]\cap \left(0 - \frac{1}{2\cdot[-2,2]} (0-2)\right) = [-2,2]\cap \Big([{-\infty}, {-0.5}]\cup  [{0.5}, {\infty}] \Big).

There is therefore a zero in x\in [{-2}, {-0.5}]\cup   \big[{0.5}, {2}\big]. More Newton steps are used separately on x\in [{-2}, {-0.5}] and [0.5,2]. These converge to arbitrarily small intervals around -\sqrt{2} and +\sqrt{2}.

The Interval Newton method can also be used with thick functions such as g(x) = x2 − [2,3], which would in any case have interval results. The result then produces intervals containing 

To get a clearer information, you can download this reference by click its title:

1.  Introduction to Interval Analysis by Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud

2. Methods and Applications of Interval Analysis (SIAM Studies in Applied and Numerical Mathematics), Ramon E. Moor

You may leave a comment in this article to get the password.


Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:


You are commenting using your account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )


Connecting to %s