拉格朗日插值法

昵称36202447 2016-11-18

展开全文

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

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

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

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

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

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

$\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]

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

范例

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

要求 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)}}$

然后应用拉格朗日插值法，就可以得到的表达式（为函数的插值函数）：

$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)$

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

证明

存在性

对于给定的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}$

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

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

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

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

唯一性

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

几何性质

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

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

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

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

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

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

优点与缺点

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

重心拉格朗日插值法

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

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

拉格朗日插值法的数值稳定性：如图，用于模拟一个十分平稳的函数时，插值多项式的取值可能会突然出现一个大的偏差（图中的14至15中间）

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

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

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

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

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

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

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

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

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

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

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

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

因此，将 L(x) 除以 g(x) 后可得到：

$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值计算 L(x) 的时候不必计算多项式 $\ell (x)$ ^[7]。它的另一个优点是，结合切比雪夫节点进行插值的话，可以很好地模拟给定的函数，使得插值点个数趋于无穷时，最大偏差趋于零^[7]。同时，重心拉格朗日插值结合切比雪夫节点进行插值可以达到极佳的数值稳定性。第一型拉格朗日插值是向后稳定的，而第二型拉格朗日插值是向前稳定的，并且勒贝格常数很小^[9]。

参考来源

^ E. Waring. Problems Concerning Interpolations. Philosophical Transactions of the Royal Society of London. 1779, 69: 59–67.
^ （英文）E. Meijering. A chronology of interpolation: From ancient astronomy to modern signal and image processing,. Proceedings of the IEEE: 323.
^ （英文）Julius Orion Smith III. Lagrange_Interpolation. Center for Computer Research in Music and Acoustics (CCRMA), Stanford University.
^ 冯有前，《数值分析》，第63页
^ 李庆扬，《数值分析》第4版，第31页
^ 冯有前，《数值分析》，第64页
^ ^7.0 ^7.1 ^7.2 ^7.3 Jean-Paul Berrut, Lloyd N. Trefethen. Barycentric Lagrange Interpolation. SIAM Review. 2004, 46 (3): 501–517.doi:10.1137/S0036144502417715.
^ 王兆清，李淑萍，唐炳涛. 一维重心型插值：公式、算法和应用. 山东建筑大学学报. 2007, 22 (5): 447–453.
^ NICHOLAS J. HIGHAM. The numerical stability of barycentric Lagrange Interpolation. IMA Journal of Numerical Analysis. 2004, 24 (4): 547–556.