A New Remez-Type Algorithm for Best Polynomial Approximation

The best approximation problem is a classical topic of the approximation theory and the Remez algorithm is one of the most famous methods for computing minimax polynomial approximations. We present a slight modification of the (second) Remez algorithm where a new approach to update the trial reference is considered. In particular at each step, given the local extrema of the error function of the trial polynomial, the proposed algorithm replaces all the points of the trial reference considering some “ad hoc” oscillating local extrema and the global extremum (with its adjacent) of the error function. Moreover at each step the new trial reference is chosen trying to preserve a sort of equidistribution of the nodes at the ends of the approximation interval. Experimentally we have that this method is particularly appropriate when the number of the local extrema of the error function is very large. Several numerical experiments are performed to assess the real performance of the proposed method in the approximation of continuous and Lipschitz continuous functions. In particular, we compare the performance of the proposed method for the computation of the best approximant with the algorithm proposed in [17] where an update of the Remez ideas for best polynomial approximation in the context of the chebfun software system is studied.