On the effectiveness of automated search for optimal approximations with guaranteed accuracy in floating-point systems
The paper presents a method for automated parallel minimax approximation of functions R→R by polynomials Zbp→Zbp from Zbp[x] that is, defined over a subset of rational b-numbers of finite precision p. Such polynomials guarantee the existence of an upper bound on the absolute approximation error, but these guarantees are formulated in the literature with respect to the entire set of real numbers R which makes them, strictly speaking, applicable only in the field of theoretical analysis, as opposed to the numerical, with finite precision, solutions of systems of nonlinear equations using the multidimensional Householder. The use of the multidimensional method makes it possible to generalize existing implementations of the search for minimax polynomials to cases of arbitrary differentiable functions in the domain of definition. The purpose of the work is to provide guarantees regarding the accuracy of the approximation in the worst cases, therefore, the calculation of minimax polynomials is performed using long rational arithmetic; the results are rounded to floating-point numbers of the selected precision which provides guarantees regarding numerical errors of no more than half the unit-in-last-place (ULP) [1]. The results obtained by the authors include a numerical implementation of the Remez exchange algorithm based on the multidimensional Housholder method in arbitrarily finite precision. The experimental implementation is described in the paper as well as the results of the experimental research. The implementation, and therefore the results, are available for readers to be verified.
Authors: А. A. Chusov, Yu. I. Efimova
Direction: Informatics, Computer Technologies And Control
Keywords: accuracy guarantees, multidimensional Householder method, long rational arithmetic, numerical errors and ULP guarantees, Remez algorithm, non-uniform function approximation
View full article