Lagrange 插值

在数值分析中，Lagrange 插值是一种简单地逼近函数的方法，Neville 插值以及著名的 Newton 插值都是基于 Lagrange 插值给出的改进方法。

问题提出

该问题的背景是：一个函数$f(x)$上有$n+1$个样本点$(x_i, y_i), i = 0,1,2,\cdots,n$，样本点满足$x_i \ne x_j, i \ne j$，现要寻找一次数不大于$n$次的多项式$p_n$，使得它经过以上样本点。

称$f(x)$为被插函数，$p_n$为插值多项式，以上问题称作关于节点$(x_i, y_i), i = 0,1,2,\cdots,n$的 Lagrange 插值问题。

可以证明，寻找的多项式$p_n$存在且唯一。证明是构造性的，证明存在性的同时我们也找出了$p_n.$

如果我们要求的多项式次数比$n$小，可能不存在这样的多项式；如果我们要求的多项式次数比$n$大，则可能不唯一。

插值公式

假设同上，那么插值多项式为

$$p_n = \sum_{i=0}^n y_i \dfrac{\omega_n (x)}{(x-x_i)\omega_n'(x_i)},$$

其中

$$\omega_n(x) = \prod_{j=0}^n (x-x_j), \quad \omega'(x_i) = \prod_{\overset{j=0}{\underset{j \ne i}{}}}^{n} (x_i - x_j).$$

特别地有线性插值公式

$$p_1 = y_0 \dfrac{(x - x_1)}{(x_0 - x_1)} + y_1 \dfrac{x - x_0}{x_1 - x_0}.$$

函数

$$l_i(x) = \dfrac{\omega_n (x)}{(x-x_i)\omega_n'(x_i)} = \prod_{\overset{j=0}{\underset{j \ne i}{}}}^n \dfrac{x - x_j}{x_i - x_j}, \quad i = 0,1,\cdots,n$$

被称为插值的基函数，这时

$$p_n = \sum_{i=0}^n y_i l_i(x)$$

数值效用

假设样本点的个数为$n$，那么使用该方法算术复杂度为$O(n^2)$，且样本点发生变化（如增加样本点意图提高插值精确性）时必须重新计算，不具有承袭性。

由此在此基础上又发展出了 Neville 插值方法和 Newton 插值方法。

对于 Lagrange 插值的误差分析，假设$f(x)$在$[a, b]$上具有$n$阶连续导数，$f^{(n+1)} (x)$在$(a,b)$上存在，则上述插值问题的误差为

$$R_n (x) = \dfrac{f^{(n+1)} (\xi)}{(n+1)!} \prod_{i=0}^n (x - x_i), \xi \in (a, b).$$

参考资料

1. 黄云清, 《数值计算方法》, 科学出版社, 北京, 2012-06, ISBN 978-7-0302-3428-5.