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

Let ${\displaystyle f}$ be a continuous function from ${\displaystyle [a,b]}$ to ${\displaystyle \mathbb {R} }$. Among all the polynomials of degree ${\displaystyle \leq n}$, the polynomial ${\displaystyle g}$ minimizes the uniform norm of the difference ${\displaystyle \|f-g\|_{\infty }}$ if and only if there are ${\displaystyle n+2}$ points ${\displaystyle a\leq x_{0}<x_{1}<\cdots <x_{n+1}\leq b}$ such that ${\displaystyle f(x_{i})-g(x_{i})=\sigma (-1)^{i}\|f-g\|_{\infty }}$ where ${\displaystyle \sigma }$ is either -1 or +1.^[1][2]

That is, the polynomial ${\displaystyle g}$ oscillates above and below ${\displaystyle f}$ at the interpolation points, and does so to the same degree.

Proof

Let us define the equioscillation condition as the condition in the theorem statement, that is, the condition that there exists ${\displaystyle n+2}$ ordered points in the interval such that the difference ${\displaystyle f(x_{i})-g(x_{i})}$ alternates in sign and is equal in magnitude to the uniform-norm of ${\displaystyle f(x)-g(x)}$.

We need to prove that this condition is 'sufficient' for the polynomial ${\displaystyle g}$ being the best uniform approximation to ${\displaystyle f}$, and we need to prove that this condition is 'necessary' for a polynomial to be the best uniform approximation.

Sufficiency

Assume by contradiction that a polynomial ${\displaystyle p(x)}$ of degree less than or equal to ${\displaystyle n}$ existed that provides a uniformly better approximation to ${\displaystyle f}$, which means that ${\displaystyle \|f-p\|_{\infty }<\|f-g\|_{\infty }}$. Then the polynomial

${\displaystyle h(x)=g(x)-p(x)=(g(x)-f(x))-(p(x)-f(x))}$

is also of degree less than or equal to ${\displaystyle n}$. However, for every ${\displaystyle x_{i}}$ of the ${\displaystyle n+2}$ points ${\displaystyle x_{0},x_{1},...x_{n}}$, we know that ${\displaystyle |p(x_{i})-f(x_{i})|<|g(x)-f(x)|}$ because ${\displaystyle |p(x_{i})-f(x_{i})|\leq \|f-p\|_{\infty }}$ and ${\displaystyle \|f-p||_{\infty }<\|f-g\|_{\infty }}$ (since ${\displaystyle p}$ is a better approximation than ${\displaystyle g}$).

Therefore, ${\displaystyle h(x_{i})=(g(x_{i})-f(x_{i}))-(p(x_{i})-f(x_{i}))}$ will have the same sign as ${\displaystyle g(x_{i})-f(x_{i})}$ (because the second term has a smaller magnitude than the first). Thus, ${\displaystyle h(x_{i})}$ will also alternate sign on these ${\displaystyle n+2}$ points, and thus have at least ${\displaystyle n+1}$ roots. However, since ${\displaystyle h}$ is a 'polynomial' of at most degree ${\displaystyle n}$, it should only have at most ${\displaystyle n}$ roots. This is a contradiction.

Necessity

Given a polynomial ${\displaystyle g}$, let us define ${\displaystyle E=\|f(x)-g(x)\|_{\infty }}$. We will call a point ${\displaystyle x}$ an upper point if ${\displaystyle f(x)-g(x)=M}$ and a lower point if it equals ${\displaystyle -M}$ instead.

Define an alternating set (given polynomial ${\displaystyle g}$ and function ${\displaystyle f}$) to be a set of ordered points ${\displaystyle x_{0},...x_{n}}$ in ${\displaystyle [a,b]}$ such that for every point ${\displaystyle x_{i}}$ in the alternating set, we have ${\displaystyle f(x_{i})-g(x_{i})=\sigma (-1)^{i}M}$, where ${\displaystyle \sigma }$ equals ${\displaystyle 1}$ or ${\displaystyle -1}$ as before.

Define a sectioned alternating set to be an alternating set ${\displaystyle x_{0},...x_{n}}$ along with nonempty closed intervals ${\displaystyle I_{0},...I_{n}}$ called sections such that 1. the sections partition ${\displaystyle [a,b]}$ (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 ${\displaystyle i}$, the ${\displaystyle i}$th alternating point ${\displaystyle x_{i}}$ is in the ${\displaystyle i}$th section ${\displaystyle I_{i}}$ 3. If ${\displaystyle x_{i}}$ is an upper point, then ${\displaystyle I_{i}}$ contains no lower points. Likewise, if ${\displaystyle x_{i}}$ is a lower point, then ${\displaystyle I_{i}}$ contains no upper points.

Given an approximating polynomial ${\displaystyle g}$ 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 ${\displaystyle n+2}$ points in which case our improvement cannot be guaranteed to still be a polynomial of degree at most ${\displaystyle n}$ ^{[clarification needed]}

Variants

The equioscillation theorem is also valid when polynomials are replaced by rational functions: among all rational functions whose numerator has degree ${\displaystyle \leq n}$ and denominator has degree ${\displaystyle \leq m}$, the rational function ${\displaystyle g=p/q}$, with ${\displaystyle p}$ and ${\displaystyle q}$ being relatively prime polynomials of degree ${\displaystyle n-\nu }$ and ${\displaystyle m-\mu }$, minimizes the uniform norm of the difference ${\displaystyle \|f-g\|_{\infty }}$ if and only if there are ${\displaystyle m+n+2-\min\{\mu ,\nu \}}$ points ${\displaystyle a\leq x_{0}<x_{1}<\cdots <x_{m+n+1-\min\{\mu ,\nu \}}\leq b}$ such that ${\displaystyle f(x_{i})-g(x_{i})=\sigma (-1)^{i}\|f-g\|_{\infty }}$ where ${\displaystyle \sigma }$ is either -1 or +1.^[1]

Algorithms

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