拉格朗日插值

拉格朗日插值

引入

\(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\)即可