拉格朗日插值与拉格朗日反演
题目
拉格朗日公式
拉格朗日插值法：\[F(x) = \sum\limits_{k=0}^{n}{y_k\frac{\prod\limits_{j \not= k}^{}{(x-x_j)}}{\prod\limits_{j \not= k}^{}{(x_k-x_j)}}}\]
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。我们先把右边那部分提出来看：\[\ell _{j}(x):=\prod _{{i=0,\,i\neq j}}^{{k}}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\frac {(x-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x-x_{{j-1}})}{(x_{j}-x_{{j-1}})}}{\frac {(x-x_{{j+1}})}{(x_{j}-x_{{j+1}})}}\cdots {\frac {(x-x_{{k}})}{(x_{j}-x_{{k}})}}\]
举个例子吧：有二次函数上的三点\(f(4)=10,f(5)=5.25,f(6)=1\),求\(f(18)\)
求出三个基本式：
\[\ell _{0}(x)={\frac {(x-5)(x-6)}{(4-5)(4-6)}}\ell _{1}(x)={\frac {(x-4)(x-6)}{(5-4)(5-6)}}\ell _{2}(x)={\frac {(x-4)(x-5)}{(6-4)(6-5)}}\]
即：
\[\begin{aligned}p(x)&=f(4)\ell _{0}(x)+f(5)\ell _{1}(x)+f(6)\ell _{2}(x)\\ &=10\cdot {\frac {(x-5)(x-6)}{(4-5)(4-6)}}+5.25\cdot {\frac {(x-4)(x-6)}{(5-4)(5-6)}}+1\cdot {\frac {(x-4)(x-5)}{(6-4)(6-5)}}\\ &={\frac {1}{4}}(x^{2}-28x+136)\end{aligned}\]
理解拉格朗日插值的做法：
对于给定的k+1个点：\((x_{0},y_{0}),\ldots ,(x_{k},y_{k})\)
拉格朗日插值法的思路是找到一个\((\)在一点\(x_{j}\)取值为\(1\)，而在其他点取值都是\(0\)的\()\)多项式\(\ell _{j}(x)\)
这样，多项式\(y_{j}\ell _{j}(x)\)在点\(x_{j}\)取值为\(y_{j}\)，而在其他点取值都是\(0\)
而多项式\(L(x):=\sum _{{j=0}}^{{k}}y_{j}\ell _{j}(x)\)就可以满足
\[L(x_{j})=\sum _{{i=0}}^{{k}}y_{i}\ell _{i}(x_{j})=0+0+\cdots +y_{j}+\cdots +0=y_{j}\]
证明
而我们怎么找到\(\ell _{j}(x)\)呢？
在其它点取值为0的多项式容易找到，由于假定\(x\)两两互不相同，故只有当\(x=x_j\)时上面的取值才不等于\(0\)：
\[\begin{aligned}\\ &(x-x_{0})\cdots (x-x_{{j-1}})(x-x_{{j+1}})\cdots (x-x_{{k}})\Longrightarrow\\ &(x_{j}-x_{0})\cdots (x_{j}-x_{{j-1}})(x_{j}-x_{{j+1}})\cdots (x_{j}-x_{{k}})\end{aligned}\]
于是，将多项式除以这个取值，就得到一个满足“在\(x_{j}\)取值为\(1\)，而在其他点取值都是\(0\)的多项式”：
\(\ell _{j}(x):=\prod _{{i=0,\,i\neq j}}^{{k}}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\frac {(x-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x-x_{{j-1}})}{(x_{j}-x_{{j-1}})}}{\frac {(x-x_{{j+1}})}{(x_{j}-x_{{j+1}})}}\cdots {\frac {(x-x_{{k}})}{(x_{j}-x_{{k}})}}\)
这就是拉格朗日基本多项式
用此公式能优化成\(O(n^2)\)：
\(F(x) = \sum\limits_{k=0}^{n}{y_k\frac{\prod\limits_{j \not= k}^{}{(x-x_j)}}{\prod\limits_{j \not= k}^{}{(x_k-x_j)}}}\)
