Approximation of functions, extremal problems in function classes

Problems connected with the search for upper bounds of approximation errors with respect to a fixed class of functions and with the choice of an approximation tool that is best in some sense or other. The foundations of the research concerning this kind of problems were laid by A.N. Kolmogorov ([1], [2]), J. Favard ([3], ) and S.M. Nikol'skii ([5], [6]). These researches were greatly extended in the 1950s. They stimulated the requirements of numerical mathematics, penetrating ever deeper into problems of an optimization character.

If in a normed function space one considers the approximation of functions from a class by functions from a fixed set , then problems on determining the quantity

(1)

where

is the best approximation of a function by , as well as on determining the quantity

(2)

where is a specific approximation method, given by some operator acting from into , are of interest. Geometrically, the supremum in (1) characterizes the deviation of the set from in the metric of . In practice, can be looked upon, first, as the minimal-possible bound from above for the best approximation of by functions that are only known to belong to , and secondly, it gives a tool for measuring and comparing the approximative properties of concrete approximation methods on . In (2), the most important case is when is an -dimensional space and is a linear approximation method. A whole series of exact and asymptotically-exact results is known for the approximation of function classes by concrete linear methods (in particular, by polynomial or spline methods), see [1]–[12], . However, special interest attaches to methods attaining the infimum

(3)

over all linear bounded operators from into , i.e. to all linear methods that are optimal for . Obviously,

and there naturally arises the question on whether the equality sign can be attained. Apart from the trivial case when is a Hilbert function space and the best approximation of a function is given by its Fourier sums with respect to an orthogonal basis of , some results when linear methods realize the best approximation on the entire class are also known for non-Hilbert spaces.

Thus, if is the space () of -periodic functions, is the subspace of trigonometric polynomials of order (), and if , is the class of functions for which is absolutely continuous on and for which , then

where is the Favard constant. The best approximation on and is obtained, moreover, by a linear method , constructed on the basis of Fourier sums (cf. Approximation of functions, linear methods, formula (3)) for a specific choice of the multiplication coefficients . Linear operators, with values in , yielding the supremum of the best approximation on convolution classes, including, in particular, and with a rational number , as well as on classes of conjugate functions, have been established (cf. [10], [11]).

For approximation by the subspace of -periodic splines of order and defect 1 with knots (nodes, joints) at (), the equalities

are valid. The splines in interpolating a function at if is even, and at if is odd, provide the best linear methods in this case. Relative to these splines have exceptional approximative properties, since they give the best approximation of an in any (cf. [7], [15]).

When (1) and (3) coincide and when it is possible to construct a concrete linear method solving both problems, the cases considered are, in a well-known sense, optimal. In other cases it proved expedient in solving (1) to adopt an approach based on general duality theorems, reflecting fundamental relations in geometric convex analysis (see [7], [8]). If, e.g. is an arbitrary linear normed space, is its dual and is a convex set in , then for any

(4)

in particular, if is a subspace,

(5)

In a number of cases (4), or (5), allows one to reduce the calculation of the supremum (1) to the more transparent problem of determining the extremum of an explicitly defined functional on some set of functions, which, if is a subspace, is related to orthogonality conditions. For example, by (5) the estimation of , , can be reduced, using known inequalities, to the calculation of the supremum of the norms , , on the set of functions , , for which

More refined situations occur when (1) has to be solved on classes not given by restrictions on the norm of the -th derivative , but on its modulus of continuity . Particularly interesting is the case where (; ) is the class of -periodic functions () for which

where is a given modulus of continuity, e.g. (, ). Here the application of (5) requires the use of fine results on differentiable periodic functions of the type of the comparison theorem and the Kolmogorov inequality (for the norm of derivatives), here described using the tool of rearrangements (of equi-measurable functions). If is convex from above, the following equalities ([7], [15]) are valid:

Here or , the are functions in of period , with zero average over a period, for which is even, equal to on , and equal to on . The norms have an explicit expression, e.g.

where the functions on are given recurrently by

