NUMERICALLY COMPUTABLE BOUNDS FOR THE RANGE OF VALUES OF INTERVAL POLYNOMIALS
Abstract
A central problem in interval analysis is the computation
of the range of values of an interval polynomial over an interval. This problem has
been treated by Dussel and Schmitt [1] and, disregarding the
computational cost of their algorithm, solved in a satisfactory manner. In this paper
we will discuss two algorithms by Rivlin [4] (see also Cargo and
Shiska [2]) where the accuracy of the bounds depend on the amount of
work one is willing to do.
The first algorithm is based upon the expression of a polynomial in
Bernstein polynomials. This algorithm as given by Rivlin [4] is valid
for an estimate over the interval [0,1]. We will generalize the
algorithm to an arbitrary finite interval and we will show that it is an
appropriate algorithm if the width of the interval is not too large. The second
algorithm is based upon the mean value theorem. As stated by Rivlin [4]
it is valid for the interval [0,1]. We will generalize the algorithm so
that it is valid for any finite interval.
The algorithms are then generalized to interval arithmetic versions.
Finally we compare the algorithms numerically on several polynomials.
Description
Keywords
Computer Science