已知函数 f(x) 上 n 个点 $(x_i, y_i)$ ,求 f(k) 。

拉格朗日插值法的思路在于:
对于每个 $(x_i, y_i)$ 找到 $L_i(x)$ 使得 $L_i(x_i) = y_i, L_i(x_j) = 0$ ,
其中 $ x_j $ 是已知的 x 中任意一个不等于 $ x_i $ 的 x 。

n 个点无法求出 f 这个函数,
但可以求出一个 n – 1 次多项式,
可以认为这个多项式近似于 f 。

而由 L 的定义可知,
这个多项式 g 满足 $ g(x) = \sum_{i=1}^n L_i(x) $ 。
那么 f(k) 就可以近似地认为是 g(k) ,
代入上式即可 $ O(n^2) $ 求解。

现在问题在于求 L 。
下面的 L 可以满足定义:

$$ L_i(x) = y_i \cdot \prod\limits_{j≠i}\frac{x_j-x}{x_j-x_i}$$

代入可得这对于任意 $ x_i $
可以使得 $ L_i(x_i)=y_i,L_i(x_j) = 0 $


发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: