Polynomial interpolation on the unit sphere II

The problem of interpolation at (n+1)² points on the unit sphere by spherical polynomials of degree at most n is proved to have a unique solution for several sets of points. The points are located on a number of circles on the sphere with even number of points on each circle. The proof is based on a method of factorization of polynomials. Dedicated to Mariano Gasca on the occasion of his 60th birthday The second author was supported by the Graduate Program Applied Algorithmic Mathematics of the Munich University of Technology. The work of the third author was supported in part by the National Science Foundation under Grant DMS-0201669.     

Extremal Systems of Points and Numerical Integration on the Sphere

This paper considers extremal systems of points on the unit sphere S ^r⊂R ^r+1, related problems of numerical integration and geometrical properties of extremal systems. Extremal systems are systems of d _n =dim P _n points, where P _n is the space of spherical polynomials of degree at most n, which maximize the determinant of an interpolation matrix. Extremal systems for S ² of degrees up to 191 (36,864 points) provide well distributed points, and are found to yield interpolatory cubature rules with positive weights. We consider the worst case cubature error in a certain Hilbert space and its relation to a generalized discrepancy. We also consider geometrical properties such as the minimal geodesic distance between points and the mesh norm. The known theoretical properties fall well short of those suggested by the numerical experiments.

     

Numerical integration with polynomial exactness over a spherical cap

This paper presents rules for numerical integration over spherical caps and discusses their properties. For a spherical cap on the unit sphere \mathbbS²\mathbb{S}^2, we discuss tensor product rules with n ²/2 + O(n) nodes in the cap, positive weights, which are exact for all spherical polynomials of degree ≤ n, and can be easily and inexpensively implemented. Numerical tests illustrate the performance of these rules. A similar derivation establishes the existence of equal weight rules with degree of polynomial exactness n and O(n ³) nodes for numerical integration over spherical caps on \mathbbS²\mathbb{S}^2. For arbitrary d ≥ 2, this strategy is extended to provide rules for numerical integration over spherical caps on \mathbbS^d\mathbb{S}^d that have O(n ^d ) nodes in the cap, positive weights, and are exact for all spherical polynomials of degree ≤ n. We also show that positive weight rules for numerical integration over spherical caps on \mathbbS^d\mathbb{S}^d that are exact for all spherical polynomials of degree ≤ n have at least O(n ^d ) nodes and possess a certain regularity property.     

How good can polynomial interpolation on the sphere be?

This paper explores the quality of polynomial interpolation approximations over the sphere S ^r−1⊂R ^r in the uniform norm, principally for r=3. Reimer [17] has shown there exist fundamental systems for which the norm ‖Λ _n ‖ of the interpolation operator Λ _n , considered as a map from C(S ^r−1) to C(S ^r−1), is bounded by d _n , where d _n is the dimension of the space of all spherical polynomials of degree at most n. Another bound is d _n ^1/2(λ_avg/λ_min)^1/2, where λ_avg and λ_min are the average and minimum eigenvalues of a matrix G determined by the fundamental system of interpolation points. For r=3 these bounds are (n+1)² and (n+1)(λ_avg/λ_min)^1/2, respectively. In a different direction, recent work by Sloan and Womersley [24] has shown that for r=3 and under a mild regularity assumption, the norm of the hyperinterpolation operator (which needs more point values than interpolation) is bounded by O(n ^1/2), which is optimal among all linear projections. How much can the gap between interpolation and hyperinterpolation be closed?

For interpolation the quality of the polynomial interpolant is critically dependent on the choice of interpolation points. Empirical evidence in this paper suggests that for points obtained by maximizing λ_min, the growth in ‖Λ _n ‖ is approximately n+1 for n<30. This choice of points also has the effect of reducing the condition number of the linear system to be solved for the interpolation weights. Choosing the points to minimize the norm directly produces fundamental systems for which the norm grows approximately as 0.7n+1.8 for n<30. On the other hand, ‘minimum energy points’, obtained by minimizing the potential energy of a set of (n+1)² points on S ², turn out empirically to be very bad as interpolation points.

This paper also presents numerical results on uniform errors for approximating a set of test functions, by both interpolation and hyperinterpolation, as well as by non-polynomial interpolation with certain global basis functions.

     

The Coulomb energy of spherical designs on <Emphasis Type="Italic">S</Emphasis><Superscript>2</Superscript>

