拉格朗日插值法

对某个多项式函数，已知有给定的k + 1个取值点：

${\displaystyle (x_{0},y_{0}),\ldots ,(x_{k},y_{k})}$ 

其中${\displaystyle x_{j}}$ 对应着自变量的位置，而${\displaystyle y_{j}}$ 对应着函数在这个位置的取值。

假设任意两个不同的x_j都互不相同，那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为：

${\displaystyle L(x):=\sum _{j=0}^{k}y_{j}\ell _{j}(x)}$ 

其中每个${\displaystyle \ell _{j}(x)}$ 为拉格朗日基本多项式（或称插值基函数），其表达式为：

${\displaystyle \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})}}.}$ ^[3]

拉格朗日基本多项式${\displaystyle \ell _{j}(x)}$ 的特点是在${\displaystyle x_{j}}$ 上取值为1，在其它的点${\displaystyle x_{i},\,i\neq j}$ 上取值为0。

假设有某个二次多项式函数${\displaystyle f}$ ，已知它在三个点上的取值为：

• ${\displaystyle f(4)=10}$ 
• ${\displaystyle f(5)=5.25}$ 
• ${\displaystyle f(6)=1}$ 

要求${\displaystyle f(18)}$ 的值。

首先写出每个拉格朗日基本多项式：

${\displaystyle \ell _{0}(x)={\frac {(x-5)}{(4-5)}}\cdot {\frac {(x-6)}{(4-6)}}}$ 

${\displaystyle \ell _{1}(x)={\frac {(x-4)}{(5-4)}}\cdot {\frac {(x-6)}{(5-6)}}}$ 

${\displaystyle \ell _{2}(x)={\frac {(x-4)}{(6-4)}}\cdot {\frac {(x-5)}{(6-5)}}}$ 

然后应用拉格朗日插值法，就可以得到${\displaystyle p}$ 的表达式（${\displaystyle p}$ 为函数${\displaystyle f}$ 的插值函数）：

${\displaystyle p(x)=f(4)\ell _{0}(x)+f(5)\ell _{1}(x)+f(6)\ell _{2}(x)}$ 

${\displaystyle .\,\,\,\,\,\,\,\,\,\,=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)}}}$ 
${\displaystyle .\,\,\,\,\,\,\,\,\,\,={\frac {1}{4}}(x^{2}-28x+136)}$ 

此时代入数值${\displaystyle \ 18}$ 就可以求出所需之值：${\displaystyle \ f(18)=p(18)=-11}$ 。

存在性

对于给定的k+1个点：${\displaystyle (x_{0},y_{0}),\ldots ,(x_{k},y_{k})}$ ，拉格朗日插值法的思路是找到一个在一点${\displaystyle x_{j}}$ 取值为1，而在其他点取值都是0的多项式${\displaystyle \ell _{j}(x)}$ 。这样，多项式${\displaystyle y_{j}\ell _{j}(x)}$ 在点${\displaystyle x_{j}}$ 取值为${\displaystyle y_{j}}$ ，而在其他点取值都是0。而多项式${\displaystyle L(x):=\sum _{j=0}^{k}y_{j}\ell _{j}(x)}$ 就可以满足

${\displaystyle L(x_{j})=\sum _{i=0}^{k}y_{i}\ell _{i}(x_{j})=0+0+\cdots +y_{j}+\cdots +0=y_{j}}$ 

在其它点取值为0的多项式容易找到，例如：

${\displaystyle (x-x_{0})\cdots (x-x_{j-1})(x-x_{j+1})\cdots (x-x_{k})}$ 

它在点${\displaystyle x_{j}}$ 取值为：${\displaystyle (x_{j}-x_{0})\cdots (x_{j}-x_{j-1})(x_{j}-x_{j+1})\cdots (x_{j}-x_{k})}$ 。由于已经假定${\displaystyle x_{i}}$ 两两互不相同，因此上面的取值不等于0。于是，将多项式除以这个取值，就得到一个满足“在${\displaystyle x_{j}}$ 取值为1，而在其他点取值都是0的多项式”：

${\displaystyle \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})}}}$ 

这就是拉格朗日基本多项式。

唯一性

次数不超过k的拉格朗日多项式至多只有一个，因为对任意两个次数不超过k的拉格朗日多项式：${\displaystyle P_{1}}$ 和${\displaystyle P_{2}}$ ，它们的差${\displaystyle P_{1}-P_{2}}$ 在所有k+1个点上取值都是0，因此必然是多项式${\displaystyle (x-x_{0})(x-x_{1})\cdots (x-x_{k})}$ 的倍数。因此，如果这个差${\displaystyle P_{1}-P_{2}}$ 不等于0，次数就一定不小于k+1。但是${\displaystyle P_{1}-P_{2}}$ 是两个次数不超过k的多项式之差，它的次数也不超过k。所以${\displaystyle P_{1}-P_{2}=0}$ ，也就是说${\displaystyle P_{1}=P_{2}}$ 。这样就证明了唯一性^[4]。

拉格朗日插值法中用到的拉格朗日基本多项式${\displaystyle \ell _{0},\ell _{1},\cdots ,\ell _{n}}$ （由某一组${\displaystyle x_{0}<x_{1}<\cdots <x_{n}}$ 确定）可以看做是由次数不超过n的多项式所组成的线性空间：${\displaystyle \mathbb {K} _{n}[X]}$ 的一组基底。首先，如果存在一组系数：${\displaystyle \lambda _{0},\lambda _{1},\cdots ,\lambda _{n}}$ 使得，

