拉格朗日插值法與牛頓插值法的比較

1、莆螁P(xJ * (i =0,1, n)膇拉格朗日插值法與牛頓插值法的比較薄聿摘 要在生產(chǎn)和科研中岀現(xiàn)的函數(shù)是多樣的。對于一些函數(shù)很難找岀其解析表達式。即使在某些情況下，可以寫岀函數(shù)的解析表達式，但由于解析表達式的結構相當復雜，使用起來很不方便。插值法即是解決此類問題的一種古老的、然而卻是目前常用的方法，它不僅直接廣泛地應用于生產(chǎn)實際和科學研究中，而且也是進一步學習數(shù)值計算方法的基礎。拉格朗日插值法和牛頓插值法則是二種常用的簡便的插值法。本文即是討論拉格朗日插值法和牛頓插值法的理論及二者的比較。蝿關鍵詞拉格朗日插值 牛頓插值 插值多項式 比較薆芄一、 背景賺在工程和科學研究中出現(xiàn)的函數(shù)是多種多

2、樣的。常常會遇到這樣的情況：在某個實際 問題中，雖然可以斷定所考慮的函數(shù)f(x)在區(qū)間a,b上存在且連續(xù)，但卻難以找到它的解析表達式，只能通過實驗和觀測得到在有限個點上的函數(shù)值(即一張函數(shù)表)。顯然，要利用這張函數(shù)表來分析函數(shù)f (x)的性態(tài)，甚至直接求出其他一些點上的函數(shù)值可能是非 常困難的。面對這些情況，總希望根據(jù)所得函數(shù)表(或結構復雜的解析表達式)，構造某個簡單函數(shù)P(x)作為f (x)的近似。這樣就有了插值法，插值法是解決此類問題目前常用的 方法。袇如設函數(shù)y = f(x)在區(qū)間a,b上連續(xù)，且在n 1個不同的點a_x0,x1，xnb上分別 取值 y,yn。羆插值的目的就是要在一個性質

3、優(yōu)良、便于計算的函數(shù)類門中，求一簡單函數(shù)P(x)，使而在其余點 Xj(i = 0,1,k1,k 1, n)上取值為零，即膂而在其他點 X=Xj上，作為f(x)的近似。艿通常，稱區(qū)間a,b為插值區(qū)間，稱點 Xo,Xi, ,Xn為插值節(jié)點，稱式 P(Xi) = yi為插值條 件，稱函數(shù)類門為插值函數(shù)類，稱P(X)為函數(shù)f (X)在節(jié)點X0,X1/ ,Xn處的插值函數(shù)。求 插值函數(shù)P(x)的方法稱為插值法。蒅插值函數(shù)類門的取法不同，所求得的插值函數(shù)P(x)逼近f(x)的效果就不同。它的選擇 取決于使用上的需要，常用的有代數(shù)多項式、三角多項式和有理函數(shù)等。當選用代數(shù)多項 式作為插值函數(shù)時，相應的插值問

4、題就稱為多項式插值。本文討論的拉格朗日插值法與牛 頓插值法就是這類插值問題。蒁在多項式插值中，最常見、最基本的問題是：求一次數(shù)不超過n 的代數(shù)多項式罿P(x) =a0亠 亠 anxn莈使 Pn(Xi)二 yi(i =0,1,n)，其中,ao,ai/,an為實數(shù)。裊拉格朗日插值法即是尋求函數(shù) Ln(x)(拉格朗日插值多項式)近似的代替函數(shù)f(X)。相似的，牛頓插值法則是通過 Nn(X)(牛頓插值多項式)近似的求得函數(shù)的值。節(jié)肁、理論基礎蒆(一)拉格朗日插值法芄在求滿足插值條件 n 次插值多項式 Pn(x)之前，先考慮一個簡單的插值問題：對節(jié)點Xi(i =0,1/ ,n)中任一點 Xk(0k n)

5、，作一 n 次多項式 g(x)，使它在該點上取值為 1,0羂Ik(Xi ) = *肂上式表明 n 個點 Xo*，xk，xk“，x 都是 n 次多項式 lk(x)的零點，故可設衿lk(x)二 Ak(X Xo)(X - Xi)(X - Xk/)(X Xk 1) (x Xn)1螃其中，Ak為待定系數(shù)。由條件 Ik(Xk)=1 立即可得1_(Xk-Xo)(Xk-XkJ(Xk-Xk .1)(Xk- Xn)衿故lk(x)=(X-Xo)(X-Xk)(X-Xk1)(X-Xn)(Xk-Xo) (Xk-Xkj)(Xk-Xk 1)(Xk- Xn)羇由上式可以寫出n 1個 n 次插值多項式 l0(x)，h(x),，l

6、n(x)。我們稱它們?yōu)樵趎點 Xo,X1/,Xn上的 n 次基本插值多項式或 n 次插值基函數(shù)。莇利用插值基函數(shù)立即可以寫出滿足插值條件的n 次插值多項式蒃ylo(X)%l1(X)ynln(x)-1個節(jié)1i =k羈根據(jù)條件 lk(X|)=，容易驗證上面多項式在節(jié)點 xi處的值為 yi(i=0,1；0 i 式 k因此，它就是待求的 n 次插值多項式 Pn(x)。,n)，艿形如 yolo(x) yJdx)亠亠 ynln(x)的插值多項式就是拉格朗日插值多項式，記為Ln(x)，Ln(x) =y1h(x)y2l2(X)yn(x)祎_ (X-X。)(X -Xk4)(X- XkJ (X-Xn)(Xk-Xo

7、)(Xk-Xk4)(Xk-Xk1)(Xk- Xn)0膃作為常用的特例，令n =1,由上式即得兩點插值公式螈Lx) = y。上 匹(x xo)，這是一個線性函數(shù)，故又名線性插值。xi xo蒈若令n =1,則又可得到常用的三點插值公式羃這是一個二次函數(shù)，故又名二次插值或拋物插值。袀(二)牛頓插值法薆由線性代數(shù)知，任何一個不高于 n 次多項式，都可以表示成函數(shù)i, X - Xo,(X - Xo)(X - Xi), ,(x - Xo)(X - Xi)(x - Xn)的線性組合。既可以吧滿足插值條件P(Xi)二(i =0,i，,n)的 n 次插值多項式寫成如下形式蚅a。y(x x。) a2(x Xo)(

8、x Xi)a.(x -x)(x - xj (x - 人)蚄其中，ak為待定系數(shù)。這種形式的插值多項式稱為牛頓插值多項式，記為Nn(x)，即Nn(x) =a。 ai(x-Xo) a?(x - x)(x - xja.(x - x)(x - xj (x-Xn)i袁因此，牛頓插值多項式 Nn(x)是插值多項式 Pn(x)的另一種表示形式。袈設函數(shù)f (x)在等距節(jié)點 Xk=Xo，kh(k=0,i，n)處的函數(shù)值 f(xj 二 yk為已知，其中h是正常數(shù)，稱步長。我們稱兩個相鄰點 Xk和 Xk i處函數(shù)之差 y-i-yk為函數(shù)f (x)在點 Xk處 以 h 為步長的一階向前差分，記作yk，即 y yky

9、k膄于是，函數(shù)f (x)在各節(jié)點處的一階差分依次為 勺。=yi- y0, = y2- 二二 yn- ynv蒄又稱一階差分的差分A2yk= A(Ayk) = Ayk+-Ayk為二階差分。一般的，定義函數(shù)f (x)在芅L2(X)(xxj(xX2)丄yoyi(x0-xi)(x0 -x2)(X -Xo)(X-X2)(xiX0)(xix2)(X-X)(X-Xi)(X2X0)(x2xi)點 Xk處的 m 階差分為 ykyk卑-AmJLyk。蚈在等距節(jié)點 Xk =Xo kh(k=0,1,，n)情況下，可以利用差分表示牛頓插值多項式的系數(shù)。事實上，由插值條件 Nn(Xo) = y可得 a二 y;再由插值條件

10、Nn(xJ = y!可得aXlHy; 一般的，由插值條件Nn(xQ=yk可得y (k = 1,2,，n)。% x0hk! h心20(x Xo)(X xj(x Xo)(x xj (X Xn)2!h2n !hn膅三、二者的比較螀拉格朗日插值法與牛頓插值法都是二種常用的簡便的插值法。但牛頓法插值法則更為 簡便，與拉格朗日插值多項式相比較，它不僅克服了“增加一個節(jié)點時整個計算工作必須 重新開始”(見下面例題)的缺點，而且可以節(jié)省乘、除法運算次數(shù)。同時，在牛頓插值 多項式中用到的差分與差商等概念，又與數(shù)值計算的其他方面有著密切的關系。荿現(xiàn)用一實例比較拉格朗日插值法與牛頓插值法芇例已知函數(shù)表如下：蟻X肅o

11、.i螂0.2羈0.3蚅0.4袃0.5袀0.6莀si nx莆0.09983襖0.19867芃0.29552蝿0.38942膆0.47943羆0.56464莁計算 sin(0.12)的值。腿利用拉格朗日插值法計算過程如下：(計算程序代碼見附件)羇于是，滿足插值條件Nn(xj 二 yi的插值多項式為薄Nn(X)=yo(XXo)莇因為 0.12 位于 0.1 與 0.2 之間，故取節(jié)點& =0.1,洛=0.2螃利用線性插值所求的近似值為sin0.12：丄(0.12):0.119598蚈計算結果如下圖襖利用拋物插值所求的近似值為sinO.12 ： L1(0.12)(0.12 -0.2)(0.12

12、 - 0.3) +0 19867 乂(0.12-0.1)(0.12-0.3)(0.1 -0.2)(0.1 -0.3).(0.2-0.1)(0.2-0.3)(0.12-0.1)(0.12-0.2)=0.099830.12-0.20.1 - 0.20.198670.12-0.10.2 -0.1-0.099830.29552蚇莇(0.3-0.1)(0.3-0.2)0.119757莁計算結果如下圖祎利用牛頓插值法計算過程如下:羀構造差分表如下:螁x膈si nx蚃A y血2前也yA3膀也y袈0.1聿0.09983肀莆薅螄荿袈0.09884蒃袃蒁0.2薃0.19867薆薁-0.00199蒀薀羂蚆0.096

13、85羀螇-0.00096蕿0.3蒈0.29552蒂肆-0.00295螆裊薁0.09390袃0.4蚄0.38942蚆利用線性插值所求的近似值為sin(0.12) ： N,(0.12)肁二 0.9983 0.2 0.09884= 0.11960衿利用拋物插值所求的近似值為sin(0.12)N2(0.12)0 2x (0 21)= 0.9983 + 0.2x0.09884+ * 丿 x(0.00199)薇2二 N1(0.12) 0.00016= 0.11976蒃從上面的計算過程可以看出，拉格朗日插值法的線性插值與拋物插值的計算過程沒有 繼承性，即增加一個節(jié)點時整個計算工作必須重新開始。而牛頓插值則避

14、免了這一問題， 這樣大量的節(jié)省了乘、除法運算次數(shù)，減少了計算的時間。因此，對于一些結構相當復雜 的函數(shù)f (x)，牛頓插值法比拉格朗日插值法要占優(yōu)勢。莄艿羋參考文獻蒅1易大義，沈云寶，李有法編.計算方法.杭州：浙江大學出版社，2002蒂2馮康等編.數(shù)值計算方法.北京：國防工業(yè)出版社，1987螈3李慶陽，王能超，易大義編.數(shù)值分析(第四版).北京：清華大學出版社，施普林格出版社，2001肇4Burden R L，F(xiàn)aires J D，Reynolds A C. Numerical Analysis. Alpine Press,1981薆5易大義，陳道琦編.數(shù)值分析引論.杭州：浙江大學出版社，19

15、98蟻蒁螈Comparison between Lagrange interpolation method and Newtoninterpolation method莃Abstract In the production and scientific researches, there appears a variety of functions. For some function, it is difficult tofind out its analytical expression. Though in some cases, the analytical expressions o

16、f the structure can be worked out, it is inconvenient to usethem because of the complexity of structure. Interpolation method is a kind of old way to solve such problems, which is now commonly used. It isnot only applied in the actual production or scientific researchesdirectly and widely, but also

17、become the foundation of further study of numericalcalculation method. Lagrange interpolation method and Newton interpolation law are two commonly used simple interpolation methods. Thispaper is a discussion of theory and the comparison between Lagrange interpolation method and Newton interpolation

18、method.羃Key Words Lagrange interpolation,Newton interpolation,Interpolation polynomials附件：comparison#include void main()float x6=0.1,0.2,0.3,0.4,0.5,0.6;int n,k,j;float f6=0.09983,0.19867,0.29552,0.38942,0.47943,0.56464; float p,a,sum=0;printf(輸入插值次數(shù) n 和所要求 sina 的 a 的值:)；scanf(%d %f,&n,&a);for(k=0；k=n；k+)p=1；for(j=0；j=n；j+)if(k!=j)p=p*(a-xj)/(xk-xj)； sum=sum+p*fk；printf(x=%f,y=%f,a,sum)；以下無正文僅供個人用于學習、研究；不得用于商業(yè)用途For personal use only in study and research; not for commercial use.Nur fur den pers?nlichen