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 $X$ one considers the approximation of functions from a class $\mathfrak{M}$ by functions from a fixed set $\mathfrak{N}\subset X$, then problems on determining the quantity

$$\begin{array}{}\text{(1)}& E(\mathfrak{M},\mathfrak{N}{)}_X=\underset{f\in \mathfrak{M}}{sup}E(f,\mathfrak{N}{)}_X,\end{array}$$

where

$$E(f,\mathfrak{N}{)}_X=\underset{\varphi \in \mathfrak{N}}{inf}\Vert f-\varphi {\Vert }_X$$

is the best approximation of a function $f(t)$ by $\mathfrak{N}$, as well as on determining the quantity

$$\begin{array}{}\text{(2)}& \mathcal{E}(\mathfrak{M},\mathfrak{N},U{)}_X=\underset{f\in \mathfrak{M}}{sup}\Vert f-Uf{\Vert }_X,\end{array}$$

where $U$ is a specific approximation method, given by some operator acting from $X$ into $\mathfrak{N}$, are of interest. Geometrically, the supremum in (1) characterizes the deviation of the set $\mathfrak{M}$ from $\mathfrak{N}$ in the metric of $X$. In practice, $E(\mathfrak{M},\mathfrak{N}{)}_X$ can be looked upon, first, as the minimal-possible bound from above for the best approximation of $\mathfrak{N}$ by functions that are only known to belong to $\mathfrak{M}$, and secondly, it gives a tool for measuring and comparing the approximative properties of concrete approximation methods on $\mathfrak{M}$. In (2), the most important case is when $\mathfrak{N}={\mathfrak{N}}_N$ is an $N$- dimensional space and $U$ 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

$$\begin{array}{}\text{(3)}& \mathcal{E}(\mathfrak{M},{\mathfrak{N}}_N{)}_X=\underset{UX\subset {\mathfrak{N}}_N}{inf}\mathcal{E}(\mathfrak{M},{\mathfrak{N}}_N,U{)}_X,\end{array}$$

over all linear bounded operators $U$ from $X$ into ${\mathfrak{N}}_X$, i.e. to all linear methods that are optimal for $\mathfrak{M}$. Obviously,

$$E(\mathfrak{M},{\mathfrak{N}}_N{)}_X\le \mathcal{E}(\mathfrak{M},{\mathfrak{N}}_N{)}_X,$$

and there naturally arises the question on whether the equality sign can be attained. Apart from the trivial case when $X$ 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 ${\mathfrak{N}}_X$, some results when linear methods realize the best approximation on the entire class $\mathfrak{M}$ are also known for non-Hilbert spaces.

Thus, if $X$ is the space $\tilde{L}={\tilde{L}}_p[0,2\pi ]$( $1\le p\le \mathrm{\infty }$) of $2\pi$- periodic functions, ${\mathfrak{N}}_{2n-1}^T$ is the subspace of trigonometric polynomials of order $n-1$( $\dim {\mathfrak{N}}_{2n-1}^T=2n-1$), and if $M\tilde{W}{}_p^r$, $r=1,2\dots$ is the class of functions $f\in {\tilde{L}}_p$ for which $f^{(r-1)}(t)$ is absolutely continuous on $[0,2\pi ]$ and for which $\Vert f^{(r)}{\Vert }_{{\tilde{L}}_p}\le M$, then

$$E(M\tilde{W}{}_p^r,{\mathfrak{N}}_{2n-1}^T{)}_{{\tilde{L}}_p}=\mathcal{E}(M\tilde{W}{}_p^r,{\mathfrak{N}}_{2n-1}^T{)}_{{\tilde{L}}_p}=M{K}_r{n}^{-r},$$

$$p=1,\mathrm{\infty };n,r=1,2\dots$$

where $K_r$ is the Favard constant. The best approximation on $M\tilde{W}{}_1^r$ and $M\tilde{W}{}_{\mathrm{\infty }}^r$ is obtained, moreover, by a linear method $U_{n-1}^{\lambda }$, constructed on the basis of Fourier sums (cf. Approximation of functions, linear methods, formula (3)) for a specific choice of the multiplication coefficients ${\lambda }_k^{(n-1)}={\lambda }_k^{(n-1)}(r)$. Linear operators, with values in ${\mathfrak{N}}_{2n-1}^T$, yielding the supremum of the best approximation on convolution classes, including, in particular, $M\tilde{W}{}_{\mathrm{\infty }}^r$ and $M\tilde{W}{}_1^r$ with a rational number $r>0$, as well as on classes of conjugate functions, have been established (cf. [10], [11]).

