One drawback of Lagrange interpolation is that when we add a new node and corresponding function value, the Lagrange basis functions must be completely recomputed. This raises the question: Can we make full use of the existing interpolating polynomial and simply add a correction term to obtain the new interpolating polynomial? In other words, can we give the interpolating polynomial in a recursive form?
The Newton interpolation polynomial provides such a form. To make full use of existing results, the basis functions should grow as nodes are added. Therefore, we select the following special basis functions:
Clearly, when using this form of basis functions, adding a new node \(x_{n+1}\) only requires adding a new term \(c_{n+1}(x - x_0)(x - x_1) \cdots (x - x_n)\) to equation (10.3.2).
The coefficients \(c_0, c_1, c_2, \ldots, c_n\) in (10.3.2) can be determined by the interpolation condition (10.1.1). Setting \(x = x_0\) in (10.3.2), we get:
and call it the first-order divided difference of \(f\) at nodes \(x_0\) and \(x_1\text{.}\) It represents the ratio of the function difference to the variable difference.
To understand how this expression relates to divided differences, we substitute the known values \(c_0 = f_0\) and \(c_1 = \frac{f_1 - f_0}{x_1 - x_0}\text{:}\)
Therefore, we have shown that \(c_2 = f[x_0, x_1, x_2]\text{.}\) This calculation reveals the pattern: each coefficient \(c_i\) in the Newton form equals the \(i\)-th order divided difference starting from \(x_0\text{.}\)
To illustrate the detailed computation of \(c_3\text{,}\) we follow the same systematic approach used for \(c_2\text{.}\) This calculation will show how the pattern extends to higher-order divided differences.
By adding and subtracting appropriate terms and using the fact that \(f[x_1, x_2] = \frac{f_2 - f_1}{x_2 - x_1}\) and \(f[x_0, x_1] = \frac{f_1 - f_0}{x_1 - x_0}\text{,}\) we can show through algebraic manipulation (similar to the derivation of \(c_2\)) that:
Detailed algebraic steps: The key insight in the simplification is to group terms by their order and use the recursive nature of divided differences. Specifically, when we expand all the divided differences in terms of function values and manipulate the resulting expression, the terms cancel in such a way that we obtain the standard form of a third-order divided difference.
This computation confirms the general pattern: \(c_i = f[x_0, x_1, \ldots, x_i]\) for all \(i\text{,}\) establishing that each coefficient in the Newton form equals the corresponding divided difference.
The \(i\)-th order divided difference \(f[x_0, x_1, \ldots, x_i]\) can be expressed as a linear combination of \(f(x_0), f(x_1), \ldots, f(x_i)\text{.}\) For example:
If \(f(x)\) is a polynomial of degree \(m\text{,}\) then the \(i\)-th order divided difference \(f[x_0, \ldots, x_{i-1}, x]\) with respect to \(x_0, \ldots, x_{i-1}, x\) is a polynomial of degree \(m - i\) when \(i \leq m\text{,}\) and is identically zero when \(i > m\text{.}\)
From (10.3.3), we see that constructing the Newton interpolation polynomial reduces to computing divided differences. The computation of divided differences can be carried out row by row in a table format, as shown in Table 10.3.5.
We can use SageMath to compute divided differences automatically. The following code implements a recursive function that computes the \(i\)-th order divided difference \(f[x_i, x_{i+1}, \ldots, x_j]\text{:}\)
For practical computation, it’s more efficient to build the entire divided difference table at once using dynamic programming: There is an error in the code, fix it.
Find an interpolating polynomial \(p_4(x)\) of degree at most 4 that passes through all five data points, and compute an approximate value for \(f(4.0)\text{.}\)
Example 10.3.7 clearly demonstrates the main advantage of Newton interpolation over Lagrange interpolation: when adding new nodes, we simply add new terms to the existing polynomial rather than recomputing everything from scratch. This recursive structure makes Newton interpolation particularly efficient for incremental interpolation.
Additionally, the nested form (Horner’s method) used in part (2) provides an efficient way to evaluate the polynomial, requiring only \(n\) multiplications and \(n\) additions for a degree-\(n\) polynomial, compared to \(O(n^2)\) operations for direct evaluation.
