拉格朗日插值
算是一个小技巧，前段时间看到一个恶臭函数计算用了这个，感兴趣就学了下。
OI 里的用法，我看 OI-wiki 没看懂，之后补。
问题：我们现在有 \(n\) 个点 \((x_i, y_i)\)，我们需要求出一个函数（多项式）\(f(x)\) 满足 \(\forall i, f(x_i) = y_i\)。
拉格朗日伯爵提出了一个很有意思的做法，我之前也考虑过类似的东西，但是没有实现出来，可能这就是我和神之间的差距吧。
就是说，我们考虑一个做法，解方程不好搞的话，我们是否可以考虑构造一些类似"开关"的东西。
相当于是，有一个函数 \(g_i(x)\)，只有在 \(x = x_i\) 的时候会取到 \(y_i\)，其他时候都只会取到 \(0\)。
然后我们对于这样的 \(n\) 个函数分别求和就行了。
更一般的形式长成这样：\(f(x) = \sum\limits_{i = 1}^n y_if_i(x)\)，\(f_i(x)\) 就是我们构造的“开关”，这东西也叫做基函数。
不难想到 \(f_i(x)\) 的一种构造：\(\prod\limits_{j = 1\land j\not=i}^n\dfrac{x - x_j}{x_i - x_j}\)。
展开可能更直观：\(f_1(x) = \dfrac{(x - x_2)(x - x_3)\dots(x - x_n)}{(x_1 - x_2)(x_1 - x_3)\dots(x_1 - x_n)}\)
然后带回原函数解出即可。
小练习：
若 \(f(x)\) 满足：\(f(1) = 1, f(2) = 3, f(3) = 5, f(4) = a_1, f(5) = a_2\)。
那么 \(a_1, a_2 = ?\)
答案：\(a_1 = 114514, a_2 = 1919810\)。
构造基函数：
\[
\begin{aligned}
f_1(x) &= 439686176034x^4-894467657863599288x^3+96670016881119792168198x^2-773316306253317660861720x+1449942917421022589993400 \\
f_2(x) &= -219839019377\,x^4+447225112289212410\,x^3-48333219453900921255953 \,x^2+289985452779219448973820\,x-241652680550210977910900 \\
f_3(x) &= \dfrac{219834950745\,x^4-447216395679174360\,x^3+48331430503867261481055 \,x^2-193319908211118614687340\,x+144988924923427197429900}{2} \\
f_4(x) &= -\dfrac{23672016190564304\,x^4-45445986450952971540976\,x^3+ 409012505081637691139152\,x^2-1045253143344809757096080\,x+ 681686601042108846933600}{114513} \\
f_5(x) &= {{6653698369034154960\,x^4-762001498316898528484080\,x^3+ 6857627570346682775369040\,x^2-17524756951201811597381520\,x+ 11429124225473658316341600}\over{1919809}}
\end{aligned}
\]
所以当 \(f(x)\) 满足：
\[
f(x) = \dfrac{855711694412849661824705}{219843088017}x^4 -\dfrac{49153001818340526730091159410}{219843088017}x^3 + \dfrac{31881493579541826570550093377433241}{439686176034} x^2 -\dfrac{85010938062374872741332328977740390}{219843088017}x + \dfrac{93858093625853837594397793694159950}{73281029339}
\]
时，\(f(4) = 114514, f(5) = 1919810\)。
哇，真有逻辑，数学真是有趣！这个可以有！
最后更新:
June 20, 2023