${\displaystyle P=\lambda _{0}\ell _{0}+\lambda _{1}\ell _{1}+\cdots +\lambda _{n}\ell _{n}=0}$ ，

那么，一方面多项式P是满足${\displaystyle P(x_{0})=\lambda _{0},P(x_{1})=\lambda _{1},\cdots ,P(x_{n})=\lambda _{n}}$ 的拉格朗日插值多项式，另一方面P是零多项式，所以取值永远是0。所以

${\displaystyle \lambda _{0}=\lambda _{1}=\cdots =\lambda _{n}=0}$ 。

这证明了${\displaystyle \ell _{0},\ell _{1},\cdots ,\ell _{n}}$ 是线性无关的。同时它一共包含n+1个多项式，恰好等于${\displaystyle \mathbb {K} _{n}[X]}$ 的维数。所以${\displaystyle \ell _{0},\ell _{1},\cdots ,\ell _{n}}$ 构成了${\displaystyle \mathbb {K} _{n}[X]}$ 的一组基底。

拉格朗日基本多项式作为基底的好处是所有的多项式都是齐次的（都是n次多项式）。

拉格朗日插值法的公式结构整齐紧凑，在理论分析中十分方便，然而在计算中，当插值点增加或减少一个时，所对应的基本多项式就需要全部重新计算，于是整个公式都会变化，非常繁琐^[5]。这时可以用重心拉格朗日插值法或牛顿插值法来代替。此外，当插值点比较多的时候，拉格朗日插值多项式的次数可能会很高，因此具有数值不稳定的特点，也就是说尽管在已知的几个点取到给定的数值，但在附近却会和“实际上”的值之间有很大的偏差（如右下图）^[6]。这类现象也被称为龙格现象，解决的办法是分段用较低次数的插值多项式。

重心拉格朗日插值法是拉格朗日插值法的一种改进。在拉格朗日插值法中，运用多项式

${\displaystyle \ell (x)=(x-x_{0})(x-x_{1})\cdots (x-x_{k})}$ 

可以将拉格朗日基本多项式重新写为：

${\displaystyle \ell _{j}(x)={\frac {\ell (x)}{x-x_{j}}}{\frac {1}{\prod _{i=0,i\neq j}^{k}(x_{j}-x_{i})}}}$ 

定义重心权^[7][8]

${\displaystyle w_{j}={\frac {1}{\prod _{i=0,i\neq j}^{k}(x_{j}-x_{i})}}}$ 

上面的表达式可以简化为：

${\displaystyle \ell _{j}(x)=\ell (x){\frac {w_{j}}{x-x_{j}}}}$ 

于是拉格朗日插值多项式变为：

${\displaystyle L(x)=\ell (x)\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}y_{j}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)}$ 

即所谓的重心拉格朗日插值公式（第一型）或改进拉格朗日插值公式。它的优点是当插值点的个数增加一个时，将每个${\displaystyle w_{j}}$ 都除以${\displaystyle (x_{j}-x_{k+1})}$ ，就可以得到新的重心权${\displaystyle w_{k+1}}$ ，计算复杂度为${\displaystyle {\mathcal {O}}(n)}$ ，比重新计算每个基本多项式所需要的复杂度${\displaystyle {\mathcal {O}}(n^{2})}$ 降了一个量级。

将以上的拉格朗日插值多项式用来对函数${\displaystyle g(x)\equiv 1}$ 插值，可以得到：

${\displaystyle \forall x,\,g(x)=\ell (x)\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}}$ 

因为${\displaystyle g(x)\equiv 1}$ 是一个多项式。

因此，将${\displaystyle L(x)}$ 除以${\displaystyle g(x)}$ 后可得到：

${\displaystyle L(x)={\frac {\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}y_{j}}{\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)}$ ^[7]

这个公式被称为重心拉格朗日插值公式（第二型）或真正的重心拉格朗日插值公式。它继承了（1）式容易计算的特点，并且在代入x值计算${\displaystyle L(x)}$ 的时候不必计算多项式${\displaystyle \ell (x)}$ ^[7]。它的另一个优点是，结合切比雪夫节点进行插值的话，可以很好地模拟给定的函数，使得插值点个数趋于无穷时，最大偏差趋于零^[7]。同时，重心拉格朗日插值结合切比雪夫节点进行插值可以达到极佳的数值稳定性。第一型拉格朗日插值是向后稳定的，而第二型拉格朗日插值是向前稳定的，并且勒贝格常数很小^[9]。

引用

来源

书籍

• 李庆扬、王能超、易大义. 《数值分析》 第4版. 清华大学出版社. 2001. ISBN 7-302-04561-5 （中文（简体））. 
• 冯有前. 《数值分析》. 清华大学出版社. 2001. ISBN 7-810-82495-3 （中文（简体））. 
• 拉格朗日插值多项式. 太原理工大学. （原始内容存档于2008-06-09） （中文（简体））. 

• 约瑟夫·拉格朗日
• 多项式插值
• 样条插值
• 伯恩斯坦多项式
• 牛顿多项式
• 龙格现象