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.