Skip to main content

Numerical Analysis A look at rootfinding, quadrature and approximation using analytic and computing tools

Peter Staab

Section 4.3 Newton Divided Differences

We saw above in Section 4.2 that an interpolated polynomial is unique. Therefore the method of finding the polynomial is not important. We will see in this section that another method, Newton Divided Differences has some advantages not seen in the Lagrange form.
🔗
Recall in Section Section 4.1 that a factored form of the polynomial was shown to have advantage mainly due to evaluation speed. Similar to this form, the Newton form of a polynomial given by
\begin{align} P_{0,1,2, \ldots, n}(x) \amp = a_{0} + a_{1} (x-x_{0}) + a_{2} (x-x_{0})(x-x_{1}) + \notag\\ \amp \qquad \qquad \cdots + a_{n} (x-x_{0})(x-x_{1}) \cdots (x-x_{n-1}),\notag\\ \amp = \sum_{k=0}^{n} a_{k} \bigl(\prod_{i=0}^{k-1}(x-x_{i}) \bigr), \tag{4.3.1} \end{align}
has advantages when it comes to interpolations. The number \(x_{0}, x_{1}, \ldots\) can be any set of numbers, however when using this form for interpolation, the \(x\)-values of the data set is typically used.
🔗
Next, if we introduce the notation that
\begin{align} f[x_{0}]\amp = f(x_{0}), \tag{4.3.2}\\ f[x_{0},x_{1}]\amp = \frac{ f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}}, \tag{4.3.3}\\ f[x_{0},x_{1},x_{2}]\amp = \frac{ f[x_{1},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{0}}, \tag{4.3.4} \end{align}
and in general the \(k\)th divided difference of \(f\) with respect to the points \(x_{i}, x_{i+1}, \ldots, x_{i+k}\) is:
\begin{equation} f[x_{i},x_{i+1}, \ldots,x_{i+k}]= \frac{f[x_{i+1},\ldots,x_{i+k}]-f[x_{i},x_{i+1},\ldots,x_{i+k-1}]}{x_{i+k}-x_{i}}.\tag{4.3.5} \end{equation}
🔗
The divided differences that we see above is closely related to derivatives as we will see. That is, \(f[x_{0},x_{1}]\) is approximately equal to \(f'(x_{0})\) or \(f'(x_{1})\text{.}\) Similarly \(f[x_{0},x_{1},x_{2}] \approx f''(x_{1})\text{.}\)
🔗

Subsection 4.3.1 Newton Divided Difference Form of the Interpolating Polynomial

Let’s now return to the interpolation problem. That is for a set of points \(\{(x_{i}, f_{i})\}\text{,}\) for \(i=0,1,\ldots,n\text{,}\) find an \(n\)th degree polynomial that passes through all points. In terms of the Newton’s Divided Difference formulas, let the polynomial \(P_{0,1,2,\ldots,n}(x)\) be that defined in (4.3.1).
🔗
Since the polynomial satisfies \(P_{0,1,2,\ldots,n}(x_{0})=f_{0}\text{,}\) then
\begin{equation*} P_{0,1,2,\ldots,n}(x_{0}) = a_{0} = f(x_{0}) = f[x_{0}]. \end{equation*}
🔗
Also, since the polynomial passes through \((x_{1},f_{1})\text{,}\) then
\begin{equation*} P_{0,1,2,\ldots,n}(x_{1}) = f[x_{1}] = a_{0} + a_{1}(x_{1}-x_{0}), \end{equation*}
setting \(a_{0}=f[x_{0}]\) and solving for \(a_{1}\text{,}\) we get:
\begin{equation*} a_{1} = \frac{f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}}= f[x_{0},x_{1}] . \end{equation*}
🔗
Similarly, we can show that
\begin{equation*} a_{k} = f[x_{0},x_{1},x_{2},\ldots, x_{k}] \qquad \text{for $k=0,1,2,\ldots,n$}. \end{equation*}
🔗
And therefore the interpolating polynomial can be written as
\begin{equation} P_{0,1,2,\ldots,n}(x) = \sum_{k=0}^{n} f[x_{0},x_{1},x_{2},\ldots,x_{k}] \biggl(\prod_{i=0}^{k-1}(x-x_{i}) \biggr).\tag{4.3.6} \end{equation}
🔗
🔗

