Namespaces
Variants
Actions

Best approximation

From Encyclopedia of Mathematics
Jump to: navigation, search


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