给出\(n-1\)次函数\(f(x)\)经过的\(n\)个点\((x_i,y_i)\)，要你求出\(f_k\)。
根据拉格朗日插值法：
\[
f(k)=\sum_{i=1}^n y_i\prod_{i\neq j} \dfrac{k-x_j}{x_i-x_j}
\]
举个例子：设一个二次函数经过了\(3\)个点\(\{(1,2),(3,3),(4,2)\}\)。
我们可以求出这个二次函数的解析式为：
\[
f(x)=-0.5x^2+2.5x
\]
将\(f(k)\)展开：
\[
f(k)=2\times\dfrac{(k-3)(k-4)}{(1-3)(1-4)}+3\times\dfrac{(k-1)(k-4)}{(3-1)(3-4)}+2\times\dfrac{(k-1)(k-3)}{(4-1)(4-3)}
\]
我们试着将\(4\)代入：
\[
f(k)=2\times0+3\times0+2\times\dfrac{3}{3} =2
\]
正是 2！
显然，我们在这里构造了一个“开关组”。
我们试着将\(5\)代入：
\[
f(k)=2\times\dfrac{2}{6}-3\times\dfrac{4}{2}+2\times\dfrac{8}{3}=0
\]
理解：我们把
\[
f(k)=\sum_{i=0}^b y_i\prod_{i\neq j} \dfrac{k-x_j}{x_i-x_j}
\]
写成
\[
f(k)=y1\times f1(x) + y2 \times f2(x)+ ...
\]
每一个\(f(x)\)可以看成一个小于\(n\)次的元，又因为这样的\(y1\)是唯一的，所以我们可以沿用求出k。
原文：https://www.cnblogs.com/guodongLovesOi/p/12283371.html