hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox Chapter Introduction

E01 — Interpolation

Scope of the Chapter

This chapter is concerned with the interpolation of a function of one or more variables. When provided with the value of the function (and possibly one or more of its lowest-order derivatives) at each of a number of values of the variable(s), the functions provide either an interpolating function or an interpolated value. For some of the interpolating functions, there are supporting functions to evaluate, differentiate or integrate them.

Background to the Problems

In motivation and in some of its numerical processes, this chapter has much in common with Chapter E02 (Curve and Surface Fitting). For this reason, we shall adopt the same terminology and refer to dependent variable and independent variable(s) instead of function and variable(s). Where there is only one independent variable, we shall denote it by xx and the dependent variable by yy. Thus, in the basic problem considered in this chapter, we are given a set of distinct values x1,x2,,xmx1,x2,,xm of xx and a corresponding set of values y1,y2,,ymy1,y2,,ym of yy, and we shall describe the problem as being one of interpolating the data points (xr,yr)(xr,yr), rather than interpolating a function. In modern usage, however, interpolation can have either of two rather different meanings, both relevant to functions in this chapter. They are
(a) the determination of a function of xx which takes the value yryr at x = xrx=xr, for r = 1,2,,mr=1,2,,m (an interpolating function or interpolant),
(b) the determination of the value (interpolated value or interpolate) of an interpolating function at any given value, say x^, of xx within the range of the xrxr (so as to estimate the value at x^ of the function underlying the data).
The latter is the older meaning, associated particularly with the use of mathematical tables. The term ‘function underlying the data’, like the other terminology described above, is used so as to cover situations additional to those in which the data points have been computed from a known function, as with a mathematical table. In some contexts, the function may be unknown, perhaps representing the dependency of one physical variable on another, say temperature upon time.
Whether the underlying function is known or unknown, the object of interpolation will usually be to approximate it to acceptable accuracy by a function which is easy to evaluate anywhere in some range of interest. Polynomials, rational functions (ratios of two polynomials) and piecewise polynomials, such as cubic splines (see Section [Curve Fitting] in the E02 Chapter Introduction for definitions of terms in the latter case), being easy to evaluate and also capable of approximating a wide variety of functions, are the types of function mostly used in this chapter as interpolating functions. An interpolating polynomial is taken to have degree m1m-1 when there are mm data points, and so it is unique. It is called the Lagrange interpolating polynomial. The rational function, in the special form used, is also unique. An interpolating spline, on the other hand, depends on the choice made for the knots.
One way of achieving the objective in (b) above is, of course, through (a), but there are also methods which do not involve the explicit computation of the interpolating function. Everett's formula and Aitken's successive linear interpolation (see Dahlquist and Björck (1974)) provide two such methods. Both are used in this chapter and determine a value of the Lagrange interpolating polynomial.
It is important to appreciate, however, that the Lagrange interpolating polynomial often exhibits unwanted fluctuations between the data points. These tend to occur particularly towards the ends of the data range, and to get larger with increasing number of data points. In severe cases, such as with 3030 or 4040 equally spaced values of xx, the polynomial can take on values several orders of magnitude larger than the data values. (Closer spacing near the ends of the range tends to improve the situation, and wider spacing tends to make it worse.) Clearly, therefore, the Lagrange polynomial often gives a very poor approximation to the function underlying the data. On the other hand, it can be perfectly satisfactory when its use is restricted to providing interpolated values away from the ends of the data range from a reasonably small number of data values.
In contrast, a cubic spline which interpolates a large number of data points can often be used satisfactorily over the whole of the data range. Unwanted fluctuations can still arise but much less frequently and much less severely than with polynomials. Rational functions, when appropriate, would also be used over the whole data range. The main danger with these functions is that their polynomial denominators may take zero values within that range. Unwanted fluctuations are avoided altogether by a function using piecewise cubic polynomials having only first derivative continuity. It is designed especially for monotonic data, but for other data still provides an interpolant which increases, or decreases, over the same intervals as the data.
The concept of interpolation can be generalized in a number of ways. Firstly, at each xx, the interpolating function may be required to take on not only a given value but also given values for all its derivatives up to some specified order (which can vary with rr). This is the Hermite–Birkoff interpolation problem. Secondly, we may be required to estimate the value of the underlying function at a value x^ outside the range of the data. This is the process of extrapolation. In general, it is a good deal less accurate than interpolation and is to be avoided whenever possible.
Interpolation can also be extended to the case of two or more independent variables. If the data values are given at the intersections of a regular two-dimensional mesh bicubic splines (see Section [Bicubic splines: definition and representation] in the E02 Chapter Introduction) are very suitable and usually very effective for the problem. For other cases, perhaps where the data values are quite arbitrarily scattered, polynomials and splines are not at all appropriate and special forms of interpolating function have to be employed. Many such forms have been devised and two of the most successful are in functions in this chapter. They both have continuity in first, but not higher, derivatives.

