Lagrange Optimal points
Our first candidate for a training set are the Lagrange optimal points which are based on the Lagrange characteristic polynomials.
Let be the set of polynomials on with total degree at most and let . For consider , the Lagrange characteristic polynomials, defined so that
which form a basis of . They can be written in terms of Vandermonde determinants,
where is such that . Recall that the Lebesgue constant of is defined by,
We are interested in the solutions of the following optimization problem,
These solutions constitute the definition of the Lagrange optimal points.
Consider the -th degree Chebyshev polynomial defined by . The Gauss-Chebyshev-Lobatto points (of degree ) are the extrema in of . They are given by the explicit formula:
The Clenshaw-Curtis points are the nested subsequence of such points with
A property of the Clenshaw-Curtis points that can be easily deduced from the explicit formula above is the asymptotic (for large) clustering of points near the boundary (i.e. near -1 and 1).
Previously we discussed the one dimensional Clenshaw-Curtis points and now we would like to go to an arbitrary dimension 1. As soon as we try that we run into the Curse of Dimensionality: If we took the full tensor product of one dimensional points we end up with points in dimensions which is far too big a number for numerical schemes. The technique of Sparse Grids allows us to overcome this problem.
We start off with one dimensional points . We would like to build a collection of -dimensional points, our sparse grid. Let be a multi-index and consider the norm and let
Take a nested family of collections of points so that
for all , if and
Now define the sparse grid in dimensions as follows,
One should note that even though the actual points in the sparse grid depend on how we chose the nested family , the cardinality of the sparse grid is independent of this choice.
Other points that we have used as training sets are :
- Uniform Grid points.
- Random points.