On the orders of nonlinear approximations for classes of functions of given form (Q2577348)

For an interval \(I \subset {\mathbb R}\) and \(s \in {\mathbb N}\), the set \(\Delta_+^s B_q\) is defined as the collection of functions \(f \in L_q(I)\), \(\| f\| _q \leq 1\), for which the divided differences \([f; t_0, \ldots ,t_s]\) are nonnegative for every \(s+1\) points \(t_0, \ldots ,t_s \in I\). Given two subsets, \(W\) and \(G\), of \(L_q\), let \[ E(W,G)_q=\sup_{f \in W}\, \inf_{g \in G} \| f-g\| _q . \] In the paper under review, \(G\) is either the set \(R_n\) of rational functions \(g=u/v\), where \(u,v\) are polynomials of order \(\leq n\), or the set \(\Sigma_{r,n}\) of splines of order \(r\) with \(n-1\) free knots. It is proved that \(E(\Delta_+^s B_\infty, G)_\infty \asymp n^{-1}\) for both \(G=R_n\) and \(G=\Sigma_{r,n}\) if \(s>1\), \(r=1,2, \ldots\) (the case \(s=2\) has been established earlier). This estimate remains true if \(s=1\), but only for \(G=\Sigma_{r,n}\), whereas \(E(\Delta_+^s B_\infty, R_n)\) does not tend to zero as \(n \to \infty\). In the case of \(W=\Delta_+^s B_q\) with \(q< \infty\), \(E(W,G)_q\) tends to zero for neither \(G=R_n\) nor \(G=\Sigma_{r,n}\). To compare the above results, the author uses the concept of the so-called pseudodimension of a set of functions. The pseudodimension of \(R_n\) and \(\Sigma_{r,n}\) is \(\asymp n\), and these sets are asymptotically optimal in the sense that \(E(\Delta_+^s B_\infty, G)_\infty \geq c n^{-1}\), with \(c\) independent of \(n\), for any set \(G\) of pseudodimension \(n\).