\(n + 1\) 个点\((x_i, y_i)\)可以唯一地确定一个不超过\(n\)次的多项式
比较直观的做法是待定系数法然后高斯消元解方程
不过复杂度是\(O(n^3)\)的，不是特别优秀
那有没有更快的做法呢？
考虑构造函数\(L(x)\)，使得\(L(x)\)随着自变量\(x_i\)的变化，对应的就是\(y_i\)这个值
\[
L(x) = \sum_{i = 0}^{n}y_i ?_i(x)
\]
其中\(?_i(x)\)为拉格朗日基本多项式，其表达式为:
\[
?_i(x) = \prod_{j \ne i} \frac {x - x_j} {x_i - x_j}
\]
发现对于给定的\(n + 1\)个\(x\)，仅当\(x = x_i\)时\(?_i(x) = 1\)，否则\(?_i(x) = 0\)，这表明了构造成立
当需要求\(x=k\)时的函数值时，可以直接将\(k\)带入\(L(x)\)即可，复杂度\(O(n^2)\)
若给定点值的\(x\)是连续的整数时，可以预处理阶乘做到\(O(n)\)求点值
拉格朗日重心插值法是拉格朗日插值法的一种改进
不难发现每次计算\(?_i\)时其实是算了很多重复的东西，我们可以把它简化一下
设
\[
?(x) = \prod_{i = 0}^{n} (x - x_i)
\]
定义重心权
\[
ω_i = \frac 1 {\prod_{i = 0,i \ne j}^{n}(x_i - x_j)}
\]
可以将拉格朗日基本多项式重新写为：
\[
?_i(x) = ?(x)\frac {?_i} {x - x_i}
\]
则
\[
L(x) = ?(x)\sum_{i = 0}^n \frac {ω_i} {x - x_i}
\]
优势:
每次新增加一个点，一般拉格朗日插值会重新计算一次达到\(O(n^2)\)的复杂度，而重心拉格朗日插值只需要\(O(n)\)计算\(ω_i\)即可
原文：https://www.cnblogs.com/Lskkkno1/p/12104535.html