🔹 Definition: Second Divided Differences

The second divided differences of a function \(f(x)\) are defined from the first divided differences as:

\[ f[x_i, x_{i+1}, x_{i+2}] = \frac{f[x_{i+1}, x_{i+2}] - f[x_i, x_{i+1}]}{x_{i+2} - x_i} \]

Similarly, the \(n\)-th divided differences are defined recursively from the \((n-1)\)-th differences:

\[ f[x_0, x_1, \dots, x_n] = \frac{f[x_1, x_2, \dots, x_n] - f[x_0, x_1, \dots, x_{n-1}]}{x_n - x_0} \]

Note that the 0th divided differences are simply \(f(x_i)\). Using this notation:

\[ a_2 = f[x_0, x_1, x_2] \]

🔹 Remark: Recursive Property

The quadratic polynomial:

\[ p_2(x) = f(x_0) + f[x_0,x_1](x - x_0) + f[x_0,x_1,x_2](x - x_0)(x - x_1) \]

passes through the first three collocation points. Notice that this polynomial is obtained by simply adding a second-degree term to the first-degree polynomial \(p_1(x)\). This recursive property generalizes to higher degrees.

For example, the third coefficient is:

\[ a_3 = f[x_0,x_1,x_2,x_3] \]

🔹 Theorem: Newton's Interpolation Polynomial

The unique polynomial of degree \(n\) passing through the \((n+1)\) collocation points \((x_i,f(x_i))\) can be written in Newton's form or recursively as:

\[ p_n(x) = p_{n-1}(x) + a_n (x-x_0)(x-x_1)\dots(x-x_{n-1}) \]

The coefficients are the divided differences:

\[ a_i = f[x_0,x_1,\dots,x_i], \quad 0 \le i \le n \]

🔹 Remark: Efficient Evaluation

Once the coefficients \(a_i\) are known, the Newton polynomial can be evaluated efficiently using a Horner-like scheme:

\[ p_n(x) = a_0 + (x-x_0)\Big(a_1 + (x-x_1)\big(a_2 + (x-x_2)(a_3 + \dots + (x-x_{n-2})(a_{n-1} + a_n(x-x_{n-1})) \dots )\big)\Big) \]

This reduces the number of operations required to evaluate the polynomial and also makes the evaluation less sensitive to round-off errors.