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

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)