拉格朗日插值法

維基百科,自由的百科全書
前往: 導覽搜尋
已知平面上四個點:(−9, 5), (−4, 2), (−1, −2), (7, 9),拉格朗日多項式:Lx(黑色)穿過所有點。而每個基本多項式:y00(x), y11(x), y22(x)以及y33(x)各穿過對應的一點,並在其它的三個點的x值上取零。

數值分析中,拉格朗日插值法是以法國十八世紀數學家約瑟夫·拉格朗日命名的一種多項式插值方法。許多實際問題中都用函數來表示某種內在聯繫或規律,而不少函數都只能通過實驗和觀測來了解。如對實踐中的某個物理量進行觀測,在若干個不同的地方得到相應的觀測值,拉格朗日插值法可以找到一個多項式,其恰好在各個觀測的點取到觀測到的值。這樣的多項式稱為拉格朗日(插值)多項式數學上來說,拉格朗日插值法可以給出一個恰好穿過二維平面上若干個已知點的多項式函數。拉格朗日插值法最早被英國數學家愛德華·華林於1779年發現[1],不久後(1783年)由萊昂哈德·歐拉再次發現。1795年,拉格朗日在其著作《師範學校數學基礎教程》中發表了這個插值方法,從此他的名字就和這個方法聯繫在一起[2]

對於給定的若n+1個點(x_0, y_0),(x_1, y_1),\ldots,(x_n, y_n),對應於它們的次數不超過n的拉格朗日多項式\scriptstyle L只有一個。如果計入次數更高的多項式,則有無窮個,因為所有與\scriptstyle L相差\lambda (x-x_0)(x-x_1)\ldots(x-x_n)的多項式都滿足條件。

定義[編輯]

對某個多項式函數,已知有給定的k + 1個取值點:

(x_0, y_0),\ldots,(x_k, y_k)

其中x_j對應著自變數的位置,而y_j對應著函數在這個位置的取值。

假設任意兩個不同的xj都互不相同,那麼應用拉格朗日插值公式所得到的拉格朗日插值多項式為:

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,已知它在三個點上的取值為:

  • 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)}

然後應用拉格朗日插值法,就可以得到p的表達式(p為函數f的插值函數):

 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的多項式」:

\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的拉格朗日多項式: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]

參見[編輯]

參考來源[編輯]

  1. ^ E. Waring. Problems Concerning Interpolations. Philosophical Transactions of the Royal Society of London. 1779, 69: 59–67. 
  2. ^ (英文)E. Meijering. A chronology of interpolation: From ancient astronomy to modern signal and image processing,. Proceedings of the IEEE: 323. 
  3. ^ (英文)Julius Orion Smith III. Lagrange_Interpolation. Center for Computer Research in Music and Acoustics (CCRMA), Stanford University. 
  4. ^ 馮有前,《數值分析》,第63頁
  5. ^ 李慶揚,《數值分析》第4版,第31頁
  6. ^ 馮有前,《數值分析》,第64頁
  7. ^ 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. 
  8. ^ 王兆清,李淑萍,唐炳濤. 一維重心型插值:公式、算法和應用. 山東建築大學學報. 2007, 22 (5): 447–453. 
  9. ^ NICHOLAS J. HIGHAM. The numerical stability of barycentric Lagrange Interpolation. IMA Journal of Numerical Analysis. 2004, 24 (4): 547–556.