An algorithm for best rational approximation based on barycentric rational interpolation

We present a novel algorithm for computing best uniform rational approximations to real scalar functions in the setting of zero defect. The method, dubbed BRASIL (best rational approximation by successive interval length adjustment), is based on the observation that the best rational approximation r to a function f must interpolate f at a certain number of interpolation nodes (x(j)). Furthermore, the sequence of local maximum errors per interval (x(j-1),x(j)) must equioscillate. The proposed algorithm iteratively rescales the lengths of the intervals with the goal of equilibrating the local errors. The required rational interpolants are computed in a stable way using the barycentric rational formula. The BRASIL algorithm may be viewed as a fixed-point iteration for the interpolation nodes and converges linearly. We demonstrate that a suitably designed rescaled and restarted Anderson acceleration (RAA) method significantly improves its convergence rate. The new algorithm exhibits excellent numerical stability and computes best rational approximations of high degree to many functions in a few seconds, using only standard IEEE double-precision arithmetic. A free and open-source implementation in Python is provided. We validate the algorithm by comparing to results from the literature. We also demonstrate that it converges quickly in some situations where the current state-of-the-art method, the minimax function from the Chebfun package which implements a barycentric variant of the Remez algorithm, fails.

Automated summary

The algorithm, named BRASIL, iteratively adjusts interval lengths to achieve the best rational approximation of a scalar function by exploiting the equioscillation of local maximum errors. It utilizes the barycentric rational formula for stable computation and demonstrates improved convergence rate with the Anderson acceleration method. The algorithm shows excellent numerical stability and computational efficiency for high degree rational approximations.