Newton's Divided Differences Interpolation Formula

Suppose that $P_n(x)$ is the polynomial that interpolates the function $y = f(x)$ at the distinct points $(x_0, y_0)$, $(x_1, y_1)$, …, $(x_n, y_n)$, that is, $P_n(x_i) = f(x_i)$ for $i = 0, 1, ..., n$. Using the Divided Differences that we previously saw, we can obtain the polynomials $P_n$ for $n ≥ 1$ as follows:

(1)

\begin{align} \quad P_n(x) = f(x_0) + (x - x_0)f[x_0, x_1] + ... + (x - x_0)(x - x_1)...(x - x_{n-1})f[x_0, x_1, ..., x_n] \end{align}

For example, the polynomial $P_1$ that interpolates the two points $(x_0, y_0)$ and $(x_1, y_1)$ is given by the following formula:

(2)

\begin{align} \quad P_1(x) = f(x_0) + (x - x_0)f[x_0, x_1] \end{align}

This shouldn't be too hard to see since $P_1(x_0) = f(x_0)$ and $P_1(x_1)$ is computed as:

(3)

\begin{align} \quad P_1(x_1) = f(x_0) + (x_1 - x_0) \frac{f(x_1) - f(x_0)}{x_1 - x_0} = f(x_0) + f(x_1) - f(x_0) = f(x_1) \end{align}

Furthermore, the polynomial $P_2$ that interpolates the three points $(x_0, y_0)$, $(x_1, y_1)$, and $(x_2, y_2)$ is given by the following formula:

(4)

\begin{align} \quad P_2(x) = f(x_0) + (x - x_0)f[x_0, x_1] + (x - x_0)(x - x_1)f[x_0, x_1, x_2] \\ \quad P_2(x) = P_1(x) + (x - x_0)(x - x_1)f[x_0, x_1, x_2] \end{align}

Notice that we can easily obtain the polynomial $P_{k+1}(x)$ that interpolates the the points $(x_0, y_0)$, $(x_1, y_1)$, …, $(x_{k+1}, y_{k+1})$ from the polynomial $P_k$ that interpolates the $k$ points $(x_0, y_0)$, $(x_1, y_1)$, …, $(x_{k-1}, y_{k-1})$ as:

(5)

\begin{align} \quad P_{k+1}(x) = P_k(x) + (x - x_0)(x - x_1)...(x - x_k)f[x_0, x_1, ..., x_{k+1}] \end{align}

Example 1

Find the polynomial $P_2$ for the function $y = \sqrt{x}$ that interpolates the points $(1, 1)$, $(4, 2)$, and $(9, 3)$ using Newton's divided difference formula.

Applying Newton's divided difference formula from above and we get that:

(6)

\begin{align} \quad P_2(x) = f(x_0) + (x - x_0)f[x_0, x_1] + (x - x_0)(x - x_1)f[x_0, x_1, x_2] \\ \quad P_2(x) = 1 + (x - 1) \frac{f(x_1) - f(x_0)}{x_1 - x_0} + (x - 1)(x - 4) \frac{f[x_1, x_2] - f[x_0, x_1]}{x_2 - x_0} \\ \quad P_2(x) = 1 + (x - 1) \frac{2 - 1}{4 - 1} + (x - 1)(x - 4) \frac{\frac{3 - 2}{9 - 4} - \frac{2 - 1}{4 - 1}}{9 - 1} \\ \quad P_2(x) = 1 + \frac{1}{3}(x - 1) - \frac{1}{60} (x - 1)(x - 4) \end{align}

The graph of $y = P_2(x)$ is given below.

Example 2

Find the polynomial $P_3$ for the function $y = \sin x$ that interpolates the points $(1, \sin 1)$, $\left ( \frac{\pi}{2}, 1 \right )$, $(2, \sin 2)$ and $(\pi, 0)$ using Newton's divided difference formula.

Applying Newton's divided different formula from above and we get that:

(7)

\begin{align} \quad P_3(x) = f(x_0) + (x - x_0)f[x_0, x_1] + (x - x_0)(x - x_1)f[x_0, x_1, x_2] + (x - x_0)(x - x_1)(x - x_2)f[x_0, x_1, x_2, x_3] \\ \quad P_3(x) = \sin 1 + (x - 1) \frac{1 - \sin 1}{\frac{\pi}{2} - 1} + (x - 1)\left (x - \frac{\pi}{2} \right ) \frac{\frac{\sin 2 - 1}{2 - \frac{\pi}{2}} - \frac{1 - \sin 1}{\frac{\pi}{2} - 1}}{2 - 1} + (x - 1)\left (x - \frac{\pi}{2} \right)(x - 2) \frac{f[x_1, x_2, x_3] - f[x_0, x_1, x_2]}{x_3 - x_0} \\ \quad P_3(x) = \sin 1 + (x - 1) \frac{1 - \sin 1}{\frac{\pi}{2} - 1} + (x - 1)\left (x - \frac{\pi}{2} \right ) \frac{\frac{\sin 2 - 1}{2 - \frac{\pi}{2}} - \frac{1 - \sin 1}{\frac{\pi}{2} - 1}}{2 - 1} + (x - 1)\left (x - \frac{\pi}{2} \right)(x - 2) \frac{\frac{f[x_2, x_3] - f[x_1, x_2]}{x_3 - x_1} - \frac{f[x_1, x_2] - f[x_0, x_1]}{x_2 - x_0}}{x_3 - x_0} \\ \quad P_3(x) = \sin 1 + (x - 1) \frac{1 - \sin 1}{\frac{\pi}{2} - 1} + (x - 1)\left (x - \frac{\pi}{2} \right ) \frac{\frac{\sin 2 - 1}{2 - \frac{\pi}{2}} - \frac{1 - \sin 1}{\frac{\pi}{2} - 1}}{2 - 1} + (x - 1)\left (x - \frac{\pi}{2} \right)(x - 2) \frac{ \left ( \frac{\frac{0 - \sin 2}{\pi - 2} - \frac{\sin 2 - 1}{2 - \frac{\pi}{2}}}{\pi - \frac{\pi}{2}} \right ) - \left ( \frac{\frac{\sin 2 - 1}{2 - \frac{\pi}{2}} - \frac{1 - \sin 1}{\frac{\pi}{2} - 1}}{2 - 1} \right )}{\pi - 1} \\ \end{align}

The graph of $y = P_3(x)$ is given below.