Subsection 4.3.2 Calculating the Newton Divided Differences

Although the formula for the interpolation through Newton Divided differences in (4.3.6) seems complicated, the determination of the divided differences is not very difficult as we can create a Newton Divided Differences table for data \((x_{0},f(x_{0}))\text{,}\) \((x_{1},f(x_{1}))\text{,}\) \((x_{2},f(x_{2}))\text{,}\) \((x_{3},f(x_{3}))\text{.}\)
🔗
\(x_{0}\) \(f[x_{0}]\)
\(f[x_{0},x_{1}]\)
\(x_{1}\) \(f[x_{1}]\) \(f[x_{0},x_{1},x_{2}]\)
\(f[x_{1},x_{2}]\) \(f[x_{0},x_{1},x_{2},x_{3}]\)
\(x_{2}\) \(f[x_{2}]\) \(f[x_{1},x_{2},x_{3}]\)
\(f[x_{2},x_{3}]\)
\(x_{3}\) \(f[x_{3}]\)
where the first column are the \(x\)-values and the 2nd column are the \(y\) (or \(f\)) values. Both of these are typically given. For the remaining columns, the formula in (4.3.5) is used. Each value in the third column and to the left uses the the divided differences just to the left (above and below) and the \(x\)-values given in the divided difference. The following example shows a specific case.
🔗

Example 4.3.1.

Construct a Newton Divided Differences Table for the data in the table:
🔗
\(x\) \(0\) \(1\) \(3\) \(6\)
\(y\) \(0\) \(1\) \(2\) \(5\)
Solution.
\(x_{0}=0\) \(f[x_{0}]=0\)
\(f[x_{0},x_{1}]=1\)
\(\boxed{x_1=1}\) \(f[x_{1}]=1\) \(f[x_{0},x_{1},x_{2}]=-1/6\)
\(f[x_{1},x_{2}]=1/2\) \(f[x_{0},x_{1},x_{2},x_{3}]=2/45\)
\(x_{2}=3\) \(f[x_{2}]=2\) \(f[x_{1},x_{2},x_{3}]=1/10\)
\(f[x_{2},x_{3}]=1\)
\(\boxed{x_3=6}\) \(f[x_{3}]=5\)
The table is built up from left to right. The second column is the \(y\) values in the table. The third column is from (4.3.3) and so on. For example, using (4.3.4),
\begin{equation*} f[x_{1},x_{2},x_{3}] = \frac{f[x_{2},x_{3}]-f[x_{1},x_{2}]}{x_{3}-x_{1}}= \frac{1 - \frac{1}{2}}{6-1} = - \frac{1}{10}. \end{equation*}
where the numerator is the difference of the two adjacent numbers, and the denominator are the first-column values followed back (see the boxed values above).
🔗
🔗
🔗

Example 4.3.2.

