|
In the mathematical field of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is the interpolation polynomial for a given set of data points in the Newton form. The Newton polynomial is sometimes called Newton's divided differences interpolation polynomial because the coefficients of the polynomial are calculated using divided differences. Mathematics is commonly defined as the study of patterns of structure, change, and space; more informally, one might say it is the study of figures and numbers. Mathematical knowledge is constantly growing, through research and application, but mathematics itself is not usually considered a natural science. ...
Numerical analysis is the study of algorithms for the problems of continuous mathematics (as distinguished from discrete mathematics). ...
Sir Isaac Newton, FRS (4 January 1643 – 31 March 1727) [OS: 25 December 1642 – 20 March 1727][1] was an English physicist, mathematician, astronomer, alchemist, and natural philosopher who is generally regarded as one of the greatest scientists and mathematicians in history. ...
In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. ...
In mathematics, a polynomial is an expression in which constants and variables are combined using only addition, subtraction, multiplication, and positive whole number exponents (raising to a power). ...
In mathematics divided differences is a recursive division process. ...
As there is only one interpolation polynomial for a given set of data points it is a bit misleading to call the polynomial Newton interpolation polynomial. The more precise name is interpolation polynomial in the Newton form.
Definition
Given a set of k + 1 data points  where no two xj are the same, the interpolation polynomial in the Newton form is linear combination of Newton basis polynomials In mathematics, linear combinations are a concept central to linear algebra and related fields of mathematics. ...
 with the Newton basis polynomials defined as  and the coefficients defined as ![a_j := [y_0,ldots,y_j]](http://upload.wikimedia.org/math/b/4/9/b491d0408158e036e9d4e317aaee6e03.png) where ![[y_0,ldots,y_j]](http://upload.wikimedia.org/math/6/d/a/6daef1a01980a186b9c9b04125727b67.png) is the notation for divided differences. In mathematics divided differences is a recursive division process. ...
Thus the Newton polynomial can be written as
![N(x) := [y_0] + [y_0,y_1](x-x_0) + cdots + [y_0,ldots,y_k](x-x_0)cdots(x-x_{k-1}).](http://upload.wikimedia.org/math/0/b/8/0b8005ccdb0b393c505c88604da9f587.png)
General case 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. That is, one also has the Newton polynomials pn(z) given by In mathematics, particularly in combinatorics, the binomial coefficient of the natural number n and the integer k is defined to be the natural number and (Here, for a natural number m, m! denotes the factorial of m. ...
 In this form, the Newton polynomials generate the Newton series. These are in turn a special case of the general difference polynomials which allow the representation of analytic functions through generalized difference equations. In mathematics, a difference operator maps a function, f(x), to another function, f(x + a) − f(x + b). ...
In mathematics, in the area of complex analysis, the general difference polynomials are a polynomial sequence, a certain subclass of the Sheffer polynomials, which include the Newton polynomials, Selbergs polynomials, and the Stirling interpolation polynomials as special cases. ...
In mathematics, an analytic function is a function that is locally given by a convergent power series. ...
Main idea Solving an interpolation problem leads to a problem in linear algebra where we have to solve a matrix. Using a standard monomial basis for our interpolation polynomial we get the very complicated Vandermonde matrix. By choosing another basis, the Newton basis, we get a much simpler lower triangular matrix which can be solved faster. this article has been removed from wikipedia because it was useless. ...
In linear algebra, a Vandermonde matrix, named after Alexandre-Théophile Vandermonde, is a matrix with a geometric progression in each row, i. ...
In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix where the entries below or above the main diagonal are zero. ...
For k + 1 data points we construct the Newton basis as
 Using these polynomials as a basis for Πk we have to solve  to solve the polynomial interpolation problem.
This matrix can be solved recursively by solving
Application As can be seen from the definition of the divided differences new data points can be added to the data set to create a new interpolation polynomial without recalculation the old coefficients. And when a data point changes we usually do not have to recalculate all coefficients. Furthermore if the xi are distributed equidistantly the calculation of the divided differences becomes significantly easier. Therefore the Newton form of the interpolation polynomial is usually preferred over the Lagrange form for practical purposes. In numerical analysis, a Lagrange polynomial, named after Joseph Louis Lagrange, is the interpolation polynomial for a given set of data points in the Lagrange form. ...
Example The divided differences can be written in the form of a table. For example, for a function f is to be interpolated on points  . Write  the interpolating polynomial is formed as above using the topmost entries in each column as coefficients.
For example, if we are to construct the interpolating polynomial to f(x) = tanx using divided differences, at the points
| x0 = − 1.5 | x1 = − 0.75 | x2 = 0 | x3 = 0.75 | x4 = 1.5 | | f(x0) = − 14.1014 | f(x1) = − 0.931596 | f(x2) = 0 | f(x3) = 0.931596 | f(x4) = 14.1014 | we construct the table  Thus, the interpolating polynomial is    Neglecting minor numerical stability problems in evaluating the entries of the table, this polynomial is essentially the same as that obtained with the same function and data points in the Lagrange polynomial article. In numerical analysis, a Lagrange polynomial, named after Joseph Louis Lagrange, is the interpolation polynomial for a given set of data points in the Lagrange form. ...
See also | 
Feeds |
Contact