The optimal exchange algorithm and comparisons with the generalized remes algorithm † ‡

This paper is concerned with the general problem of the determination of the best uniform approximation of a given function. A special case is the calculation of the minimax solution of an overdetermined linear system. Single point exchange algorithms produce successive approximate solutions for such problems. An example is furnished by the generalized Remes algorithm, which includes both the original Remes algorithm and the Stiefel algorithm as special cases. The optimal exchange algorithm is similar, but it has the important feature that every exchange is optimal in a certain desirable sense. It is proved that eventually the optimal exchange and generalized Remes algorithms coincide. However, early exchanges in the latter algorithm can be far from optimal and quite inefficient. A combination of the optimal exchange and generalized Remes algorithms is suggested as a reasonable strategy.