cmlabs.interpolate.divided_differences

cmlabs.interpolate.divided_differences(xvals, yvals)

Return the ordered divided differences list.

Parameters:

• xvals (array_like, 1-D) – The x-coordinates of the data points.

• yvals (array_like, 1-D) – The y-coordinates of the data points.

Returns:

res – The divided differences list.

Return type:

array_like, 1-D

Notes

The divided differences list has the following structure:

\[[f(x_0), f(x_0, x_1), f(x_0, x_1, x_2), \ldots, f(x_0, x_1, \ldots, x_n)]\]

Algorithm is based on the following formula:

\[f(x_0, x_1, \ldots, x_n) = \frac{f(x_1, \ldots, x_n) - f(x_0, \ldots, x_{n-1})}{x_n - x_0}\]

where \(f(x_0, x_1, \ldots, x_n)\) is the divided difference of the function at the points \(x_0, x_1, \ldots, x_n\).

It starts moving from the right side of the array, so the iterations look like this:

\[\begin{split}\begin{aligned} \\ [f(x_0), f(x_1), \ldots, f(x_n)] &\to [f(x_0), f(x_0, x_1), \ldots, f(x_{n-1}, x_n)] \\ [f(x_0), f(x_0, x_1), \ldots, f(x_{n-1}, x_n)] &\to [f(x_0), f(x_0, x_1), \ldots, f(x_{n-2}, x_{n-1}, x_n)] \\ &\vdots \\ [f(x_0), f(x_0, x_1), \ldots, f(x_1, x_2, \ldots, x_n)] &\to [f(x_0), f(x_0, x_1), \ldots, f(x_0, x_1, \ldots, x_n)] \end{aligned}\end{split}\]

The divided differences list is used to compute the coefficients of the Newton interpolation polynomial.