View source for Best approximation

<!--
b0158901.png
$#A+1 = 101 n = 1
$#C+1 = 101 : ~/encyclopedia/old_files/data/B015/B.0105890 Best approximation
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

''of a function  $  x (t) $
by functions  $  u (t) $
from a fixed set  $  F $''

The quantity

$$ 
E (x, F)  =  \inf _ {u \in F }  \mu (x, u),
$$

where  $  \mu (x, u) $
is the error of approximation (see [[Approximation of functions, measure of|Approximation of functions, measure of]]). The concept of a best approximation is meaningful in an arbitrary metric space  $  X $
when  $  \mu (x, u) $
is defined by the distance between  $  x $
and  $  u $; 
in this case  $  E (x, F) $
is the distance from  $  x $
to the set  $  F $. 
If  $  X $
is a normed linear space, then for a fixed  $  F \subset  X $
the best approximation

$$ \tag{1 }
E (x, F)  = \ 
\inf _ {u \in F }  \| x - u \|
$$

may be regarded as a functional defined on  $  X $(
the functional of best approximation).

The functional of best approximation is continuous, whatever the set  $  F $. 
If  $  F $
is a subspace, the functional of best approximation is a semi-norm, i.e.

$$ 
E (x _ {1} + x _ {2} , F)  \leq   E (x _ {1} , F) + E (x _ {2} , F)
$$

and

$$ 
E ( \lambda x, F)  =  | \lambda | E (x, F)
$$

for any  $  \lambda \in \mathbf R $. 
If  $  F $
is a finite-dimensional subspace, then for any  $  x \in X $
there exists an element  $  u _ {0} \in F $(
an element of best approximation) at which the infimum in (1) is attained:

$$ 
E (x, F)  =  \| x - u _ {0} \| .
$$

In a space  $  X $
with a strictly convex norm, the element of best approximation is unique.

