The Journal of Online Mathematics and Its Applications, Volume 6 (2006)
The Chebyshev Equioscillation Theorem, Robert Mayans

## 5. Lower Bound on the Best Minimax Error

### Non-uniform alternating sets

We extend the definition of an alternating set to allow non-uniform distances.

#### Definition 1

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:

• ax0 < x1 < ··· < xn − 1b, and
• f(xi) − p(xi) = (−1)i ei for i = 0, 1, ..., n − 1.

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 fp, 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:

Your browser does not support the applet tag.

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 ||fg|| < |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.

Your browser does not support the applet tag.

### Lower bounds on the minimax error

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.

#### Theorem 4 (de la Vallee-Poussin)

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}.

#### Proof

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 pnq 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 qpn = 0 everywhere. But this is impossible, since by assumption q and pn disagree at x0, ..., xn + 1.