In the mathematical field of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton,[1] is an interpolation polynomial for a given set of data points.
, then, This is called the Newton backward divided difference formula.
[citation needed] Newton's formula is of interest because it is the straightforward and natural differences-version of Taylor's polynomial.
Newton's formula is Taylor's polynomial based on finite differences instead of instantaneous rates of change.
for some unknown function in Newton divided difference formulas, if the representation of x in the previous sections was instead taken to be
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.
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.
For any given finite set of data points, there is only one polynomial of least possible degree that passes through all of them.
They can be derived from Newton's by renaming the x-values of the data points, but in practice they are important.
Lagrange is sometimes said to require less work, and is sometimes recommended for problems in which it is known, in advance, from previous experience, how many terms are needed for sufficient accuracy.
The divided difference methods have the advantage that more data points can be added, for improved accuracy.
The terms based on the previous data points can continue to be used.
There is a "barycentric" version of Lagrange that avoids the need to re-do the entire calculation when adding a new data point.
Additionally, suppose that one wants to find out if, for some particular type of problem, linear interpolation is sufficiently accurate.
That can be determined by evaluating the quadratic term of a divided difference formula.
If the problem is sufficiently important, or if the quadratic term is nearly big enough to matter, then one might want to determine whether the sum of the quadratic and cubic terms is large enough to matter in the problem.
The divided difference formulas are more versatile, useful in more kinds of problems.
The Lagrange formula is at its best when all the interpolation will be done at one x value, with only the data points' y values varying from one problem to another, and when it is known, from past experience, how many terms are needed for sufficient accuracy.
For the special case of xi = i, there is a closely related set of polynomials, also called the Newton polynomials, that are simply the binomial coefficients for general argument.
Using a standard monomial basis for our interpolation polynomial we get the very complicated Vandermonde matrix.
This system of equations can be solved iteratively by solving While the interpolation formula can be found by solving a linear system of equations, there is a loss of intuition in what the formula is showing and why Newton's interpolation formula works is not readily apparent.
Induction step: Suppose the result holds for any divided difference involving at most
Then using the induction hypothesis in the following 2nd equality we see that for a divided difference involving
We formulate next Fact 2 which for purposes of induction and clarity we also call Statement
(It will be helpful for fluent reading of the proof to have the precise statement and its subtlety in mind:
Furthermore, if the xi are distributed equidistantly the calculation of the divided differences becomes significantly easier.
Therefore, the divided-difference formulas are usually preferred over the Lagrange form for practical purposes.
Write Then the interpolating polynomial is formed as above using the topmost entries in each column as coefficients.
For example, suppose we are to construct the interpolating polynomial to f(x) = tan(x) using divided differences, at the points Using six digits of accuracy, we construct the table Thus, the interpolating polynomial is Given more digits of accuracy in the table, the first and third coefficients will be found to be zero.