Interpolation and Cubature on the Sphere

Rob Womersley

What is the best choice of points on the sphere for
polynomial interpolation and interpolatory cubature?

Contents

1. Notation
2. Point Sets
3. Mesh Norms
4. Interpolation Norms
5. Condition numbers and eigenvalues
6. Uniform errors in approximations
7. Cubature weights
8. Related publications
9. Related web sites
• n = degree of interpolating polynomial.
• Pn = space of all spherical polynomials of degree at most n.
• dn = dimension of Pn
• dn = number of interpolation points in a fundamental system for Pn
• dn = (n+1)2 for S2
• A system of dn points is a fundamental system if and only if the only polynomial of Pn which is zero at all points is the zero polynomial.
• G = dn by dn  Gram matrix from reproducing kernel basis;
• Gij = Gn(< xi, xj >) where Gn(z) is the reproducing kernel for Pn.
• Gij depends only on the angle between the points xi and xj, so G is symmetric.
• G is positive semi-definite for any set of dn points.
• G is positive definite if and only if {xj, j = 1,...,dn} is a fundamental system.
• Gjj = dn / |S2| for j = 1,...,dn and any point set.
• The vector of reproducing kernel polynomials is g : S2 -> Rdn where
gj(x) = Gn ( < xj, x>) for j = 1,...,dn and x in S2.
• Associated with each point xj of a fundamental system is the Lagrange polynomial Lj in Pn, determined by
Lj(xj) = 1 for j = 1,...,dn  and   Lj(xi) = 0, for i not equal to j
• For a fundametnal system Lj(x) = (G-1  g(x))j.
• The vector of Lagrangians is l(x) = G-1  g(x).
• The norms of the vector of Lagrangians of interest are
• the 1-norm || l (x) ||1,
• the 2-norm || l (x) ||2,
• the max-norm || l (x) ||infinity.
• ||Ln|| = norm of the interpolation operator Ln as a map from C(S2) to  C(S2),
• ||Ln|| = maxx in S2   || l(x) ||1.
• The eigenvalues of the Gram matrix G are
• lmin = smallest eigenvalue of the matrix G,
• lavg = average eigenvalue of the matrix G = trace G / dn  = dn / |S2| =  dn / (4 p),
• lmax = largest eigenvalue of the matrix G
• The 2-norm condition number of G is lmax / lmin
•  R = sqrt(dn) sqrt(lavg / lmin)  =  Reimer's upper bound on ||Ln||,
• Cubature weights wj, j = 1,...,dn, such that the rule

Q(f) = sum_{j=1}^{dn}   wj f(xj)

is exact for all polynomials in Pn are given by the solution of

Gw = e,
where e is the vector of all ones.
• As cubature rule is exact for constant polynomials the average cubature weight is
wavg = eT w / dn = |S2| / dn.
• For comparison it is easier to consider the scaled cubature weights wj / wavg.
• Spherical n-designs are equal weight cubature rules with m <= dn points which are exact for all polynomials of degree less than or equal to n.
• Fundamental systems with wj / wavg = 1 for j = 1,...,dn are spherical n-desigins.
• Mesh norm h = max_{x in S2} min_{j = 1,...,dn} dist(x, xj)  where
• Geodesic distance between x and y in S2 is dist(x, y) = cos-1(<x, xj>),
• The mesh norm is the covering radius for convering S2 with spherical caps of radius h centered at each point xj for j = 1,...,dn.
• The mesh norm function is  min_{j=1,...,dn}   cos-1 (< x, xj>) for x in S2
• Potential energy (PE) is

sum_{i=1}^dn   sum(j=i+1}^dn  1/|| xi - xj ||2

• || xi - xj ||22 = 2(1 - < xi, xj >)
• The minimum distance (angle) between the points xj, j = 1,...,dn

min_{i, j = 1,...,dn} cos-1 (< xi, xj >)

is twice the packing radius for spherical caps centred at each of the points.

Point Sets

Click on the following links to obtain images or tables of different point sets. Point sets obtained by the four criteria below have very different characteristics, the differences being generally not understood theoretically.

