Approximation theory/Proofs

{Proof that an N^th-degree polynomial that gives rise to an error function that has N + 2 maxima, of alternating signs and equal magnitudes, is optimal in the sense of approximation theory. Such an optimal polynomial gives the minimum value, over all polynomials, of the maximum error of that polynomial. The maximum error of a polynomial P is the maximum, over the domain of approximation, of |P(x) − f(x)|.

This is most easily seen with a graph. Let N = 4 in the example. Suppose P(x) is an N^th-degree polynomial that is level, in the sense that P(x) − f(x) oscillates among N + 2 maxima, of alternating signs, at +ε and −ε.

The error function P(x) − f(x) might look like the red graph:

Error P(x) − f(x) for level polynomial (red), and for purported better polynomial (blue)

P(x) − f(x) achieves N + 2 maxima (2 at the end points), that have the same magnitude -- just over 6 divisions on the above graph.

Now suppose Q(x) is another N^th-degree polynomial that is strictly better than P. That means that the maxima of its error function must all have strictly smaller magnitude than ε, so that it lies strictly inside the error graph for P(x). The error function for Q(x) might look like the blue graph above. This means that [P(x) − f(x)] − [Q(x) − f(x)] must alternate between strictly positive nonzero numbers and strictly negative nonzero numbers, a total of N + 2 times. But [P(x) − f(x)] − [Q(x) − f(x)] is just P(x) − Q(x), an N^th-degree polynomial. It must have at least N + 1 roots between the N + 2 places where it has these alternating nonzero values. By the fundamental theorem of algebra, that is impossible.