In this work we give upper bounds for the Coulomb energy of a sequence of well separated spherical n-designs, where a spherical n-design is a set of m points on the unit sphere S ² ⊂ ℝ³ that gives an equal weight cubature rule (or equal weight numerical integration rule) on S ² which is exact for spherical polynomials of degree ⩽ n. (A sequence Ξ of m-point spherical n-designs X on S ² is said to be well separated if there exists a constant λ > 0 such that for each m-point spherical n-design X ∈ Ξ the minimum spherical distance between points is bounded from below by .) In particular, if the sequence of well separated spherical designs is such that m and n are related by m = O(n ²), then the Coulomb energy of each m-point spherical n-design has an upper bound with the same first term and a second term of the same order as the bounds for the minimum energy of point sets on S ². Dedicated to Edward B. Saff on the occasion of his 60th birthday.     

Constructions of Spherical 3-Designs

 Spherical t-designs are Chebyshev-type averaging sets on the d-sphere which are exact for polynomials of degree at most t. This concept was introduced in 1977 by Delsarte, Goethals, and Seidel, who also found the minimum possible size of such designs, in particular, that the number of points in a 3-design on S ^d must be at least . In this paper we give explicit constructions for spherical 3-designs on S ^d consisting of n points for d=1 and ; d=2 and ; d=3 and ; d=4 and ; and odd or even. We also provide some evidence that 3-designs of other sizes do not exist. We will introduce and apply a concept from additive number theory generalizing the classical Sidon-sequences. Namely, we study sets of integers S for which the congruence mod n, where and , only holds in the trivial cases. We call such sets Sidon-type sets of strength t, and denote their maximum cardinality by s(n, t). We find a lower bound for s(n, 3), and show how Sidon-type sets of strength 3 can be used to construct spherical 3-designs. We also conjecture that our lower bound gives the true value of s(n, 3) (this has been verified for n≤125). Received: June 19, 1996     

Positive Cubature Formulas and Marcinkiewicz–Zygmund Inequalities on Spherical Caps

Let Π _n ^d denote the space of all spherical polynomials of degree at most n on the unit sphere $\mathbb{S}^{d}Let Π _n ^d denote the space of all spherical polynomials of degree at most n on the unit sphere \mathbbS^d\mathbb{S}^{d} of ℝ ^d+1, and let d(x,y) denote the geodesic distance arccos x⋅y between x,y ? \mathbbS^dx,y\in\mathbb{S}^{d} . Given a spherical cap