Recommendations on Choice and Use of Available Functions

General

Before undertaking interpolation, in other than the simplest cases, you should seriously consider the alternative of using a function from Chapter E02 to approximate the data by a polynomial or spline containing significantly fewer coefficients than the corresponding interpolating function. This approach is much less liable to produce unwanted fluctuations and so can often provide a better approximation to the function underlying the data.
When interpolation is employed to approximate either an underlying function or its values, you will need to be satisfied that the accuracy of approximation achieved is adequate. There may be a means for doing this which is particular to the application, or the function used may itself provide a means. In other cases, one possibility is to repeat the interpolation using one or more extra data points, if they are available, or otherwise one or more fewer, and to compare the results. Other possibilities, if it is an interpolating function which is determined, are to examine the function graphically, if that gives sufficient accuracy, or to observe the behaviour of the differences in a finite difference table, formed from evaluations of the interpolating function at equally-spaced values of xx over the range of interest. The spacing should be small enough to cause the typical size of the differences to decrease as the order of difference increases.

One Independent Variable

Interpolated values: data without derivatives

When the underlying function is well represented by data points on both sides of the value, x^, at which an interpolated value is required, nag_interp_1d_everett (e01ab) should be tried first if the data points are equally spaced, nag_interp_1d_aitken (e01aa) if they are not. Both compute a value of the Lagrange interpolating polynomial, the first using Everett's formula, the second Aitken's successive linear interpolation. The first function requires an equal (or nearly equal) number of data points on each side of x^; such a distribution of points is preferable also for the second function. If there are many data points, this will be achieved simply by using only an appropriate subset for each value of x^. Ten to twelve data points are the most that would be required for many problems. Both functions provide a means of assessing the accuracy of an interpolated value, with nag_interp_1d_everett (e01ab) by examination of the size of the finite differences supplied, with nag_interp_1d_aitken (e01aa) by intercomparison of the set of interpolated values obtained from polynomials of increasing degree.
In other cases, or when the above functions fail to produce a satisfactory result, one of the functions discussed in the next section should be used. The spline and other piecewise polynomial functions are the most generally applicable. They are particularly appropriate when interpolated values towards the ends of the range are required. They are also likely to be preferable, for reasons of economy, when many interpolated values are required.
nag_interp_1d_aitken (e01aa) above, and three of the functions discussed in the next section, can be used to compute extrapolated values. These three are nag_interp_1d_cheb (e01ae), nag_interp_1d_monotonic (e01be) and nag_interp_1d_ratnl (e01ra) based on polynomials, piecewise polynomials and rational functions respectively. Extrapolation is not recommended in general, but can sometimes give acceptable results if it is to a point not far outside the data range, and only the few nearest data points are used in the process. nag_interp_1d_ratnl (e01ra) is most likely to be successful.

Interpolating function: data without derivatives

