Polynomial Admissible Meshes

Polynomial Admissible Meshes

S. De Marchi, F. Piazzon, A. Sommariva and M. Vianello

Dept. of Mathematics University of Padova fpiazzon@math.unipd.it

Definition

Let K ⊂ C ^d (or R ^d ) be a compact polynomial determining set. A sequence {A _n } of its subsets is said to be a weakly admissible mesh (WAM) of constant C ⁿ if

i) max ^K |p| ≤ C _n max _A

_n

|p| for any polynomial p such that deg p ≤ n, ii) Card(A ⁿ ) and C ⁿ grow at most polynomially w.r.t. n.

If sup n A _n =: C < ∞ then A ⁿ is said an admissible mesh (AM). If fur- thermore Card(A ⁿ ) = O(n ^d ) then {A ⁿ } is termed optimal.

Relevant (univariate) examples

ˆ Chebyshev-Lobatto nodes. For an interval [a, b], X ⁿ (a, b) =

 _b−a

2 ξ _j + ^b+a ₂

, where ξ ^j = cos (jπ/n) , 0 ≤ j ≤ n.

ˆ Chebyshev nodes. Z _n (a, b) =  _b−a

2 η _j + ^b+a ₂ , where η ^j = cos 

(2j+1)π 2(n+1)



, 0 ≤ j ≤ n.

ˆ Chebyshev-like subperiodic angular nodes. Θ _n (α, β) = ϕ _ω (Z _2n (−1, 1)) + ^α+β ₂ ⊂ (α, β) , ω = ^β−α ₂ ≤ π, where ϕ ^ω (s) = 2 arcsin sin ^ω ₂
s

The following inequalities hold with c ⁿ = _π ² log(n + 1) + 1 . kpk _[a,b] ≤ c _n kpk _X

_n

∀p ∈ P ¹ _n .

kpk _[a,b] ≤ c _n kpk _Z

_n

∀p ∈ P ¹ _n . ktk _[α,β] ≤ c _2n ktk _Θ

_n

∀t ∈ T ¹ _n .

Basic Properties

ˆ Any ane transformation of a WAM is still a WAM, C ⁿ being in- variant;

ˆ Any sequence of unisolvent interpolation sets whose Lebesgue con- stant Λ ⁿ grows at most polynomially with n is a WAM, with constant C _n = Λ _n ;

ˆ A nite product of WAMs is a WAM on the corresponding product of compacts, C ⁿ being the product of the corresponding constants;

ˆ A nite union of WAMs is a WAM on the corresponding union of compacts, C ⁿ being the maximum of the corresponding constants.

Applications

ˆ Polynomial least squares tting. Theoretical and numerical bounds for the projection operator norm available.

ˆ Discrete orthonormal polynomials computation and tting, with al- gorithm for computing a stable basis.

ˆ Extraction of unisolvent interpolation nodes with slow growth of Lebesgue constant.

ˆ Collocation methods for PDEs.

convex set, lune, polygon, Lissajous WAM

−0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8

−1.5

−1

−0.5 0 0.5 1 1.5

−1.5 −1 −0.5 0 0.5 1

−0.8

−0.6

−0.4

−0.2 0 0.2 0.4 0.6 0.8

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

−1 0

1

−1

−0.5 0 0.5 1

−1

−0.8

−0.6

−0.4

−0.2 0 0.2 0.4 0.6 0.8 1

References

[1] L. Bos, S. De Marchi, A. Sommariva, and M. Vianello. Weakly admissible meshes and discrete extremal sets. Numer. Math. Theory Methods Appl., 4(1):112, 2011.

[2] J.P. Calvi and N. Levenberg. Uniform approximation by discrete least squares polynomials. JAT, 152:82100, 2008.

[3] S. De Marchi, F. Piazzon, A. Sommariva, and M. Vianello. Polynomial meshes:

Computation and approximation. Proceeedings of CMMSE 2015, to appear.

[4] F. Piazzon. Optimal polynomial admissible meshes on compact subsets of R

^d

with mild boundary regularity. submitted to JAT, underr revision, arXiv:1302.4718, 2013.

[5] F. Piazzon and M. Vianello. Small perturbations of admissible meshes. Appl. Anal., 92, 2013.

[6] F. Piazzon and M. Vianello. Computing optimal polynomial meshes on planar starlike domains. Dolomites Res. Notes Approx. DRNA, 7:2225, 2014.

Constructing WAMs

The bilinear transformation σ(s ₁ , s ₂ ) = 1

