• Non ci sono risultati.

Good Points for Multivariate Polynomial Approximation

N/A
N/A
Protected

Academic year: 2021

Condividi "Good Points for Multivariate Polynomial Approximation"

Copied!
1
0
0

Testo completo

(1)

Dolomites Research Week on Approximation 2010 (DRWA10) Alba di Canazei (Trento, Italy), Sept. 6-9 2010

Good Points for Multivariate Polynomial Approximation

L. B OS

a

, S. D E M ARCHI

b

, 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

Weakly Admissible MeshesandDiscrete Extremal Sets(com- puted by basic numerical linear algebra) give new tools for multivariatepolynomialleast squaresandinterpolationon multidimensional compact sets.

Fekete Points

K⊂ Rd(or Cd)compact set (notation: kf kK= maxx∈K|f (x)|) p={pj}1≤j≤N, N = dim(Pdn(K))polynomial basis

ξ={ξ1, . . . , ξN} ⊂ Kinterpolation points

V(ξ, p) = [pji)]Vandermonde matrix, det(V ) 6= 0 Πnf(x) =PN

j=1f(ξj) ℓj(x)determinantal Lagrange formula ℓj(x) = det(V (ξ1, . . . , ξj−1, x, ξj+1, . . . , ξN))

det(V (ξ1, . . . , ξj−1, ξj, ξj+1, . . . , ξN)), ℓji) = δij Fekete points: |det(V (ξ1, . . . , ξN))| ismaxin KN

=⇒Lebesgue constant= Λn= max

x∈K N

X

j=1

|ℓj(x)| ≤ N

Fekete points(and Lebesgue constants) are independentof the choice of the basis

Fekete pointsare analytically known only in afew cases:

interval: Gauss-Lobatto points, Λn=O(log n) complex circle: equispaced points, Λn=O(log n) cube: for tensor-product polynomials, Λn=O(logdn) recent important result:

Fekete pointsare asymptoticallyequidistributedwith respect to the pluripotentialequilibrium measureof K (cf. [1]) essentially open problems:

•asymptotic spacingin the multivariate case (cf. [5])

•efficient computation, even in the univariate complex case (large scaleoptimization problem inN× d variables[10])

• idea: extract Fekete points from a discretization of K:

but which could be asuitable mesh?

Weakly Admissible Meshes

Weakly Admissible Mesh (WAM): sequence of discrete sub- sets An⊂ K satisfying thepolynomial inequality

kpkK≤ C(An)kpkAn, ∀p ∈ Pdn(K)

where card(An)≥ N and C(An)grow polinomiallywith n C(An) bounded:Admissible Mesh (AM)

propertiesrelevant to theconstructionof WAMs (cf. [3, 6]):

• C(An) isinvariant under affine mapping

• good unisolvent interpolation sets are WAMs (e.g., Fekete or Chebyshev points in one variable, Padua points [2] in two variables)

• finite unions and productsof (W)AMs are (W)AMs for the corresponding unions and products of compacts

• given a polynomial mapping πm of degree m, then πm(Anm) is a (W)AM for πm(K) with constants C(Anm)

• any K satisfying a Markov polynomial inequality like k∇pkK≤ MnrkpkKhas anAMwith O(nrd) points Relevance to polynomial approximation:

•Least Squarespolynomial LAnfon a (W)AM, f ∈ C(K):

kf − LAnfkK≈ C(An)pcard(An) min{kf − pkK, p∈ Pdn(K)}

• Fekete points extracted from a WAM have a Lebesgue constant Λn≤ NC(An)

Discrete Extremal Sets

extractingFekete points from WAMs, An= a ={a1, . . . , aM} m

discrete optimization problem:

extracting amaximum determinantN× N submatrix from the M × N Vandermonde matrix V = V (a, p) = [pj(ai)]

this is NP-hard(cf. [7]): then we look for anapproximate solution; surprisingly, this can be obtained bybasic numerical linear algebra!

we compute two kinds of suchDiscrete Extremal Sets:

•Approximate Fekete Points

•Discrete Leja Points

Key asymptotic result(cf. [3, 4]): Discrete Extremal Setsex- tracted from a WAM by the greedy algorithms below have thesame asymptotic behaviorof the true Fekete points

1 N

N

X

j=1

δξj

−−−→N →∞

Z

K

f(x) dµK, ∀f ∈ C(K)

where µKis theequilibrium measureof K

Approximate Fekete Points

algorithm greedy 1 (AFP, Approximate Fekete Points)

• V = V (a, p); ind = [ ];

•fork= 1 : N

“select ik: vol V ([ind, ik] , 1 : N) is max”; ind = [ind, ik];

end

• ξ = a(i1, . . . , iN)

method:greedy maximization of submatrix volumes

iteration core: subtractfrom each row itsorthogonal projec- tiononto thelargest normone (preserves volumes like with parallelograms)

implementation: QR factorization with column pivoting (Businger and Golub, 1965) applied to Vt

feature: AFP areindependentof theorderof the basis Matlab script:

w= V\ones(1 : N) ; ind =find(w6= 0); ξ = a(ind)

Discrete Leja Points

algorithm greedy 2 (DLP, Discrete Leja Points)

• V = V (a, p); ind = [ ];

•fork= 1 : N

“select ik: |det V ([ind, ik] , 1 : k)| is max”; ind = [ind, ik];

end

• ξ = a(i1, . . . , iN)

method:greedy maximization of nested subdeterminants iteration core: one column step of Gaussian elimination withrow pivoting(preserves the relevant subdeterminants) implementation:LU factorization with row pivoting

