lagrange_interp_nd


lagrange_interp_nd, a C++ code which defines and evaluates the Lagrange polynomial p(x) which interpolates a set of data depending on a M-dimensional argument that was evaluated on a product grid, so that p(x(i)) = z(i).

The interpolation function requires that the data points defining the interpolant lie on a product grid [A1,B1]x[A2,B2]x...x[Am,Bm], to be defined by a vector AB of dimension (M,2).

The interpolation function requires that the user supply a vector N_1D of length M, which specifies the number or "order" of data points in each dimension. The number of points in the product grid will then be the product of the entries in N_1D.

(A second version of the interpolation function uses instead a vector IND of length M, which is interpreted as a set of "levels". Each level corresponds in a simple way to the number of "order" of data points. In particular, levels 0, 1, 2, 3, 4 correspond to 1, 3, 5, 9 and 17 points. This version is useful when a nested rule is desired.)

The interpolation function sets the location of the data points in each dimension using the Clenshaw Curtis rule, that is, using the N extrema of the Chebyshev polynomial of the first kind of order N-1. Those polynomials are defined on [-1,+1], but a simple linear mapping is used to adjust the points to the interval specified by the user.

The interpolation function needs data at the data points. It is assumed that this will be supplied by a user specified function of the form

        v = f ( m, n, x )
      
where M is the spatial dimension, N is the number of points to be evaluated, X is a vector of dimension (M,N) containing the points, and the result is the vector V of dimension (N) containing the function values.

Typical usage involves several steps. The size of the interpolant grid is determined by a call like:

        nd = lagrange_interp_nd_size ( m, ind );
      
Then the interpolant grid is determined by
        xd = lagrange_interp_nd_grid ( m, ind, ab, nd );
      
and the interpolant data is evaluated by
        zd = f ( m, nd, xd );
      
Once the interpolant has been defined, the user is free to evaluate it repeatedly, by specifying NI points XI, and requesting the interpolated values ZI by:
        zi = lagrange_interp_nd_value ( m, ind, ab, nd, zd, ni, xi );
      

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

lagrange_interp_nd is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

LAGRANGE_INTERP_1D, a C++ code which defines and evaluates the Lagrange polynomial p(x) which interpolates a set of data, so that p(x(i)) = y(i).

LAGRANGE_INTERP_2D, a C++ code which defines and evaluates the Lagrange polynomial p(x,y) which interpolates a set of data depending on a 2D argument that was evaluated on a product grid, so that p(x(i),y(j)) = z(i,j).

lagrange_interp_nd_test

RBF_INTERP_ND, a C++ code which defines and evaluates radial basis function (RBF) interpolants to multidimensional data.

SHEPARD_INTERP_ND, a C++ code which defines and evaluates Shepard interpolants to multidimensional data, based on inverse distance weighting.

SPARSE_INTERP_ND a C++ code which can be used to define a sparse interpolant to a function f(x) of a multidimensional argument.

SPINTERP, a MATLAB library which carries out piecewise multilinear hierarchical sparse grid interpolation; an earlier version of this software is ACM TOMS Algorithm 847, by Andreas Klimke;

TEST_INTERP_ND, a C++ code which defines test problems for interpolation of data z(x), depending on an M-dimensional argument.

Reference:

  1. Philip Davis,
    Interpolation and Approximation,
    Dover, 1975,
    ISBN: 0-486-62495-1,
    LC: QA221.D33

Source Code:


Last revised on 22 March 2020.