Interpolatory Pointwise Estimates for Polynomial Approximation

We discuss whether or not it is possible to have interpolatory pointwise estimates in the approximation of a function f∈ C[0,1] , by polynomials. For the sake of completeness, as well as in order to strengthen some existing results, we discuss briefly the situation in unconstrained approximation. Then we deal with positive and monotone constraints where we show exactly when such interpolatory estimates are achievable by proving affirmative results and by providing the necessary counterexamples in all other cases. November 16, 1998. Date revised: July 12, 1999. Date accepted: September 13, 1999.     

More on Comonotone Polynomial Approximation

The main achievement of this paper is that we show, what was to us, a surprising conclusion, namely, twice continuously differentiable functions in (0,1) (with some regular behavior at the endpoints) which change monotonicity at least once in the interval, are approximable better by comonotone polynomials, than are such functions that are merely monotone. We obtain Jackson-type estimates for the comonotone polynomial approximation of such functions that are impossible to achieve for monotone approximation. July 7, 1998. Date revised: May 5, 1999. Date accepted: July 23, 1999.     

Approximation of Scattered Data by Trigonometric Polynomials on the Torus and the 2-sphere

Fast, efficient and reliable algorithms for the discrete least-square approximation of scattered points on the torus T ^d and the sphere S ² by trigonometric polynomials are presented. The algorithms are based on iterative CG-type methods in combination with fast Fourier transforms for nonequispaced data. The emphasis is on numerical aspects, in order to solve large scale problems. Numerical examples show the efficiency of the new algorithms.     

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     

Greedy Algorithm and m -Term Trigonometric Approximation

We study the following nonlinear method of approximation by trigonometric polynomials in this paper. For a periodic function f we take as an approximant a trigonometric polynomial of the form , where is a set of cardinality m containing the indices of the m biggest (in absolute value) Fourier coefficients of function f . We compare the efficiency of this method with the best m -term trigonometric approximation both for individual functions and for some function classes. It turns out that the operator G _m provides the optimal (in the sense of order) error of m -term trigonometric approximation in the L _p -norm for many classes. September 23, 1996. Date revised: February 3, 1997.     

Fast evaluation of trigonometric polynomials from hyperbolic crosses

The discrete Fourier transform in d dimensions with equispaced knots in space and frequency domain can be computed by the fast Fourier transform (FFT) in arithmetic operations. In order to circumvent the ‘curse of dimensionality’ in multivariate approximation, interpolations on sparse grids were introduced. In particular, for frequencies chosen from an hyperbolic cross and spatial knots on a sparse grid fast Fourier transforms that need only arithmetic operations were developed. Recently, the FFT was generalised to nonequispaced spatial knots by the so-called NFFT. In this paper, we propose an algorithm for the fast Fourier transform on hyperbolic cross points for nonequispaced spatial knots in two and three dimensions. We call this algorithm sparse NFFT (SNFFT). Our new algorithm is based on the NFFT and an appropriate partitioning of the hyperbolic cross. Numerical examples confirm our theoretical results.     

Approximation by complex genuine Durrmeyer type polynomials in compact disks

In this paper, the order of simultaneous approximation and Voronovskaja kind results with quantitative estimate for the complex genuine Durrmeyer polynomials attached to analytic functions on compact disks are obtained. In this way, we put in evidence the overconvergence phenomenon for the genuine Durrmeyer polynomials, namely the extensions of the approximation properties (with quantitative estimates) from real intervals to compact disks in the complex plane.     

Approximation of monomials by lower degree polynomials

