Lagrange Formula·拉格朗日插值法

$\rm{0x01~~} Preface$

插值($Interpolaton$) 在多项式域中可以看做是求值$(Evaluation)$的逆运算,即给定$n$组确定的本质不同的二元组$(x_i, y_i)$,满足$F(x_i) = y_i$,可以逆向求出原$n$次多项式。

而其实,拉格朗日插值公式本身是标准的$\Theta(n^2)$算法——或者不能称其为算法,运算过程$\Theta(n^2)$或许会更准确一些。$Indeed$,该公式是构造出来的,所以没有多么繁琐的证明——

$\rm{0x02}~~\rm{Proof}$

$Proof ~of~Existence$

​ 我们定义$F(x)$为一在实数域上的平凡$n-1$次多项式。

​ 首先我们需要构造一个对于第$i$个二元组的特殊多项式$L_i(x)$,满足$$L_i(x_j) = \begin{cases}1, &\rm{i=j} \newline 0, & \rm{i \neq j}\end{cases}$$

那么我们所求的多项式$F(x)$就可以写作$$F(x) = \sum L_i(x_i)\cdot y_i$$这个式子保证了我们对应的$n$个二元组,$F(x)=y$恒成立。

​ 那么对于$L_i(x)$,我们考虑由我们对$L_i(x)$的定义可以得出$$L_i(x) = k_i(x-x_1)(x-x_2)\cdots(x-x_n)$$其中不包含$x-x_i$这一因式。而由$L_i(x_i)=1$可知我们的比例系数$$k_i=\frac{1}{(x_i-x_1)(x_i-x_2)\cdots(x_i - x_{i-1})(x_i - x_{i+1})\cdots(x_i-x_n)}$$那么$$L_i(x) = \prod\limits_{i=1, i \neq j}^{n}\frac{x - x_j}{x_i-x_j}$$从而$$F(x)=\sum L_i(x)\cdot y_i(x) = \sum y_i \cdot \prod\limits_{i=1, i \neq j}^{n}\frac{x - x_j}{x_i-x_j}$$

$\mathcal{Q.E.D.}$


$Proof~of~Uniqueness^{[1]}$

​ 我们接下来要证明的是多项式$L_i(x)$的唯一性

​ 我们假设同时有两个实数域上的$n-1$次多项式$L_1(x),L_2(x)$满足$L_i(x_j) = \begin{cases}1, &\rm{i=j} \ 0, & \rm{i \neq j}\end{cases}$,那么我们由作差法可以得出多项式$L_{\Delta} = L_1 - L_2$在取所有的$x_i$时,其值均为$0$。那么一定会有多项式$$L’(x) = \prod\limits_{i=1}^{n}(x - x_i)$$满足$$L’|L_{\Delta}$$ 其中$|$表示多项式整除。但是我们知道,对于$L’$这个多项式,其次数为$n-1$;而对于我们所定义的$L_i(x)$,均为$(n-2)$次的,从而$L_{\Delta}$也是$n-2$次多项式。所以我们可以得出$$L_{\Delta} = 0$$从而有$$L_1=L_2$$

$\mathcal{Q.E.D.}$

$\rm{0x03~\color{red}{C}\color{cyan}{o}\color{gold}{d}\color{green}{e}}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
题号:Luogu4781
#include <cstdio>
#include <iostream>

#define MAXN 2020
#define LL long long
#define Mod 998244353

using namespace std ; LL Ans, xs ;
int N, i, j ; LL T, t, xv[MAXN], yv[MAXN] ;

inline LL expow(LL A, LL B){
LL res = 1 ;
while (B){
if (B & 1) (res *= A) %= Mod ;
B >>= 1, (A *= A) %= Mod ;
}
return res ;
}
int main(){
cin >> N >> T ;
for (i = 1 ; i <= N ; ++ i) scanf("%lld%lld", &xv[i], &yv[i]) ;
for (i = 1 ; i <= N ; ++ i){
t = 1 ;
for (j = 1 ; j <= N ; ++ j){
if (i == j) continue ;
(t *= (xv[i] - xv[j] + Mod)) %= Mod ;
}
t = expow(t, Mod - 2) ;
for (j = 1 ; j <= N ; ++ j){
if (i == j) continue ;
(t *= (T - xv[j] + Mod)) %= Mod ;
}
(t *= yv[i]) %= Mod, (Ans += t) %= Mod ;
// cout << Ans << endl ;
}
printf("%lld", Ans) ; return 0 ;
}

$\rm{Reference}$

$\mathfrak{writter:pks}$