Polynomial interpolation and algebraic cubature at the Padua points

10th International Symposium on Orthogonal Polynomials, Special Functions and Applications - Leuven, July 20-25 2009

Polynomial interpolation and algebraic cubature at the Padua points

M. C ^ALIARI

^a

, S. D ^E M ^ARCHI

^a

, A. S ^OMMARIVA

^b

^AND M. V ^IANELLO

^b

aDepartment of Computer Science, University of Verona, ITALY

bDepartment of Pure and Applied Mathematics, University of Padua, ITALY

Abstract

ThePadua points(recently studied during an international collaboration at theUniversity of Padua) give anear-optimal point set fortotal-degree polynomial interpolationand even foralgebraic cubature. We have developedfastinterpolation and cubaturealgorithmsinFortran/Matlabby representing the interpolant in the bivariateChebyshev orthogonal basis.

Which are the Padua points?

Chebyshev-Lobatto points in [−1, 1]

Cn+1:= {cos(jπ/n), j = 0, . . . , n}

card(Cn+1) = n + 1 = dim(P¹n) Padua points in [−1, 1] × [−1, 1]

Padn:= (C_n+1^odd× C_n+2^even) ∪ (C_n+1^even× C^odd_n+2) ⊂ Cn+1× Cn+2

card(Padn) =(n + 1)(n + 2)

2 = dim(P²n)

Alternative representationasself-intersectionsandboundary contactsof thegenerating curve

g(t) := (− cos((n + 1)t), − cos(nt)) , t ∈ [0, π]

FIGURE1. ^ThePadua pointswith theirgenerating curvefor n = 12 (left, 91 points) and n = 13 (right, 105 points), also asunion of two Chebyshev-Lobatto subgrids(red and blue bullets).

-1 -0,5 0 0,5 1

-1 -0,5 0 0,5 1

-1 -0,5 0 0,5 1

-1 -0,5 0 0,5 1

-1 -0,5 0 0,5 1

-1 -0,5 0 0,5 1

-1 -0,5 0 0,5 1

-1 -0,5 0 0,5 1

There are4 familiesof such points, corresponding to succes- siverotationsof 90 degrees.

Interpolation at the Padua points

trigonometric quadratureon thegenerating curve

⇓

algebraic cubatureat thePadua pointsξ∈ Padn

for theproduct Chebyshev measure dµ = dx1dx2

π²p(1 − x²₁)(1 − x²₂) withweights

wξ:= 1 n(n + 1)·







1/2 if ξ is a vertex point 1 if ξ is an edge point 2 if ξ is an interior point near-exactnessin P²2n

namely, exactness in P²2n∩ (span{T2n(x1)})^⊥dµ

⇓

Lagrange interpolation formula LPadnf (x) = X

ξ∈Padn

f (ξ) Lξ(x) , Lξ(η) = δξη

Lξ(x) = wξ[Kn(ξ, x)−Tn(ξ1)Tn(x1)]

Tn(·) = cos (n arccos (·)) and Kn(x, y)reproducing kernelof theproduct Chebyshev orthonormal basis

Θj(x) = T_j^∗1(x1) T_j^∗2(x2) , j = (j1, j2) , 0 ≤ |j| = j1+ j2≤ n Kn(x, y) =X

|j|≤n

Θj(x) Θj(y)

The Lebesgue constant

Unisolvencegives theprojection operator

LPadn: C([−1, 1]², k · k∞) → P²n([−1, 1]², k · k∞)

Theorem(interpolationstability, cf. [1]) kLPadnk = max

x∈[−1,1]²

X

ξ∈Padn

|Lξ(x)| = O(log²(n))

i.e., the Lebesgue constant hasoptimal order of growth[9].

Conjecture

x∈[−1,1]max² X

ξ∈Padn

|Lξ(x)|. 4

π² log²(n)

and themaxis attained at one of theverticesof the square.

Classical convergence estimate kLPadnf − f k∞≤ (1 + kLPadnk) min

p∈P²n

kf − pk∞= o(n^−p log²(n)) for f ∈ C^p([−1, 1]²), p > 0

Numerical implementation

Representationof the interpolant at the Padua points in theproduct Chebyshev orthonormal basis

LPadnf (x) = X