• Each set of interpolation points has dn points xj, j = 1,...,dn on S2.
• Point sets are normalized so that the first point is at the north pole (theta = 0, phi irrelevant) and the second point is on the prime meridian (phi = 0). <

Caveat: All point sets are only approximate local optimizers of their respective criteria.

Recent point sets

For these point sets attempts to find global optima have been made, but with decreasing reliability as the degree n of the polynomials increases.

Point Sets from the "How Good ... " paper

 Code Points, Data and Images Criterion ME Minimum Energy points Minimize the potential energy (from Fliege and Maier) MD Maximum Determinant points Maximizime det(G) EV Eigenvalue points Maximize lmin, the smallest eigenvalue of G MN Minimum Norm points Minimize ||Ln||, the interpolation operator norm

The mesh norm gives a measure of how geometrically well distirbuted the points on the sphere are.

Interpolation norms

The norm of the ploynomial interpolation operator, as a map from C(S2) to C(S2), gives a bound on the quality of the polynomial interpolant.

Points with small mesh norm do not necessarily correspond to points with low interpolation norm.

Some point sets, like the minimal energy points sets of Fliege and Maier and the generlaized spiral points, have interpolation matrices which are very close to singular, making it numerically difficult to accuratley solve the linear system for the interpolation weights. A very small eigenvalue also makes the Reimers bound R on the Lebesgue constant is large. Plot of the condition number, largest and smallest eigenvalues for the ME, EV, MD and MN points

To illustrate the effect that a poor choice of interpolation points can have, the interpolants and the errors in the interpolation are plotted for the minimum energy (ME) and minimum norm (MN) points for the cosine cap.

Cubature weights w so that the rule Q(f) is exact for all polynomials of degree at most n are given by G*w = e. These weights may not be positive for any given point set. However the maximum determinant point set numerically has positive weights. As the weights sum to give the surface area of the sphere, the plots show the minimum and maximum of the scaled weights wj / wavg.

• Ian H. Sloan and Robert S. Womersley, Extremal systems of points and numerical integration on the Sphere, Advances in Computational Mathematics 21 (2004) 102-125.
Applied Mathematics Report AMR15-01, School of Mathematics, University of New South Wales. Gzipped postscript extremal.ps.gz (339 Kb), PDF: extremal.pdf (354 Kb),
• Ian H. Sloan and Robert S. Womersley, Good approximation on the sphere, with application to geodesy and the scattering of sound, Jounral of Computational and Applied Mathematics 149 (2002) 227-238.
• Robert S. Womersley and Ian H. Sloan, How Good can Polynomial Interpolation on the Sphere be?, Advances in Computational Mathematics 14 (2001) 195-226.
• Robert S. Womersley, A continuous minimax problem for calculating minimum norm polynomial interpolation points on the sphere, ANZIAM Journal 42 (E), (2000) C1536--C1557.
• Ian H. Sloan and Robert S. Womersley, The search for good polynomial interpolation points on the sphere, in: D. F. Griffiths and G. A. Watson eds., Numerical Analysis 1999 CRC Press LLC (2000) 211-230.
• Ian H. Sloan and Robert S. Womersley, The Uniform Error of Hyperinterpolation on the Sphere, in: K. Jetter, W. Haussmann and M. Reimer eds. Advances in Multivariate Approximation, (1999) 289-306. Postscript version hyperr.ps (456Kb), Gzipped postscript version hyperr.ps.gz (200Kb)
• Ian H. Sloan and Robert S. Womersley, Constructive Approximation on the Sphere, Journal of Approximation Theory, 103, 1 (2000) 91-118.
• Ian H. Sloan, Interpolation and hyperinterpolation on the sphere, in: W. Haussmann, K. Jetter and M. Reimer eds., Multivariate Approximation: Recent Trends and Results, Akademie Verlag GmbH, Berlin (1997) 255-268.
• Ian H. Sloan, Polynomial interpolation and hyperinterpolation over general regions, Journal of Approximation Theory 83 (1995) 238-254.