Newton divided differences

Let \(x_0,\dots,x_n\) be distinct nodes. The zeroth-order divided difference is \(f[x_i]=f(x_i)\), and higher orders are obtained recursively. They are symmetric in their nodes, so \(f[x_0,x_1]=f[x_1,x_0]\). Moreover, \(f[x_0,\dots,x_k]\) vanishes if the function is a polynomial of degree less than \(k\), which is useful for checking calculations.

Worked example: for \(f(x)=x^2\) with nodes \(0,1,3\), the values are \(0,1,9\). Then \(f[0,1]=1\), \(f[1,3]=4\), and \(f[0,1,3]=\frac{4-1}{3-0}=1\). With these coefficients, \(p(x)=0+1\cdot x+1\cdot x(x-1)=x^2\) reproduces the function at all three nodes.

Typical error: dividing by the difference of function values instead of the difference of nodes, or using \(x_{i+1}-x_i\) in the denominator of a higher-order difference. Another frequent mistake is forgetting the sign when the order of the nodes is reversed. It is good practice to verify that the resulting polynomial passes through all the original data.