|j|≤n

c^′jΘj(x)

withcoefficients c^′j= cj:= X

ξ∈Padn

wξf (ξ) Θj(ξ) , c^′(n,0)= c(n,0)

2

Two differentfast algorithms(cf. [2, 4]) using

•optimized matrix subroutines

•2-dimensional Fast Fourier Transform (competitive and more stable atlarge degrees) Other features

•extensionto interpolation overrectangles

•practical convergence estimate

kLPadnf − f k∞/

n

X

|j|=n−2

|c^′j| kΘjk∞≤ 2

n

X

|j|=n−2

|c^′j|

• there is arecent applicationby the developers of themolecular simulationcodeCP2K[5]

Numerical results on interpolation

FIGURE2.Six test functions from the Franke-Renka-Brown test set [7];

top:F1, F2, F3;bottom:F5, F7, F8.

0.2 0 0.6 0.4 1 0.8 0

0.5 1 0 0.2 0.4 0.6 0.8 1 1.2 1.4

0 0.2 0.4 0.6 0.8 1

0 0.5 10 0.05 0.1 0.15 0.2 0.25

0 0.5

10 0.2 0.4 0.6 0.8 1

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4

0

0.5

10 0.2 0.4 0.6 0.8 1

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35

0 0.2 0.4 0.6 0.8 1

0 0.5 1

−2

−1 0 1 2 3

0 0.2 0.4 0.6 0.8 1

0 0.5 1 0 0.5 1 1.5 2 2.5

TABLE1.True and (estimated) interpolation errors for the test functions above.

n card(Padn) F1 F2 F3 F5 F7 F8

10 66 9E-2 4E-1 8E-3 4E-2 3E-1 1E-1

(2E-1) (6E-1) (6E-2) (2E-1) (1E+0) (4E-1)

20 231 7E-3 6E-2 1E-5 6E-5 8E-6 3E-3

(2E-2) (8E-2) (8E-5) (8E-4) (2E-4) (1E-2)

30 496 1E-4 1E-2 2E-8 1E-8 7E-13 2E-5

(8E-4) (1E-2) (1E-7) (2E-7) (2E-11) (1E-4)

40 861 3E-6 2E-3 2E-11 4E-13 4E-14 6E-8

(1E-5) (2E-3) (2E-10) (2E-11) (8E-15) (6E-7)

50 1326 1E-8 4E-4 1E-13 1E-15 7E-14 5E-11

(8E-8) (4E-4) (4E-13) (1E-15) (1E-14) (6E-10)

Nontensorial Clenshaw-Curtis cubature

• integration of the interpolant at the Chebyshev-Lobatto pointsgives the 1DClenshaw-Curtis quadratureformula

•integrationof the interpolant at thePadua pointsgives a 2D nontensorial Clenshaw-Curtis cubatureformula

I(f ) :=

Z Z

[−1,1]²

f (x) dx ≈ IPadn(f ) :=

Z Z

[−1,1]²

LPadnf (x) dx

= X

|j|≤n

c^′jmj= X

ξ∈Padn

λξf (ξ) , λξ:= wξ

X

|j|≤n

m^′jΘj(ξ)

(exactfor f ∈ P²n), via theChebyshev moments mj:=

Z Z

[−1,1]²

Θj(x) dx = Z 1

−1

Tj^∗1(t) dt Z 1

−1

Tj^∗2(t) dt

The cubatureweights{λξ} arenot all positive,nevertheless Theorem(cubaturestabilityandconvergence, cf. [8])

n→∞lim kIPadnk = lim

n→∞

X

ξ∈Padn

|λξ| = area of the square = 4

and I(f ) = IPadn(f ) + o(n^−p) for f ∈ C^p([−1, 1]²), p ≥ 0.

Numerical results on cubature

•near-optimality: onnon-entireintegrands, IPadn performs betterthan tensor-productGauss-Legendre quadrature and even than the few knownminimalformulas, see Fig. 3 right (similar to the well-known 1D phenomenon studied in [10])

•fast algorithm: computing theweightsby a suitablematrix formulation(cf. [2]) is very fast inMatlab/Octave(e.g. less than 0.01 sec at n = 100 on a 2.4Ghz PC)

