Equioscillation theorem

In mathematics, the equioscillation theorem concerns the approximation of continuous functions using polynomials when the merit function is the maximum difference (uniform norm). Its discovery is attributed to Chebyshev.[1]

Statement

edit

Let   be a continuous function from   to  . Among all the polynomials of degree  , the polynomial   minimizes the uniform norm of the difference   if and only if there are   points   such that   where   is either -1 or +1.[1][2]

That is, the polynomial   oscillates above and below   at the interpolation points, and does so to the same degree.

Proof

edit

Let us define the equioscillation condition as the condition in the theorem statement, that is, the condition that there exists   ordered points in the interval such that the difference   alternates in sign and is equal in magnitude to the uniform-norm of  .

We need to prove that this condition is 'sufficient' for the polynomial   being the best uniform approximation to  , and we need to prove that this condition is 'necessary' for a polynomial to be the best uniform approximation.

Sufficiency

edit

Assume by contradiction that a polynomial   of degree less than or equal to   existed that provides a uniformly better approximation to  , which means that  . Then the polynomial

 

is also of degree less than or equal to  . However, for every   of the   points  , we know that   because   and   (since   is a better approximation than  ).

Therefore,   will have the same sign as   (because the second term has a smaller magnitude than the first). Thus,   will also alternate sign on these   points, and thus have at least   roots. However, since   is a 'polynomial' of at most degree  , it should only have at most   roots. This is a contradiction.

Necessity

edit

Given a polynomial  , let us define  . We will call a point   an upper point if   and a lower point if it equals   instead.

Define an alternating set (given polynomial   and function  ) to be a set of ordered points   in   such that for every point   in the alternating set, we have  , where   equals   or   as before.

Define a sectioned alternating set to be an alternating set   along with nonempty closed intervals   called sections such that 1. the sections partition   (meaning that the union of the sections is the whole interval, and the intersection of any two sections is either empty or a single common endpoint) 2. For every  , the  th alternating point   is in the  th section   3. If   is an upper point, then   contains no lower points. Likewise, if   is a lower point, then   contains no upper points.

Given an approximating polynomial   that does not satisfy the equioscillation condition, it is possible to show that the polynomial will have a two point alternating set. This alternating set can then be expanded to a sectioned alternating set. We can then use this sectioned alternating set to improve the approximation, unless the sectioned alternating set has more than   points in which case our improvement cannot be guaranteed to still be a polynomial of degree at most   [clarification needed]

Variants

edit

The equioscillation theorem is also valid when polynomials are replaced by rational functions: among all rational functions whose numerator has degree   and denominator has degree  , the rational function  , with   and   being relatively prime polynomials of degree   and  , minimizes the uniform norm of the difference   if and only if there are   points   such that   where   is either -1 or +1.[1]

Algorithms

edit

Several minimax approximation algorithms are available, the most common being the Remez algorithm.

References

edit
  1. ^ a b c Golomb, Michael (1962). Lectures on Theory of Approximation.
  2. ^ "Notes on how to prove Chebyshev's equioscillation theorem" (PDF). Archived from the original (PDF) on 2 July 2011. Retrieved 2022-04-22.
edit