For approximation by the subspace $S_{2\pi }^m$ of $2\pi$- periodic splines of order $m$ and defect 1 with knots (nodes, joints) at $k\pi /n$( $\dim S_{2n}^m=2n$), the equalities

$$E(M\tilde{W}{}_p^r,S_{2n}^{r-1}{)}_{{\tilde{L}}_p}=\mathcal{E}(M\tilde{W}{}_p^r,S_{2n}^{r-1}{)}_{{\tilde{L}}_p}=M{K}_r{n}^{-r},$$

$$p=1,\mathrm{\infty };n,r=1,2\dots$$

are valid. The splines ${\sigma }_{r-1}(f,t)$ in $S_{2\pi }^{r-1}$ interpolating a function $f$ at $k\pi /n$ if $r$ is even, and at $(2k+1)\pi /2n$ if $r$ is odd, provide the best linear methods in this case. Relative to $M\tilde{W}{}_{\mathrm{\infty }}^r$ these splines have exceptional approximative properties, since they give the best approximation of an $f\in M\tilde{W}{}_{\mathrm{\infty }}^r$ in any ${\tilde{L}}_p$( 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. $X$ is an arbitrary linear normed space, $X^{\ast }$ is its dual and $\mathfrak{N}$ is a convex set in $X$, then for any $x\in X$

$$\begin{array}{}\text{(4)}& \underset{u\in \mathfrak{N}}{inf}\Vert x-u\Vert =\underset{\genfrac{}{}{0ex}{}{F\in X^{\ast },}{\Vert F\Vert \le 1}}{sup}[F(x)-\underset{u\in \mathfrak{N}}{sup}F(u)];\end{array}$$

in particular, if $\mathfrak{N}$ is a subspace,

$$\begin{array}{}\text{(5)}& \underset{u\in \mathfrak{N}}{inf}\Vert x-u\Vert =sup\{F(x):F\in X^{\ast },\Vert F\Vert \le 1,F(u)=0\text{ for }\text{ all }u\in \mathfrak{N}\}.\end{array}$$

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 $\mathfrak{N}$ is a subspace, is related to orthogonality conditions. For example, by (5) the estimation of $E\widetilde{(W}{}_q^r,{\mathfrak{N}}_{2n-1}^T{)}_{{\tilde{L}}_p}$, $1\le p,q\le \mathrm{\infty }$, can be reduced, using known inequalities, to the calculation of the supremum of the norms $\Vert g{\Vert }_{q^{\prime }}$, $q^{\prime }=q/(q-1)$, on the set of functions $g\in W_{p^{\prime }}^r$, $p^{\prime }=p/(p-1)$, for which

$$\underset{0}{\overset{2\pi }{\int }}g(t)\genfrac{}{}{0ex}{}{\cos }{\sin }\genfrac{}{}{0ex}{}{kt}{kt}dt=0,k=0\dots n-1.$$

More refined situations occur when (1) has to be solved on classes not given by restrictions on the norm of the $r$- th derivative $f^{(r)}(t)$, but on its modulus of continuity $\omega (f^{(r)},\delta {)}_X$. Particularly interesting is the case where $\mathfrak{M}=\tilde{W}{}^r{H}^{\omega }$( $r=0,1,\dots$; $\tilde{W}{}^0{H}^{\omega }=\tilde{H}{}^{\omega }$) is the class of $2\pi$- periodic functions $f\in \tilde{C}{}^r$( ${\tilde{C}}^0=\tilde{C}$) for which

$$\omega (f^{(r)},\delta {)}_C=\omega (f^{(r)},\delta )\le \omega (\delta ),$$

where $\omega (\delta )$ is a given modulus of continuity, e.g. $\omega (\delta )=M{\delta }^{\alpha }$( $0<\alpha \le 1$, $0\le \delta \le \pi$). 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 $\omega (\delta )$ is convex from above, the following equalities ([7], [15]) are valid:

$$E\widetilde{(W}{}^r{H}^{\omega },{\mathfrak{N}}_{2n-1}^T{)}_X=E\widetilde{(W}{}^r{H}^{\omega },S_{2n}^r{)}_X=\Vert f_{nr}(\omega ){\Vert }_X,$$

$$n=1,2,\dots ;r=0,1,\dots .$$

Here $X=\tilde{C}$ or ${\tilde{L}}_1$, the $f_{nr}(\omega ,t)$ are functions in $\tilde{W}{}^r{H}^{\omega }$ of period $2\pi /n$, with zero average over a period, for which $f_{nr}^{(r)}$ is even, equal to $[\omega (\pi /n-2t)]/2$ on $[0,\pi /2n]$, and equal to $-[\omega (2t-\pi /n)]/2$ on $[\pi /2n,\pi /n]$. The norms $\Vert f_{nr}(\omega ){\Vert }_X$ have an explicit expression, e.g.

$$\Vert f_{n0}(\omega ){\Vert }_{\tilde{C}}=\frac{1}{2}\omega \left(\frac{\pi }{n}\right),$$

$$\Vert f_{nr}(\omega ){\Vert }_{\tilde{C}}=\frac{1}{2n^r}\underset{0}{\overset{\pi }{\int }}{\mathrm{\Phi }}_r(\pi -t)\omega \left(\frac{t}{n}\right)dt,r=1,2\dots$$

where the functions ${\mathrm{\Phi }}_k(t)$ on $[0,\pi ]$ are given recurrently by

$${\mathrm{\Phi }}_1(t)=\frac{1}{2},{\mathrm{\Phi }}_k(t)=\frac{1}{2}\underset{0}{\overset{\pi -t}{\int }}{\mathrm{\Phi }}_{k-1}(u)du.$$

The best linear method from $\tilde{C}$ into ${\mathfrak{N}}_{2n-1}^T$, or into $S_{2n}^r$, for the class $\tilde{W}{H}^{\omega }$ is known for $\omega (\delta )=m\delta$, $0\le \delta \le \pi$, i.e. when $\tilde{W}{}^r{H}^{\omega }=M\tilde{W}{}_{\mathrm{\infty }}^{r+1}$. The interpolation splines ${\sigma }_r(f,t)$ in $S_{2\pi }^r$ yield the supremum $E\widetilde{(W}{}^r{H}^{\omega },S_{2\pi }^r{)}_{\tilde{C}}$( for any convex $\omega (\delta )$) only if $r=1$.

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 $M{W}^r{H}^{\alpha }$, $r=0,1\dots$ $0<\alpha <1$, $M{W}^0{H}^{\alpha }=M{H}^{\alpha }$, is the class of functions $f\in C^r[-1,1]$ for which

$$|f^{(r)}(t^{\prime })-f^{(r)}(t^{\prime \prime })|\le M|t^{\prime }-t^{\prime \prime }{|}^{\alpha }(t^{\prime },t^{\prime \prime }\in [-1,1]),$$

then for the best uniform approximation on $[-1,1]$ by the subspace ${\mathfrak{N}}_n^A$ of algebraic polynomials of degree $n-1$, the relations

$$\begin{array}{}\text{(6)}& \underset{n\to \mathrm{\infty }}{lim}{n}^{\alpha }E(M{H}^{\alpha },{\mathfrak{N}}_n^A{)}_C=\frac{M{\pi }^{\alpha }}{2},\end{array}$$

$$\begin{array}{}\text{(7)}& \underset{n\to \mathrm{\infty }}{lim}{n}^{r+\alpha }E(M{W}^r{H}^{\alpha },{\mathfrak{N}}_n^A{)}_C=\frac{M}{2}\underset{0}{\overset{\pi }{\int }}{\mathrm{\Phi }}_r(\pi -t)t^{\alpha }dt,\end{array}$$

$$r=1,2\dots$$

hold. It is useful to compare these results with the corresponding ones in the periodic case. For $\alpha =1$, the right-hand sides of (6), (7) are equal, respectively, to $M{K}_1$ and $M{K}_{r+1}$. Dropping the requirement of a polynomial of best approximation, one obtains stronger results, essentially improving the approximation at the end points of $[-1,1]$ without losing the best asymptotics on the whole interval. E.g., for any $f\in M{H}^{\alpha }$ there is a sequence of algebraic polynomials $p_n(f,t)\in {\mathfrak{N}}_n^A$ such that uniformly in $t\in [-1,1]$, as $n\to \mathrm{\infty }$, one has

$$|f(t)-p_n(f,t)|\le \frac{M}{2}[{\left(\frac{\pi }{n}\sqrt{1-t^2}\right)}^{\alpha }+o(n^{-\alpha })]=$$

$$=E(M{H}^{\alpha },{\mathfrak{N}}_n^A{)}_C[(1-t^2{)}^{\alpha /2}+o(1)].$$

Analogous results hold for $M{W}^r{H}^1,r=1,2\dots$ 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 $\mathfrak{M}$, to the problem of widths: Determine (cf. (1), (3)):

$$d_N(\mathfrak{M},X)=\underset{{\mathfrak{N}}_N}{inf}E(\mathfrak{M},{\mathfrak{N}}_N{)}_X,$$

$$d_N^{\prime }(\mathfrak{M},X)=\underset{{\mathfrak{N}}_N}{inf}\mathcal{E}(\mathfrak{M},{\mathfrak{N}}_N{)}_X,$$

where the infima are taken over all subspaces ${\mathfrak{N}}_N$ of $X$( as well as over their translations) of dimension $N$, and also to determine extremal (best) subspaces yielding these infima. An upper bound for $d_N$ and $d_N^{\prime }$ is given by $E(\mathfrak{M},\mathfrak{N}{)}_X$ and $\mathcal{E}(\mathfrak{M},{\mathfrak{N}}_N{)}_X$, which have been established for concrete subspaces ${\mathfrak{N}}_N$. 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 $M\tilde{W}{}_p^r$ and $\tilde{W}{}^r{H}^{\omega }$ of periodic functions by the subspaces ${\mathfrak{N}}_{2n-1}^T$( trigonometric polynomials of order $n-1$) or $S_{2n}^m$( splines of order $m$ and defect 1 with respect to the partition of knots $k\pi /n$), the known exact upper bounds $E(\mathfrak{M},{\mathfrak{N}}_N{)}_X$ give also the values of $d_N$ for these classes. Moreover, for periodic classes $d_{2n-1}=d_{2n}$. In particular (cf. [7], [8], [15], )

$$d_{2n-1}(\tilde{W}{}_{\mathrm{\infty }}^r,\tilde{C})=d_{2n}(\tilde{W}{}_{\mathrm{\infty }}^r,\tilde{C})=d_{2n-1}(\tilde{W}{}_1^r,{\tilde{L}}_1)=$$

$$=d_{2n}(\tilde{W}{}_1^r,{\tilde{L}}_1)=K_r{n}^{-r},n,r=1,2\dots$$

and for an upper convex $\omega (\delta )$ and for $X=\tilde{C}$ or ${\tilde{L}}_1$ one has

$$d_{2n-1}(\tilde{W}{}^r{H}^{\omega },X)=d_{2n}(\tilde{W}{}^r{H}^{\omega },X)=\Vert f_{nr}(\omega ){\Vert }_X,$$

$$n=1,2,...;r=0,1,....$$

It should be observed that ${\mathfrak{N}}_{2n-1}^T$ is extremal for the classes considered, for all $r$, and that no subspace of dimension $2n$ gives a better approximation for these classes than ${\mathfrak{N}}_{2n-1}^T$( which is of dimension $2n-1$). The subspace $S_{2n}^m$ of splines is extremal for $\tilde{W}{}_{\mathrm{\infty }}^{r+1}$ and $\tilde{W}{}^r{H}^{\omega }$ in $\tilde{C}$ if $m=r$ and for $\tilde{W}{}_p^{r+1}$ in ${\tilde{L}}_1$ if $m\ge r$. The linear widths $d_N^{\prime }$ of $\tilde{W}{}_{\mathrm{\infty }}^r$ in $\tilde{C}$ and $\tilde{W}{}_1^r$ in ${\tilde{L}}_1$ coincide with $d_N$, they are attained on ${\mathfrak{N}}_{2n-1}^T$ and $S_{2n}^{r-1}$ by the best linear methods that were referred to above. The widths $d_N$ and $d_N^{\prime }$ of $\tilde{W}{}_2^r$ in ${\tilde{L}}_2$ for $N=2n-1$ and $N=2n$ 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 $d_N$ and $d_N^{\prime }$ of $W_{\mathrm{\infty }}^r$ in $C[-1,1]$ coincide and are obtained for interpolation splines of order $r-1$ with respect to non-uniform partitions (cf. [8]).

The problem of estimating the approximation error on the set $X^r$ of $r$- fold integrals of functions from $X$( which is not locally compact) can be stated properly if for $f\in X^r$ and fixed $\gamma >0$ one estimates

$$\frac{E(f,{\mathfrak{N}}_N{)}_X}{\omega (f^{(r)},\gamma {)}_X}$$

( $\omega (g,\delta {)}_X$ is the modulus of continuity of $g$ in $X$) or (in the case of a concrete approximation method) if one estimates

$$\frac{\Vert f-U_{N}f{\Vert }_X}{\omega (f^{(r)},\gamma {)}_X}.$$

Determining the suprema of these quantities on $X^r$ 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 $N$. In a number of cases, these problems have been solved. E.g. in the inequality

$$E(f,S_{2n}^r{)}_{\tilde{C}}\le M_r{n}^{-r}\omega {(f^{(r)},\frac{\pi }{n})}_{\tilde{C}},f\in \tilde{C}{}^r,$$

the least constant is $M_r=K_r/2$, and it cannot be improved if $S_{2n}^r$ 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 $\mathfrak{M}$ by another ${\mathfrak{M}}_1$ 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

$$E(\tilde{H}{}^{\omega },{\mathfrak{N}}_{2n-1}^T{)}_{\tilde{C}}(\mathfrak{M}=\tilde{H}{}^{\omega },{\mathfrak{M}}_1=M\tilde{W}{}_{\mathrm{\infty }}^1)$$

(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

$$\mathfrak{M}=M_1{W}_p^r,$$

$${\mathfrak{M}}_1=M_2{W}_q^k(0<r<k)$$

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 $f\in X$ be given by a vector $T(f,\mathrm{\Lambda })=\{{\lambda }_1(f)\dots {\lambda }_n(f)\}$, where ${\lambda }_k$ are given functionals on $X$( e.g. values of $f$ and/or some derivatives in fixed points). Given that $f$ belongs to a class $\mathfrak{M}$, it is required to reconstruct $f$ or some linear functional $L(f)$ of it (e.g. $L(f)=f(\bar{t})$, $L(t)={\int }_a^{b}f(t)dt$, etc.) on the basis of $T(f,\mathrm{\Lambda })$ with least possible error. The minimization need not only take into account methods $S$ juxtaposing $T(f,\mathrm{\Lambda })$ with a function $\varphi (t)\approx f(t)$( or a functional $l(f)\approx L(f)$), but also involves the choice of functionals ${\lambda }_k$, $k=1\dots N$. Depending on the choice of the error measure and the class of methods $S$, the problem of optimal recovery of a function may sometimes be reduced to determining the widths $d_N,d_N^{\prime }$, the Chebyshev centre, or other characteristics of $\mathfrak{M}$. The problem of optimal recovery of ${\int }_a^{b}f(t)dt$ on the basis of information of the form $\{f(t_k)\}$ or $\{f^{(\nu )}(t_k)\}$ leads to the problem of best quadrature formulas for $\mathfrak{M}$. The best tool of recovering is achieved, in a number of cases, by splines; e.g. the splines ${\sigma }_{r-1}(f,t)$ in $S_{2n}^{r-1}$ that interpolate at equally-distant points $t_k$ reconstruct an $f\in \tilde{W}{}_{\mathrm{\infty }}^r$ on the basis of information ${\lambda }_k(f)=f(t_k)$ in each point $t\ne t_k$ with minimum error on the whole class $\tilde{W}{}_{\mathrm{\infty }}^r$.

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[edit]

Comments[edit]

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

References[edit]