In the mathematical field of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is an interpolation polynomial for a given set of data points. The Newton polynomial is sometimes called Newton's divided differences interpolation polynomial because the coefficients of the polynomial are calculated using Newton's divided differences method.
Definition
Given a set of k + 1 data points
where no two xj are the same, the Newton interpolation polynomial is a linear combination of Newton basis polynomials
with the Newton basis polynomials defined as
for j > 0 and .
The coefficients are defined as
where
is the notation for divided differences.
Thus the Newton polynomial can be written as
Newton forward divided difference formula
The Newton polynomial can be expressed in a simplified form when
are arranged consecutively with equal spacing. Introducing the notation for each and , the difference can be written as . So the Newton polynomial becomes
This is called the Newton forward divided difference formula.
Newton backward divided difference formula
If the nodes are reordered as , the Newton polynomial becomes
If are equally spaced with and for i = 0, 1, ..., k, then,
is called the Newton backward divided difference formula.
Significance
Newton's formula is of interest because it is the straightforward and natural differences-version of Taylor's polynomial. Taylor's polynomial tells where a function will go, based on its y value, and its derivatives (its rate of change, and the rate of change of its rate of change, etc.) at one particular x value. Newton's formula is Taylor's polynomial based on finite differences instead of instantaneous rates of change.
Addition of new points
As with other difference formulas, the degree of a Newton interpolating polynomial can be increased by adding more terms and points without discarding existing ones. Newton's form has the simplicity that the new points are always added at one end: Newton's forward formula can add new points to the right, and Newton's backward formula can add new points to the left.
The accuracy of polynomial interpolation depends on how close the interpolated point is to the middle of the x values of the set of points used. Obviously, as new points are added at one end, that middle becomes farther and farther from the first data point. Therefore, if it isn't known how many points will be needed for the desired accuracy, the middle of the x-values might be far from where the interpolation is done.
Gauss, Stirling, and Bessel all developed formulae to remedy that problem.
Gauss's formula alternately adds new points at the left and right ends, thereby keeping the set of points centered near the same place (near the evaluated point). When so doing, it uses terms from Newton's formula, with data points and x values renamed in keeping with one's choice of what data point is designated as the x0 data point.
Stirling's formula remains centered about a particular data point, for use when the evaluated point is nearer to a data point than to a middle of two data points.
Bessel's formula remains centered about a particular middle between two data points, for use when the evaluated point is nearer to a middle than to a data point.
Bessel and Stirling achieve that by sometimes using the average of two differences, and sometimes using the average of two products of binomials in x, where Newton's or Gauss's would use just one difference or product. Stirling's uses an average difference in odd-degree terms (whose difference uses an even number of data points); Bessel's uses an average difference in even-degree terms (whose difference uses an odd number of data points).
Strengths and weaknesses of various formulae
For any given finite set of data points, there is only one polynomial of least possible degree that passes through all of them. Thus, it is appropriate to speak of the "Newton form", or Lagrange form, etc., of the interpolation polynomial. However, different methods of computing this polynomial can have differing computational efficiency. There are several similar methods, such as those of Gauss, Bessel and Stirling. They can be derived from Newton's by renaming the x-values of the data points, but in practice they are important.
Bessel vs. Stirling
The choice between Bessel and Stirling depends on whether the interpolated point is closer to a data point, or closer to a middle between two data points.