divdif

divdif, an Octave code which creates, prints and manipulates divided difference polynomials from a table of values (x,f(x)). The code can compute the coefficients of the Newton and power sum forms of the interpolating polynomial. It can compute the derivative or antiderivate polynomial. It can compute the form of the Lagrange basis polynomials. It can compute the points and weights for Newton Cotes quadrature rules. It can compute the weights for a Lagrange interpolation scheme.

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 information on this web page is distributed under the MIT license.

Languages:

divdif is available in a C version and a C++ version and a Fortran77 version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

divdif_test

bernstein_polynomial, an Octave code which evaluates the Bernstein polynomials, useful for uniform approximation of functions;

chebyshev_polynomial, an Octave code which considers the Chebyshev polynomials T(i,x), U(i,x), V(i,x) and W(i,x). Functions are provided to evaluate the polynomials, determine their zeros, produce their polynomial coefficients, produce related quadrature rules, project other functions onto these polynomial bases, and integrate double and triple products of the polynomials.

differ, an Octave code 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_polynomial, an Octave code which computes the Hermite interpolant, a polynomial that matches function values and derivatives.

interp, an Octave code which can be used for parameterizing and interpolating data;

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

rbf_interp_1d, an Octave code which defines and evaluates radial basis function (RBF) interpolants to 1D data.

shepard_interp_1d, an Octave code which defines and evaluates Shepard interpolants to 1D data, which are based on inverse distance weighting.

spline, an Octave code which includes many routines to construct and evaluate spline interpolants and approximants.

test_approx, an Octave code which defines a number of test problems for approximation and interpolation.

test_interp_1d, an Octave code which defines test problems for interpolation of data y(x), depending on a 1D argument.

vandermonde_interp_1d, an Octave code which finds a polynomial interpolant to a function of 1D data 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:

• cheby_t_zero.m, returns zeroes of the Chebyshev polynomial T(N)(X).
• cheby_u_zero.m, returns zeroes of the Chebyshev polynomial U(N)(X).
• data_to_dif.m, computes a divided difference table.
• data_to_dif_display.m, computes a divided difference table and shows how.
• data_to_r8poly.m, computes the coefficients of a polynomial interpolating data.
• data_to_table.m, computes the full divided difference table for given data.
• dif_antideriv.m, computes the antiderivative of a divided difference polynomial.
• dif_append.m, adds a pair of data values to a divided difference table.
• dif_basis.m, computes all Lagrange basis polynomials in divided difference form.
• dif_basis_deriv.m, computes divided difference tables for the first derivatives of all Lagrange basis polynomials.
• dif_basis_derivk.m, computes divided difference tables for the K-th derivatives of all Lagrange basis polynomials.
• dif_basis_i.m, computes the I-th Lagrange basis polynomial in divided difference form.
• dif_deriv_table.m, computes the derivative of a polynomial in divided difference form.
• dif_print.m, prints the polynomial represented by a divided difference table.
• dif_shift_x.m, replaces one abscissa of a divided difference table with a new one.
• dif_shift_zero.m, shifts a divided difference table so that all abscissas are zero.
• dif_to_r8poly.m, converts a divided difference table to standard polynomial form.
• dif_value.m, evaluates a divided difference polynomial at a point.
• lagrange_rule.m, computes the weights of a Lagrange interpolation rule.
• lagrange_sum.m, carries out a Lagrange interpolation rule.
• lagrange_value.m, applies a naive form of Lagrange interpolation.
• nc_rule.m, computes the weights of a Newton-Cotes quadrature rule.
• ncc_rule.m, computes the coefficients of a Newton-Cotes closed quadrature rule.
• nco_rule.m, computes the coefficients of a Newton-Cotes open quadrature rule.
• r8mat_print.m, prints an R8MAT;
• r8mat_print_some.m, prints some of an R8MAT;
• r8mat_transpose_print.m, prints the transpose of an R8MAT;
• r8mat_transpose_print_some.m, prints some of the transpose of an R8MAT;
• r8poly_ant_coef.m, integrates a polynomial in standard form.
• r8poly_ant_val.m, evaluates the antiderivative of a polynomial in standard form.
• r8poly_basis.m, computes all Lagrange basis polynomials in standard form.
• r8poly_basis_1.m, computes the I-th Lagrange basis polynomial in standard form.
• r8poly_deriv_coef.m, computes the coefficients of the derivative of a polynomial.
• r8poly_deriv_value.m, evaluates the derivative of a polynomial.
• r8poly_order.m, returns the order of a polynomial.
• r8poly_print.m, prints out a polynomial.
• r8poly_shift.m, adjusts the coefficients of a polynomial for a new argument.
• r8poly_value_horner.m, evaluates a polynomial in standard form.
• r8vec_is_distinct.m, is true if the entries in an R8VEC are distinct.
• r8vec_print.m, prints an R8VEC.
• r8vec_transpose_print.m, prints an R8VEC, transposed.
• r8vec2_print.m, prints an R8VEC2.
• roots_to_dif.m, sets up a divided difference table for a polynomial from its roots.
• roots_to_r8poly.m, converts polynomial roots to polynomial coefficients.