Use the Newton divided difference table above to construct the interpolating polynomial through each of the following sets of points.
🔗
(a)
\((0,0)\text{,}\) \((1,1),\) and \((3,2)\text{.}\)
🔗
Solution.
In this case, \(n=2\text{,}\) so the interpolating polynomial is:
\begin{equation*} \begin{aligned}P_{0,1,2}(x)\amp = f[x_{0}] + f[x_{0},x_{1}] (x-x_{0}) + f[x_{0},x_{1},x_{2}] (x-x_{0})(x-x_{1}),\\ \amp = 0 + 1(x-0) - \frac{1}{6}(x-0)(x-1), \\\amp = -\frac{1}{6}x^{2} + \frac{7}{6}x.\end{aligned} \end{equation*}
🔗
This is the same polynomial as we have seen above in Example 4.1.2 and Example 4.2.2.
🔗
🔗
🔗
(b)
\((0,0)\text{,}\) \((1,1),\) \((3,2)\) and \((6,5)\text{.}\)
🔗
Solution.
In this case, this is the same 3 points as above with an additional point added. Due to the nature of the Newton form of the polynomial, only one term needs to be found:
\begin{equation*} \begin{aligned}P_{0,1,2,3}(x)\amp = P_{0,1,2}(x) + f[x_{0},x_{1},x_{2},x_{3}] (x-x_{0})(x-x_{1})(x-x_{2}) \\\amp = -\frac{1}{6}x^{2} + \frac{7}{6}x +\frac{2}{45}x(x-1)(x-3) \\\amp = \frac{2}{45}\,{x}^{3}-\frac{31}{90}\,{x}^{2}+\frac{13}{10}\,x\end{aligned} \end{equation*}
🔗
🔗
🔗
🔗
The last example shows that the Newton Divided Difference form of the interpolating polynomial is nice in that the entire polynomial need not be regenerated from scratch as Lagrange needs. In the next example, we interpolate through the point of the cumulative density function of the normal distribution as seen in the beginning of the chapter.
🔗

Example 4.3.3.

Use the Newton Divided Differences to find the interpolating polynomial through the points given by the cumulative density function at the beginning of the chapter.
🔗
\(x\) \(0\) \(0.25\) \(0.50\) \(0.75\) \(1\)
\(y\) \(0.0000\) \(0.0987\) \(0.1915\) \(0.2734\) \(0.3413\)
Solution.
First, we build the Newton Divided Difference table:
🔗
\(i\) \(x_{i}\) \(f[x_{i}]\) \(f[x_{i},x_{i+1}]\)
0 \(0\) \(0.0000\)
\(0.3948\)
1 \(0.25\) \(0.0987\) \(-0.0472\)
\(0.3712\) \(-0.05333\)
2 \(0.5\) \(0.1915\) \(-0.0872\) \(0.02026\)
\(0.3276\) \(-0.03307\)
3 \(0.75\) \(0.2734\) \(-0.1120\)
\(0.2716\)
4 \(1.0\) \(0.3413\)
And the interpolating polynomial is:
\begin{equation*} \begin{aligned}P_{0,1,2,3,4}(x)\amp = 0 + 0.3948x-0.0472x(x-0.25) -0.053333x(x-0.25)(x-0.5)\\\amp \qquad +0.02026x(x-0.25)(x-0.5)(x-0.75) \\\amp = 0.01923862081x^{4}-0.08107936270x^{3}+0.00479110462x^{2}+0.3983943834x,\end{aligned} \end{equation*}
🔗
The coefficients of each term are the upper diagonal elements. The corresponding \(x\) terms are the products of the \(x-x_{i}\) terms up (but not including the current one). For example, the term associated with \(-0.0472\) goes up to \(i=2\text{.}\) These \(x\) terms are \((x-x_{0})(x-x_{1}) = (x-0)(x-0.25)\text{.}\) The resulting polynomial is the same as that in Example 4.2.3, which used the Lagrange form of the interpolation polynomial.
🔗
🔗
🔗
🔗

Subsection 4.3.3 Errors and Interpolation, revisited

