On the Convergence of Exchange Algorithms for Calculating Minimax Approximations

Open Access
Publisher Website
Google Scholar
Abstract
Given a function f(x) 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 f(x) 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, λ1, λ2, … λn, and we use the notation Φ (x,λ1,λ2, …,λn)εC. Most algorithms for calculating the required function Φ(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 (n + 1) distinct points of S, x0, x1, …, xn say. The value of the minimax error over the point set, η(x0, x1, …, xn), is regarded as a function of the points; so are μ1(x0, x1, …, xn) which are the values of λt, t = 1, 2, …, n, yielding η. In this paper we present theorems on the first and second derivatives of η and μt. They provide much insight into the convergence of exchange algorithms.

This publication has 0 references indexed in Scilit: