The range of an arithmetic expression on an interval can be estimated by evaluating the expression using interval arithmetic, but there are some cases where no overestimation error occurs. This paper demonstrates such cases systematically and provides a sufficient condition for when interval estimation yields the exact range. The author shows that for certain classes of expressions there is no overestimation if the input interval has a sufficiently large distance to zero. The formulation of the minimal distance for polynomials in Horner as well as in factorial forms is derived.
There is a need to understand the essential differences between one arithmetic expression and an alternative equivalent expression. The author presents an example arithmetic expression, f = ((x - 1) x - 17)x - 15, which was estimated over the interval X. The evaluation of f on X by interval estimation yields
(([5,6] - 1) [5,6] - 17)[5,6] - 15 = [0,63],
which is the range of f on X. The evaluation of the “equivalent” expression g = x3 - x2 - 17x - 15 on X provides [5,6]3 - [5,6]2 - 17[5,6] - 15 = [-28,91], which is a proper overestimation. The author found a sufficient condition for a given expression and interval such that interval evaluation yields the exact range. It appears that there are only a few cases found in which the condition is not satisfied but the evaluation is still exact. This paper shows that, for polynomial expressions in Horner form, the evaluation is exact if the input interval has a sufficiently large distance to zero. The minimal distance can be expressed in terms of the roots of certain subpolynomials of the given polynomial. A similar result is presented for polynomials in factorized form. The author has organized this paper in seven interesting sections. Section 1 provides the introduction. Section 2 deals with the overestimation error of some simple arithmetic expressions. Section 3 provides notation and basic definitions. Section 4 shows the non-overestimation condition and its proof. In section 5, the author presents an efficient procedure for testing the condition for a given expression and input interval. The non-overestimation condition is applied to polynomial expressions in factorized form and in Horner form in sections 6 and 7, respectively. The author cites seven interesting, pertinent references.