LAGRANGE_INTERP_ND
M-dimensional Lagrange Interpolant

LAGRANGE_INTERP_ND is a C++ library 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 GNU LGPL license.

Languages:

LAGRANGE_INTERP_ND is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

LAGRANGE_INTERP_1D, a C++ library 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++ library 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).

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

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

SPARSE_INTERP_ND a C++ library 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++ library which defines test problems for interpolation of data z(x), depending on an M-dimensional argument.

Reference:

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

Source Code:

lagrange_interp_nd.cpp, the source code.
lagrange_interp_nd.hpp, the include file.
lagrange_interp_nd.sh, BASH commands to compile the source code.

Examples and Tests:

lagrange_interp_nd_prb.cpp, a sample calling program.
lagrange_interp_nd_prb.sh, BASH commands to compile and run the sample program.
lagrange_interp_nd_prb_output.txt, the output file.

List of Routines:

CC_COMPUTE_POINTS computes Clenshaw Curtis quadrature points.
I4_POWER returns the value of I^J.
I4VEC_PRODUCT multiplies the entries of an I4VEC.
LAGRANGE_BASE_1D evaluates the Lagrange basis polynomials.
LAGRANGE_INTERP_ND_GRID sets an M-dimensional Lagrange interpolant grid.
LAGRANGE_INTERP_ND_GRID2 sets an M-dimensional Lagrange interpolant grid.
LAGRANGE_INTERP_ND_SIZE sizes an M-dimensional Lagrange interpolant.
LAGRANGE_INTERP_ND_SIZE2 sizes an M-dimensional Lagrange interpolant.
LAGRANGE_INTERP_ND_VALUE evaluates an ND Lagrange interpolant.
LAGRANGE_INTERP_ND_VALUE2 evaluates an ND Lagrange interpolant.
ORDER_FROM_LEVEL_135 evaluates the 135 level-to-order relationship.
R8_ABS returns the absolute value of an R8.
R8MAT_UNIFORM_01_NEW returns a unit pseudorandom R8MAT.
R8VEC_DIRECT_PRODUCT creates a direct product of R8VEC's.
R8VEC_DIRECT_PRODUCT2 creates a direct product of R8VEC's.
R8VEC_DOT_PRODUCT computes the dot product of a pair of R8VEC's.
R8VEC_NORM_AFFINE returns the affine L2 norm of an R8VEC.
TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.

Last revised on 30 September 2012.

LAGRANGE_INTERP_ND M-dimensional Lagrange Interpolant