Namespaces
Variants
Actions

Difference between revisions of "Best approximation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (→‎References: latexify)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
''of a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b0158901.png" /> by functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b0158902.png" /> from a fixed set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b0158903.png" />''
+
<!--
 +
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
 
The quantity
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b0158904.png" /></td> </tr></table>
+
$$
 +
E (x, F)  = \inf _ {u \in F }  \mu (x, u),
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b0158905.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b0158906.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b0158907.png" /> is defined by the distance between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b0158908.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b0158909.png" />; in this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589010.png" /> is the distance from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589011.png" /> to the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589012.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589013.png" /> is a normed linear space, then for a fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589014.png" /> the best approximation
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589015.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
E (x, F)  = \
 +
\inf _ {u \in F }  \| x - u \|
 +
$$
  
may be regarded as a functional defined on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589016.png" /> (the functional of best approximation).
+
may be regarded as a functional defined on $  X $(
 +
the functional of best approximation).
  
The functional of best approximation is continuous, whatever the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589017.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589018.png" /> is a subspace, the functional of best approximation is a semi-norm, i.e.
+
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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589019.png" /></td> </tr></table>
+
$$
 +
E (x _ {1} + x _ {2} , F)  \leq  E (x _ {1} , F) + E (x _ {2} , F)
 +
$$
  
 
and
 
and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589020.png" /></td> </tr></table>
+
$$
 +
E ( \lambda x, F)  = | \lambda | E (x, F)
 +
$$
  
for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589021.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589022.png" /> is a finite-dimensional subspace, then for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589023.png" /> there exists an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589024.png" /> (an element of best approximation) at which the infimum in (1) is attained:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589025.png" /></td> </tr></table>
+
$$
 +
E (x, F)  = \| x - u _ {0} \| .
 +
$$
  
In a space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589026.png" /> with a strictly convex norm, the element of best approximation is unique.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589027.png" /> can be expressed in terms of the supremum of the values of certain functionals from the adjoint space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589028.png" /> (see, e.g. [[#References|[5]]], [[#References|[8]]]). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589029.png" /> is a closed convex subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589030.png" />, then for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589031.png" />
+
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 $
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589032.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589033.png" /> is a subspace, then
+
in particular, if $  F $
 +
is a subspace, then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589034.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{3 }
 +
E (x, F)  = \
 +
\sup _ {\begin{array}{c}
 +
f \in F  ^  \perp  \\
 +
\| f \| \leq  1
 +
\end{array}
 +
} \
 +
f (x),
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589035.png" /> is the set of functionals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589036.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589037.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589038.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589039.png" />. In the function spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589040.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589041.png" />, the right-hand sides of (2) and (3) take explicit forms depending on the form of the linear functional. In a Hilbert space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589042.png" />, the best approximation of an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589043.png" /> by an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589044.png" />-dimensional subspace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589045.png" /> is obtained by orthogonal projection on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589046.png" /> and can be calculated; one has:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589047.png" /></td> </tr></table>
+
$$
 +
E (x, F _ {n} )  = \
 +
\sqrt {
 +
\frac{G (x, u _ {1} \dots u _ {n} ) }{G (u _ {1} \dots u _ {n} ) }
 +
} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589048.png" /> form a basis of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589049.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589050.png" /> is the Gram determinant, the elements of which are the scalar products <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589052.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589053.png" /> is an orthonormal basis, then
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589054.png" /></td> </tr></table>
+
$$
 +
E  ^ {2} (x, F _ {n} )  = \
 +
\| x \|  ^ {2} - \sum _ {k = 1 } ^ { n }  (x, u _ {k} )  ^ {2} .
 +
$$
  
In the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589055.png" /> one has the following estimate for the best uniform approximation of a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589056.png" /> by an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589057.png" />-dimensional Chebyshev subspace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589058.png" /> (the de la Vallée-Poussin theorem): If for some function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589059.png" /> there exist <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589060.png" /> points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589062.png" />, for which the difference
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589063.png" /></td> </tr></table>
+
$$
 +
\Delta (t)  = x (t) - u (t)
 +
$$
  
 
takes values with alternating signs, then
 
takes values with alternating signs, then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589064.png" /></td> </tr></table>
+
$$
 
