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

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

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

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

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

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

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

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

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

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

10、式的截?cái)嗾`差我們?cè)赼,b上用多項(xiàng)式Pn(x)來(lái)近似代替函數(shù)f(x),其截?cái)嗾`差記作Rn(x)=f(x)-Pn(x)當(dāng)x在插值結(jié)點(diǎn)xi上時(shí)Rn(xi)=f(xi)-P n(xi)=0,下面來(lái)估計(jì)截?cái)嗾`差：定理1：設(shè)函數(shù)y=f(x)的n階導(dǎo)數(shù)y(n)=f(n)(x) 在a,b上連續(xù)，y(n+1)=f(n+1)(x)在(a,b)上存在；插值結(jié)點(diǎn)為：a<x0 x1 xn&b,Pn(x)是n次拉格朗日插值多項(xiàng)式；則對(duì)任意 xCa,b有：其中己 (a,b),己依賴于 x： n+1(x)=(x-x0)(x-x1)(x-xn)證明：由插值多項(xiàng)式的要求：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個(gè)零點(diǎn)，反復(fù)使用羅爾中值定理：存在 七 (a,b),使；因Pn(x)是n次多項(xiàng)式，故P(n+1)()=0,而 n+1(t)=(t-x0)(t-x1)(t-xn)是首項(xiàng)系數(shù)為1的n+1次多項(xiàng)式，故有于是H(

12、n+1)(士尸f(n+1)( E)-(n+1) ! K(x)得：所以設(shè)，則：易知，線性插值的截?cái)嗾`差為：二次插值的截?cái)嗾`差為：下面來(lái)分析前面兩個(gè)例子(例1,例2)中計(jì)算lg12的截?cái)嗾`差：在例1中，用lg10和lg20計(jì)算lg12,P1(12)=1.0602,lg12=1.0792 e=|1.0792-1.0602|=0.0190估計(jì)誤差：f(x)=lgx,，當(dāng) xC 10,20時(shí)，在例2中，用lg10,lg15 和lg20計(jì)算lg12.P2(12)=1.0766,e=|1.0792-1.0766|=0.0026估計(jì)誤差：對(duì)應(yīng)的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"請(qǐng)輸入點(diǎn)的個(gè)數(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"請(qǐng)輸入 x"i+1",y"i+1": "endl ;cin xiyi ;cout"請(qǐng)輸入x"；cin X ；for(i=0 ; i n ; i+)Sn=Sn+func(X,i,x,n)*yi ；cout"通過(guò)拉格朗