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]

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

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

Let us define the equioscillation condition as the condition in the theorem statement, that is, the condition that there exists ${\displaystyle n+2}${\displaystyle n+2} ordered points in the interval such that the difference ${\displaystyle f(x_{i})-g(x_{i})}${\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)}${\displaystyle f(x)-g(x)}.

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

Assume by contradiction that a polynomial ${\displaystyle p(x)}${\displaystyle p(x)} of degree less than or equal to ${\displaystyle n}${\displaystyle n} existed that provides a uniformly better approximation to ${\displaystyle f}${\displaystyle f}, which means that ${\displaystyle \|f-p\|_{\infty }<\|f-g\|_{\infty }}${\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))}${\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}${\displaystyle n}. However, for every ${\displaystyle x_{i}}${\displaystyle x_{i}} of the ${\displaystyle n+2}${\displaystyle n+2} points ${\displaystyle x_{0},x_{1},...x_{n}}${\displaystyle x_{0},x_{1},...x_{n}}, we know that ${\displaystyle |p(x_{i})-f(x_{i})|<|g(x)-f(x)|}${\displaystyle |p(x_{i})-f(x_{i})|<|g(x)-f(x)|} because ${\displaystyle |p(x_{i})-f(x_{i})|\leq \|f-p\|_{\infty }}${\displaystyle |p(x_{i})-f(x_{i})|\leq \|f-p\|_{\infty }} and ${\displaystyle \|f-p||_{\infty }<\|f-g\|_{\infty }}${\displaystyle \|f-p||_{\infty }<\|f-g\|_{\infty }} (since ${\displaystyle p}${\displaystyle p} is a better approximation than ${\displaystyle g}${\displaystyle g}).

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

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

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

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

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

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

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

• Notes on how to prove Chebyshev’s equioscillation theorem at the Wayback Machine (archived July 2, 2011)
• The Chebyshev Equioscillation Theorem by Robert Mayans
• The de la Vallée-Poussin alternation theorem at the Encyclopedia of Mathematics
• Approximation theory by Remco Bloemen

• Theorems about polynomials
• Numerical analysis
• Theorems in mathematical analysis
• Mathematical analysis stubs

• Articles with short description
• Short description matches Wikidata
• Wikipedia articles needing clarification from July 2025
• Webarchive template wayback links
• All stub articles