The best linear method from into , or into , for the class is known for , , i.e. when . The interpolation splines in yield the supremum (for any convex ) only if .

For solutions to extremal problems for function classes on a finite interval and not restricted by rigid boundary conditions, it is not possible to give such complete results as in the periodic case; the extremal end points of the interval have a perturbing influence on the extremal functions, which require an increase in the order of differentiability. Here, some exact asymptotic results are known. If , , , is the class of functions for which

then for the best uniform approximation on by the subspace of algebraic polynomials of degree , the relations

(6)

(7)

hold. It is useful to compare these results with the corresponding ones in the periodic case. For , the right-hand sides of (6), (7) are equal, respectively, to and . Dropping the requirement of a polynomial of best approximation, one obtains stronger results, essentially improving the approximation at the end points of without losing the best asymptotics on the whole interval. E.g., for any there is a sequence of algebraic polynomials such that uniformly in , as , one has

Analogous results hold for see [11]. In spline-approximation problems (both of best and of interpolation type) certain exact and asymptotically-exact results are known for function classes on intervals (cf. [15]).

In the case of one-sided approximation (in an integral metric) a series of exact results concerning the estimation of the error of best approximation by polynomials and splines regarding the above-mentioned function classes is known (cf. [14]). In deriving them, essential use is made of duality relations for the best approximation under restrictions given by cones.

The search for a best approximation tool (of fixed dimension), leads, for a fixed function class , to the problem of widths: Determine (cf. (1), (3)):

where the infima are taken over all subspaces of (as well as over their translations) of dimension , and also to determine extremal (best) subspaces yielding these infima. An upper bound for and is given by and , which have been established for concrete subspaces . The fundamental difficulty in the problem of widths, here, is to obtain exact lower bounds. In a number of cases it is possible to obtain such bounds by appealing to topological considerations, in particular, Borsuk's antipodal theorem (cf. [8]). In practically all cases of exactly solving best approximation problems in the classes and of periodic functions by the subspaces (trigonometric polynomials of order ) or (splines of order and defect 1 with respect to the partition of knots ), the known exact upper bounds give also the values of for these classes. Moreover, for periodic classes . In particular (cf. [7], [8], [15], )

and for an upper convex and for or one has

It should be observed that is extremal for the classes considered, for all , and that no subspace of dimension gives a better approximation for these classes than (which is of dimension ). The subspace of splines is extremal for and in if and for in if . The linear widths of in and in coincide with , they are attained on and by the best linear methods that were referred to above. The widths and of in for and are equal and are obtained by Fourier trigonometric sums. Exact asymptotic results for widths of function classes on an interval are known in a number of cases: The widths and of in coincide and are obtained for interpolation splines of order with respect to non-uniform partitions (cf. [8]).

The problem of estimating the approximation error on the set of -fold integrals of functions from (which is not locally compact) can be stated properly if for and fixed one estimates

( is the modulus of continuity of in ) or (in the case of a concrete approximation method) if one estimates

Determining the suprema of these quantities on is equivalent to the search for the least constant in the corresponding Jackson inequality; subsequently one may deal with the minimization over all subspaces of dimension . In a number of cases, these problems have been solved. E.g. in the inequality

the least constant is , and it cannot be improved if is replaced by any other subspace of the same dimension (cf. [15]). Exact constants in the Jackson inequalities for trigonometric approximation in the uniform and in an integral metric are known (cf. [7]). In the non-periodic case there are asymptotic results available.

Among approximation problems in which the approximating set is not a linear manifold but a convex set, the problem of approximating one function class by another with best, in some sense or other, smoothness properties, is of interest. Such a problem arose initially at an intermediate stage in obtaining exact bounds for

(cf. [7]); later it became to be considered as an independent problem, and in a number of cases it was possible, using (4), to obtain exact results.

For

relations have been obtained between inequalities for norms of derivatives and best approximations of a differentiation operator by linear bounded operators (cf. [13]).