nag_interp_1d_cheb (e01ae) computes the Lagrange interpolating polynomial by a method (based on Newton's formula with divided differences (see Fröberg (1970)) which has proved numerically very stable. Thus, it can sometimes be used to provide interpolated values in more difficult cases than can nag_interp_1d_aitken (e01aa) (see the previous section). However, the likelihood of the polynomial having unwanted fluctuations, particularly near the ends of the data range when a moderate or large number of data points are used, should be remembered.
Such fluctuations of the polynomial can be avoided if you are at liberty to choose the xx values at which to provide data points. In this case, a function from Chapter E02, namely nag_fit_1dcheb_glp (e02af), should be used in the manner and with the xx values discussed in Section [Least squares polynomials: selected data points] in the E02 Chapter Introduction.
Usually however, when the whole of the data range is of interest, it is preferable to use a cubic spline as the interpolating function. nag_interp_1d_spline (e01ba) computes an interpolating cubic spline, using a particular choice for the set of knots which has proved generally satisfactory in practice. If you wish to choose a different set, a cubic spline function from Chapter E02, namely nag_fit_1dspline_knots (e02ba), may be used in its interpolating mode, setting NCAP7 = m + 4NCAP7=m+4 and all elements of the parameter w to unity.
The cubic spline does not always avoid unwanted fluctuations, especially when the data shows a steep slope close to a region of small slope, or when the data inadequately represents the underlying curve. In such cases, nag_interp_1d_monotonic (e01be) can be very useful. It derives a piecewise cubic polynomial (with first derivative continuity) which, between any adjacent pair of data points, either increases all the way, or decreases all the way (or stays constant). It is especially suited to data which is monotonic over the whole range.
In this function, the interpolating function is represented simply by its value and first derivative at the data points. Supporting functions compute its value and first derivative elsewhere, as well as its definite integral over an arbitrary interval. The other functions mentioned, namely nag_interp_1d_cheb (e01ae) and nag_interp_1d_spline (e01ba), provide the interpolating function either in Chebyshev series form or in B-spline form (see Sections [Representation of polynomials] and [Representation of cubic splines] in the E02 Chapter Introduction). Functions for evaluating, differentiating and integrating these forms are discussed in Section [Evaluation, Differentiation and Integration] in the E02 Chapter Introduction. The splines and other piecewise cubics will normally provide better estimates of the derivatives of the underlying function than will interpolating polynomials, at any rate away from the central part of the data range.
nag_interp_1d_ratnl (e01ra) computes an interpolating rational function. It is intended mainly for those cases where you know that this form of function is appropriate. However, it is also worth trying in cases where the other functions have proved unsatisfactory. nag_interp_1d_ratnl_eval (e01rb) is available to compute values of the function provided by nag_interp_1d_ratnl (e01ra).

Data containing derivatives

nag_interp_1d_cheb (e01ae) (see Section [Interpolating function: data without derivatives]) can also compute the polynomial which, at each xrxr, has not only a specified value yryr but also a specified value of each derivative up to order prpr.

Two Independent Variables

Data on a rectangular mesh

Given the value fqrfqr of the dependent variable ff at the point (xq,yr)(xq,yr) in the plane of the independent variables xx and yy, for each q = 1,2,,mq=1,2,,m and r = 1,2,,nr=1,2,,n (so that the points (xq,yr)(xq,yr) lie at the m × nm×n intersections of a rectangular mesh), nag_interp_2d_spline_grid (e01da) computes an interpolating bicubic spline, using a particular choice for each of the spline's knot-set. This choice, the same as in nag_interp_1d_spline (e01ba), has proved generally satisfactory in practice. If, instead, you wish to specify your own knots, a function from Chapter E02, namely nag_fit_2dspline_panel (e02da), may be used (it is more cumbersome for the purpose, however, and much slower for larger problems). Using mm and nn in the above sense, the parameter m must be set to m × nm×n, px and py must be set to m + 4m+4 and n + 4n+4 respectively and all elements of w should be set to unity. The recommended value for eps is zero.

Arbitrary data

As remarked at the end of Section [Background to the Problems], specific methods of interpolating are required for this problem, which can often be difficult to solve satisfactorily. Two of the most successful are employed in nag_interp_2d_scat (e01sa) and nag_interp_2d_scat_shep (e01sg), the two functions which (with their respective evaluation functions nag_interp_2d_scat_eval (e01sb) and nag_interp_2d_scat_shep_eval (e01sh)) are provided for the problem. Definitions can be found in the function documents. Both interpolants have first derivative continuity and are ‘local’, in that their value at any point depends only on data in the immediate neighbourhood of the point. This latter feature is necessary for large sets of data to avoid prohibitive computing time. nag_interp_2d_scat_shep_eval (e01sh) allows evaluation of the interpolant and its first partial derivatives.
The relative merits of the two methods vary with the data and it is not possible to predict which will be the better in any particular case.

Three Independent Variables

Arbitrary data

The function nag_interp_3d_scat_shep (e01tg) and its evaluation function nag_interp_3d_scat_shep_eval (e01th) are provided for interpolation of three-dimensional scattered data. As in the case of two independent variables, the method is local, and produces an interpolant with first derivative continuity. nag_interp_3d_scat_shep_eval (e01th) allows evaluation of the interpolant and its first partial derivatives.

Four and Five Independent Variables

Arbitrary data

The function nag_interp_4d_scat_shep (e01tk) and its evaluation function nag_interp_4d_scat_shep_eval (e01tl) allow interpolation of four-dimensional scattered data, while the function nag_interp_5d_scat_shep (e01tm) and its evaluation function nag_interp_5d_scat_shep_eval (e01tn) allow interpolation of five-dimensional scattered data. nag_interp_4d_scat_shep (e01tk) and nag_interp_5d_scat_shep (e01tm) are higher dimensional analogues to the functions nag_interp_2d_scat_shep (e01sg) and nag_interp_3d_scat_shep (e01tg), while nag_interp_4d_scat_shep_eval (e01tl) and nag_interp_5d_scat_shep_eval (e01tn) are analogous to nag_interp_2d_scat_shep_eval (e01sh) and nag_interp_3d_scat_shep_eval (e01th).

Multi-dimensional interpolation

Arbitrary data

Interpolation of scattered data in dd-dimensions, where d > 2d>2, is provided by function nag_interp_nd_scat_shep (e01zm). This extends the local method of nag_interp_3d_scat_shep (e01tg) and nag_interp_4d_scat_shep (e01tk) to higher dimensions. Evaluation of the interpolant, which has continuous first derivatives, is carried out by function nag_interp_nd_scat_shep_eval (e01zn).

Decision Tree

Tree 1

More than one independent variable? _
yes
Data on rectangular mesh? _
yes
nag_interp_2d_spline_grid (e01da)
| no
|
| Two independent variables? _
yes
nag_interp_2d_scat (e01sa) or nag_interp_2d_scat_shep (e01sg)
| no
|
| Three independent variables? _
yes
nag_interp_3d_scat_shep (e01tg)
| no
|
| Four independent variables? _
yes
nag_interp_4d_scat_shep (e01tk)
| no
|
| Five independent variables? _
yes
nag_interp_5d_scat_shep (e01tm)
| no
|
| More than five independent variables? _
yes
nag_interp_nd_scat_shep (e01zm)
no
|
Does data contain derivatives? _
yes
nag_interp_1d_cheb (e01ae)
no
|
Interpolating function required? _
yes
Do you wish to impose monotonicity? _
yes
nag_interp_1d_monotonic (e01be)
| no
|
| Polynomial function required? _
yes
nag_interp_1d_cheb (e01ae)
| no
|
| Rational function required? _
yes
nag_interp_1d_ratnl (e01ra)
| no
|
| nag_interp_1d_spline (e01ba) unless you have received an unacceptable result in which case nag_interp_1d_monotonic (e01be)
no
|
Well away from end of data range? _
yes
Data points equally spaced? _
yes
nag_interp_1d_everett (e01ab)
| no
|
| nag_interp_1d_aitken (e01aa)
no
|
nag_interp_1d_spline (e01ba) unless you have received an unacceptable result in which case nag_interp_1d_monotonic (e01be)

Functionality Index

Derivative, 
    of interpolant, 
        from nag_interp_1d_monotonic (e01be) nag_interp_1d_monotonic_deriv (e01bg)
        from nag_interp_2d_scat_shep (e01sg) nag_interp_2d_scat_shep_eval (e01sh)
        from nag_interp_3d_scat_shep (e01tg) nag_interp_3d_scat_shep_eval (e01th)
        from nag_interp_4d_scat_shep (e01tk) nag_interp_4d_scat_shep_eval (e01tl)
        from nag_interp_5d_scat_shep (e01tm) nag_interp_5d_scat_shep_eval (e01tn)
        from nag_interp_nd_scat_shep (e01zm) nag_interp_nd_scat_shep_eval (e01zn)
Evaluation, 
    of interpolant, 
        from nag_interp_1d_monotonic (e01be) nag_interp_1d_monotonic_eval (e01bf)
        from nag_interp_1d_ratnl (e01ra) nag_interp_1d_ratnl_eval (e01rb)
        from nag_interp_2d_scat (e01sa) nag_interp_2d_scat_eval (e01sb)
        from nag_interp_2d_scat_shep (e01sg) nag_interp_2d_scat_shep_eval (e01sh)
        from nag_interp_3d_scat_shep (e01tg) nag_interp_3d_scat_shep_eval (e01th)
        from nag_interp_4d_scat_shep (e01tk) nag_interp_4d_scat_shep_eval (e01tl)
        from nag_interp_5d_scat_shep (e01tm) nag_interp_5d_scat_shep_eval (e01tn)
        from nag_interp_nd_scat_shep (e01zm) nag_interp_nd_scat_shep_eval (e01zn)
Extrapolation, 
    one variable, 
        piecewise cubic nag_interp_1d_monotonic (e01be)
        polynomial, 
            data with or without derivatives nag_interp_1d_cheb (e01ae)
            general data nag_interp_1d_aitken (e01aa)
        rational function nag_interp_1d_ratnl (e01ra)
Integration (definite) of interpolant from nag_interp_1d_monotonic (e01be) nag_interp_1d_monotonic_intg (e01bh)
Interpolated values, 
    d variables, 
        from interpolant from nag_interp_nd_scat_shep (e01zm) nag_interp_nd_scat_shep_eval (e01zn)
    five variables, 
        from interpolant from nag_interp_5d_scat_shep (e01tm) nag_interp_5d_scat_shep_eval (e01tn)
    four variables, 
        from interpolant from nag_interp_4d_scat_shep (e01tk) nag_interp_4d_scat_shep_eval (e01tl)
    one variable, 
        from interpolant from nag_interp_1d_monotonic (e01be) nag_interp_1d_monotonic_eval (e01bf)
        from interpolant from nag_interp_1d_monotonic (e01be) (including derivative) nag_interp_1d_monotonic_deriv (e01bg)
        from polynomial, 
            equally spaced data nag_interp_1d_everett (e01ab)
            general data nag_interp_1d_aitken (e01aa)
        from rational function nag_interp_1d_ratnl_eval (e01rb)
    three variables, 
        from interpolant from nag_interp_3d_scat_shep (e01tg) nag_interp_3d_scat_shep_eval (e01th)
    two variables, 
        from interpolant from nag_interp_2d_scat (e01sa) nag_interp_2d_scat_eval (e01sb)
        from interpolant from nag_interp_2d_scat_shep (e01sg) nag_interp_2d_scat_shep_eval (e01sh)
Interpolating function, 
    d variables, 
        modified Shepard method nag_interp_nd_scat_shep (e01zm)
    five variables, 
        modified Shepard method nag_interp_5d_scat_shep (e01tm)
    four variables, 
        modified Shepard method nag_interp_4d_scat_shep (e01tk)
    one variable, 
        cubic spline nag_interp_1d_spline (e01ba)
        other piecewise polynomial nag_interp_1d_monotonic (e01be)
        polynomial, 
            data with or without derivatives nag_interp_1d_cheb (e01ae)
        rational function nag_interp_1d_ratnl (e01ra)
    three variables, 
        modified Shepard method nag_interp_3d_scat_shep (e01tg)
    two variables, 
        bicubic spline nag_interp_2d_spline_grid (e01da)
        modified Shepard method nag_interp_2d_scat_shep (e01sg)
        other piecewise polynomial nag_interp_2d_scat (e01sa)

References

Dahlquist G and Björck Å (1974) Numerical Methods Prentice–Hall
Fröberg C E (1970) Introduction to Numerical Analysis Addison–Wesley

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013