B(e,a)={x ? \mathbbSd:d(x,e) ￡ a}    (e ? \mathbbSd, a ? (0,p) is bounded awayfrom p),B(e,\alpha)=\big\{x\in\mathbb{S}^{d}:d(x,e)\leq\alpha\big\}\quad \bigl(e\in\mathbb{S}^{d},\ \alpha\in(0,\pi)\ \mbox{is bounded awayfrom}\ \pi\bigr),      8. Construction of spherical t-designs      Bela Bajnok 《Geometriae Dedicata》1992,43(2):167-179 Spherical t-designs are Chebyshev-type averaging sets on the d-dimensional unit sphere S d–1, that are exact for polynomials of degree at most t. The concept of such designs was introduced by Delsarte, Goethals and Seidel in 1977. The existence of spherical t-designs for every t and d was proved by Seymour and Zaslavsky in 1984. Although some sporadic examples are known, no general construction has been given. In this paper we give an explicit construction of spherical t-designs on S d–1 containing N points, for every t,d and N,NN 0, where N 0 = C(d)t O(d 3).      9. On the Energy of a Unit Vector Field      C. M. Wood 《Geometriae Dedicata》1997,64(3):319-330 The energy of a unit vector field on a Riemannian manifold M is defined to be the energy of the mapping M T 1 M, where the unit tangent bundle T 1 M is equipped with the restriction of the Sasaki metric. The constrained variational problem is studied, where variations are confined to unit vector fields, and the first and second variational formulas are derived. The Hopf vector fields on odd-dimensional spheres are shown to be critical points, which are unstable for M=S 5,S 7,..., and an estimate on the index is obtained.      10. A note on stability results for scattered data interpolation on Euclidean spheres      Stefan Kunis 《Advances in Computational Mathematics》2009,30(4):303-314 The present work considers the interpolation of the scattered data on the d-sphere by spherical polynomials. We prove bounds on the conditioning of the problem which rely only on the separation distance of the sampling nodes and on the degree of polynomials being used. To this end, we establish a packing argument for well separated sampling nodes and construct strongly localized polynomials on spheres. Numerical results illustrate our theoretical findings. Dedicated to Professor Manfred Tasche on the occasion of his 65th birthday.      11. On G 2 Continuous Spline Interpolation of Curves in ℝ d      Emil Žagar 《BIT Numerical Mathematics》2002,42(3):670-688 In this paper the problem of G 2 continuous interpolation of curves in d by polynomial splines of degree n is studied. The interpolation of the data points and two tangent directions at the boundary is considered. The case n = r + 2 = d, where r is the number of interior points interpolated by each segment of the spline curve, is studied in detail. It is shown that the problem is uniquely solvable asymptotically, e., when the data points are sampled regularly and sufficiently dense, and lie on a regular, convex parametric curve in d . In this case the optimal approximation order is also determined.      12. Error estimates for Hermite interpolation on spheres      J. Levesley  Z. Luo 《Journal of Mathematical Analysis and Applications》2003,281(1):46-61 In this paper, we prove convergence rates for spherical spline Hermite interpolation on the sphere Sd−1 via an error estimate given in a technical report by Luo and Levesley. The functionals in the Hermite interpolation are either point evaluations of pseudodifferential operators or rotational differential operators, the desirable feature of these operators being that they map polynomials to polynomials. Convergence rates for certain derivatives are given in terms of maximum point separation.      13. On partial polynomial interpolation      Maria Chiara Brambilla  Giorgio Ottaviani 《Linear algebra and its applications》2011,435(6):1415-1445 The Alexander-Hirschowitz theorem says that a general collection of k double points in Pn imposes independent conditions on homogeneous polynomials of degree d with a well known list of exceptions. We generalize this theorem to arbitrary zero-dimensional schemes contained in a general union of double points. We work in the polynomial interpolation setting. In this framework our main result says that the affine space of polynomials of degree ?d in n variables, with assigned values of any number of general linear combinations of first partial derivatives, has the expected dimension if d≠2 with only five exceptional cases. If d=2 the exceptional cases are fully described.      14. Quadrature Rules for the Surface Integral of the Unit Sphere Based on Extremal Fundamental Systems      M. Reimer 《Mathematische Nachrichten》1994,169(1):235-241 Quadrature rules for the surface integral of the unit Sphere Sr–1 based on an extremal fundamental system, i.e., a nodal system which provides fundamental Lagrange interpolatory polynomials with minimal uniform norm, are investigated. Such nodal systems always exist; their construction has been given in earlier work. Here the main results is that the corresponding interpolatory quadrature for the space of homogeneous polynomials of degree two is equally weighted for arbitrary r, and hence positive. For the full quadratic polynomial space we can prove positivity of the weights, only.      15. Discrete Fourier Analysis on Fundamental Domain and Simplex of A d Lattice in d-Variables      Huiyuan Li  Yuan Xu 《Journal of Fourier Analysis and Applications》2010,16(3):383-433 A discrete Fourier analysis on the fundamental domain Ω d of the d-dimensional lattice of type A d is studied, where Ω2 is the regular hexagon and Ω3 is the rhombic dodecahedron, and analogous results on d-dimensional simplex are derived by considering invariant and anti-invariant elements. Our main results include Fourier analysis in trigonometric functions, interpolation and cubature formulas on these domains. In particular, a trigonometric Lagrange interpolation on the simplex is shown to satisfy an explicit compact formula and the Lebesgue constant of the interpolation is shown to be in the order of (log n) d . The basic trigonometric functions on the simplex can be identified with Chebyshev polynomials in several variables already appeared in literature. We study common zeros of these polynomials and show that they are nodes for a family of Gaussian cubature formulas, which provides only the second known example of such formulas.      16. The uniform norm of hyperinterpolation on the unit sphere in an arbitrary number of dimensions      T. Le Gia  I. H. Sloan 《Constructive Approximation》2001,17(2):249-265 In this paper we study the order of growth of the uniform norm of the hyperinterpolation operator on the unit sphere S r−1 ⊂ Rr. The hyperinterpolation approximation L n ƒ, where ƒ ∈ C(S r −1), is derived from the exact L 2 orthogonal projection Π ƒ onto the space P n r (S r −1) of spherical polynomials of degree n or less, with the Fourier coefficients approximated by a positive weight quadrature rule that integrates exactly all polynomials of degree ≤ 2n. We extend to arbitrary r the recent r = 3 result of Sloan and Womersley [9], by proving that under an additional “quadrature regularity” assumption on the quadrature rule, the order of growth of the uniform norm of the hyperinterpolation operator on the unit sphere is O(n r /2−1), which is the same as that of the orthogonal projection Πn, and best possible among all linear projections onto P n r (S r −1).      17. Weighted Approximation of Functions on the Unit Sphere      Yuan?XuEmail author 《Constructive Approximation》2004,21(1):1-28 The direct and inverse theorems are established for the best approximation in the weighted Lp space on the unit sphere of Rd+1, in which the weight functions are invariant under finite reflection groups. The theorems are stated using a modulus of smoothness of higher order, which is proved to be equivalent to a K-functional defined using the power of the spherical h-Laplacian. Furthermore, similar results are also established for weighted approximation on the unit ball and on the simplex of Rd.      18. Limiting Values under Scaling of the Lebesgue Function for Polynomial Interpolation on Spheres      L. Bos  S. De Marchi 《Journal of Approximation Theory》1999,96(2):366 We consider interpolation by spherical harmonics at points on a (d−1)-dimensional sphere and show that, in the limit, as the points coalesce under an angular scaling, the Lebesgue function of the process converges to that of an associated algebraic interpolation problem for the original angles considered as points in d−1.      19. On the bivariate hermite interpolation problem      H. V. Gevorgian  H. A. Hakopian  A. A. Sahakian 《Constructive Approximation》1995,11(1):23-35       20. A symmetry of sphere map implies its chaos*      Jerzy Jezierski  Wacław Marzantowicz 《Bulletin of the Brazilian Mathematical Society》2005,36(2):205-224 A well-known example, given by Shub, shows that for any |d| ≥ 2 there is a self-map of the sphere Sn, n ≥ 2, of degree d for which the set of non-wandering points consists of two points. It is natural to ask which additional assumptions guarantee an infinite number of periodic points of such a map. In this paper we show that if a continuous map f : Sn → Sn commutes with a free homeomorphism g : Sn → Sn of a finite order, then f has infinitely many minimal periods, and consequently infinitely many periodic points. In other words the assumption of the symmetry of f originates a kind of chaos. We also give an estimate of the number of periodic points. *Research supported by KBN grant nr 2 P03A 045 22.

