Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Newton polynomial
Summary
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.
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
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.
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.
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.
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.