lebesgue¶

The Lebesgue function¶

recursivenodes.lebesgue.lebesgue(x, d, n, nodes, Vinv=None)[source]¶

The Lebesgue function in the biunit \(d\)-simplex with a choice of nodes for degree-\(n\) polynomials.

Notes

Let \(X_n = \{\boldsymbol{x}_i\}\) be the set of \(\binom{n+d}{d}\) nodes. The associated shape functions \(\{\phi_i\}\) are polynomials with degree at most \(n\) such that \(\phi_i(\boldsymbol{x}_j) = \delta_{ij}\).

The Lebesgue function is the sum of the absolute value of the shape functions,

\[l(\boldsymbol{x}) = \sum_{i=1}^{\binom{n+d}{d}} | \phi_i(\boldsymbol{x}) |.\]

Parameters:

x (ndarray) – Shape (\(N\), \(d\)), points at which to evaluate the Lebesgue function.
d (int) – The spatial dimension.
n (int) – The polynomial degree that the nodes are unisolvent for.
nodes (ndarray) – Shape (\(\binom{n+d}{d}\), \(d\)), the nodes defining the shape functions.
Vinv (ndarray, optional) – Shape (\(\binom{n+d}{d}\), \(\binom{n+d}{d}\)), the inverse of the Vandermonde matrix for the Proriol-Koornwinder-Dubiner basis evaluated at the nodes. These polynomials are used as a basis for stable evluation in the biunit \(d\)-simplex, so the inverse of the Vandermonde matrix must be computed if it is not already known.

Returns:

Shape (\(N\),), the value of the Lebesgue function for the nodes at the points x.

Return type:

ndarray

The Lebesgue constant¶

recursivenodes.lebesgue.lebesguemax(d, n, nodes, Vinv=None, solver_options={'barrier_tol': 0.001, 'gtol': 0.001}, ex_nodes=None, logger=None)[source]¶

An estimate of the Lebesgue constant \(\Lambda_n^{\max}(\Delta^d)\), the maximum of the Lebesgue function on the biunit \(d\)-simplex for a set of nodes for polynomials up to degree \(n\).

Notes

If \(l\) is the Lebesgue function defined by the nodes (see lebesgue()), then

(1)¶\[\Lambda_n^{\max}(\Delta^d) = \max_{\boldsymbol{x}\in\Delta^d} l(\boldsymbol{x}).\]

This constant is significant in quantifying the interpolation quality of a set of nodes because of the error estimate

\[\| f - p^n(f) \|_{\infty} \leq (1 + \Lambda_n^{\max}) \inf_{q\in\mathcal{P}_n(\Delta^d)} \| f - q \|_{\infty},\]

where \(p^n(f)\) is the interpolant of \(f\) defined by the nodes.

\(\Lambda_n^{\max}(\Delta^d)\) is nonconvex and only piecewise smooth, with many local maxima. This function is designed to estimate \(\Lambda_n^{\max}(\Delta^d)\) when the nodes have the same lattice-like layout as equispaced nodes (as all but one of the node sets implemented in this package do, see nodes).

When this lattice-like structure is present, the maxima always occur in one of the “void”s between nodes in the lattice:

>>> import matplotlib.pyplot as plt
>>> from recursivenodes import recursive_nodes
>>> from recursivenodes.nodes import equispaced
>>> from recursivenodes.utils import coord_map
>>> from recursivenodes.lebesgue import lebesgue
>>> x = equispaced(2, 200, domain='biunit')
>>> nodes = recursive_nodes(2, 6, domain='biunit')
>>> l = lebesgue(x, 2, 6, nodes)
>>> x = coord_map(x, 'biunit', 'equilateral')
>>> ax = plt.gca()
>>> ax.tricontour(x[:,0], x[:, 1], l, 41)
<matplotlib.tri._tricontour.TriContourSet object at ...>
>>> ax.set_aspect('equal')
>>> plt.show()

Also, though the Lebesgue function is only piecewise smooth, it is guaranteed to be smooth at the maxima. An efficient way to estimate the \(\Lambda_n^{\max}(\Delta^d)\) for nodes with lattice-like structure is to try to optimize the Lebesgue function from one initial guess at the centroid of each void. The node sets in this package are also fully symmetric, which means that initial guesses can be placed in only a fraction of the voids. Here, for instance, are the 3D degree 7 equispaced nodes and the initial guesses used by lebesguemax:

This function uses scipy.optimize.minimize (method=’trust-constr’) to find the local maxima from the initial guesses. While it is not theoretically guaranteed that the global maximum is always found in this way, the values of \(\Lambda_n^{\max}(\Delta^d)\) that have been compute with lebesguemax agree with previously computed values in [BP06, LP06, War06].

Parameters:

d (int) – The spatial dimension.
n (int) – The polynomial degree that the nodes are unisolvent for.
nodes (ndarray) – Shape (\(\binom{n+d}{d}\), \(d\)), the nodes defining the shape functions.
Vinv (ndarray, optional) – See documentation for lebesgue().
solver_options (dict, optional) – Options to control the behavior of scipy.optimize.minimize.
ex_nodes (ndarray, optional) – if nodes includes nodes that do not touch the boundary of the simplex, ex_nodes is a set of nodes that includes extra boundary locations that can be used to help define initial guesses.
logger (logging.logger, optional) – Logger for progress information.

Returns:

The estimate and estimated argmax of (1).

Return type:

(float, ndarray)

recursivenodes.lebesgue.lebesguemax_reference(d, n, nodes='recursive')[source]¶

Look up previously computed Lebesgue constants (\(\Lambda_n^{\max}(\Delta^d)\)) for node sets implemented in this package and other node sets in the literature.

Parameters:

d (int) – The spatial dimension.
n (int) – The polynomial degree that the nodes are unisolvent for.
nodes (str, optional) –
The name of the node set to query. Choices include:
- 'recursive': recursivenodes.recursive_nodes().
- 'equispaced': recursivenodes.nodes.equispaced().
- 'warburton': recursivenodes.nodes.warburton().
- 'blyth_luo_pozrikidis': recursivenodes.nodes.blyth_luo_pozrikidis().
- 'Chen-Babuska': Chen-Babuška type nodes [CB95, CB96], computed in [Rot05].
- 'Fekete': Fekete nodes, computed in [Rot05].
- 'Lebesgue': Lebesgue-constant-minimizing nodes, computed in [Rot05].
- 'Heinrichs-asymmetric': Lebesgue-constant-minimizing nodes [Hei05].
- 'Heinrichs-symmetric': Symmetric Lebesgue-constant-minimizing nodes [Hei05].
- 'Hesthaven': Hesthaven electrostatic nodes [Hes98].
- 'Hesthaven-Teng': Hesthaven-Teng electrostatic nodes [Hes98].
- 'Rapetti-Sommariva-Vianello-leb': Lebesgue-constant-minimizing nodes, computed in [RSV12].
- 'Rapetti-Sommariva-Vianello-lebgl': Lebesgue-constant-minimizing nodes wih Lobatto-Gauss-Legendre edges, computed in [RSV12].
- 'Rapetti-Sommariva-Vianello-lebgls': Symmetric Lebesgue-constant-minimizing nodes wih Lobatto-Gauss-Legendre edges, computed in [RSV12].

Returns:

\(\Lambda_n^{\max}(\Delta^d)\) for that node set.

Return type:

float

Raises:

KeyError – The node set is unknown, or \(\Lambda_n^{\max}(\Delta^d)\) has not been precomputed for it.

recursivenodes

Navigation

Related Topics

lebesgue¶

The Lebesgue function¶

The Lebesgue constant¶