Universal Algorithms for Learning Theory. Part II: Piecewise Polynomial Functions

This paper is concerned with estimating the regression function f_ρ in supervised learning by utilizing piecewise polynomial approximations on adaptively generated partitions. The main point of interest is algorithms that with high probability are optimal in terms of the least square error achieved for a given number m of observed data. In a previous paper [1], we have developed for each β > 0 an algorithm for piecewise constant approximation which is proven to provide such optimal order estimates with probability larger than 1- m^-β. In this paper we consider the case of higher-degree polynomials. We show that for general probability measures ρ empirical least squares minimization will not provide optimal error estimates with high probability. We go further in identifying certain conditions on the probability measure ρ which will allow optimal estimates with high probability.     

On mean approximation by polynomials with gaps on Caratheodory sets

The paper presents some new results on the possibility of approximation by polynomials with gaps. The approximations are done in the norm of the space L _p , 1 ≤ p < + ∞, on the Caratheodory sets in the complex plane. The lacunary versions of some results by Farell—Markushevich, S. Sinanian, A. L. Shahinian are obtained (Theorems 1, 3, 5). Similar approximations by the real parts of lacunary polynomials are given (Theorems 2, 4, 6). Dedicated to the memory of academician S. N. Mergelyan     

On CP, LP and other piecewise perturbation methods for the numerical solution of the Schr?dinger equation

The piecewise perturbation methods (PPM) have proven to be very efficient for the numerical solution of the linear time-independent Schr?dinger equation. The underlying idea is to replace the potential function piecewisely by simpler approximations and then to solve the approximating problem. The accuracy is improved by adding some perturbation corrections. Two types of approximating potentials were considered in the literature, that is piecewise constant and piecewise linear functions, giving rise to the so-called CP methods (CPM) and LP methods (LPM). Piecewise polynomials of higher degree have not been used since the approximating problem is not easy to integrate analytically. As suggested by Ixaru (Comput Phys Commun 177:897–907, 2007), this problem can be circumvented using another perturbative approach to construct an expression for the solution of the approximating problem. In this paper, we show that there is, however, no need to consider PPM based on higher-order polynomials, since these methods are equivalent to the CPM. Also, LPM is equivalent to CPM, although it was sometimes suggested in the literature that an LP method is more suited for problems with strongly varying potentials. We advocate that CP schemes can (and should) be used in all cases, since it forms the most straightforward way of devising PPM and there is no advantage in considering other piecewise polynomial perturbation methods.     

Convex polynomial and spline approximation inL p,O<p<∞

We prove that a convex functionf ∈ L _p[−1, 1], 0<p<∞, can be approximated by convex polynomials with an error not exceeding Cω ₃ ^ϕ (f,1/n)_p where ω ₃ ^ϕ (f,·) is the Ditzian-Totik modulus of smoothness of order three off. We are thus filling the gap between previously known estimates involving ω ₃ ^ϕ (f,1/n)_p, and the impossibility of having such estimates involving ω₄. We also give similar estimates for the approximation off by convexC ⁰ andC ¹ piecewise quadratics as well as convexC ² piecewise cubic polynomials. Communicated by Dietrich Braess     

On 3-monotone approximation by piecewise polynomials

We consider 3-monotone approximation by piecewise polynomials with prescribed knots. A general theorem is proved, which reduces the problem of 3-monotone uniform approximation of a 3-monotone function, to convex local L₁ approximation of the derivative of the function. As the corollary we obtain Jackson-type estimates on the degree of 3-monotone approximation by piecewise polynomials with prescribed knots. Such estimates are well known for monotone and convex approximation, and to the contrary, they in general are not valid for higher orders of monotonicity. Also we show that any convex piecewise polynomial can be modified to be, in addition, interpolatory, while still preserving the degree of the uniform approximation. Alternatively, we show that we may smooth the approximating piecewise polynomials to be twice continuously differentiable, while still being 3-monotone and still keeping the same degree of approximation.     

Best approximations of the classes B p,θ r of periodic functions of many variables in uniform metric

We obtain estimates exact in order for the best approximations of the classes B _∞,θ ^r of periodic functions of two variables in the metric of L _∞ by trigonometric polynomials whose spectrum belongs to a hyperbolic cross. We also investigate the best approximations of the classes B _p,θ ^r , 1 ≤ p < ∞, of periodic functions of many variables in the metric of L _∞ by trigonometric polynomials whose spectrum belongs to a graded hyperbolic cross. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 10, pp. 1395–1406, October, 2006.     

