The Journal of Online Mathematics and Its Applications, Volume 6 (2006)
The Chebyshev Equioscillation Theorem, Robert Mayans
We extend the definition of an alternating set to allow non-uniform distances.
Let f be continuous on [a, b], and let p be a polynomial. A non-uniform alternating set of length n is a sequence of points x_{0}, x_{1}, ..., x_{n − 1} such that:
where the e_{i}'s are all positive or all negative.
Although in an ordinary alternating set, the points x_{i} are global maxima and minima of f − p, for non-uniform alternating sets the points x_{i} need not be local maxima or minima.
Here is an example of a non-uniform alternating set of length 4:
Suppose that X = (x_{0}, ..., x_{n − 1}) is a non-uniform alternating set of f, p. of length n. If g is a continuous function on [a, b] that is close to f, in the sense that ||f − g|| < |e_{i}| for i = 0, ..., n − 1, then X is a non-uniform alternating set on g, p. The proof is trivial. Here is a picture of the previous example, but applied to a function g which is close to f.
We can get a lower bound on d_{n}, the best minimax error, if we can find a polynomial p of degree ≤ n such that f, p has a non-uniform alternating set of length n + 2.
Let f be continuous on [a, b], and let q be a polynomial of degree ≤ n. If f, q has a non-uniform alternating set X = (x_{0}, ..., x_{n + 1}) of length n + 2, then d_{n} ≥ min{|e_{i}|: i = 0, 1, ..., n + 1}.
Suppose not: suppose that X is a non-uniform alternating set for f, q of length n + 2, and that d_{n} < |e_{i}| for i = 0, ..., n + 1. Let p_{n} be a polynomial of best approximation. Then by the argument above, X is a non-uniform alternating set for p_{n}, q as well as f, q. So p_{n} − q is a polynomial of degree ≤ n but also has at least n + 2 changes in sign, (at each of the points in the alternating set) and hence has at least n + 1 zeroes. We must conclude that q − p_{n} = 0 everywhere. But this is impossible, since by assumption q and p_{n} disagree at x_{0}, ..., x_{n + 1}.