拉格朗日插值法總結(jié)

1、拉格朗日插值法總結(jié)拉格朗日插值法2008-05-12 16 : 44一、問題的背景在實際問題中常遇到這樣的函數(shù) y=f(x),其在某個區(qū)間a,b上是存在的。 但是，通過觀察或測量或試驗只能得到在區(qū)間a,b上有限個離散點x0,x1,xn上的函數(shù)值yi=f(xi),(i=0,1,n)?；蛘遞(x)的函數(shù)f(x)表達式是已知的，但卻很復雜而不便于計算；希望用一個既能反映函數(shù)f(x)的特性,又便于計算的簡單函數(shù)來描述它。二、插值問題的數(shù)學提法：已知函數(shù)在n+1個點x0,x1，,xn上的函數(shù)值yi=f(xi),(i=0,1,n)求一個簡單函數(shù)y=P(x),使其滿足：P(xi)=yi,(i=0,1,n)。

2、即要求該簡單函數(shù)的曲線要經(jīng)過 y=f(x)上已知的這個n+1個點：(x0,y0),(x1,y1),(xn,yn),同時在其它xCa,b上要估計誤差：R(x)=f(x)-P(x)其中P(x)為f(x)的插值函數(shù)，x0,x1，,xn稱為插值節(jié)點，包含插值節(jié)點 的區(qū)間a,b稱為插值區(qū)間，求插值函數(shù) P(x)的方法稱為插值法。若P(x)是次 數(shù)不超過n的代數(shù)多項式，就稱P(x)為插值多項式，相應的插值法稱為多項式插值。若P(x)是分段的多項式，就是分段插值。若P(x)是三角多項式，就稱三角插值。三、插值方法面臨的幾個問題第一個問題：根據(jù)實際問題選擇恰當?shù)暮瘮?shù)類。本章我們選擇代數(shù)多項式 類，其原因有兩個

3、：(1)代數(shù)多項式類簡單；微分、積分運算易于實行；(2)根 據(jù)著名的Weierstrass逼近定理，任何連續(xù)的函數(shù)都可以用代數(shù)多項式作任意 精確的逼近。第二個問題：構(gòu)造插值函數(shù) P(x),使其滿足：P(xi)=yi,(i=0,1,n)與此相關(guān)的問題是：插值問題是否可解(存在性的問題)，如果有解，是否唯一 ？(唯一 性的問題)第三個問題：插值誤差R(x)=f(x)-P(x) 的估計問題。與此相關(guān)的問題是插 值過程的收斂性的問題。第一節(jié)拉格朗日插值公式一.線性插值(一次插值)已知函數(shù)f(x)在區(qū)間xk,xk+1的端點上的函數(shù)值yk=f(xk),yk+1=f(xk+1), 求一個一次函數(shù)y=P1(x

4、)使彳3yk=f(xk),yk+1=f(xk+1), 其幾何意義是已知平面 上兩點(xk,yk),(xk+1,yk+1), 求一條直線過該已知兩點。1.插值函數(shù)和插值基函數(shù)由直線的點斜式公式可知：把此式按照yk和yk+1寫成兩項：記并稱它們?yōu)橐淮尾逯祷瘮?shù)。該基函數(shù)的特點如下表：從而P1(x)=yk lk(x)+yk+1 lk+1(x)此形式稱之為拉格朗日型插值多項式。其中,插值基函數(shù)與yk、yk+1無關(guān), 而由插值結(jié)點xk、xk+1所決定。一次插值多項式是插值基函數(shù)的線性組合，相應的組合系數(shù)是該點的函數(shù)值 yk、yk+1.例1:已知lg10=1,lg20=1.3010,利用插值一次多項式求l

5、g12的近似值。解：f(x)=lgx,f(10)=1,f(20)=1.3010, 設(shè)x0=10,x1=20,yO=1,y1=1.3010則插值基函數(shù)為：于是,拉格朗日型一次插值多項式為：故：即lg12由lg10和lg20兩個值的線性插值得到，且具有兩位有效數(shù)字(精確 值 lg12=1.0792).二.二次插值多項式已知函數(shù)y=f(x)在點xk-1,xk,xk+1 上的函數(shù)值yk-1=f(xk- 1),yk=f(xk),yk+1=f(xk+1),求一個次數(shù)不超過二次的多項式 P2(x),使其滿足，P2(xk-1)=yk-1,P2(xk)=yk,P2(xk+1)=yk+1.其幾何意義為：已知平面上

6、的三個點(xk-1,yk-1),(xk,yk),(xk+1,yk+1),求一個二次拋物線，使得該拋物線經(jīng)過這三點。1 .插值基本多項式有三個插值結(jié)點xk-1,xk,xk+1構(gòu)造三個插值基本多項式，要求滿足：(1)基本多項式為二次多項式；(2)它們的函數(shù)值滿足下表:因為 lk-1(xk)=0,lk-1(xk+1)=0,故有因子(x-xk)(x-xk+1),而其已經(jīng)是一個二次多項式，僅相差一個常數(shù)倍，可設(shè)lk-1(x)=a(x-xk)(x-xk+1),又因為lk-1(xk-1)=1=a(xk-1-xk)(xk-1-xk+1)=1得從而同理得基本二次多項式見右上圖(點擊按鈕"顯示Li&qu

7、ot;)。2 .拉格朗日型二次插值多項式由前述，拉格朗日型二次插值多項式：P2(x)=yk-1 lk-1(x)+yk lk(x)+yk+1 lk+1(x),P2(x)是三個二次插值多項式的線性組合，因而其是次數(shù)不超過二次的多項式，且 滿足：P2(xi)=yi,(i=k-1,k,k+1)。例2已知：xi 10 15 20 yi=lgxi 11.1761 1.3010利用此三值的二次插值多項式求lg12的近似值。解：設(shè) x0=10,x1=15,x2=20,則：故:所以7利用三個點進行拋物插值得到lg12的值，與精確值lg12=1.0792相比，具 有3位有效數(shù)字，精度提高了。三、拉格朗日型n次插值