4 ((1 − s ₁ )(1 − s ₂ )v ₁ + (1 + s ₁ )(1 − s ₂ )v ₂ + (1 + s ₁ )(1 + s ₂ )v ₃ + (1 − s ₁ )(1 + s ₂ )v ₄

maps the square [−1, 1] ² onto the convex quadrangle with vertices v ₁ , v ₂ , v ₃ , v ₄ ; with a triangle, e.g. v ³ = v ₄ , as a special degenerate case.

Proposition 1 (Quadrangles and Triangles). The sequence A ⁿ = σ(X _n (−1, 1) × X _n (−1, 1)) is a WAM of the convex quadrangle σ([−1, 1] ² ) , with constant C ⁿ = c ² _n = O(log ² n) and card(A ⁿ ) ≤ (n + 1) ² .

Proposition 2 (Polygons). Let K be a polygon with ` sides. Then K has a WAM given by the union of the WAMs of ` − 2 triangles of a minimal triangulation, with constant C ⁿ = c ² _n = O(log ² n) and Card(A ⁿ ) ∼ (` − 2)n ² .

The blending transformation

ψ _u,v (s, θ) = su(θ) + (1 − s)v(θ),

maps [0, 1] × [α, β] onto the region K ^u,v lying between u and v, where u(θ) = a ₁ cos(θ)+b ₁ sin(θ)+c ₁ , v(θ) = a ² cos(θ)+b ₂ sin(θ)+c ₂ , θ ∈ [α, β], a _i = (a _i1 , a _i2 ) , b ⁱ = (b _i1 , b _i2 ) , c ⁱ = (c _i1 , c _i2 ) , i = 1, 2, with a ⁱ , b _i not all zero and [α, β], 0 < β − α ≤ 2π.

Proposition 3 (Circular sections). The sequence A ⁿ = ψ _u,v (X _n (0, 1) × Θ _n (α, β)) is a WAM for K ^u,v with C ⁿ = O(log ² n) and Card(A ⁿ ) ≤ (n + 1)(2n + 1) .

Similar results are available in higher dimension e.g. for cylinders, cones, pyramids and solids of rotation.

Proposition 4 (Star-like UIBC bodies). Let K ⊂ R ² be the closure of a star-like domain satisfying the Uniform Interior Ball Condition (UIBC) of parameter ρ > 0. Then, for every xed α ∈ (0, 1/ √

2) , K has an optimal admissible mesh {A ⁿ } such that C ⁿ ≡

√ 2 1−α √

2 , Card A ⁿ ∼ n 2 length(∂K) αρ .

Finally, WAMS have been shown to be stable under small perturbations and moreover WAMs can be computed on sets that are images under smooth maps of sets where a WAM is given.

Lissajous WAMS in the cube

Z

[−1,1]

³

p(x) dx

p(1 − x ² ₁ )(1 − x ² ₂ )(1 − x ² ₃ ) = π ²

Z π 0

p(` _n (θ)) dθ , ∀p ∈ P ³ _2n , where we used the Lissajous curve

` _n (θ) = (cos(α _n θ), cos(β _n θ), cos(γ _n θ)), θ ∈ [0, π], (α _n , β _n , γ _n ) =

( 3

4 n ² + ¹ ₂ n, ³ ₄ n ² + n, ³ ₄ n ² + ³ ₂ n + 1
, n even,

3

4 n ² + ¹ ₄ , ³ ₄ n ² + ³ ₂ n − ¹ ₄ , ³ ₄ n ² + ³ ₂ n + ³ ₄
, n odd .

Proposition 5 (Lissajous WAMs by hyperinterpolation). The sequence {A _n } = {` _n (sπ/ν)} , s = 0, . . . , ν = nγ ⁿ + 1 is a WAM for the cube, with C _n = O(log ³ n) and Card A ⁿ ∼ ³ ₄ n ³ .

Compression and interpolation sets

Proposition 6. Let {A ⁿ } be a WAM of a compact set K ⊂ R ^d with Card A _n > N _2n = dim(P ²ⁿ ) and constant C ⁿ . Then there exists (and can be numerically computed) a WAM A ^∗ n ⊂ A _n with Card A ^∗ n ≤ N _2n with constant C _n ^∗ = C _n √

Card A _n .

It is possible to extract unisolvent interpolation sets from a WAM by nu- merical linear algebra, namely approximate Fekete points (AFP) by QR and Discrete Leja Sequences (DLS) by LU factorization.

Proposition 7. Let F ⁿ = {ξ _i

1

, . . . , ξ _i

N

} the AFP or DLP extracted from a WAM of a compact set K ⊂ R ^d (or K ⊂ C ^d ). Then lim _{n→∞ N} ¹ P N

k=1 f (ξ _i

k

) = R

K f (x) dµ _K for every f ∈ C (K), where µ ^K

is the pluripotential equilibrium measure of K.