Many extremal problems in the approximation of functions may be interpreted as problems of optimal recovery (cf. [15]). Let the information on a function be given by a vector , where are given functionals on (e.g. values of and/or some derivatives in fixed points). Given that belongs to a class , it is required to reconstruct or some linear functional of it (e.g. , , etc.) on the basis of with least possible error. The minimization need not only take into account methods juxtaposing with a function (or a functional ), but also involves the choice of functionals , . Depending on the choice of the error measure and the class of methods , the problem of optimal recovery of a function may sometimes be reduced to determining the widths , the Chebyshev centre, or other characteristics of . The problem of optimal recovery of on the basis of information of the form or leads to the problem of best quadrature formulas for . The best tool of recovering is achieved, in a number of cases, by splines; e.g. the splines in that interpolate at equally-distant points reconstruct an on the basis of information in each point with minimum error on the whole class .

In spaces of functions of two or more variables, excluding the trivial case of approximation in Hilbert spaces, exact solutions of extremal problems have not yet been obtained (1983). In a few cases an asymptotic relation for the error of uniform approximation in function classes by Fourier sums or some average Fourier sums is known (cf. [12]).

References

[1]	A.N. Kolmogorov, Ann. of Math. , 36 : 2 (1935) pp. 521–526
[2]	A.N. [A.N. Kolmogorov] Kolmogoroff, "Ueber die beste Annäherung von Funktionen einer gegebenen Funktionenklasse" Ann. of Math. , 37 : 1 (1936) pp. 107–110
[3]	J. Favard, C.R. Acad. Sci. , 203 (1936) pp. 1122–1124
[4a]	J. Favard, "Sur les meilleurs procédés d'approximation de certaines classes de fonctions par des polynômes trigonométriques" Bull. Sci. Math. , 61 (1937) pp. 209–224
[4b]	J. Favard, "Sur les meilleurs procédés d'approximation de certaines classes de fonctions par des polynômes trigonométriques" Bull. Sci. Math. , 61 (1937) pp. 243–256
[5]	S.M. Nikol'skii, "Approximations of periodic functions by trigonometric polynomials" Trudy Mat. Inst. Steklov. , 15 (1945) pp. 1–76 (In Russian) (English abstract)
[6]	S.M. Nikol'skii, "Mean approximation of functions by trigonometric polynomials" Izv. Akad. Nauk SSSR Ser. Mat. , 10 (1946) pp. 207–256 (In Russian)
[7]	N.P. Korneichuk, "Extremal problems in approximation theory" , Moscow (1976) (In Russian)
[8]	V.M. Tikhomirov, "Some problems in approximation theory" , Moscow (1976) (In Russian)
[9]	V.K. Dzyadyk, "Introduction to the theory of uniform approximation of functions by polynomials" , Moscow (1977) (In Russian)
[10]	N.I. [N.I. Akhiezer] Achiezer, "Theory of approximation" , F. Ungar (1956) (Translated from Russian)
[11]	A.F. Timan, "Theory of approximation of functions of a real variable" , Pergamon (1963) (Translated from Russian)
[12]	A.I. Stepanets, "Uniform approximation by trigonometric polynomials. Linear methods" , Kiev (1984) (In Russian)
[13]	V.V. Arestov, "Some extremal problems for differentiable functions of one variable" Trudy Mat. Inst. Steklov. , 138 (1975) pp. 3–28 (In Russian)
[14]	N.P. Korneichuk, A.A. Ligun, V.G. Doronin, "Approximation with constraints" , Kiev (1982) (In Russian)
[15]	N.P. Korneichuk, "Splines in approximation theory" , Moscow (1984) (In Russian)

Comments

The recent book by A. Pinkus [a1] contains a comprehensive and valuable bibliography.

References

[a1]	A. Pinkus, "-widths in approximation theory" , Springer (1985) (Translated from Russian)
[a2]	C.A. Michelli, T.J. Rivlin, "A survey of optimal recovery" C.A. Michelli (ed.) T.J. Rivlin (ed.) , Optimal estimation in approximation theory , Plenum (1977) pp. 1–54