= Newton polynomial
{c}
{title2=$p_n(x)=\sum_{k=0}^n f[x_0,\ldots,x_k]\prod_{i=0}^{k-1}(x-x_i)$}
{wiki}
= Newton interpolation polynomial
{c}
{synonym}
The <Newton polynomial> expresses the <interpolation polynomial> in products that successively vanish at all previously used <interpolation nodes>. With $y_i=f(x_i)$, the coefficients are <divided differences>:
$$
p_n(x)=f(x_0)+\sum_{k=1}^nf[x_0,\ldots,x_k]
\prod_{i=0}^{k-1}(x-x_i).
$$
A triangular <divided difference> table computes all its coefficients using exactly $n(n+1)/2$ divisions. The <Newton polynomial> and the <Lagrange polynomial> have the same <polynomial degree> bound and the same nodal values, hence are equal by uniqueness of <polynomial interpolation>.
For $f(0)=1$, $f(1)=2$, $f(2)=5$, the complete <divided difference> table is
$$
\begin{array}{c|r|r|r}
x_i&f[x_i]&f[x_i,x_{i+1}]&f[x_i,x_{i+1},x_{i+2}]\\\hline
0&1&1&1\\
1&2&3&\\
2&5&&
\end{array}
$$
The first <divided differences> are $1$ and $3$, and their <divided difference> is $(3-1)/(2-0)=1$. Reading the top entries gives
$$
p_2(x)=1+1(x-0)+1(x-0)(x-1)=1+x+x(x-1)=x^2+1.
$$
The initial term fits $(0,1)$; adding $x$ also fits $(1,2)$; adding $x(x-1)$ fits $(2,5)$ while leaving the first two data values unchanged. This is the practical beauty of the <Newton polynomial>: each new correction respects all previous interpolation constraints.
If a new distinct <interpolation node> $x_{n+1}$ with value $y_{n+1}$ arrives, append one term:
$$
p_{n+1}(x)=p_n(x)+c\prod_{i=0}^n(x-x_i),\qquad
c=\frac{y_{n+1}-p_n(x_{n+1})}{\prod_{i=0}^n(x_{n+1}-x_i)}.
$$
For example, appending $(3,11)$ to the three-point data gives $c=(11-10)/(3\cdot2\cdot1)=1/6$, hence $p_3(x)=x^2+1+x(x-1)(x-2)/6$. Changing the order of the <interpolation nodes> changes the <Newton polynomial> coefficients and products, but not the final <interpolation polynomial> in exact arithmetic.
The products also permit nested evaluation analogous to <Horner's method>. If $a_k=f[x_0,\ldots,x_k]$, start with $b_n=a_n$ and work backwards by $b_k=a_k+(x-x_k)b_{k+1}$; the answer is $b_0$. The three-point example becomes $1+x[1+(x-1)]$, needing two multiplications for each evaluation. This organization is useful when adding observations incrementally or evaluating a stored <Newton polynomial> many times; the <Runge phenomenon> still depends on the <interpolation nodes> rather than on which representation is used.
To justify the update formula, its added <product> vanishes at every previous <interpolation node>. Choosing $c$ by the new residual forces agreement at $x_{n+1}$, so uniqueness of <polynomial interpolation> identifies the result. For $n\geq0$, $p_n$ has <polynomial degree> at most $n$, and the added <product> has <leading coefficient> one. Thus the new <coefficient> $c$ is exactly $f[x_0,\ldots,x_{n+1}]$. The initial state is $p_0(x)=f(x_0)$, with the <empty product> interpreted as one.<NIST Digital Library of Mathematical Functions/3.3 Interpolation>[NIST Digital Library of Mathematical Functions; §3.3(iv), equation 3.3.38 and the following new-point update paragraph]{ref}
Appending $(4,57)$ to the four-point example in <divided difference table> leaves the <Newton polynomial> unchanged: $p_3(4)=57$, so the new fourth <divided difference> is zero. If the appended value is instead $58$, the new <coefficient> is
$$
c=\frac{58-57}{(4+1)\cdot4\cdot(4-2)\cdot(4-3)}=\frac1{40},\qquad
p_4(x)=x^3-2x+1+\frac{(x+1)x(x-2)(x-3)}{40}.
$$
This <polynomial> still takes values $2,1,5,22$ at the original <interpolation nodes>, and now takes value $58$ at $4$. A zero update is a valid completed step: adding another exact sample of the original <polynomial> need not increase the <polynomial degree>.
Back to article page
