6.3 Divided differences and Newton’s interpolation formulas
Lagrange’s form is awkward when nodes are added, since every basis polynomial changes. Newton’s form builds the interpolant one node at a time: \begin {align*} P_n(x) &= a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\dots \\ &\quad +a_n(x-x_0)(x-x_1)\cdots (x-x_{n-1}), \end {align*}
so that \(P_n = P_{n-1}+a_n(x-x_0)\cdots (x-x_{n-1})\). The coefficients are the divided differences introduced in Section 2.4: \[f[x_i] = f(x_i),\qquad f[x_i,\dots ,x_{i+k}] = \frac {f[x_{i+1},\dots ,x_{i+k}]-f[x_i,\dots ,x_{i+k-1}]}{x_{i+k}-x_i} .\]
Theorem 6.3.1 (Newton’s divided-difference formula). The interpolating polynomial at \(x_0,\dots ,x_n\) is \[P_n(x) = f[x_0]+\sum _{k=1}^nf[x_0,\dots ,x_k](x-x_0)\cdots (x-x_{k-1}) .\]
Proof. We show that the coefficient \(a_n\) of \(x^n\) in the interpolant at \(x_0,\dots ,x_n\) is \(f[x_0,\dots ,x_n]\), by induction on \(n\); the case \(n = 0\) is clear. By Theorem 6.2.1 with \(i = n\), \(j = 0\), \[P_{0,\dots ,n}(x) = \frac {(x-x_0)P_{1,\dots ,n}(x)-(x-x_n)P_{0,\dots ,n-1}(x)}{x_n-x_0} .\] By induction the leading coefficients of \(P_{1,\dots ,n}\) and \(P_{0,\dots ,n-1}\) are \(f[x_1,\dots ,x_n]\) and \(f[x_0,\dots ,x_{n-1}]\), so the coefficient of \(x^n\) above is \(\frac {f[x_1,\dots ,x_n]-f[x_0,\dots ,x_{n-1}]}{x_n-x_0} = f[x_0,\dots ,x_n]\). Since \(P_n-P_{n-1}\) has degree at most \(n\), vanishes at \(x_0,\dots ,x_{n-1}\) and has leading coefficient \(f[x_0,\dots ,x_n]\), it equals \(f[x_0,\dots ,x_n](x-x_0)\cdots (x-x_{n-1})\). □
Comparing the leading coefficient with Theorem 6.1.3 applied to the polynomial \(f-P_{n-1}\) gives the useful relation (generalizing Lemma 2.4.8) \begin {equation} \label {eq:ddderiv} f[x_0,\dots ,x_n] = \frac {f^{(n)}(\xi )}{n!}\qquad \text {for some }\xi \text { between the smallest and largest node.} \end {equation}
Example 6.3.2. Construct the divided-difference table for the Bessel data of Example 6.2.2, and use Newton’s formula at \(x = 1.5\).
Solution.
| \(x_i\) | \(f[x_i]\) | first | second | third | fourth |
| \(1.0\) | \(0.7651977\) | ||||
| \(1.3\) | \(0.6200860\) | \(-0.4837057\) | |||
| \(1.6\) | \(0.4554022\) | \(-0.5489460\) | \(-0.1087339\) | ||
| \(1.9\) | \(0.2818186\) | \(-0.5786120\) | \(-0.0494433\) | \(0.0658784\) | |
| \(2.2\) | \(0.1103623\) | \(-0.5715210\) | \(0.0118183\) | \(0.0680685\) | \(0.0018251\) |
For example, \begin {gather*} f[x_0,x_1] = \frac {0.6200860-0.7651977}{0.3} = -0.4837057,\\ f[x_0,x_1,x_2] = \frac {-0.5489460+0.4837057}{0.6} = -0.1087339 . \end {gather*} The top diagonal gives the coefficients: \begin {align*} P_4(x) &= 0.7651977-0.4837057(x-1.0)-0.1087339(x-1.0)(x-1.3)\\ &\quad +0.0658784(x-1.0)(x-1.3)(x-1.6)\\ &\quad +0.0018251(x-1.0)(x-1.3)(x-1.6)(x-1.9), \end {align*}
and \(P_4(1.5) = 0.5118200\), the same value as Neville’s method, as it must be. The small last coefficient shows that adding a fifth node changed the value by only \(0.0018251\times (0.5)(0.2)(-0.1)(-0.4) = 7.3\times 10^{-6}\); by (6.1), it also estimates \(\frac {f^{(4)}}{4!}\approx 0.0018\).
Equally spaced nodes
When \(x_i = x_0+ih\), write \(x = x_0+sh\). With the forward differences \(\Delta f(x_i) = f(x_{i+1})-f(x_i)\) and \(\Delta ^k = \Delta (\Delta ^{k-1})\), induction gives \(f[x_0,\dots ,x_k] = \frac {\Delta ^kf(x_0)}{k!\,h^k}\), and since \((x-x_0)\cdots (x-x_{k-1}) = h^ks(s-1)\cdots (s-k+1)\), Newton’s formula becomes the Newton forward-difference formula \[P_n(x) = \sum _{k=0}^n\binom {s}{k}\Delta ^kf(x_0),\qquad \binom sk = \frac {s(s-1)\cdots (s-k+1)}{k!} .\] Ordering the nodes backwards from \(x_n\), with \(x = x_n+sh\) and backward differences \(\nabla f(x_i) = f(x_i)-f(x_{i-1})\), gives the Newton backward-difference formula \begin {align*} P_n(x) &= \sum _{k=0}^n(-1)^k\binom {-s}{k}\nabla ^kf(x_n)\\ &= f(x_n)+s\nabla f(x_n)+\frac {s(s+1)}{2}\nabla ^2f(x_n)+\cdots . \end {align*}
The forward formula is natural near the beginning of a table and the backward formula near its end: the first few terms already use the nearest values.
Example 6.3.3. For the Bessel table (\(h = 0.3\)), use the forward formula to approximate \(f(1.1)\) and the backward formula to approximate \(f(2.0)\).
Solution. The forward differences at \(x_0 = 1.0\) are \begin {gather*} \Delta f = -0.1451117,\qquad \Delta ^2f = -0.0195721,\\ \Delta ^3f = 0.0106723,\qquad \Delta ^4f = 0.0003548 . \end {gather*} For \(x = 1.1\), \(s = \frac 13\): \begin {align*} P_4(1.1) &= 0.7651977+\tfrac 13(-0.1451117)+\tfrac {\frac 13(-\frac 23)}{2}(-0.0195721)\\ &\quad +\tfrac {\frac 13(-\frac 23)(-\frac 53)}{6}(0.0106723)+\tfrac {\frac 13(-\frac 23)(-\frac 53)(-\frac 83)}{24}(0.0003548) = 0.7196460 . \end {align*}
For \(x = 2.0\), use the backward differences at \(x_4 = 2.2\): \(\nabla f = -0.1714563\), \(\nabla ^2f = 0.0021273\), \(\nabla ^3f = 0.0110271\), \(\nabla ^4f = 0.0003548\), and \(s = \frac {2.0-2.2}{0.3} = -\frac 23\): \begin {align*} P_4(2.0) &= 0.1103623-\tfrac 23(-0.1714563)-\tfrac 19(0.0021273)\\ &\quad -\tfrac {4}{81}(0.0110271)-\tfrac {7}{243}(0.0003548) = 0.2238754 . \end {align*}
The true values are \(J_0(1.1) = 0.7196220\) and \(J_0(2.0) = 0.2238908\).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.