DIVDIF
Divided Difference Polynomials
DIVDIF
is a MATLAB library which
creates, prints and manipulates divided
difference polynomials.
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 NewtonCotes 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 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 MATLAB library which
evaluates the Bernstein polynomials,
useful for uniform approximation of functions;
CHEBYSHEV,
a MATLAB library which
computes the Chebyshev interpolant/approximant to a given function
over an interval.
DIFFER,
a MATLAB 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.
divdif_test
HERMITE,
a MATLAB library which
computes the Hermite interpolant, a polynomial that matches function values
and derivatives.
INTERP,
a MATLAB library which
can be used for parameterizing and interpolating data;
LAGRANGE_INTERP_1D,
a MATLAB library 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,
a MATLAB library which
defines and evaluates radial basis function (RBF) interpolants to 1D data.
SHEPARD_INTERP_1D,
a MATLAB library which
defines and evaluates Shepard interpolants to 1D data,
which are based on inverse distance weighting.
SPLINE,
a MATLAB library which
includes many routines to construct
and evaluate spline interpolants and approximants.
TEST_APPROX,
a MATLAB library which
defines a number of test problems
for approximation and interpolation.
TEST_INTERP_1D,
a MATLAB library which
defines test problems for interpolation of data y(x),
depending on a 1D argument.
VANDERMONDE_INTERP_1D,
a MATLAB library 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:

Philip Davis,
Interpolation and Approximation,
Dover, 1975,
ISBN: 0486624951,
LC: QA221.D33

Carl deBoor,
A Practical Guide to Splines,
Springer, 2001,
ISBN: 0387953663,
LC: QA1.A647.v27.

JeanPaul Berrut, Lloyd Trefethen,
Barycentric Lagrange Interpolation,
SIAM Review,
Volume 46, Number 3, September 2004, pages 501517.

FM Larkin,
Root Finding by Divided Differences,
Numerische Mathematik,
Volume 37, pages 93104, 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.

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 Kth derivatives
of all Lagrange basis polynomials.

dif_basis_i.m,
computes the Ith Lagrange basis polynomial in divided difference form.

dif_deriv_table.m,
computes the derivative of a polynomial in divided difference form.

dif_derivk_table.m,
computes the Kth 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_val.m,
evaluates a divided difference polynomial at a point.

dif_vals.m,
evaluates a divided difference polynomial at a set of points.

lagrange_rule.m,
computes the weights of a Lagrange interpolation rule.

lagrange_sum.m,
carries out a Lagrange interpolation rule.

lagrange_val.m,
applies a naive form of Lagrange interpolation.

nc_rule.m,
computes the weights of a NewtonCotes quadrature rule.

ncc_rule.m,
computes the coefficients of a NewtonCotes closed quadrature rule.

nco_rule.m,
computes the coefficients of a NewtonCotes open quadrature rule.

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_cof.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 Ith Lagrange basis polynomial in standard form.

r8poly_der_cof.m,
computes the coefficients of the derivative of a polynomial.

r8poly_der_val.m,
evaluates the derivative of a polynomial in standard form.

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_val_horner.m,
evaluates a polynomial in standard form.

r8vec_distinct.m,
is true if the entries in an R8VEC are distinct.

r8vec_indicator.m,
sets an R8VEC to the indicator vector A(I)=I.

r8vec_print.m,
prints an R8VEC.

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.

timestamp.m,
prints the current YMDHMS date as a time stamp.
Examples and Tests:

divdif_test.m, calls all the tests;

divdif_test.sh, runs all the tests;

divdif_test.txt,
the output file.

divdif_test01.m,
tests DATA_TO_DIF_DISPLAY, DIF_APPEND, DIF_ANTIDERIV,
DIF_DERIV_TABLE, DIF_SHIFT_ZERO, and DIF_VAL;

divdif_test02.m,
tests DATA_TO_DIF and DIF_VAL;

divdif_test03.m,
tests DIF_BASIS;

divdif_test05.m,
tests DIF_TO_R8POLY and DIF_SHIFT_ZERO;

divdif_test06.m,
tests R8POLY*.

divdif_test07.m,
tests R8POLY_BASIS;

divdif_test08.m,
tests R8POLY_SHIFT.

divdif_test16.m,
tests NCC_RULE;

divdif_test17.m,
tests NCO_RULE;

divdif_test18.m,
tests ROOTS_TO_DIF and DIF_TO_R8POLY.

divdif_test19.m,
tests ROOTS_TO_R8POLY.

divdif_test20.m,
tests DIF_DERIVK_TABLE.

divdif_test21.m,
tests DIF_BASIS_DERIV.

divdif_test22.m,
tests DIF_BASIS_DERIVK.
Last modified on 07 January 2019.