Near-optimal interpolation and quadrature in two variables: the Padua points

5th European Congress of Mathematics - Amsterdam, July 14-18 2008

Near-optimal interpolation and quadrature in two variables: 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, are the first known near-optimalpoint set forbivariate polynomial interpolation of total degree. Also the associatealgebraic cubature formulas are both, in some sense,near-optimal.

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²2) 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) = Tj^∗1(x1) Tj^∗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 the product 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 which areapproximate Fourier-Chebyshevcoefficients (with a correction for j = (n, 0))

Two differentfast algorithms(cf. [3, 5]) 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|

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^′jm^′j= 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. [3]) 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] L. BOS, S. DEMARCHI, M. VIANELLO ANDY. XU, Bivariate Lagrange interpolation at the Padua points: the ideal theory approach, Numer. Math. 108 (2007).

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

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

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

code available athttp://www.math.unipd.it/∼marcov/CAAsoft.html [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, published online 27 May 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).