Lagrange interpolation
This implementation computes both the Lagrange interpolation polynomial and its derivative at a specified point using Newton's divided difference method. The algorithm efficiently computes both values simultaneously through a single triangular computation scheme.
Tip
Lagrange interpolation is particularly useful for trajectory interpolation when provided distinct states with their first order derivative, e.g., position and velocity. It is less commonly used in ephemeris interpolation than the Hermite interpolation.
Foundation¶
For
and its derivative:
Algorithm¶
Initialization¶
- Input: Points
and evaluation point - Two working arrays:
work
: stores function valuesdwork
: stores derivative values
Divided Difference Table Construction¶
For each level
For each index
-
Compute coefficients:
-
Update function value:
-
Update derivative:
Output¶
Returns tuple
: interpolated function value : interpolated derivative
Error Handling¶
The implementation includes checks for:
- Array length consistency
- Non-empty input arrays
- Division by zero (minimum spacing of
)
Complexity¶
The algorithm achieves:
- Time complexity:
- Space complexity:
This implementation is particularly efficient as it computes both the interpolated value and its derivative in a single pass through the divided difference table, avoiding redundant calculations.