Approximation theory/Proofs

Proof

Approximation theory

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.

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 $+\epsilon$ and $-\epsilon$.

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 $\epsilon$, 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 various places where it has these nonzero values. By the Fundamental theorem of algebra, that is impossible.