Construction of spherical t-designs

Spherical t-designs are Chebyshev-type averaging sets on the d-dimensional unit sphere S ^d–1, that are exact for polynomials of degree at most t. The concept of such designs was introduced by Delsarte, Goethals and Seidel in 1977. The existence of spherical t-designs for every t and d was proved by Seymour and Zaslavsky in 1984. Although some sporadic examples are known, no general construction has been given. In this paper we give an explicit construction of spherical t-designs on S ^d–1 containing N points, for every t,d and N,NN ₀, where N ₀ = C(d)t ^{O(d 3}).     

On the Energy of a Unit Vector Field

The energy of a unit vector field on a Riemannian manifold M is defined to be the energy of the mapping M T ₁ M, where the unit tangent bundle T ₁ M is equipped with the restriction of the Sasaki metric. The constrained variational problem is studied, where variations are confined to unit vector fields, and the first and second variational formulas are derived. The Hopf vector fields on odd-dimensional spheres are shown to be critical points, which are unstable for M=S ⁵,S ⁷,..., and an estimate on the index is obtained.     

A note on stability results for scattered data interpolation on Euclidean spheres

The present work considers the interpolation of the scattered data on the d-sphere by spherical polynomials. We prove bounds on the conditioning of the problem which rely only on the separation distance of the sampling nodes and on the degree of polynomials being used. To this end, we establish a packing argument for well separated sampling nodes and construct strongly localized polynomials on spheres. Numerical results illustrate our theoretical findings. Dedicated to Professor Manfred Tasche on the occasion of his 65th birthday.     

On G 2 Continuous Spline Interpolation of Curves in ℝ d

In this paper the problem of G ² continuous interpolation of curves in ^d by polynomial splines of degree n is studied. The interpolation of the data points and two tangent directions at the boundary is considered. The case n = r + 2 = d, where r is the number of interior points interpolated by each segment of the spline curve, is studied in detail. It is shown that the problem is uniquely solvable asymptotically, e., when the data points are sampled regularly and sufficiently dense, and lie on a regular, convex parametric curve in ^d . In this case the optimal approximation order is also determined.     

Error estimates for Hermite interpolation on spheres

In this paper, we prove convergence rates for spherical spline Hermite interpolation on the sphere S^d−1 via an error estimate given in a technical report by Luo and Levesley. The functionals in the Hermite interpolation are either point evaluations of pseudodifferential operators or rotational differential operators, the desirable feature of these operators being that they map polynomials to polynomials. Convergence rates for certain derivatives are given in terms of maximum point separation.     

