Jump to content

Approximation theory/Proofs

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by William Ackerman (talk | contribs) at 16:00, 6 April 2006. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
Proof

Approximation theory

Proof that an Nth 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 Nth 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 Nth 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 Nth 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.