A divergence-free weak Galerkin method for quasi-Newtonian Stokes flows

This paper proposes a weak Galerkin finite element method to solve incompressible quasi-Newtonian Stokes equations. We use piecewise polynomials of degrees k + 1(k 0) and k for the velocity and pressure in the interior of elements, respectively, and piecewise polynomials of degrees k and k + 1 for the boundary parts of the velocity and pressure, respectively. Wellposedness of the discrete scheme is established. The method yields a globally divergence-free velocity approximation. Optimal priori error estimates are derived for the velocity gradient and pressure approximations. Numerical results are provided to confirm the theoretical results.     

Asymptotic analysis of the Askey-scheme I: from Krawtchouk to Charlier

We analyze the Charlier polynomials C _n (χ) and their zeros asymptotically as n → ∞. We obtain asymptotic approximations, using the limit relation between the Krawtchouk and Charlier polynomials, involving some special functions. We give numerical examples showing the accuracy of our formulas.      

Approximation of multidimensional functions with a given majorant of mixed moduli of continuity

In the paper order-exact upper bounds for the best approximations of classesH _q ^Emphasis>/ω by trigonometric polynomials are obtained. The spectrum of the approximating polynomials lies in sets generated by the level surfaces of the function ω(t). These sets are a generalization of hyperbolic crosses to the case of an arbitrary function ω(t). Translated fromMatematicheskie Zametki, Vol. 65, No. 1, pp. 107–117, January, 1999.     

Approximative characteristics of the isotropic classes of periodic functions of many variables

Exact-order estimates are obtained for the best orthogonal trigonometric approximations of the Besov (B _p,θ ^r ) and Nukol’skii (H _p ^r ) classes of periodic functions of many variables in the metric of L _q , 1 ≤ p, q ≤ ∞. We also establish the orders of the best approximations of functions from the same classes in the spaces L ₁ and L _∞ by trigonometric polynomials with the corresponding spectrum.     

Uniformn-analytic polynomial approximations of functions on rectifiable contours in ℂ

We study approximations of functions byn-analytic polynomials in the uniform norm on closed rectifiable Jordan curves in the complex plane. It is shown that, in contrast to the case of uniform approximations by complex polynomials, there are no topological criteria for the existence of such approximations. We obtain a criterion for the existence ofn-analytic polynomial approximations in terms of analytic properties of these curves. Translated fromMatematicheskie Zametki, Vol. 59, No. 4, pp. 603–609, April, 1996. The author is extremely grateful to A. G. Vitushkin and P. V. Paramonov for the statement of the problem and their attention to the work. The work was partially supported by the Russian Foundation for Basic Research under grant No. 93-01-00225.     

On CP,LP and other piecewise perturbation methods for the numerical solution of the Schrödinger equation

The piecewise perturbation methods (PPM) have proven to be very efficient for the numerical solution of the linear time-independent Schrödinger equation. The underlying idea is to replace the potential function piecewisely by simpler approximations and then to solve the approximating problem. The accuracy is improved by adding some perturbation corrections. Two types of approximating potentials were considered in the literature, that is piecewise constant and piecewise linear functions, giving rise to the so-called CP methods (CPM) and LP methods (LPM). Piecewise polynomials of higher degree have not been used since the approximating problem is not easy to integrate analytically. As suggested by Ixaru (Comput Phys Commun 177:897–907, 2007), this problem can be circumvented using another perturbative approach to construct an expression for the solution of the approximating problem. In this paper, we show that there is, however, no need to consider PPM based on higher-order polynomials, since these methods are equivalent to the CPM. Also, LPM is equivalent to CPM, although it was sometimes suggested in the literature that an LP method is more suited for problems with strongly varying potentials. We advocate that CP schemes can (and should) be used in all cases, since it forms the most straightforward way of devising PPM and there is no advantage in considering other piecewise polynomial perturbation methods.     

Approximation of solutions of operator-differential equations by operator polynomials

We prove theorems that characterize the classes of functions whose best approximations by algebraic polynomials tend to zero with given order. We construct approximations of solutions of operator-differential equations by polynomials in the inverse operator. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 11, pp. 1506–1516, November, 1998.     

Comparison between the best approximations by lacunary and ordinary polynomials

