Editing Newton polynomial (section)

==Definition==
Given a set of ''k''&nbsp;+&nbsp;1 data points

:<math>(x_0, y_0),\ldots,(x_j, y_j),\ldots,(x_k, y_k)</math>

where no two ''x''<sub>''j''</sub> are the same, the Newton interpolation polynomial is a [[linear combination]] of '''Newton basis polynomials'''

:<math>N(x) := \sum_{j=0}^{k} a_{j} n_{j}(x)</math>

with the Newton basis polynomials defined as

:<math>n_j(x) := \prod_{i=0}^{j-1} (x - x_i)</math>

for ''j'' > 0 and <math>n_0(x) \equiv 1</math>.

The coefficients are defined as

:<math>a_j := [y_0,\ldots,y_j]</math>

where <math>[y_0,\ldots,y_j]</math> are the [[divided differences]] defined as 
<math display="block">\begin{align}
\mathopen[y_k] &:= y_k, && k \in \{ 0,\ldots,n\} \\
\mathopen[y_k,\ldots,y_{k+j}] &:= \frac{[y_{k+1},\ldots , y_{k+j}] - [y_{k},\ldots , y_{k+j-1}]}{x_{k+j}-x_k}, && k\in\{0,\ldots,n-j\},\ j\in\{1,\ldots,n\}.
\end{align}</math>

Thus the Newton polynomial can be written as

:<math>N(x) = [y_0] + [y_0,y_1](x-x_0) + \cdots + [y_0,\ldots,y_k](x-x_0)(x-x_1)\cdots(x-x_{k-1}).</math>

===Newton forward divided difference formula=== 
The Newton polynomial can be expressed in a simplified form when <math>x_0, x_1, \dots, x_k</math> are arranged consecutively with equal spacing.

If <math>x_0, x_1, \dots, x_k</math> are consecutively arranged and equally spaced with <math>{x}_{i}={x}_{0}+ih  </math> for ''i'' = 0, 1, ..., ''k'' and some variable x is expressed as <math>{x}={x}_{0}+sh</math>, then the difference <math>x-x_i</math> can be written as <math>(s-i)h</math>. So the Newton polynomial becomes
:<math>\begin{align}
N(x) &= [y_0] + [y_0,y_1]sh + \cdots + [y_0,\ldots,y_k] s (s-1) \cdots (s-k+1){h}^{k} \\
&= \sum_{i=0}^{k}s(s-1) \cdots (s-i+1){h}^{i}[y_0,\ldots,y_i] \\
&= \sum_{i=0}^{k}{s \choose i}i!{h}^{i}[y_0,\ldots,y_i].
\end{align}</math>

This is called the '''Newton forward divided difference formula'''.{{citation needed|date=October 2017}}

===Newton backward divided difference formula===
If the nodes are reordered as <math>{x}_{k},{x}_{k-1},\dots,{x}_{0}</math>, the Newton polynomial becomes

:<math>N(x)=[y_k]+[{y}_{k}, {y}_{k-1}](x-{x}_{k})+\cdots+[{y}_{k},\ldots,{y}_{0}](x-{x}_{k})(x-{x}_{k-1})\cdots(x-{x}_{1}).</math>

If <math>{x}_{k},\;{x}_{k-1},\;\dots,\;{x}_{0}</math> are equally spaced with <math>{x}_{i}={x}_{k}-(k-i)h</math> for ''i'' = 0, 1, ..., ''k'' and <math>{x}={x}_{k}+sh</math>, then,

:<math>\begin{align}
N(x) &= [{y}_{k}]+ [{y}_{k}, {y}_{k-1}]sh+\cdots+[{y}_{k},\ldots,{y}_{0}]s(s+1)\cdots(s+k-1){h}^{k} \\
&=\sum_{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots,{y}_{k-i}].
\end{align}</math>

This is called the '''Newton backward divided difference formula'''.{{citation needed|date=October 2017}}