= Divided difference table
{title2=$D_{i,k}=f[x_i,\ldots,x_{i+k}]$}
A <divided difference table> arranges <divided differences> by starting <interpolation node> $i$ and order $k$. Its base column is $D_{i,0}=f(x_i)$; every later entry uses two neighboring entries from the previous column:
$$
D_{i,k}=\frac{D_{i+1,k-1}-D_{i,k-1}}{x_{i+k}-x_i},\qquad
1\leq k\leq n,\quad 0\leq i\leq n-k.
$$
The denominator spans all $k+1$ <interpolation nodes> of that entry, even though the numerator uses adjacent table entries. The <interpolation nodes> must be distinct; they need not be equally spaced or sorted.<NIST Digital Library of Mathematical Functions/3.3 Interpolation>[NIST Digital Library of Mathematical Functions; §3.3(iii), equation 3.3.34: initial values and divided-difference recurrence for distinct nodes]{ref}
Take the <polynomial> $f(x)=x^3-2x+1$ at the <interpolation nodes> $(-1,0,2,3)$, giving values $(2,1,5,22)$. Its <divided difference table> is
$$
\begin{array}{c|r|r|r|r}
x_i&D_{i,0}&D_{i,1}&D_{i,2}&D_{i,3}\\\hline
-1&2&-1&1&1\\
0&1&2&5&\\
2&5&17&&\\
3&22&&&
\end{array}
$$
The first <divided differences> are $(1-2)/(0+1)=-1$, $(5-1)/(2-0)=2$, and $(22-5)/(3-2)=17$. The second <divided differences> use the wider spans: $(2+1)/(2+1)=1$ and $(17-2)/(3-0)=5$. The third <divided difference> is $(5-1)/(3+1)=1$. Reading the top row gives the <Newton polynomial> coefficients $(2,-1,1,1)$, rather than all the entries in any one column.
The resulting <Newton polynomial> grows through four partial <interpolants>:
$$
\begin{aligned}
p_0(x)&=2,\\
p_1(x)&=2-(x+1)=1-x,\\
p_2(x)&=2-(x+1)+(x+1)x=x^2+1,\\
p_3(x)&=2-(x+1)+(x+1)x+(x+1)x(x-2)=x^3-2x+1.
\end{aligned}
$$
At $x=2$, $p_1(2)=-1$ misses $f(2)=5$ by $6$; the correction $(x+1)x$ supplies exactly $6$ there and vanishes at the earlier <interpolation nodes> $-1,0$. At $x=3$, $p_2(3)=10$ misses $f(3)=22$ by $12$; the correction $(x+1)x(x-2)$ supplies exactly $12$ there and vanishes at all three earlier <interpolation nodes>. Each added term therefore preserves the previous agreements while satisfying the next one.
\Image[/divided-difference-triangle-newton-stages.png]
{title=Divided-difference triangle and successive Newton interpolants for the constructed polynomial x cubed minus 2x plus 1}
For $n+1$ <interpolation nodes>, the triangle contains $n+(n-1)+\cdots+1=n(n+1)/2$ recurrence steps. Once the top row is known, nested evaluation of the <Newton polynomial> uses only $n$ multiplications and $n$ additions per argument. The triangle organizes the work; the factors explain why the construction works.
Back to article page
