type
status
date
slug
summary
tags
category
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 function
its 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

 
Rust Notes 4Leetcode reflection (1)
Loading...