Chebyshev alternance

Chebyshev alterna- tion (or simply an alterna- tion ) - in mathematics such a set of points $x_{1}<x_{2}<...<x_{N}$ ${\ displaystyle x_ {1} <x_ {2} <... <x_ {N}}$ $x_ {1} <x_ {2} <... <x_ {N}$ in which a continuous function of one variable $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ consistently takes its maximum modulo value, with the signs of the function at these points $g(x_{1}),$ ${\ displaystyle g (x_ {1}),}$ $g (x_ {1}),$ $g(x_{2}),...,$ ${\ displaystyle g (x_ {2}), ...,}$ $g (x_ {2}), ...,$ $g(x_{N})$ ${\ displaystyle g (x_ {N})}$ $g (x_ {N})$ - alternate.

Such a construction was first encountered in the theorem on the characterization of the best approximation polynomial discovered by P. L. Chebyshev in the 19th century. The term alternation itself was introduced by I.P. Natanson in the 1950s.

Content

Chebyshev theorem on alternance

To polynomial $Q_{n}(x)$ ${\ displaystyle Q_ {n} (x)}$ degrees $n$ ${\ displaystyle n}$ was a polynomial of the best uniform approximation of a continuous function $f(x)$ ${\ displaystyle f (x)}$ , it is necessary and sufficient existence on $[a,b]$ ${\ displaystyle [a, b]}$ at least $n+2$ ${\ displaystyle n + 2}$ points $x_{0}<...<x_{n+1}$ ${\ displaystyle x_ {0} <... <x_ {n + 1}}$ such that

 $f(x_{i})-Q_{n}(x_{i})=\alpha (-1)^{i}||f-Q_{n}||$           $f$       $($         $x$         $i$           $)$       $-$         $Q$         $n$           $($         $x$         $i$           $)$       $=$       $α$       $($       $-$       $one$         $)$         $i$             $|$           $|$         $f$       $-$         $Q$         $n$             $|$           $|$             ${\ displaystyle f (x_ {i}) - Q_ {n} (x_ {i}) = \ alpha (-1) ^ {i} || f-Q_ {n} ||}$       ,

Where

i=0,...,n+1,\alpha =\pm 1

{\ displaystyle i = 0, ..., n + 1, \ alpha = \ pm 1}

at the same time for all

i

{\ displaystyle i}

.

Points $x_{0}<...<x_{n+1}$ ${\ displaystyle x_ {0} <... <x_ {n + 1}}$ that satisfy the conditions of the theorem are called Chebyshev alternance points.

Example of function approximation

Suppose that it is necessary to approximate the square root function using a linear function (a polynomial of first degree) on the interval (1, 64). From the condition of the theorem, we need to find $n+2$ ${\ displaystyle n + 2}$ (in this case - 3) points of the Chebyshev alternance. Therefore, due to the convexity of the difference between the square root and the linear function, these points are the only extremum point of this difference and the ends of the interval on which the function is approximated. Denote $a=1,b=64$ ${\ displaystyle a = 1, b = 64}$ . $d$ ${\ displaystyle d}$ - point of extremum. Then the following equations hold:

${\sqrt {1}}-(\alpha _{0}+\alpha _{1}\times 1)=\alpha L$ ${\ displaystyle {\ sqrt {1}} - (\ alpha _ {0} + \ alpha _ {1} \ times 1) = \ alpha L}$

${\sqrt {d}}-(\alpha _{0}+\alpha _{1}\times d)=-\alpha L$ ${\ displaystyle {\ sqrt {d}} - (\ alpha _ {0} + \ alpha _ {1} \ times d) = - \ alpha L}$

${\sqrt {64}}-(\alpha _{0}+\alpha _{1}\times 64)=\alpha L$ ${\ displaystyle {\ sqrt {64}} - (\ alpha _ {0} + \ alpha _ {1} \ times 64) = \ alpha L}$

Here $\alpha L$ ${\ displaystyle \ alpha L}$ - the difference between the values of the function and the polynomial. By subtracting the first equation from the third, one can get that

$\alpha _{1}={\frac {1}{9}}$ ${\ displaystyle \ alpha _ {1} = {\ frac {1} {9}}}$

Because $d$ ${\ displaystyle d}$ - the extremum point, and the linear function and the square root function are continuous and differentiable, determine the value $d$ ${\ displaystyle d}$ can be from the following equation:

$({\sqrt {x}})'(d)-\alpha _{1}=0$ ${\ displaystyle ({\ sqrt {x}}) '(d) - \ alpha _ {1} = 0}$

From here $d=20{\frac {1}{4}}$ ${\ displaystyle d = 20 {\ frac {1} {4}}}$

Now you can calculate $\alpha _{0}$ ${\ displaystyle \ alpha _ {0}}$

$\alpha _{0}={\frac {113}{72}}$ ${\ displaystyle \ alpha _ {0} = {\ frac {113} {72}}}$

Therefore, the best linear approximation of the function ${\sqrt {x}}$ ${\ displaystyle {\ sqrt {x}}}$ in the range from 1 to 64:

${\frac {1}{9}}x+{\frac {113}{72}}$ ${\ displaystyle {\ frac {1} {9}} x + {\ frac {113} {72}}}$ .

Literature

Bakhvalov, N.S .; Zhidkov, N. P .; Kobelkov, G. N. Numerical methods
Ulyanov, M. V. Resource-efficient computer algorithms.

Links

Lectures A. M. Matzokina