Our topic is the uniform approximation ofx ^k by polynomials of degreen (n on the interval [–1, 1]. Our major result indicates that good approximation is possible whenk is much smaller thann ² and not possible otherwise. Indeed, we show that the approximation error is of the exact order of magnitude of a quantity,p _k,n , which can be identified with a certain probability. The numberp _k,n is in fact the probability that when a (fair) coin is tossedk times the magnitude of the difference between the number of heads and the number of tails exceedsn.     

A fractional version of the peano-sard theorem

Sard's classical generalization of the Peano kernel theorem provides an extremely useful method for expressing and calculating sharp bounds for approximation errors. The error is expressed in terms of a derivative of the underlying function. However, we can apply the theorem only if the approximation is exact on a certain set of polynomials.

In this paper, we extend the Peano-Sard theorem to the case that the approximation is exact for a class of generalized polynomials (with non-integer exponents). As a result, we obtain an expression for the remainder in terms of a fractional derivative of the function under consideration. This expression permits us to give sharp error bounds as in the classical situation. An application of our results to the classical functional (vanishing on polynomials) gives error bounds of a new type involving weighted Sobolev-type spaces. In this way, we may state estimates for functions with weaker smoothness properties than usual.

The standard version of the Peano-Sard theory is contained in our results as a special case.     

Shape-preserving approximation inL p

We prove a direct theorem for shape preservingL _p -approximation, 0p, in terms of the classical modulus of smoothnessw ₂(f, t _p ¹ ). This theorem may be regarded as an extension toL _p of the well-known pointwise estimates of the Timan type and their shape-preserving variants of R. DeVore, D. Leviatan, and X. M. Yu. It leads to a characterization of monotone and convex functions in Lipschitz classes (and more general Besov spaces) in terms of their approximation by algebraic polynomials.Communicated by Ron DeVore.     

Greedy Algorithms with Regard to Multivariate Systems with Special Structure

The question of finding an optimal dictionary for nonlinear m -term approximation is studied in this paper. We consider this problem in the periodic multivariate (d variables) case for classes of functions with mixed smoothness. We prove that the well-known dictionary U ^d which consists of trigonometric polynomials (shifts of the Dirichlet kernels) is nearly optimal among orthonormal dictionaries. Next, it is established that for these classes near-best m -term approximation, with regard to U ^d , can be achieved by simple greedy-type (thresholding-type) algorithms. The univariate dictionary U is used to construct a dictionary which is optimal among dictionaries with the tensor product structure. June 22, 1998. Date revised: March 26, 1999. Date accepted: March 22, 1999.     

Plane wave approximation of homogeneous Helmholtz solutions

In this paper, we study the approximation of solutions of the homogeneous Helmholtz equation Δu + ω ² u = 0 by linear combinations of plane waves with different directions. We combine approximation estimates for homogeneous Helmholtz solutions by generalized harmonic polynomials, obtained from Vekua’s theory, with estimates for the approximation of generalized harmonic polynomials by plane waves. The latter is the focus of this paper. We establish best approximation error estimates in Sobolev norms, which are explicit in terms of the degree of the generalized polynomial to be approximated, the domain size, and the number of plane waves used in the approximations.     

On near-best discrete quasi-interpolation on a four-directional mesh

Spline quasi-interpolants are practical and effective approximation operators. In this paper, we construct QIs with optimal approximation orders and small infinity norms called near-best discrete quasi-interpolants which are based on Ω-splines, i.e. B-splines with octagonal supports on the uniform four-directional mesh of the plane. These quasi-interpolants are exact on some space of polynomials and they minimize an upper bound of their infinity norms depending on a finite number of free parameters. We show that this problem has always a solution, in general nonunique. Concrete examples of such quasi-interpolants are given in the last section.     

Numerical stability of nonequispaced fast Fourier transforms

This paper presents some new results on numerical stability for multivariate fast Fourier transform of nonequispaced data (NFFT). In contrast to fast Fourier transform (of equispaced data), the NFFT is an approximate algorithm. In a worst case study, we show that both approximation error and roundoff error have a strong influence on the numerical stability of NFFT. Numerical tests confirm the theoretical estimates of numerical stability.     

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.     

Degree of approximation of analytic functions by “near-best” polynomial approximants

We study the rate of approximation of a functionfA(K) in the interior of the compact setK by polynomials, that are close to best polynomial approximants on the whole setK. Lower and upper estimates of possible improvement of convergence (depending on the geometry ofK) are obtained.Communicated by Vilmos Totik.     

Approximation Methods by Regular Functions

This paper is a survey of approximation results and methods by smooth functions in Banach spaces. The topics considered in the paper are the following: approximation by polynomials by C^k-functions using the method of smooth partitions of unity, approximation by the fine topology, analytic approximation and regularization in Banach spaces using the infimal convolution method.     

Moduli of smoothness and approximation on the unit sphere and the unit ball

A new modulus of smoothness based on the Euler angles is introduced on the unit sphere and is shown to satisfy all the usual characteristic properties of moduli of smoothness, including direct and inverse theorem for the best approximation by polynomials and its equivalence to a K-functional, defined via partial derivatives in Euler angles. The set of results on the moduli on the sphere serves as a basis for defining new moduli of smoothness and their corresponding K-functionals on the unit ball, which are used to characterize the best approximation by polynomials on the ball.     

Erdös-Turán theorems on a system of Jordan curves and arcs

Erdös and Turán established in [4] a qualitative result on the distribution of the zeros of a monic polynomial, the norm of which is known on [–1, 1]. We extend this result to a polynomial bounded on a systemE of Jordan curves and arcs. If all zeros of the polynomial are real, the estimates are independent of the number of components ofE for any regular compact subsetE ofR. As applications, estimates for the distribution of the zeros of the polynomials of best uniform approximation and for the extremal points of the optimal error curve (generalizations of Kadec's theorem) are given.Communicated by Dieter Gaier.     

Fourier Reconstruction of Functions from their Nonstandard Sampled Radon Transform

In this article, we suggest a new Fourier transform based algorithm for the reconstruction of functions from their nonstandard sampled Radon transform. The algorithm incorporates recently developed fast Fourier transforms for nonequispaced data. We estimate the corresponding aliasing error in dependence on the sampling geometry of the Radon transform and confirm our theoretical results by numerical examples.