In Example 4.2.7, we found the interpolating polynomial that passes through the sine curve for \(x=0,\pi/2\) and \(\pi\text{.}\) First, let’s use Newton’s Divided Difference to find this polynomial again.
🔗
The interpolating data will be:
🔗
\(x\) 0 \(\pi/2\) \(\pi\)
\(y\) 0 1 0
Using Newton’s Divided Differences we get the table:
🔗
\(i\) \(x_{i}\) \(f[x_{i}]\) \(f[x_{i},x_{i+1}]\) \(f[x_{0},x_{1},x_{2}]\)
0 \(0\) \(0\)
\(2/\pi\)
1 \(\pi/2\) \(1\) \(-4/\pi^{2}\)
\(-2/\pi\)
2 \(\pi\) \(0\)
and for the interpolating polynomial, we get:
\begin{equation*} \begin{aligned}P_{0,1,2}(x)\amp = 0 + \frac{2}{\pi}x - \frac{4}{\pi^{2}}x(x-\pi/2) \\\amp = -\frac{4}{\pi^{2}}x^{2} + \frac{4}{\pi}x\end{aligned} \end{equation*}
which is the same as seen in Example 4.2.7.
🔗
Next, let’s add two additional points on the sine curve when \(x=\pi/4\) and \(x=3\pi/4\text{.}\) We can add these points into the table and expand the table. (Note: even though the \(x\)-values are not listed smallest to largest, this does not matter).
🔗
\(i\) \(x_{i}\) \(f[x_{i}]\) \(f[x_{i},x_{i+1}]\)
\(0\) \(0\) \(0\)
\(2/\pi\)
\(1\) \(\pi/2\) \(1\) \(\qquad \qquad-4/\pi^{2}\)
\(-2/\pi\) \(\qquad \qquad(32\sqrt{2}-48)/(3\pi^{3})\)
\(2\) \(\pi\) \(0\) \(\qquad \qquad (8\sqrt{2}-24)/(3\pi^{2})\) \(\qquad (192-128\sqrt{2})/(3\pi^{4})\)
\(-2\sqrt{2}/(3\pi)\) \(\qquad (96-64\sqrt{2})/(3\pi^{3})\)
\(3\) \(\pi/4\) \(\sqrt{2}/2\) \(\qquad\qquad -8\sqrt{2}/(3\pi^{2})\)
\(0\)
\(4\) \(3\pi/4\) \(\sqrt{2}/2\)
So the interpolation polynomial is:
\begin{equation*} \begin{aligned}P_{0,1,2,3,4}(x)\amp = 0 + \frac{2}{\pi}x -\frac{4}{\pi^{2}}x(x-\pi/2) +\frac{32\sqrt{2}-48}{3\pi^{3}}x(x-\pi/2)(x-\pi) \\\amp \qquad + \frac{192-128\sqrt{2}}{3\pi^{4}}x(x-\pi/2)(x-\pi)(x-\pi/4)\end{aligned} \end{equation*}
🔗
From the error formula given in Theorem 4.2.6.
\begin{equation*} \begin{aligned}|f(x)-P(x)|\amp = \biggl\vert \frac{f^{(n+1)}(\xi(x))}{(n+1)!}\prod_{i=0}^{n} (x-x_{i}) \biggr\vert\end{aligned} \end{equation*}
🔗
in this case \(|f^{(n+1)}(x)| \leq 1\) so
\begin{equation*} \begin{aligned}|f(x)-P(x)| \leq \frac{1}{(n+1)!}\prod_{i=0}^{n} (x-x_{i})\end{aligned} \end{equation*}
🔗
It can be shownThis is quite difficult to show and is not a very tight bound, but is sufficient for this example. See ???? for a reference. that if the \(x_{i}\) are equally-spaced on the interval \([a,b]\text{,}\) that
\begin{equation*} \begin{aligned}\prod_{i=0}^{n} (x-x_{i}) \leq (b-a)^{n} \frac{n!}{n^{n}}.\end{aligned} \end{equation*}
🔗
Therefore the error in this situation can be shown to be:
\begin{equation*} \begin{aligned}|f(x)-P(x)|\amp \leq \frac{1}{(n+1)!}\frac{\pi^{n} n!}{n^{n}}\\\amp = \frac{(\pi)^{n}}{(n+1) n^{n}}\end{aligned} \end{equation*}
and in the case of \(n=4\text{,}\) this is
\begin{equation*} \begin{aligned}|f(x)-P(x)| \leq 0.0761.\end{aligned} \end{equation*}
🔗
Therefore theoretically, the maximum error between the sine function and the interpolated polynomial through the five equally-space points on \([0,\pi\)] is bounded by 0.0761.
🔗
🔗

Subsection 4.3.4 Summary

This section showed a second method called Newton Divided Difference method for finding an interpolated polynomial through a set of points. The two advantages to this method is that the polynomial can be found by finding a divided difference table and that additional points can be added without recalculating the entire polynomial.
🔗
🔗
🔗
PrevTopNext