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 x0, x1, ..., xn − 1 such that:
where the ei's are all positive or all negative.
Although in an ordinary alternating set, the points xi are global maxima and minima of f − p, for non-uniform alternating sets the points xi need not be local maxima or minima.
Here is an example of a non-uniform alternating set of length 4:
Suppose that X = (x0, ..., xn − 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|| < |ei| 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 dn, 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 = (x0, ..., xn + 1) of length n + 2, then dn ≥ min{|ei|: 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 dn < |ei| for i = 0, ..., n + 1. Let pn be a polynomial of best approximation. Then by the argument above, X is a non-uniform alternating set for pn, q as well as f, q. So pn − 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 − pn = 0 everywhere. But this is impossible, since by assumption q and pn disagree at x0, ..., xn + 1.