cmlabs.differentiate.lagrange_derivative

cmlabs.differentiate.lagrange_derivative(xvals, yvals, x, k)[source]

Return the k-th derivative of the Lagrange polynomial.

\[\begin{split}\begin{gather} L_n^{(k)}(x) = \sum_{i=0}^{n} f(x_i) l_i^{(k)}(x) \\ l_i^{(k)}(x) = \left(\prod_{j=0, j \neq i}^{n} \frac{x - x_j}{x_i - x_j}\right)^{(k)} \end{gather}\end{split}\]

Parameters:

xvals (array_like, 1-D) – The sorted x-coordinates of the data points.
yvals (array_like, 1-D) – The y-coordinates of the data points, i.e., f(\(x\)).
x (float) – The x-coordinate at which to evaluate the polynomial.
k (int) – The order of the derivative.

Returns:

res – The value of the k-th derivative of the polynomial at \(x\).

Return type:

float

See also

lagrange

Notes

This function might be slow but it is useful for testing purposes.

Complexity analysis. The function lagrange_derivative recursively computes the k-th derivative of the Lagrange interpolating polynomial. The recursive step involves iterating over all subsets of given indices, resulting in a combinatorial growth of the number of recursive calls. Therefore, the overall time complexity is approximately \(O(n^k)\), where \(n\) is the number of interpolation points and \(k\) is the derivative order. Since the recursion is not based on simple division into smaller subproblems, the Master Theorem does not apply. If \(k\) is fixed and small, the algorithm runs in polynomial time with respect to \(n\); otherwise, for large \(k\), the complexity becomes exponential.

Examples

>>> from cmlabs.differentiate import lagrange_derivative
>>> xvals = np.array([0, 1, 2, 3, 4])
>>> yvals = np.array([0, 1, 4, 9, 16])
>>> x = 2.5
>>> k = 2
>>> lagrange_derivative(xvals, yvals, x, k)
6.0