Bivariate interpolation at Xu points

Bivariate interpolation at Xu points

L. B OS ^a , M. C ALIARI ^b , S. D E M ARCHI ^b , AND M. V IANELLO ^c

a

Department of Mathematics and Statistics, University of Calgary, CANADA

b

Department of Computer Science, University of Verona, ITALY

c

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

Abstract In [5], Y. Xu proposed a set of Chebyshev-like points for poly- nomial interpolation on the square [−1, 1]

²

. We have recently proved that the Lebesgue constant of these points grows like log

²

(n), n being the de- gree, as with the best known points for the square, and we have imple- mented an accurate version of their Lagrange interpolation formula at lin- ear cost; see [1, 2]). Here we construct non-polynomial Xu-like interpo- lation formulas on bivariate compact domains with various geometries.

Applications to regular surface compression are presented.

1 Polynomial interpolation at Xu points

Given the Chebyshev-Lobatto points on the interval [−1, 1]

ξ

k

= ξ

k,n

= cos kπ

n , k = 0, . . . , n, n = 2m ,

the Xu interpolation points on the square Q = [−1, 1]

²

are the two- dimensional Chebyshev array X

N

= {z

r,s

} of dimension N = n(n + 2)/2

z

2i,2j+1

= (ξ

2i

, ξ

2j+1

), 0 ≤ i ≤ m, 0 ≤ j ≤ m − 1 , z

_2i+1,2j

= (ξ

2i+1

, ξ

2j

), 0 ≤ i ≤ m − 1, 0 ≤ j ≤ m . The Xu interpolant of degree n in Lagrange form of a function f on Q is

L

^Xu_n

f (x) = X

zr,s∈XN

f (z

r,s

)`

n

(x, z

r,s

), `

n

(x, z

r,s

) := K

_n^∗

(x, z

r,s

) K

_n^∗

(z

r,s

, z

r,s

) ,

K

n^∗

(z

r,s

, z

r,s

) = 1

2 (K

n

(z

r,s

, z

r,s

) + K

n+1

(z

r,s

, z

r,s

)) − 1 , K

n

(x, y) = D

n

(θ

1

+ φ

1

, θ

2

+ φ

2

) + D

n

(θ

1

+ φ

1

, θ

2

− φ

2

) +

+ D

n

(θ

1

− φ

1

, θ

2

+ φ

2

) + D

n

(θ

1

− φ

1

, θ

2

− φ

2

) , x = (cos θ

1

, cos θ

2

), y = (cos φ

1

, cos φ

2

) , where the function D

n

is defined by

D

n

(α, β) = 1 2

cos((n − 1/2)α) cos(α/2) − cos((n − 1/2)β) cos (β/2)

cos α − cos β .

• Drawback: numerical instability.

• Stabilization:

D

n

(α, β) = 1

4 (U

n−1

(cos φ)U

n−1

(cos ψ) + U

n−2

(cos φ)U

n−2

(cos ψ)) , with φ = (α − β)/2, ψ = (α + β)/2, U

n

Chebyshev polynomial of the second kind computed by the three-term recurrence, with

overall computational cost ≈ 8nN

• Hybrid stable formula for U

n

(cos θ): three-term recurrence if |θ − kπ| ≤ ε, otherwise U

n

(cos θ) = sin (n + 1)θ/ sin θ. For ε = 0.01, L

^Xu_n

f (x) is computed at machine precision, the recurrence relation is used globally less than 1%, and for degrees n up to the hundreds,

overall computational cost ≈ 32c

sin

N c

sin

the average evaluation cost of the sine function.

Thus, in practical applications the computational cost becomes linear in the number N of Xu points.

2 The Lebesgue constant of the Xu points

FIGURE1. Left: the distribution of N = 144 (deg n = 16) Xu-like points on Q. Right: the behavior of the Lebesgue constant of the Xu points up to degree n = 100.

T

HEOREM

1 Λ

^Xun

≤ 8

_π²

log n + 5

²

+

³₄

.

R

EMARK

. The Lebesgue constant of the Xu points has the same order of growth as the Padua points (the best known on Q, cf. [3]).

TABLE1.Lebesgue constants size of different nodal sets on Q: Morrow-Patterson (MP), Extended Morrow-Patterson (EMP), Padua points (PD), Xu points.

interp. pts. Λ34 Λ48 Λ62 Λ76

MP 649 1264 2082 3102

EMP 237 456 746 1106

PD 11 13 14 15

XU 10 12 13 14

3 Beyond the square: extensions

Consider a surjective map σ : Q → K , t = (t

1

, t

2

) 7→ x = (x

1

, x

2

) , with “inverse” σ

⁻¹

: K → Q , σ

⁻¹

(x) = t(x) ∈ ← − σ (x) , where t(x) denotes a point selected in some manner from the inverse image ← − σ (x). By interpolating the composition g = f ◦ σ at the Xu points in Q, we get a (in general) non-polynomial interpolation formula

L

^Xu_n

f (x) = L

^Xu_n

g(σ

⁻¹

(x)) , g = f ◦ σ , x ∈ K , Thus, f will be sampled at the Xu-like points K 3 x

r,s

= σ(z

r,s

) .

• Key feature: smoothness of the transformation σ.

3.1 Generalized rectangles

K = {x = (x

1

, x

2

) : a ≤ x

1

≤ b , φ(x

1

) ≤ x

2

≤ ψ(x

1

)} , φ and ψ being suitable functions.

