Alternant set

The alternant set in approximation theory gives a necessary and sufficient condition for the best approximation of a continuous function by polynomials. He is attributed to the Russian mathematician Pafnuti Lwowitsch Chebyshev .

Alternant set

Let be an interval and a continuous function . Among all polynomials of degree , the polynomial minimizes the supremum if and only if it extreme points are so ${\displaystyle [a,b]}$ ${\displaystyle \subset \mathbb {R} }$ ${\displaystyle f\colon [a,b]\to \mathbb {R} }$ ${\displaystyle \leq n}$ ${\displaystyle p}$ ${\displaystyle \|f-p\|_{\infty }}$ ${\displaystyle n+2}$ ${\displaystyle a\leq x_{0}<x_{1}<\cdots <x_{n+1}\leq b}$

${\displaystyle f(x_{i})-p(x_{i})=\sigma (-1)^{i}E}$   for all   ${\displaystyle i=0,\ldots ,n+1}$

is with and solid . ${\displaystyle E:=\|f-p\|_{\infty }}$ ${\displaystyle \sigma =\pm 1}$

${\displaystyle E}$is the minimum distance (or approximation error ) from to , the space of algebraic polynomials of degree less than or equal to . A polynomial with a minimum distance to is called a proximum or best approximation to with respect to . ${\displaystyle f}$ ${\displaystyle {\mathcal {P}}_{n}}$ ${\displaystyle n}$ ${\displaystyle p\in {\mathcal {P}}_{n}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle {\mathcal {P}}_{n}}$

example 1

Best approximation of the square root function by a linear function: The maximum difference 1/8 is assumed three times with alternating signs

After alternant set is the polynomial that of polynomial of degree less than or equal that the square root function , on the interval most approximates with respect to the supremum. Since the error function and therefore also the error function is strictly concave , the latter assumes a local minimum at the interval boundaries and in each case, furthermore a maximum in the interior of . This is determined by setting the derivative to zero . Now is with at these extreme points , so is first and second with . ${\displaystyle p(x)=x+{\tfrac {1}{8}}}$ ${\displaystyle n=1}$ ${\displaystyle f\colon [0,1]\to \mathbb {R} }$ ${\displaystyle f(x)={\sqrt {x}}}$ ${\displaystyle [a,b]=[0,1]}$ ${\displaystyle f}$ ${\displaystyle f-p}$ ${\displaystyle x_{0}:=0}$ ${\displaystyle x_{2}:=1}$ ${\displaystyle x_{1}}$ ${\displaystyle [0,1]}$ ${\displaystyle f'-p'={\tfrac {1}{2{\sqrt {x_{1}}}}}-1}$ ${\displaystyle x_{1}={\tfrac {1}{4}}}$ ${\displaystyle E:={\tfrac {1}{8}}}$ ${\displaystyle f(0)-p(0)=-E,\ f({\tfrac {1}{4}})-p({\tfrac {1}{4}})=+E,\ f(1)-p(1)=-E}$ ${\displaystyle E=\max _{0\leq x\leq 1}|f(x)-p(x)|=\|f-p\|_{\infty }}$ ${\displaystyle f(x_{i})-p(x_{i})=\sigma (-1)^{i}E}$ ${\displaystyle \sigma =-1}$

Example 2

The function with a is in the interval for each by the polynomial ${\displaystyle f(x)={\frac {1}{r-x}}}$ ${\displaystyle r>1}$ ${\displaystyle [-1,1]}$ ${\displaystyle n\in \mathbb {N} _{0}}$

${\displaystyle p_{n}(x):={\frac {1}{r-x}}-E_{n}V_{n}}$

optimally approximated by the degree . ${\displaystyle n}$

It is     set   as well   ${\displaystyle E_{n}:={\frac {{\bigl (}r-{\sqrt {r^{2}-1}}{\bigr )}^{n}}{r^{2}-1}}}$ ${\displaystyle V_{n}(x):=\cos(n\varphi +\psi )}$

and     implicitly defined   by     and     by   . ${\displaystyle \varphi }$ ${\displaystyle \cos \varphi :=x}$ ${\displaystyle \psi }$ ${\displaystyle \tan {\frac {\psi }{2}}:={\sqrt {\frac {r+1}{r-1}}}\tan {\frac {\varphi }{2}}}$

Remark
The (best) polynomials converge for increasing ( uniformly and) with a linear speed of convergence against the function . ${\displaystyle p_{n}(x)}$ ${\displaystyle n}$ ${\displaystyle f}$

Evidence sketch

