拉格朗日插值法 笔记
Garbage_fish
·
·
算法·理论
由于是为了补题才学这个，所以介绍的是最简单的拉格朗日插值法。
引入
一个 n 次多项式（其实也就是函数）f(x)，只要知道其中 n+1 个自变量和对应的因变量，就能解出这个多项式每一项的系数。比如解一次函数 / 二次函数，用待定系数法只需要分别知道两个点 / 三个点就能解二元 / 三元一次方程组解出来。
解线性方程组的方法有高斯消元，但其时间复杂度为 O(n^3)，而拉格朗日插值法面对这种问题只需要 O(n^2)。
公式
设要求的多项式是 f(x)，给出在其图像上 n 个的坐标 (x_i,y_i)，需要求这个多项式自变量为 k 时的取值，则有：
f(k)=\sum_{i=1}^n y_i\prod_{i\ne j}\frac{k-x_j}{x_i-x_j}
假设这三个点的坐标是 (1,4),(2,9),(3,16)，将式子展开：
f(k)=4\times \frac{(k-2)(k-3)}{(1-2)(1-3)}+9\times \frac{(k-1)(k-3)}{(2-1)(2-3)}+16\times \frac{(k-1)(k-2)}{(3-1)(3-2)}
将 x_1 代入，会发现除了和 y_1 相乘的那项以外，每一项都出现了一个 (k-p)=0，所以那一项乘起来也是 0，而对于和 y_1 相乘那一项，乘上的东西变成 1 了，所以就是 y_1。
严格证明不会。
然后这个式子就可以 O(n^2) 暴力求。