feature: DLP depend on the order of the basis and form asequence

Matlab script:

[L, U, σ] =LU(V, “vector”); ind = σ(1 : N); ξ = a(ind)

Examples in Two Variables

Admissible Mesheson 2-dimensional compacts via Markov polynomial inequalies [6]:O(n4) points

Weakly Admissible Meshes via geometric transformations [3]: onlyO(n2) cardinality!

Examples: triangles and quadrangles (bilinear transfor- mations of the square), disk (trigonometric polynomial inequalities),polygons(triangulation and finite union)

FIGURE1. N = 45 AFP (circles) and DLP (asterisks) for degree n = 8 extracted from two WAMs (dots) of a nonregular convex hexagon; WAM1 (left): barycentric triangulation, WAM2 (right): minimal triangulation.

0 0.2 0.4 0.6 0.8 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 0.2 0.4 0.6 0.8 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

TABLE1.Lebesgue constantsfor AFP and DLP of the hexagon above.

mesh points n = 5 n = 10 n = 15 n = 20 n = 25 n = 30

WAM1 AFP 6.5 18.9 20.4 40.8 73.3 73.0

DLP 7.1 19.6 49.8 58.3 108.0 167.0

WAM2 AFP 6.8 12.3 34.2 52.3 49.0 80.4

DLP 10.7 48.4 62.0 91.6 86.6 203.0

TABLE2. Max-norm of theinterpolation errorswith AFP and DLP from WAM2; test functions: f1= cos (x1+ x2), f2= ((x1−0.5)2+(x2−0.5)2)3/2.

function points n = 5 n = 10 n = 15 n = 20 n = 25 n = 30

f1 AFP 6E-06 5E-13 3E-15 3E-15 3E-15 4E-15

DLP 8E-06 2E-12 2E-15 4E-15 3E-15 4E-15

f2 AFP 3E-03 2E-04 1E-04 4E-05 2E-05 1E-05

DLP 3E-03 3E-04 1E-04 3E-05 2E-05 5E-06

FIGURE2.N= 136 AFP (circles) and DLP (asterisks) for degree n = 15 in a hand shaped polygon with 39 sides and a 37 element triangulation.

0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6

0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7

Developments and Applications

•algebraic cubature: formulas exact for polynomials of de- gree n at AFP or DLP (the latter give nested formulas)

•weighted interpolation: prescribed poles, digital filters, ...

•three-dimensional instances: cube, ball, tetrahedron, cylin- der, solid torus, ...

•numerical PDEs: spectral and high order methods, discrete least squares, ...

References

[1] R. BERMAN, S. BOUCKSOM ANDD. WITTNYSTROM¨ , Fekete points and convergence to- wards equilibrium measures on complex manifolds, arXiv preprint, 2009.

[2] 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).

[3] L. BOS, J.-P. CALVI, N. LEVENBERG, A. SOMMARIVA ANDM. VIANELLO, Geometric Weakly Admissible Meshes, Discrete Least Squares Approximations and Approximate Fekete Points, Math. Comp., to appear.

[4] L. BOS, S. DEMARCHI, A. SOMMARIVA ANDM. VIANELLO, Computing multivariate Fekete and Leja points by numerical linear algebra, SIAM J. Numer. Anal., to appear.

[5] L. BOS, N. LEVENBERG ANDS. WALDRON, On the Spacing of Fekete Points for a Sphere, Ball or Simplex, Indag. Math. 19 (2008).

[6] J.-P. CALVI ANDN. LEVENBERG, Uniform approximation by discrete least squares polyno- mials, J. Approx. Theory 152 (2008).

[7] A. CIVRIL ANDM. MAGDON-ISMAIL, On Selecting a Maximum Volume Sub-matrix of a Matrix and Related Problems, Theoretical Computer Science 410 (2009).

[8] A. SOMMARIVA ANDM. VIANELLO, Computing approximate Fekete points by QR factor- izations of Vandermonde matrices, Comput. Math. Appl. 57 (2009).

[9] A. SOMMARIVA ANDM. VIANELLO, Approximate Fekete points for weighted polynomial interpolation, Electron. Trans. Numer. Anal. 37 (2010).

[10] M.A. TAYLOR, B.A. WINGATE ANDR.E. VINCENT, An algorithm for computing Fekete points in the triangle, SIAM J. Numer. Anal. 38 (2000).

Riferimenti

Documenti correlati

(Read classifier configurations from booster.spr and bagger.spr and apply them to test data. Save input variables and classifier output into test.root. Classifier responses will

The educational methodology used in the Museum with students was also adopted with teachers. Teacher training is conceived as a tool for teachers’ professional development as well

This introductory paper describes the main topics of this special issue, ded- icated to Leonardo Traversoni, known at international level as the promoter of the conference

Schaback [32], we show that this algorithm can be easily implemented by another basic tool of linear algebra, the LU factorization with partial (row) pivoting. We recall

Vianello, Geometric Weakly Admissible Meshes, Discrete Least Squares Approximations and Approximate Fekete Points, Math.. Xu, Bivariate Lagrange interpolation at the Padua points:

Since we use here for the first time algorithm AFP for the construction of polynomial filters based on interpolation at approximate Fekete points, we begin by a simple nonweighted

We want to compute the discrete orthogonal polynomials on the nodes of a cubature rule with positive weights (Chapter 3) or on good points for multivariate polynomial

We want to compute the discrete orthogonal polynomials on the nodes of a cubature rule with positive weights (Chapter 3) or on good points for multivariate polynomial