拉格朗日插值法学习笔记

# 引入 给定两个点，求过这两个点的一次函数。 很简单，待定系数法即可。 -------- 给定三个点，求过这三个点的二次函数。 同样，待定系数法即可。 -------- 给定四个点，求过这四个点的三次函数。 同上。 ...... 给定 $n+1$ 个点，求过这 $n+1$ 个点的 $n$ 次函数。 ？？？ # 拉格朗日插值 拉格朗日插值正是用于求解上面的问题的。 设已知这 $n+1$ 个点为 $(x_i,y_i)$。 设这个函数为 $n$ 次多项式 $L$。 设 $L_i(x)$ 是一个 $n$ 次多项式，且满足 $$ \begin{cases} L_i(x_i)=y_i\\ L_i(x_j)=0\ \ \ (i\not=j) \end{cases} $$ 即 $L_i(x)$ 仅满足 $x_i$ ，而其他的 $x_j$ 则必须对应为零。 那么 $L=\sum\limits^{n+1}_{i=1}{L_i}$。 如何构造 $L_i$ 呢？ 可以考虑先构造 $L_i'(x)$，使其满足 $$ \begin{cases} L_i(x_i)=1\\ L_i(x_j)=0\ \ \ (i\not=j) \end{cases} $$ 那么 $L_i=y_iL_i'$。 因为 $L_i'(x)$ 的取值只有 $0$ 和 $1$，那么可以考虑构造一个分式，使得当 $x=x_i$ 时，分式的分子分母相等，即分式的值为 $1$，当 $x\not=x_i$ 时，分式的分子为零，即分式的值为 $0$。 可以得出 $L_i'(x)$ 可以是下面的多项式： $$\frac{\prod\limits^{n+1}_{j=1}{(x-x_j)(i\neq j)}}{\prod\limits^{n+1}_{j=1}{(x_i-x_j)(i\neq j)}}$$ 那么 $L_i(x)$ 就应该是: $$yi\frac{\prod\limits^{n+1}_{j=1}{(x-x_j)(i\neq j)}}{\prod\limits^{n+1}_{j=1}{(x_i-x_j)(i\neq j)}}$$ 因为 $L=\sum\limits^{n+1}_{i=1}{L_i}$，所以 $L(x)$ 应该为： $$\sum\limits^{n+1}_{i=1}{(y_i{\frac{\prod\limits^{n+1}_{j=1}{(x-x_j)(i\neq j)}}{\prod\limits^{n+1}_{j=1}{(x_i-x_j)(i\neq j)}}})}$$ 这就是拉格朗日插值法。 # 应用 >~~1.求过两定点的直线解析式。~~ ~~反正我也不知道老师会不会给你扣分。~~ >2.求自然数前 $n$ 项的 $k$ 次方和。 首先，设 $f(n)=\Sigma^{n}_{i=1}{i^k}$。 然后利用差分表法可以得知，这是一个关于 $n$ 的 $k+1$ 次多项式。 那么要求出这个多项式就只需要取 $k+2$ 个在函数 $f(n)$ 上的点，然后利用拉格朗日插值法即可计算出该多项式。 最后将 $n$ 代入该多项式即可。 # Update 2022.5.10 今年省选 D2T2 一言难尽... 大概是 dp 方程是关于一个变量的乘积，那么当该变量线性变化时，其 dp 值就会呈 n 次方级增长，那么直接拉插求出了 n+2 个点值就可以算出其变量取值在一定范围内时 dp 值的和了。 $by\ xk$