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
where
is the best approximation of a function
by
,
as well as on determining the quantity
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
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
in particular, if
is a subspace,
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
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]).