type
Post
status
Published
date
Sep 27, 2024
slug
summary
Imputing new data points within a certain range
tags
Mathematics
category
Theories
icon
password
🖋️ Starting from known points
Given the task of constructing a function
that passes through the points
, first let the projection of the
i th point onto the x axis be Next, consider constructing
n functions:such that for the
i th functionits graph passes through
Thus, we can derive the desired function as:
We can assume that
By substituting the point
we find that
Therefore
Thus, we obtain the Lagrange interpolation formula as:
Here's a breakdown of its components:
f(x): The interpolating polynomial
n: The number of given points
x_i,y_i: The given points through which the polynomial must pass
∏: The product symbol, indicating multiplication of terms
The formula creates a weighted sum of basis polynomials, each passing through one point and zero at all others. This ensures the resulting polynomial satisfies all given points.
The naive implementation of this algorithm has a time complexity of
O(n^2), but it can be optimized to O(nlog^2n). For more details, refer to fast polynomial interpolation.📎 References
- Author:Parker Chen
- URL:www.parkerchenca.com/article/10ff0ccf-d7f8-806f-a56b-fd51d53b9317
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