FIGURE 3. Cubature errorsof tensorial and nontensorial cubature formulas versus thenumber of evaluations: CC=Clenshaw-Curtis, GL=Gauss-Legendre, MPX=Morrow-Patterson-Xu [11], OS=Omelyan-Solovyan (minimal) [6].

Left:f = (x1+ x2)²⁰; f = exp (x1+ x2); f = exp (−(x²1+ x²2))

Right:f = 1/(1 + 16(x²1+ x²2)); f = exp (−1/(x²1+ x²2)); f = (x²1+ x²2)^3/2

0 100 200 300 400 500 600

10⁻¹⁶ 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 10⁰

Number of points

Relative Cubature Error

OS pts.

Non tens. CC MPX pts.

Non tens. CC Padua pts.

Tens. CC pts.

Tens. GL pts.

0 100 200 300 400 500 600

10⁻⁷ 10⁻⁶ 10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰

Number of points

Relative Cubature Error

OS pts.

Non tens. CC MPX pts.

Non tens. CC Padua pts.

Tens. CC pts.

Tens. GL pts.

0 100 200 300 400 500 600

10⁻¹⁸ 10⁻¹⁶ 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴

Number of points

Relative Cubature Error

OS pts.

Non tens. CC MPX pts.

Non tens. CC Padua pts.

Tens. CC pts.

Tens. GL pts.

0 100 200 300 400 500 600

10⁻⁹ 10⁻⁸ 10⁻⁷ 10⁻⁶ 10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹

Number of points

Relative Cubature Error

OS pts.

Non tens. CC MPX pts.

Non tens. CC Padua pts.

Tens. CC pts.

Tens. GL pts.

0 100 200 300 400 500 600

10⁻¹⁶ 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻²

Number of points

Relative Cubature Error

OS pts.

Non tens. CC MPX pts.

Non tens. CC Padua pts.

Tens. CC pts.

Tens. GL pts.

0 100 200 300 400 500 600

10⁻⁹ 10⁻⁸ 10⁻⁷ 10⁻⁶ 10⁻⁵ 10⁻⁴ 10⁻³ 10⁻²

Number of points

Relative Cubature Error

OS pts.

Non tens. CC MPX pts.

Non tens. CC Padua pts.

Tens. CC pts.

Tens. GL pts.

References

[1] L. BOS, M. CALIARI, S. DEMARCHI, M. VIANELLO ANDY. XU, Bivariate Lagrange in- terpolation at the Padua points: the generating curve approach, J. Approx. Theory 143 (2006).

[2] M. CALIARI, S. DEMARCHI, A. SOMMARIVA ANDM. VIANELLO, Fast interpolation and cubature at the Padua points in Matlab/Octave, submitted.

[3] M. CALIARI, S. DEMARCHI ANDM. VIANELLO, Bivariate polynomial interpolation on the square at new nodal sets, Appl. Math. Comput. 162 (2005).

[4] M. CALIARI, S. DEMARCHI ANDM. VIANELLO, Padua2D: Lagrange Interpolation at Padua Points on Bivariate Domains, ACM Trans. Math. Software 35-3 (2008).

[5] CP2K: a freely available (GPL) program in Fortran 95 to perform atomistic and molec- ular simulations (web site: http://cp2k.berlios.de).

[6] I.P. OMELYAN ANDV.B. SOLOVYAN, Improved cubature formulae of high degree of exactness for the square, J. Comput. Appl. Math. 188 (2006).

[7] R.J. RENKA ANDR. BROWN, Algorithm 792: Accuracy tests of ACM algorithms for interpo- lation of scattered data in the plane, ACM Trans. Math. Software 25 (1999).

[8] A. SOMMARIVA, M. VIANELLO ANDR. ZANOVELLO, Nontensorial Clenshaw-Curtis cu- bature, Numer. Algorithms 49 (2008).

[9] L. SZILI ANDP. VERTESI, Some New Theorems on Multivariate Projection Operators, C.R.

Acad. Bulgare Sci. 61 (2008).

[10] L.N. TREFETHEN, Is Gauss quadrature better than Clenshaw-Curtis?, SIAM Rev. 50 (2008).

[11] Y. XU, Lagrange interpolation on Chebyshev points of two variables, J. Approx. Theory 87 (1996).