Best approximation

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 $.

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)

Comments

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

References

[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, "-widths in approximation theory" , Springer (1985) (Translated from Russian)