Best approximation
of a function
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) |
Best approximation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Best_approximation&oldid=53296