Through the use of duality theorems, the best approximation in a normed linear space  $  X $
can be expressed in terms of the supremum of the values of certain functionals from the adjoint space  $  X  ^ {*} $(
see, e.g. [[#References|[5]]], [[#References|[8]]]). If  $  F $
is a closed convex subset of  $  X $, 
then for any  $  x \in X $

$$ \tag{2 }
E (x, F)  = \ 
\sup _ {\begin{array}{c}
f \in X  ^ {*} \\
 \| f \| \leq  1 
\end{array}
 } \ 
\left [ f (x) - \sup _ {u \in F }  f (u) \right ] ;
$$

in particular, if  $  F $
is a subspace, then

$$ \tag{3 }
E (x, F)  = \ 
\sup _ {\begin{array}{c}
f \in F  ^  \perp  \\
 \| f \| \leq  1 
\end{array}
 } \ 
f (x),
$$

where  $  F  ^  \perp  $
is the set of functionals  $  f $
in  $  X  ^ {*} $
such that  $  f (u) = 0 $
for any  $  u \in F $. 
In the function spaces  $  C $
or  $  L _ {p} $, 
the right-hand sides of (2) and (3) take explicit forms depending on the form of the linear functional. In a Hilbert space  $  H $, 
the best approximation of an element  $  x \in H $
by an  $  n $-
dimensional subspace  $  F _ {n} $
is obtained by orthogonal projection on  $  F _ {n} $
and can be calculated; one has:

$$ 
E (x, F _ {n} )  = \ 
\sqrt {
\frac{G (x, u _ {1} \dots u _ {n} ) }{G (u _ {1} \dots u _ {n} ) }
 } ,
$$

where  $  u _ {1} \dots u _ {n} $
form a basis of  $  F _ {n} $
and  $  G (u _ {1} \dots u _ {n} ) $
is the Gram determinant, the elements of which are the scalar products  $  (u _ {i} , u _ {j} ) $, 
$  i, j = 1 \dots n $. 
If  $  \{ u _ {k} \} $
is an orthonormal basis, then

$$ 
E  ^ {2} (x, F _ {n} )  = \ 
\| x \|  ^ {2} - \sum _ {k = 1 } ^ { n }  (x, u _ {k} )  ^ {2} .
$$

In the space  $  C = C [a, b] $
one has the following estimate for the best uniform approximation of a function  $  x (t) \in C $
by an  $  n $-
dimensional Chebyshev subspace  $  F _ {n} \subset  C $(
the de la Vallée-Poussin theorem): If for some function  $  u (t) \in F _ {n} $
there exist  $  n + 1 $
points  $  t _ {k} $, 
$  a \leq  t _ {1} < {} \dots < t _ {n + 1 }  \leq  b $, 
for which the difference

$$ 
\Delta (t)  =  x (t) - u (t)
$$

takes values with alternating signs, then

$$ 
E (x, F _ {n} )  \geq  \ 
 \mathop{\rm min} _ {1 \leq  k \leq  n + 1 }  | \Delta (t _ {k} ) | .
$$

For best approximations in  $  L _ {1} (a, b) $
see [[Markov criterion|Markov criterion]]. In several important cases, the best approximations of functions by finite-dimensional subspaces can be bounded from above in terms of differential-difference characteristics (e.g. the modulus of continuity) of the approximated function or its derivatives.

The concept of a best uniform approximation of continuous functions by polynomials is due to P.L. Chebyshev (1854), who developed the theoretical foundations of the concept and established a criterion for polynomials of best approximation in the metric space  $  C $(
see [[Polynomial of best approximation|Polynomial of best approximation]]).

The best approximation of a class of functions is the supremum of the best approximations of the functions  $  f $
in the given class  $  \mathfrak M $
by a fixed set of functions  $  F $, 
i.e. the quantity

$$ 
E ( \mathfrak M , F)  = \ 
\sup _ {f \in \mathfrak M }  E (f, F)  = \ 
\sup _ {f \in \mathfrak M }  \inf _ {\phi \in F } \ 
\mu (f, \phi ).
$$

The number  $  E ( \mathfrak M , F) $
characterizes the maximum deviation (in the specific metric chosen) of the class  $  \mathfrak M $
from the approximating set  $  F $
and indicates the minimal possible error to be expected when approximating an arbitrary function  $  f \in \mathfrak M $
by functions of  $  F $.

Let  $  \mathfrak M $
be a subset of a normed linear function space  $  X $, 
let  $  U = \{ u _ {1} (t), u _ {2} (t) ,\dots \} $
be a linearly independent system of functions in  $  X $
and let  $  F _ {n} $, 
$  n = 1, 2 \dots $
be the subspaces generated by the first  $  n $
elements of this system. By investigating the sequence  $  E ( \mathfrak M , F _ {n} ) $, 
$  n = 1, 2 \dots $
one can draw conclusions regarding both the structural and smoothness properties of the functions in  $  \mathfrak M $
and the approximation properties of the system  $  U $
relative to  $  \mathfrak M $. 
If  $  X $
is a Banach function space and  $  U $
is closed in  $  X $, 
i.e.  $  \overline{ {\cup F _ {n} }}\; = X $, 
then  $  E ( \mathfrak M , F _ {n} ) \rightarrow 0 $
as  $  n \rightarrow \infty $
if and only if  $  \mathfrak M $
is a compact subset of  $  X $.

In various important cases, e.g. when the  $  F _ {n} $
are subspaces of trigonometric polynomials or periodic splines, and the class  $  \mathfrak M $
is defined by conditions imposed on the norm or on the modulus of continuity of some derivative  $  f  ^ {(r)} $, 
the numbers  $  E ( \mathfrak M , F _ {n} ) $
can be calculated explicitly [[#References|[5]]]. In the non-periodic case, results are available concerning the asymptotic behaviour of  $  E ( \mathfrak M , F _ {n} ) $
as  $  n \rightarrow \infty $.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  P.L. Chebyshev,   "Complete collected works" , '''2''' , Moscow  (1947)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N.I. [N.I. Akhiezer] Achiezer,   "Theory of approximation" , F. Ungar  (1956)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.K. Dzyadyk,   "Introduction to the theory of uniform approximation of functions by polynomials" , Moscow  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  V.L. Goncharov,   "The theory of interpolation and approximation of functions" , Moscow  (1954)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  N.P. Korneichuk,   "Extremal problems in approximation theory" , Moscow  (1976)  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  S.M. Nikol'skii,   "Approximation of functions of several variables and imbedding theorems" , Springer  (1975)  (Translated from Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  A.F. Timan,   "Theory of approximation of functions of a real variable" , Pergamon  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  V.M. Tikhomirov,   "Some problems in approximation theory" , Moscow  (1976)  (In Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  P.J. Laurent,   "Approximation et optimisation" , Hermann  (1972)</TD></TR></table>

====Comments====
In Western literature an element, a functional or a polynomial of best approximation is also called a best approximation.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.G. Lorentz,   "Approximation of functions" , Holt, Rinehart &amp; Winston  (1966)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E.W. Cheney,   "Introduction to approximation theory" , Chelsea, reprint  (1982)  pp. 203ff</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.R. Rice,   "The approximation of functions" , '''1. Linear theory''' , Addison-Wesley  (1964)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A. Pinkus,   "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b015890102.png" />-widths in approximation theory" , Springer  (1985)  (Translated from Russian)</TD></TR></table>