DIVDIF
Divided Difference Polynomials

DIVDIF is a FORTRAN90 library which creates, prints and manipulates divided difference polynomials based on data tabulated at evenly spaced or unevenly spaced argument values.

Divided difference polynomials are a systematic method of computing polynomial approximations to scattered data. The representations are compact, and may easily be updated with new data, rebased at zero, or analyzed to produce the standard form polynomial, integral or derivative polynomials.

Other routines are available to convert the divided difference representation to standard polynomial format. This is a natural way to determine the coefficients of the polynomial that interpolates a given set of data, for instance.

One surprisingly simple but useful routine is available to take a set of roots and compute the divided difference or standard form polynomial that passes through those roots.

Finally, the Newton-Cotes quadrature formulas can be derived using divided difference methods, so a few routines are given which can compute the weights and abscissas of open or closed rules for an arbitrary number of nodes.

Licensing:

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

Languages:

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

Related Data and Programs:

BERNSTEIN_POLYNOMIAL, a FORTRAN90 library which evaluates the Bernstein polynomials, useful for uniform approximation of functions;

CHEBYSHEV, a FORTRAN90 library which computes the Chebyshev interpolant/approximant to a given function over an interval.

DIFFER, a FORTRAN90 library which determines the finite difference coefficients necessary in order to combine function values at known locations to compute an approximation of given accuracy to a derivative of a given order.

HERMITE, a FORTRAN90 library which computes the Hermite interpolant, a polynomial that matches function values and derivatives.

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

PPPACK, a FORTRAN90 library which computes piecewise polynomial functions, including cubic splines.

RBF_INTERP, a FORTRAN90 library which defines and evaluates radial basis interpolants to multidimensional data.

SPLINE, a FORTRAN90 library which can construct and evaluate spline interpolants and approximants.

TEST_APPROX, a FORTRAN90 library which defines test functions for approximation and interpolation.

TOMS446, a FORTRAN90 library which manipulates Chebyshev series for interpolation and approximation;
this is a version of ACM TOMS algorithm 446, by Roger Broucke.

VANDERMONDE_INTERP_1D, a FORTRAN90 library which finds a polynomial interpolant to data y(x) of a 1D argument, by setting up and solving a linear system for the polynomial coefficients, involving the Vandermonde matrix.

Reference:

1. Philip Davis,
   Interpolation and Approximation,
   Dover, 1975,
   ISBN: 0-486-62495-1,
   LC: QA221.D33
2. Carl deBoor,
   A Practical Guide to Splines,
   Springer, 2001,
   ISBN: 0387953663,
   LC: QA1.A647.v27.
3. Jean-Paul Berrut, Lloyd Trefethen,
   Barycentric Lagrange Interpolation,
   SIAM Review,
   Volume 46, Number 3, September 2004, pages 501-517.
4. FM Larkin,
   Root Finding by Divided Differences,
   Numerische Mathematik,
   Volume 37, pages 93-104, 1981.

Source Code:

• divdif.f90, the source code;

Examples and Tests:

• divdif_test.f90, the calling program;
• divdif_test.txt, the output file.

List of Routines:

• CHEBY_T_ZERO returns zeroes of the Chebyshev polynomial T(N)(X).
• CHEBY_U_ZERO returns zeroes of the Chebyshev polynomial U(N)(X).
• DATA_TO_DIF sets up a divided difference table from raw data.
• DATA_TO_DIF_DISPLAY computes a divided difference table and shows how.
• DATA_TO_R8POLY computes the coefficients of a polynomial interpolating data.
• DIF_ANTIDERIV computes the antiderivative of a divided difference polynomial.
• DIF_APPEND adds a pair of data values to a divided difference table.
• DIF_BASIS computes all Lagrange basis polynomials in divided difference form.
• DIF_BASIS_I: I-th Lagrange basis polynomial in divided difference form.
• DIF_DERIV computes the derivative of a polynomial in divided difference form.
• DIF_PRINT prints the polynomial represented by a divided difference table.
• DIF_ROOT seeks a zero of F(X) using divided difference techniques.
• DIF_SHIFT_X replaces one abscissa of a divided difference table.
• DIF_SHIFT_ZERO shifts a divided difference table so all abscissas are zero.
• DIF_TO_R8POLY converts a divided difference table to a standard polynomial.
• DIF_VAL evaluates a divided difference polynomial at a point.
• DIF_VALS evaluates a divided difference polynomial at a set of points.
• LAGRANGE_RULE computes the weights of a Lagrange interpolation rule.
• LAGRANGE_SUM carries out a Lagrange interpolation rule.
• LAGRANGE_VAL applies a naive form of Lagrange interpolation.
• NC_RULE computes the weights of a Newton-Cotes quadrature rule.
• NCC_RULE computes the coefficients of a Newton-Cotes closed quadrature rule.
• NCO_RULE computes the coefficients of a Newton-Cotes open quadrature rule.
• R8_SWAP swaps two R8's.
• R8POLY_ANT_COF integrates a polynomial in standard form.
• R8POLY_ANT_VAL evaluates the antiderivative of a polynomial in standard form.
• R8POLY_BASIS computes all Lagrange basis polynomials in standard form.
• R8POLY_BASIS_1 computes the I-th Lagrange basis polynomial in standard form.
• R8POLY_DER_COF computes the coefficients of the derivative of a polynomial.
• R8POLY_DER_VAL evaluates the derivative of a polynomial in standard form.
• R8POLY_ORDER returns the order of a polynomial.
• R8POLY_PRINT prints out a polynomial.
• R8POLY_SHIFT adjusts the coefficients of a polynomial for a new argument.
• R8POLY_VAL_HORNER evaluates a polynomial in standard form.
• R8VEC_DISTINCT is true if the entries in an R8VEC are distinct.
• R8VEC_EVEN returns N values, evenly spaced between ALO and AHI.
• R8VEC_EVEN_SELECT returns the I-th of N evenly spaced values in [ XLO, XHI ].
• R8VEC_INDICATOR sets an R8VEC to the indicator vector A(I)=I.
• R8VEC_PRINT prints an R8VEC.
• ROOTS_TO_DIF sets a divided difference table for a polynomial from its roots.
• ROOTS_TO_R8POLY converts polynomial roots to polynomial coefficients.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the FORTRAN90 source codes.