1. Polynomial property: Through conversions and a. on Chebyshev polynomials first and second type , the function of turns in the counter of as a polynomial of degree . This means first of all a rational function. Furthermore, the zero point has , so that the factor from can be split off and the denominator from can be reduced. At the end there is a polynomial of degree . ${\displaystyle q(x):=1-(r-x)\,E_{n}V_{n}}$ ${\displaystyle p_{n}(x)={\frac {1}{r-x}}-E_{n}V_{n}}$ ${\displaystyle n+1}$ ${\displaystyle p_{n}(x)}$ ${\displaystyle q(x)}$ ${\displaystyle r}$ ${\displaystyle (x-r)}$ ${\displaystyle q(x)}$ ${\displaystyle (r-x)}$ ${\displaystyle p_{n}(x)}$ ${\displaystyle p_{n}(x)}$ ${\displaystyle n}$
   
   

   Best approximation of the function (red) by polynomials of degree 0 , 1 and 2 . The maximum deviations are shown by vertical bars that protrude from the function in alternating directions. At grade 3, the error bars would fall below the pixel boundary. ${\displaystyle {\tfrac {1}{37/12-x}}}$
   
2. Best approximation: The given relations define a monotonic and bijective mapping

${\displaystyle {\begin{array}{clc}{]-1,1{\overleftarrow {[}}}\;\;&\to \;\;&{{\overrightarrow {]}}0,(n+1)\pi [}\\x&\mapsto &n\varphi +\psi \\\end{array}}}$

between two open intervals , in which the values ​​are met exactly among the multiples of (and thus the extreme places of the cosine ) . (The relevant are the main values of the Inverse Trigonometric been taken.) If you add the interval limits with and with added, then one has the alternants for which the error function exactly times alternating the respective extreme value takes. ${\displaystyle \pi }$ ${\displaystyle \pi ,2\pi ,\ldots ,n\pi }$ ${\displaystyle x_{0}=1}$ ${\displaystyle n\varphi +\psi =0}$ ${\displaystyle x_{n+1}=-1}$ ${\displaystyle n\varphi +\psi =(n+1)\pi }$ ${\displaystyle n+2}$ ${\displaystyle x_{0}>\dots >x_{i}>\dots >x_{n+1}}$ ${\displaystyle f(x)-p_{n}(x)=E_{n}\cos(n\varphi +\psi )}$ ${\displaystyle n+2}$ ${\displaystyle (-1)^{i}E_{n}}$

The first 4 approximations for ${\displaystyle r={\tfrac {37}{12}}}$

${\displaystyle n}$	best polynomial ${\displaystyle p_{n}}$	Extreme points	Max. error ${\displaystyle E_{n}}$
${\displaystyle 0}$	${\displaystyle {\tfrac {444}{1225}}}$	${\displaystyle 1\qquad \qquad \qquad \qquad -\!1}$	${\displaystyle {\tfrac {1}{s^{2}}}={\tfrac {144}{1225}}\;\approx 0.1176}$
${\displaystyle 1}$	${\displaystyle {\tfrac {144}{1225}}\;x+\;{\tfrac {12}{35}}}$	${\displaystyle 1\qquad \qquad {\tfrac {1}{6}}\qquad \quad \;\;-\!1}$	${\displaystyle {\tfrac {r-s}{s^{2}}}={\tfrac {24}{1225}}\;\approx 0.0196}$
${\displaystyle 2}$	${\displaystyle {\tfrac {48}{1225}}\,x^{2}+{\tfrac {4}{35}}\,x+{\tfrac {396}{105}}}$	${\displaystyle 1\quad \;\;\;{\tfrac {7}{12}}\quad \;\;\;-\!{\tfrac {5}{12}}\quad \;\,-\!1}$	${\displaystyle {\tfrac {(r-s)^{2}}{s^{2}}}={\tfrac {4}{1225}}\approx 0.0033}$
${\displaystyle 3}$	${\displaystyle {\tfrac {16}{1225}}\,x^{3}+{\tfrac {4}{105}}\,x^{2}+{\tfrac {128}{1225}}\,x+{\tfrac {34}{105}}}$	${\displaystyle 1\quad \;{\tfrac {3}{4}}\quad \;{\tfrac {1}{12}}\quad -\!{\tfrac {2}{3}}\quad -\!1}$	${\displaystyle {\tfrac {(r-s)^{3}}{s^{2}}}={\tfrac {2}{3675}}\approx 0.0005}$

Algorithms

An approximation is called a minimax approximation if it

${\displaystyle \max _{a\leq x\leq b}|f(x)-p(x)|}$

minimized. There are some minimax approximation algorithms, the most common being the Remez algorithm .

literature

• Robert Mayans: The Chebyshev Equioscillation Theorem (Chebyshev's alternant theorem)

Notes and individual references

1. ↑ Leçons sur l'approximation des fonctions d'une variable réelle . Gauthier-Villars, Paris 1919, 1952, p. 75, archive.org
2. ↑ The continuity on the compact set the following limitations .
3. ↑ René Grothmann: Lecture Notes Approximation Theory 1.38 Theorem (with proof) (PDF)
4. ↑ The alternant theorem also applies to much more general spaces, e.g. for trigonometric polynomials (see also Proximum # alternant criterion in Chebyshev systems ).