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
bAND M. V IANELLO
baDepartment 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) = [pj(ξi)]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)), ℓj(ξi) = δ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).