FIGURE2.The distribution of N = 144 Xu-like points (deg n = 16) in two generalized sectors.

TABLE2.Xu-like interpolation errors of f(x1, x2) = sin (x²1+ x²2)on the generalized rectangles of Fig. 2.

n 8 16 24 32 40

N 40 144 312 544 840

K1 1E-2 2E-5 1E-8 4E-12 5E-14 K2 3E-2 2E-4 2E-6 4E-9 3E-11

3.2 Generalized sectors and starlike domains

• Generalized sectors

K = {x = (ρ cos θ, ρ sin θ) : θ

1

≤ θ ≤ θ

2

, ρ

1

(θ) ≤ ρ ≤ ρ

2

(θ)} ,

• Starlike domains

K = {x = (ρ cos θ, ρ sin θ) : 0 ≤ θ ≤ 2 π , 0 ≤ ρ ≤ r(θ)}

= {x = (ρ cos θ, ρ sin θ) : 0 ≤ θ ≤ π , −r(θ + π) ≤ ρ ≤ r(θ)} .

FIGURE3. The distribution of N = 144 Xu-like points (deg n = 16) in the unit disk in polar (left) and starlike-polar (right) coordinates.

FIGURE4.The distribution of N = 144 Xu-like points (deg n = 16) in starlike-polar coordinates:

cardioid (left), four-leaf clover (right).

TABLE3.Xu-like interpolation errors of f(x1, x2) = cos (x1+ x2)on the unit disk in Cartesian, standard polar and “starlike polar” coordinates; n is the underlying polynomial degree, N = n(n + 2)/2the corresponding number of Xu-like interpolation points.

n 8 16 24 32 40

N 40 144 312 544 840

Cartesian 6E-2 2E-2 6E-3 3E-3 4E-3 polar 1E-1 3E-3 2E-5 1E-7 3E-10 starlike 1E-2 1E-5 4E-9 5E-13 2E-14

4 Surface compression from scattered data by

“interpolated interpolations”

We consider the problem of compressing a surface, given as a large scat- tered data set. This problem can be addressed in several ways, for example by multiresolution methods using splines or radial basis functions. Here we adopted

• Xu-like interpolation of a cubic Shepard-like interpolant (cf. [4]) The compression ratio obtained is

compr. ratio = 3 × numb. of scatt. pts.

numb. of Xu nodes ≈ 6 × numb. of scatt. pts.

n

²

,

where n is the underlying polynomial degree.

TABLE4. Compression errors (in sup-norm) for the Franke test function on [0, 1]², sampled at randomly generated point sets; last row and column: actual errors of the Xu and Shepard-like interpolants on the test function.

random pts. n = 16 n = 24 n = 32 n = 40 n = 48 “true” Shep.

5000 3E-2 2E-3 1E-4 7E-5 1E-4 2E-4

10000 3E-2 2E-3 1E-4 6E-5 4E-5 7E-5

20000 3E-2 2E-3 1E-4 1E-5 3E-5 3E-5

40000 3E-2 2E-3 1E-4 3E-6 8E-6 8E-6

“true” Xu 3E-2 2E-3 1E-4 3E-6 5E-8

TABLE5.The compression ratios corresponding to the example above.

random pts. n = 16 n = 24 n = 32 n = 40 n = 48

5000 104:1 48:1 28:1 18:1 13:1

10000 208:1 96:1 55:1 36:1 25:1

20000 416:1 192:1 110:1 71:1 50:1

40000 832:1 385:1 221:1 143:1 100:1

4.1 Compression of a Finite Element PDE solution

• Poisson equation with Dirichlet boundary conditions

 ∆f (x) = −10 , x ∈ Ω f (x) = 0 , x ∈ ∂Ω where Ω is the “lynx-eye” shaped domain in Fig. 5.

• Finite Element discretization on a Delaunay mesh with 81796 trian- gles and 41402 nodes.

• Xu-like interpolation of the Finite Element solution.

FIGURE5. Left: the distribution of N = 312 Xu-like points (deg n = 24) in the “lynx-eye”

shaped domain. Right: a detail of the Finite Element mesh in the domain above, near the internal boundary.

TABLE6. Compression errors (in the max-norm) for the Finite Element solution of the Poisson equation above.

mesh size n = 8 n = 12 n = 16 n = 20 n = 24 n = 28 n = 32

41402 1E-1 3E-2 1E-2 5E-3 2E-3 1E-3 1E-3

FIGURE6. Plot of the Xu-like interpolated solution (deg n = 24: compression ratio ≈ 400 : 1, compression error ≈ 2 · 10⁻³).

References

[1] L. BOS, M. CALIARI, S. DE MARCHI AND M. VIANELLO, A numerical study of the Xu polynomial interpolation formula, submitted (2004); code available at http://profs.sci.univr.it/∼caliari/software.htm.

[2] L. BOS, S. DEMARCHI ANDM. VIANELLO, The Lebesgue constant of the Xu interpolation points, submitted (2004).

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

[4] R.J. RENKA, Algorithm 790: CSHEP2D: Cubic Shepard Method for Bivariate Interpolation of Scattered Data, ACM Trans. Math. Software, 25 (1999), pp. 70–73.

[5] Y. XU, Lagrange interpolation on Chebyshev points of two variables, J. Approx. Theory, 87 (1996), pp. 220–238.