+
E (x, F _ {n} ) \geq  \
For best approximations in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589065.png" /> 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.
+
\mathop{\rm min} _ {1 \leq  k \leq  n + 1 }  | \Delta (t _ {k} ) | .
 
+
$$
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589066.png" /> (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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589067.png" /> in the given class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589068.png" /> by a fixed set of functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589069.png" />, i.e. the quantity
+
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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589070.png" /></td> </tr></table>
+
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 number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589071.png" /> characterizes the maximum deviation (in the specific metric chosen) of the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589072.png" /> from the approximating set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589073.png" /> and indicates the minimal possible error to be expected when approximating an arbitrary function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589074.png" /> by functions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589075.png" />.
+
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
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589076.png" /> be a subset of a normed linear function space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589077.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589078.png" /> be a linearly independent system of functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589079.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589080.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589081.png" /> be the subspaces generated by the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589082.png" /> elements of this system. By investigating the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589083.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589084.png" /> one can draw conclusions regarding both the structural and smoothness properties of the functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589085.png" /> and the approximation properties of the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589086.png" /> relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589087.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589088.png" /> is a Banach function space and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589089.png" /> is closed in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589090.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589091.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589092.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589093.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589094.png" /> is a compact subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589095.png" />.
+
$$
 +
E ( \mathfrak M , F)  = \
 +
\sup _ {f \in \mathfrak M }  E (f, F)  = \
 +
\sup _ {f \in \mathfrak M }  \inf _ {\phi \in F } \
 +
\mu (f, \phi ).
 +
$$
  
In various important cases, e.g. when the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589096.png" /> are subspaces of trigonometric polynomials or periodic splines, and the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589097.png" /> is defined by conditions imposed on the norm or on the modulus of continuity of some derivative <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589098.png" />, the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b01589099.png" /> can be calculated explicitly [[#References|[5]]]. In the non-periodic case, results are available concerning the asymptotic behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b015890100.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015890/b015890101.png" />.
+
The number $ E ( \mathfrak M , F) $
 
+
characterizes the maximum deviation (in the specific metric chosen) of the class $ \mathfrak M $
====References====
+
from the approximating set $ F $
<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>
+
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 $.
  
 
====Comments====
 
====Comments====
Line 72: Line 208:
  
 
====References====
 
====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>
+
<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>
 +
<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, "$n$-widths in approximation theory" , Springer  (1985)  (Translated from Russian)</TD></TR></table>

Latest revision as of 07:58, 26 March 2023


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). 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. [5], [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. 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).

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 [5]. In the non-periodic case, results are available concerning the asymptotic behaviour of $ E ( \mathfrak M , F _ {n} ) $ as $ n \rightarrow \infty $.

Comments

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

References

[1] P.L. Chebyshev, "Complete collected works" , 2 , Moscow (1947) (In Russian)
[2] N.I. [N.I. Akhiezer] Achiezer, "Theory of approximation" , F. Ungar (1956) (Translated from Russian)
[3] V.K. Dzyadyk, "Introduction to the theory of uniform approximation of functions by polynomials" , Moscow (1977) (In Russian)
[4] V.L. Goncharov, "The theory of interpolation and approximation of functions" , Moscow (1954) (In Russian)
[5] N.P. Korneichuk, "Extremal problems in approximation theory" , Moscow (1976) (In Russian)
[6] S.M. Nikol'skii, "Approximation of functions of several variables and imbedding theorems" , Springer (1975) (Translated from Russian)
[7] A.F. Timan, "Theory of approximation of functions of a real variable" , Pergamon (1963) (Translated from Russian)
[8] V.M. Tikhomirov, "Some problems in approximation theory" , Moscow (1976) (In Russian)
[9] P.J. Laurent, "Approximation et optimisation" , Hermann (1972)
[a1] G.G. Lorentz, "Approximation of functions" , Holt, Rinehart & Winston (1966)
[a2] E.W. Cheney, "Introduction to approximation theory" , Chelsea, reprint (1982) pp. 203ff
[a3] J.R. Rice, "The approximation of functions" , 1. Linear theory , Addison-Wesley (1964)
[a4] A. Pinkus, "$n$-widths in approximation theory" , Springer (1985) (Translated from Russian)
How to Cite This Entry:
Best approximation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Best_approximation&oldid=16361
This article was adapted from an original article by N.P. KorneichukV.P. Motornyi (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article