On partial polynomial interpolation

The Alexander-Hirschowitz theorem says that a general collection of k double points in Pⁿ imposes independent conditions on homogeneous polynomials of degree d with a well known list of exceptions. We generalize this theorem to arbitrary zero-dimensional schemes contained in a general union of double points. We work in the polynomial interpolation setting. In this framework our main result says that the affine space of polynomials of degree ?d in n variables, with assigned values of any number of general linear combinations of first partial derivatives, has the expected dimension if d≠2 with only five exceptional cases. If d=2 the exceptional cases are fully described.     

Quadrature Rules for the Surface Integral of the Unit Sphere Based on Extremal Fundamental Systems

Quadrature rules for the surface integral of the unit Sphere S^r–1 based on an extremal fundamental system, i.e., a nodal system which provides fundamental Lagrange interpolatory polynomials with minimal uniform norm, are investigated. Such nodal systems always exist; their construction has been given in earlier work. Here the main results is that the corresponding interpolatory quadrature for the space of homogeneous polynomials of degree two is equally weighted for arbitrary r, and hence positive. For the full quadratic polynomial space we can prove positivity of the weights, only.     

Discrete Fourier Analysis on Fundamental Domain and Simplex of A d Lattice in d-Variables

A discrete Fourier analysis on the fundamental domain Ω _d of the d-dimensional lattice of type A _d is studied, where Ω₂ is the regular hexagon and Ω₃ is the rhombic dodecahedron, and analogous results on d-dimensional simplex are derived by considering invariant and anti-invariant elements. Our main results include Fourier analysis in trigonometric functions, interpolation and cubature formulas on these domains. In particular, a trigonometric Lagrange interpolation on the simplex is shown to satisfy an explicit compact formula and the Lebesgue constant of the interpolation is shown to be in the order of (log n) ^d . The basic trigonometric functions on the simplex can be identified with Chebyshev polynomials in several variables already appeared in literature. We study common zeros of these polynomials and show that they are nodes for a family of Gaussian cubature formulas, which provides only the second known example of such formulas.     

The uniform norm of hyperinterpolation on the unit sphere in an arbitrary number of dimensions

In this paper we study the order of growth of the uniform norm of the hyperinterpolation operator on the unit sphere S ^r−1 ⊂ R^r. The hyperinterpolation approximation L _n ƒ, where ƒ ∈ C(S ^r −1), is derived from the exact L ² orthogonal projection Π ƒ onto the space P _n ^r (S ^r −1) of spherical polynomials of degree n or less, with the Fourier coefficients approximated by a positive weight quadrature rule that integrates exactly all polynomials of degree ≤ 2n. We extend to arbitrary r the recent r = 3 result of Sloan and Womersley [9], by proving that under an additional “quadrature regularity” assumption on the quadrature rule, the order of growth of the uniform norm of the hyperinterpolation operator on the unit sphere is O(n ^r /2−1), which is the same as that of the orthogonal projection Π_n, and best possible among all linear projections onto P _n ^r (S ^r −1).     

Weighted Approximation of Functions on the Unit Sphere

The direct and inverse theorems are established for the best approximation in the weighted L^p space on the unit sphere of R^d+1, in which the weight functions are invariant under finite reflection groups. The theorems are stated using a modulus of smoothness of higher order, which is proved to be equivalent to a K-functional defined using the power of the spherical h-Laplacian. Furthermore, similar results are also established for weighted approximation on the unit ball and on the simplex of R^d.     

Limiting Values under Scaling of the Lebesgue Function for Polynomial Interpolation on Spheres

We consider interpolation by spherical harmonics at points on a (d−1)-dimensional sphere and show that, in the limit, as the points coalesce under an angular scaling, the Lebesgue function of the process converges to that of an associated algebraic interpolation problem for the original angles considered as points in ^d−1.     

A symmetry of sphere map implies its chaos*

A well-known example, given by Shub, shows that for any |d| ≥ 2 there is a self-map of the sphere Sⁿ, n ≥ 2, of degree d for which the set of non-wandering points consists of two points. It is natural to ask which additional assumptions guarantee an infinite number of periodic points of such a map. In this paper we show that if a continuous map f : Sⁿ → Sⁿ commutes with a free homeomorphism g : Sⁿ → Sⁿ of a finite order, then f has infinitely many minimal periods, and consequently infinitely many periodic points. In other words the assumption of the symmetry of f originates a kind of chaos. We also give an estimate of the number of periodic points. *Research supported by KBN grant nr 2 P03A 045 22.