On the Convergence of Exchange Algorithms for Calculating Minimax Approximations

Given a function fix) and a range of the variable, S, the general minimax approximation problem is to determine that function of a class, C, which is the best approximation to /(.v) in the sense that the maximum error of the approximation as x ranges over S is minimized. We specialize to the usual case in which the functions of C are determined by n real parameters, Xi, X2,. . . Xn, and we use the notation (x,\u\2, , Xn)eC Most algorithms for calculating the required function (x, X) depend on the maximum error of the minimax approximation occurring for (n + 1 ) distinct values of the variable x. In particular exchange algorithms seek these values iteratively, usually calculating on each iteration a best approximation over in + 1) distinct points of S, xo, xi,..., xn say. The value of the minimax error over the point set, Y](xo, *i» , xn), is regarded as a function of the points; so are {L,(xo, * I , . . . , xn) which are the values of X,, t = 1, 2 , . . . , n, yielding i). In this paper we present theorems on the first and second derivatives of T) and (J.,. They provide much insight into the convergence of exchange algorithms.