Computing Fekete and Lebesgue points: simplex, square, disk

(1)

Computing Fekete and Lebesgue points: simplex,

square, disk

Alvise Sommariva

Universit`a degli Studi di Padova Dipartimento di Matematica Pura e Applicata

(2)

Collaborators/Group

Joint work with

I Matteo Briani, Luca Mezzalira, Marco Vianello (University of

Padua)

I Francesca Rapetti (University of Nice)

Other collaborators:

I Stefano De Marchi (University of Padua)

I Len Bos (University of Verona)

I Norman Levenberg (University of Indiana)

(3)

Purpose of our research

I Computation and analysis of good nodes for interpolation and

approximation in 2D and 3D.

I Computation and analysis of good nodes for cubature in 2D

and 3D.

(4)

Purpose of our research

and 3D.

(5)

Purpose of our research

and 3D.

(6)

Good interpolation sets

Let Ω ⊂ Rd be a compact domain. We denote by vdm(P) the

Vandermonde matrix (w.r.t. some polynomial basis {φk})

evaluated at the discrete set P. Classical good interpolation sets are:

I Fekete points (maximization of absolute value of

Vandermonde determinant).

I Leja points (known ξ1, . . . , ξk, the point ξk+1 maximizes

vdm(ξ1, . . . , ξk, x ), a generalization of the classical 1D Leja

points).

I Lebesgue points (minimization of Lebesgue constant, i.e. the

(7)

Approximate Fekete Points and Discrete Leja Points

Due to the theoretical difficulties, one tries to compute the Fekete, Leja or Lebesgue points {ξk} numerically.

Approximate Fekete Points and Discrete Leja Points are obtained

I Generating an admissible of weakly admissible mesh on the

compact domain Ω (i.e. sets satisfying a particular polynomial inequality).

I Extracting by linear algebra routines sets that mimic the

(8)

Approximate Fekete Points and Discrete Leja Points

Due to the theoretical difficulties, one tries to compute the Fekete, Leja or Lebesgue points {ξk} numerically.

Approximate Fekete Points and Discrete Leja Points are obtained

I Generating an admissible of weakly admissible mesh on the

compact domain Ω (i.e. sets satisfying a particular polynomial inequality).

I Extracting by linear algebra routines sets that mimic the

(9)

Approximate Fekete Points and Discrete Leja Points

(10)

Approximate Fekete Points and Discrete Leja Points

I Pros:

1. For mild degrees: fast computation of good points for interpolation on very general domains.

2. Many good meshes are known for simplex, squares, polygons, disk and some trivariate domains.

I Cons:

1. Possible difficulties in computing small admissible or weakly admissible meshes.

(11)

Approximate Fekete Points and Discrete Leja Points

I Pros:

1. For mild degrees: fast computation of good points for interpolation on very general domains.

2. Many good meshes are known for simplex, squares, polygons, disk and some trivariate domains.

I Cons:

1. Possible difficulties in computing small admissible or weakly admissible meshes.

(12)

Lebesgue constant

In this work, for a fixed degree N, we compute points

P = {ξ_k}_k=1,...,M on interval, simplex, square and unit disk that

have low Lebesgue constant ΛN(P).

Remember that ΛN(P) is the norm of the interpolation operator in

∞-norm and correspond to

ΛN(P) = max x ∈Ω M X k=1 |L_k(x )| where

• L_K are the Lagrange polynomials w.r.t P,

• M = bynomial(N + d, d) is the dimension of PN, the space of

(13)

Lebesgue constant

Some facts:

I There are sets {ξk}k=1,...,M that minimize the Lebesgue

constant (the so called Lebesgue points).

I At degree N, the Fekete points {ξk}k=1,...,M possess Lebesgue

constant less or equal than the cardinality M that in 2D is equal to (N + 1)(N + 2)/2. In general they do not minimize the Lebesgue constant.

I Let C (Ω) be the space of continuous functions in Ω. If

f ∈ C (Ω), pN the interpolant of f in P and p∗N ∈ PN is the

best approximant of f in PN than it is easy to show that

kf − p_Nk∞≤ (1 + ΛN(P))kf − pN∗k∞.

(14)

Lebesgue constant

Some facts:

kf − p_Nk∞≤ (1 + ΛN(P))kf − pN∗k∞.

(15)

Lebesgue constant

Some facts:

kf − p_Nk∞≤ (1 + ΛN(P))kf − p∗Nk∞.

(16)

Computation of Lebesgue/Fekete points

I Provide (almost) Fekete and Lebesgue points on simplex,

square and disk (N ≤ 18). By affine mapping, these points can be used on any simplex, parallelogram and ellipse.

I Provide freeware Matlab codes for the computation of these

(17)

Computation of Lebesgue/Fekete points

I Provide (almost) Fekete and Lebesgue points on simplex,

square and disk (N ≤ 18). By affine mapping, these points can be used on any simplex, parallelogram and ellipse.

I Provide freeware Matlab codes for the computation of these

(18)

Computation of Lebesgue points

The Lebesgue points P minimize the Lebesgue constant ΛN(P).

I We used fmincon (constrained minimization), fminsearch,

fminunc (unconstrained minimization) and the Differential Evolution algorithm for computing the (almost-)optimal sets.

I We use Matlab codes to compute the optimal points. Special

settings/strategies to avoid erratic behaviors.

I We consider a fine mesh T of about 62500 test points. At

degree N, the value target function F1 on a unisolvent set P is

(19)

Computation of Lebesgue points

(20)

Computation of Lebesgue points

(21)

Computation of Fekete points

The Fekete points P maximize the absolute value of the

determinant of the Vandermonde matrix V (P) = [φk(ξs)] with

respect to a basis {φk} of PN. Reminder: Fekete points do not

depend on the basis {φk}.

I As in the case of Lebesgue points, we used fmincon

(constrained minimization), fminsearch, fminunc

(unconstrained minimization) and the Differential Evolution algorithm for computing the (almost-)optimal sets.

I We use Matlab codes to compute the (almost-)optimal

points. Special settings/strategies to avoid erratic behaviors. Fekete points can be computed faster than Lebesgue points.

I At degree N, the value target function F2 on a set P of

(22)

Computation of Fekete points

(23)

Computation of Fekete points

(24)

Lebesgue/Fekete points on the simplex: literature

Many pointsets P on the simplex have been proposed in the literature. The best results were achieved by

I Heinrichs (2005) for the Lebesgue points .

I Taylor, Wingate, Vincent (2005) and Roth (2005) for the

Fekete points.

I Other works by Chen, Babuska (1995), Hesthaven (1998),

Blyth, Pozrikidis (2006), Warburton (2006) introduce non extremal pointsets.

(25)

Lebesgue/Fekete points on the simplex: literature

Fekete points.

(26)

Lebesgue/Fekete points on the simplex: literature

Fekete points.

(27)

Lebesgue/Fekete points on the simplex: new sets.

I General distribution (LEB).

I General distribution with Gauss-Legendre-Lobatto points on

the sides of the simplex (LEBGL).

I Symmetric distribution with Gauss-Legendre-Lobatto points

on the sides of the simplex (LEBGLS).

I Fekete points (FEK).

(28)

Lebesgue/Fekete points on the simplex: new sets.

(29)

Lebesgue/Fekete points on the simplex: new sets.

(30)

Lebesgue/Fekete points on the simplex: new sets.

(31)

Lebesgue/Fekete points on the simplex: results

Table: ΛN on the simplex. New sets: LEB, LEBGL, LEBGLS, FEK.

(32)

(Almost-)Lebesgue points on the simplex: a figure

(33)

Lebesgue/Fekete points on the square: Padua Points

The Padua points (at degree n) are defined as follows. Let Cn+1= {zj = cos ((j − 1)/n), j = 1, . . . , n + 1}

and

CEn+1 = {zj ∈ Cn+1, j − 1 even}

COn+1= {zj ∈ Cn+1, j − 1 odd}.

Then

Padn= (CEn+1× COn+2) ∪ (COn+1× CEn+2) ⊆ Cn+1× Cn+2.

The Lebesgue constant is O(log2_{(n)) (almost optimal). We can}

obtain new family of Padua points using Jacobi-Lobatto points

instead of Cn+1. We will denote by PdJ the Jacobi set with

(34)

Lebesgue/Fekete points on the square: results

Table: Lebesgue constants of some interpolation sets in the square.

(35)

(Almost-)Lebesgue points on the square: a figure

(36)

Lebesgue/Fekete points on the disk: results

Table: Lebesgue constants of (quasi)-Fekete and (quasi)-Lebesgue points in the unit disk.

(37)

(Almost-)Lebesgue points on the square: a figure

(38)

Lebesgue/Fekete points on the disk: distribution on

concentric circles

Table: Cardinality distribution (number of vertices of the regular polygons) on concentric circles of (quasi-)Fekete and (quasi-)Lebesgue points in the unit disk.

(39)

Lebesgue/Fekete points on the disk: some insight

See I. Yaman’s talk: Radially orthogonal multivariate basis function for a possible explanation of this particular distribution.

ALVANIA: S8.

(40)

References

I M. Briani, A. Sommariva, M. Vianello, Computing Fekete and

Lebesgue points : simplex, square, disk, submitted.

I J.L. Calvi and N. Levenberg, Uniform approximation by

discrete least squares polynomials, J. Approx. Theory, 152 (2008), pp.82-100.

I W. Heinrichs, Improved Lebesgue constants on the triangle, J.

Comp. Phys., 207 (2005), pp.625-638.

I F. Rapetti, A. Sommariva, M. Vianello, Computing symmetric

Lebesgue points on the triangle, submitted.

I A. Sommariva, M. Vianello, Computing approximate Fekete

points by QR factorizations of Vandermonde matrices, Comput. Math. Appl., 57 (2009), pp.1324-1336.

I M.A. Taylor, B.A. Wingate, R.E. Vincent, An algorithm for

(41)

Sets

Point sets are available at the homepage