Computing a Subinterval of the Image
Paul L. Richman · Journal of the ACM · 1974
The problem of computing a desired function value to within a prescribed tolerance can be formulated in the following two distinct ways: Formulation I: Given x and ∈ > 0, compute f (x) to within ∈. Formulation II: Given only that x is in a closed interval X, compute a subinterval of the image, f (X) = { f (x) : x ∈ X}. The first formulation is applicable when x is known to arbitrary accuracy. The second formulation is applicable when x is known only to a limited accuracy, in which case the tolerance is prescribed albeit indirectly by the interval X, and one must be satisfied with all or part of the set f (X) of possible function values. Elsewhere the author has presented an efficient solution to Formulation I for any rational f and many nonrational f . B. A. Chartres has presented an efficient solution to Formulation II for a very restricted class of rational f and for a few nonrational f . In this paper a solution to Formulation II for the arbitrary nonconstant rational f is presented. By bounding df/dx away from zero over some subset of X, it is shown how to reduce Formulation II to Formulation I, yielding the solution given here. In generalizing to vector-valued functions f, Chartres has solved Formulation II only for rational f which satisfy a linear system of equations, while this paper presents a solution for arbitrary non-degenerate rational vector-valued f.