8、多項式已知函數(shù)y=f(x)在n+1個不同的點x0,x1,四上的函數(shù)值分別為y0,y1,yn,求一個次數(shù)不超過n的多項式Pn(x),使其滿足：Pn(xi尸yi,(i=0,1,m)，即n+1個不同的點可以唯一決定一個n次多項式。3 .插值基函數(shù)過n+1個不同的點分別決定n+1個n次插值基函數(shù)l0(x),l1(x),ln(X)每個插值基本多項式li(x)滿足：(1)li(x) 是n次多項式；(2)li(xi)=1,而在其它 n 個 li(xk)=0,(k wi)。由于li(xk)=0,(k wi),故有因子：(x-x0)(x-xi-1)(x-xi+1)(x-xn)因其已經(jīng)是n次多項式，故而僅相差一個

9、常數(shù)因子。令：li(x)=a(x-x0)(x-xi-1)(x-xi+1)(x-xn)由li(xi)=1, 可以定出a,進而得到：4 .n次拉格朗日型插值多項式 Pn(x)Pn(x)是n+1個n次插值基本多項式l0(x),l1(x),ln(X)的線性組合,相應的組合系數(shù)是y0,y1,yn。即：Pn(x)=y0 l0(x)+y1 l1(x)+yn ln(x),從而Pn(x)是一個次數(shù)不超過n的多項式，且滿足Pn(xi)=yi,(i=0,1,2,m).例3求過點(2,0),(4,3),(6,5),(8,4),(10,1)的拉格朗日型插值多項式。解用4次插值多項式對5個點插值。所以四、拉格朗日插值多項

10、式的截斷誤差我們在a,b上用多項式Pn(x)來近似代替函數(shù)f(x),其截斷誤差記作Rn(x)=f(x)-Pn(x)當x在插值結(jié)點xi上時Rn(xi)=f(xi)-P n(xi)=0,下面來估計截斷誤差：定理1：設(shè)函數(shù)y=f(x)的n階導數(shù)y(n)=f(n)(x) 在a,b上連續(xù)，y(n+1)=f(n+1)(x)在(a,b)上存在；插值結(jié)點為：a<x0 x1 xn&b,Pn(x)是n次拉格朗日插值多項式；則對任意 xCa,b有：其中己 (a,b),己依賴于 x： n+1(x)=(x-x0)(x-x1)(x-xn)證明：由插值多項式的要求：Rn(xi)=f(xi)-Pn(xi)=0，

11、(i=0,1,2,n);設(shè)Rn(x)=K(x)(x-x0)(x-x1)(x-xn)=K(x) n+1(x)其中K(x)是待定系數(shù)；固定x a,b且xwxk, k=0,1,2,n ;作函數(shù)H(t)=f(t)-Pn(t)-K(x)(t-x0)(t-x1)(t-xn)則 H(xk)=0 , (k=0,1,2,n),且 H(x)=f(x)-Pn(x)-Rn(x)=0, 所以，H(t)在a,b上有n+2個零點，反復使用羅爾中值定理：存在 七 (a,b),使；因Pn(x)是n次多項式，故P(n+1)()=0,而 n+1(t)=(t-x0)(t-x1)(t-xn)是首項系數(shù)為1的n+1次多項式，故有于是H(

12、n+1)(士尸f(n+1)( E)-(n+1) ! K(x)得：所以設(shè)，則：易知，線性插值的截斷誤差為：二次插值的截斷誤差為：下面來分析前面兩個例子(例1,例2)中計算lg12的截斷誤差：在例1中，用lg10和lg20計算lg12,P1(12)=1.0602,lg12=1.0792 e=|1.0792-1.0602|=0.0190估計誤差：f(x)=lgx,，當 xC 10,20時，在例2中，用lg10,lg15 和lg20計算lg12.P2(12)=1.0766,e=|1.0792-1.0766|=0.0026估計誤差：對應的C+?序：#include iostream using name

13、space std ；double func(double X,int k,double x,int n)；int main()double Sn=0 ;int n ;cout"請輸入點的個數(shù)n："cin n ；double*x=(double*)malloc(n*sizeof(double)；double*y=(double*)malloc(n*sizeof(double);double X ；int i for(i=0 ; i n ; i+)cout"請輸入 x"i+1",y"i+1": "endl ;cin xiyi ;cout"請輸入x"；cin X ；for(i=0 ; i n ; i+)Sn=Sn+func(X,i,x,n)*yi ；cout"通過拉格朗