We denote E_n(f) and E _k ⁿ (f) the best uniform approximations to a continuous function f defined on [a,b] by the sets of algebraic polynomials of degree ≤n and algebraic polynomials of degree ≤n with the coefficients of x^k (k≤n) being zero. In this paper, in cases of r<k and r≥k while [a, b]=[−1,1] (or r<k,k≤r<2k and r>2k while [a,b]=[0, 1]), we separately discuss the condtions for r-times continuously differentiable function f which enables .     

Comparison of approximation properties of generalized polynomials and splines

We establish that, for p ∈ [2, ∞), q = 1 or p = ∞, q ∈ [ 1, 2], the classes W _p^rof functions of many variables defined by restrictions on the L _p-norms of mixed derivatives of order r = (r ₁, r ₂, ..., r _m) are better approximated in the L _q-metric by periodic generalized splines than by generalized trigonometric polynomials. In these cases, the best approximations of the Sobolev classes of functions of one variable by trigonometric polynomials and by periodic splines coincide. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 8, pp. 1011–1020, August, 1998.     

Best <Emphasis Type="Italic">n</Emphasis>-Term Approximations with Restrictions

We determine exact values of the best n-term approximations with restrictions on polynomials used for the approximation of λ, q-ellipsoids in the spaces S _ϕ ^p,μ . __________ Translated from Ukrains'kyi Matematychnyi Zhurnal, Vol. 57, No. 4, pp. 533–553, April, 2005.     

Fourier-Padé approximations and filtering for spectral simulations of an incompressible Boussinesq convection problem

In this paper, we present rational approximations based on Fourier series representation. For periodic piecewise analytic functions, the well-known Gibbs phenomenon hampers the convergence of the standard Fourier method. Here, for a given set of the Fourier coefficients from a periodic piecewise analytic function, we define Fourier-Padé-Galerkin and Fourier-Padé collocation methods by expressing the coefficients for the rational approximations using the Fourier data. We show that those methods converge exponentially in the smooth region and successfully reduce the Gibbs oscillations as the degrees of the denominators and the numerators of the Padé approximants increase.

Numerical results are demonstrated in several examples. The collocation method is applied as a postprocessing step to the standard pseudospectral simulations for the one-dimensional inviscid Burgers' equation and the two-dimensional incompressible inviscid Boussinesq convection flow.

     

A canonical form and the distribution of values of generalized polynomials

Generalized polynomials are functions obtained from conventional polynomials by applying the operations of taking the integer part, addition, and multiplication. We construct a system of “basic” generalized polynomials with the property that any bounded generalized polynomial is representable as a piecewise polynomial function of these basic ones. Such a representation is unique up to a function vanishing almost everywhere, which solves the problem of determining whether two generalized polynomials are equal a.e. The basic generalized polynomials are jointly equidistributed, thus we also obtain an effective algorithm of finding the limiting distribution of values of one or several generalized polynomials.     

On rational approximations of functions

Rational analogues of Taylor and Fourier polynomials and polynomials of the Lagrange type are constructed and investigated. These analogues are shown to approximate a function with a remainder term of the same order as in the case of the aforementioned polynomials. Conditions are established under which a polynomial of the Lagrange type and its rational analogue are two-sided approximations of a function on a segment and their derivatives are two-sided approximations of the derivative of the function at collocation nodes. Bibliography: 2 titles. Translated fromObchuslyuval’na ta Prykladna Matematyka, No. 76, 1992, pp. 32–38.     

Distribution of values of bounded generalized polynomials

A generalized polynomial is a real-valued function which is obtained from conventional polynomials by the use of the operations of addition, multiplication, and taking the integer part; a generalized polynomial mapping is a vector-valued mapping whose coordinates are generalized polynomials. We show that any bounded generalized polynomial mapping u: Z ^d  → R ^l has a representation u(n) = f(ϕ(n)x), n ∈ Z ^d , where f is a piecewise polynomial function on a compact nilmanifold X, x ∈ X, and ϕ is an ergodic Z ^d -action by translations on X. This fact is used to show that the sequence u(n), n ∈ Z ^d , is well distributed on a piecewise polynomial surface (with respect to the Borel measure on that is the image of the Lebesgue measure under the piecewise polynomial function defining ). As corollaries we also obtain a von Neumann-type ergodic theorem along generalized polynomials and a result on Diophantine approximations extending the work of van der Corput and of Furstenberg–Weiss.