第5章 插值法.ppt

1、第5章 插值法,拉格朗日插值 差商與牛頓插值 差分與牛頓差分插值 埃爾米特插值 分段插值,5.1 引言,在實(shí)際應(yīng)用中可能遇到某些難求的函數(shù)。插值法的主要思想是構(gòu)造易求的函數(shù)，如果易求的函數(shù)和難求的函數(shù)在某一區(qū)間內(nèi)足夠接近，那么在這一區(qū)間內(nèi)就可以用易求的函數(shù)代替難求的函數(shù)進(jìn)行計(jì)算。,插值的幾何意義，就是在僅知道函數(shù)曲線上若干點(diǎn)的情況下進(jìn)行作圖，用一條曲線經(jīng)過這些已知點(diǎn)，盡量使這條曲線接近原來的函數(shù)曲線，并把這條曲線近似地認(rèn)為是原來的函數(shù)曲線。,常常在以下2種情況下，用插值法求f(x)。 情況一：f(x)同時滿足下列條件。 不知道或不存在函數(shù)f(x)的具體形式。 知道f(x)上某些離散的點(diǎn)。 情況

2、二：f(x)同時滿足下列條件。 知道函數(shù)f(x)的具體形式。 對于任意的x求f(x)較為困難。 對于某些特定的x求f(x)較為容易。,5.1 引言,定義：設(shè)f(x)是區(qū)間a,b上的連續(xù)函數(shù)，已知f(x)在a,b上x=x0,x1,xn處的函數(shù)值（設(shè)ax0 x1xnb，共n1個互異點(diǎn)），若存在函數(shù)p(x)，滿足p(xi)=f(xi)，其中i=0,1,2,n，則稱： x0,x1,xn為插值節(jié)點(diǎn)（插值基點(diǎn)），所求點(diǎn)x為插值點(diǎn)。 a,b為插值區(qū)間，插值點(diǎn)x插值區(qū)間a,b為內(nèi)插，否則為外推。 p(x)為插值函數(shù)，f(x)為被插函數(shù)。 p(xi)=f(xi)，（其中i=0,1,2,n），為插值條件。 R(x

3、)=f(x)p(x)為插值余項(xiàng)。 插值函數(shù)的構(gòu)造方法為插值法。,常見的函數(shù)類型有冪函數(shù)、指數(shù)函數(shù)、三角函數(shù)等。在選擇插值函數(shù)的類型時，應(yīng)盡量遵循以下原則： 對任意插值條件，插值函數(shù)存在且唯一。 易構(gòu)造插值函數(shù)。 易估計(jì)誤差。 冪函數(shù)除了滿足以上條件之外，還具有高階可導(dǎo)、可積，易手工計(jì)算，易編程實(shí)現(xiàn)等優(yōu)點(diǎn)，是使用較廣泛的插值函數(shù)。,5.1 引言,定義：代數(shù)插值（多項(xiàng)式插值）的插值函數(shù)是冪函數(shù)。設(shè)插值節(jié)點(diǎn)共有n1個，依次為x0,x1,xn，那么插值函數(shù)p(x)是次數(shù)不超過n次的代數(shù)多項(xiàng)式，稱p(x)為n次（代數(shù)）插值多項(xiàng)式，它的一般形式為：p(x)=a0a1xa2x2anxn。,由克萊姆法則，a0

4、,a1,an存在且唯一，因此插值多項(xiàng)式p(x)存在且唯一。,本章介紹代數(shù)插值、帶導(dǎo)數(shù)的埃爾米特插值和分段插值。本章內(nèi)容是第6章數(shù)值積分的基礎(chǔ)。,計(jì)算方法,Lagrange插值多項(xiàng)式:,這樣,l0(x), l1(x)稱為以x0 , x1 為節(jié)點(diǎn)的插值基函數(shù)。,計(jì)算方法,一次拉格朗日插值幾何意義（點(diǎn)擊播放）,計(jì)算方法,例 已知 , , 求,解: 這里x0=100，y0=10，x1=121，y1=11, 利用線性插值,計(jì)算方法,為了提高精確度，我們進(jìn)一步考察以下三點(diǎn)的插值問題： 作二次多項(xiàng)式 P2(x)=a0 + a1x + a2x2使其滿足 P2(x0)=y0 ,P2(x1)=y1 , P2(x2

5、)=y2,計(jì)算方法,這樣得,則：,l0(x) , l1(x) , l2(x) 稱為以 x0 , x1 , x2為節(jié)點(diǎn)的插值基函 數(shù)。,計(jì)算方法,二次插值幾何意義（單擊播放）,計(jì)算方法,例4 已知f (x)的觀測數(shù)據(jù) x 0 1 2 4 f (x) 1 9 23 3 構(gòu)造Lagrange插值多項(xiàng)式,解 四個點(diǎn)可構(gòu)造三次Lagrange插值多項(xiàng)式:基函數(shù)為,計(jì)算方法,Lagrange插值多項(xiàng)式為,5.2 拉格朗日插值,拉格朗日插值函數(shù)一般形式,過n1個插值節(jié)點(diǎn)(x0,y0)，(x1,y1)，(xn,yn)的n次拉格郎日插值函數(shù)的一般形式為： Ln(x)= =l0(x)y0+l1(x)y1+ln(x

6、)yn,其中l(wèi)i(x)= =,式中i=0,1,2,n。稱li(x)為拉格郎日插值基函數(shù)。,對2個插值節(jié)點(diǎn)(x0,y0)，(x1,y1)的1次拉格郎日插值函數(shù)（即線性拉格郎日插值函數(shù)） 的幾何含義為經(jīng)過這2個插值節(jié)點(diǎn)的直線。,對3個插值節(jié)點(diǎn)(x0,y0)，(x1,y1)，(x2,y2)的2次拉格郎日插值函數(shù)（即拋物線拉格郎日插值函數(shù)） 的幾何含義為經(jīng)過這3個插值節(jié)點(diǎn)的拋物線。,拉格郎日插值余項(xiàng)函數(shù)Rn(x)=被插函數(shù)f(x)插值函數(shù)Ln(x)。,5.2 拉格朗日插值,二、拉格郎日插值函數(shù)的余項(xiàng),定理：拉格郎日插值余項(xiàng)函數(shù)Rn(x)= Wn(x)， 其中Wn(x)= =(x-x0)(x-x1)(x

7、-x2)(x-xn)， 當(dāng)xa,b時，a,b，且與x有關(guān)。,5.2 拉格朗日插值,三、n次拉格郎日插值的算法,5.2 拉格朗日插值,n次拉格郎日插值對應(yīng)的程序（1/2）,#include #include #define MAXSIZE 50 void input(double xMAXSIZE,double yMAXSIZE,long n); void main(void) double xMAXSIZE,yMAXSIZE,_x,_y,t; long n,i,j; printf(n請輸入插值節(jié)點(diǎn)的個數(shù)：);scanf(%ld,5.2 拉格朗日插值,n次拉格郎日插值對應(yīng)的程序（2/2）,voi

8、d input(double xMAXSIZE,double yMAXSIZE,long n) long i; for(i=0;i=n-1;i+) printf(n請輸入插值節(jié)點(diǎn)x%ld,y%ld:,i,i); scanf(%lf,%lf, ,一、差商及其性質(zhì),定義 函數(shù)y= f(x)在區(qū)間xi ,xi+1上的平均變化率,自變量之差和因變量之差之比叫差商 。,稱為f(x)關(guān)于xi , xi+1 的一階差商,并記為fxi ,xi+1。,5.3 牛頓插值,計(jì)算方法,計(jì)算方法,m階差商,二階差商,計(jì)算方法,fxi,xj,xk是指,fxi , xj , xk=,fxj , xk- fxi , xj ,

9、xk- xi,一般的,可定義區(qū)間xi, xi+1 , xi+n上的n階差商為,5.3 差商與牛頓插值,差商的遞歸定義,定義：f(x)在x0點(diǎn)處的0階差商fx0=f(x0),f(x)在x0,x1點(diǎn)處的1階差商fx0,x1=,f(x)在x0,x1,x2點(diǎn)處的2階差商為fx0,x1,x2=,f(x)在x0,x1,xn處的n階差商fx0,x1,xn=,說明：定義中要求當(dāng)ij時xixj，除此之外，對點(diǎn)xi具體代表哪一點(diǎn)沒有限制（可以把xi換成任意1點(diǎn)），對各點(diǎn)的次序也沒有限制（即不要求x0 x1xn）。,性質(zhì)1 如果f(x)是代數(shù)多項(xiàng)式，那么對f(x)求1次差商，降1次冪。,5.3 差商與牛頓插值,二、

10、差商的性質(zhì),對m階多項(xiàng)式f(x)=a0a1xa2x2amxm求n階差商fx,x0,x1,xn-1， nm時， fx,x0,x1,xn-1是x的mn次多項(xiàng)式； n=m時， fx,x0,x1,xn-1是f(x)的m階項(xiàng)amxm的系數(shù)am； nm時， fx,x0,x1,xn-1恒為0。,如果f(x)不能用有限次多項(xiàng)式精確表示（如f(x)為三角函數(shù)），那么可能無論對f(x)求多少次差商，結(jié)果也不會恒為0。,性質(zhì)2 f(x)在x0,x1,xn處的n階差商也可以定義為：,fx0,x1,xn=,由性質(zhì)2可知，交換節(jié)點(diǎn)的次序，不改變差商的值。,性質(zhì)3 如果f(x)在a,b上存在n階導(dǎo)數(shù)，節(jié)點(diǎn)x0,x1,xna

11、,b，那么至少有1點(diǎn)a,b，滿足fx,x0,x1,xn-1=,5.3 差商與牛頓插值,三、差商表,差商表對節(jié)點(diǎn)的次序沒有限制。當(dāng)新增加節(jié)點(diǎn)時，可以把新增節(jié)點(diǎn)添加到差商表最下1行，原有節(jié)點(diǎn)的數(shù)據(jù)不變。,5.3 差商與牛頓插值,四、牛頓插值函數(shù)和余項(xiàng),過n1個插值節(jié)點(diǎn)(x0,f(x0)，(x1,f(x1)，(xn,f(xn)的n次牛頓插值函數(shù)的一般形式為：,Nn(x)=fx0fx0,x1(x-x0)fx0,x1,x2(x-x0)(x-x1) fx0,x1,xn(x-x0) (x-x1)(x-xn-1),牛頓插值余項(xiàng)函數(shù)Rn(x)=被插函數(shù)f(x)插值函數(shù)Nn(x) =fx,x0,x1,xn(x-x

12、0) (x-x1)(x-xn)=fx,x0,x1,xnWn(x) 其中Wn(x)=(x-x0) (x-x1)(x-xn),由代數(shù)插值的存在唯一性，經(jīng)過n1個插值節(jié)點(diǎn)(x0,y0)，(x1,y1)，(xn,yn)的n次拉格郎日插值函數(shù)與n次牛頓插值函數(shù)是一致的，因此它們的余項(xiàng)函數(shù)也是一致的。,因此Rn(x)=fx,x0,x1,xnWn(x)= Wn(x)，與差商的性質(zhì)3吻合。,計(jì)算方法,例 已知 x = 1, 4, 9 的平方根值，求 解：,計(jì)算方法,N2(7)=1+(7-1)0.33333+ (7-1)(7-4)(-0.01667)= 2.69992,+ (x- x0) (x-x1) fx1,

13、x0,x,+ (x- x0) fx1,x0,=f(x0),N(x),計(jì)算方法,例 已知 x=0, 2, 3, 5 對應(yīng)的函數(shù)值為 y=1, 3, 2, 5 , 作三次Newton插值多項(xiàng)式。 xi f(xi) 一階差商 二階差商 三階差商,5 5,0 1,2 3,3 2,1,-1,3/2,-2/3,5/6,3/10,計(jì)算方法, 所求的三次Newton插值多項(xiàng)式為,5.3 差商與牛頓插值,五、n次牛頓插值的算法,5.3 差商與牛頓插值,n次牛頓插值對應(yīng)的程序（1/2）,#include #include #define MAXSIZE 50 void input(double xMAXSIZE,

14、double fMAXSIZEMAXSIZE,long n); void main(void) double xMAXSIZE,fMAXSIZEMAXSIZE,_x,_y; long n,i,j; printf(n請輸入插值節(jié)點(diǎn)的個數(shù)：);scanf(%ld,5.3 差商與牛頓插值,n次牛頓插值對應(yīng)的程序（2/2）,void input(double xMAXSIZE,double fMAXSIZEMAXSIZE,long n) long i; for(i=0;i=n-1;i+) printf(n請輸入插值節(jié)點(diǎn)x%ld,y%ld:,i,i); scanf(%lf,%lf, ,定義：如果某插值過

15、程的插值節(jié)點(diǎn)位于x=x0,x1,xn處，且xi-xi-1=h（i=1,2,n），h0，那么這個插值就是等距節(jié)點(diǎn)插值，h為步長。,5.4 差分與牛頓差分插值,一、差分和等距節(jié)點(diǎn)插值的定義,等距節(jié)點(diǎn)插值的滿足xi=x0+ih（i=0,1,2,n），且x0 x1xn。,在做等距節(jié)點(diǎn)插值時，差商演變?yōu)椴罘?，牛頓插值簡化為牛頓差分插值。差分有向前差分和向后差分。,計(jì)算方法,設(shè)函數(shù)y=f(x)在等距節(jié)點(diǎn)xi=x0+ih (i=0,1, ,n)上的函數(shù)值為fi=f(xi)(h為步長),定義： fi=fi+1-fi 和 fi=fi-fi-1 分別稱為函數(shù)f(x)在點(diǎn)xi處的一階向前差分和一階向后差分。,5.4

16、 差分與牛頓差分插值,其中1階向前差分1yi可以簡記為yi，1階向后差分1yi可以簡記為yi 。,5.4 差分與牛頓差分插值,二、差分表,向 前 差 分 表,向 后 差 分 表,性質(zhì)1 對相同插值節(jié)點(diǎn)構(gòu)造的向前差分表各項(xiàng)和向后差分表各項(xiàng)按位置對應(yīng)相等，對應(yīng)關(guān)系式為kyi=kyi+k，或者表示為kyi=kyi-k 。,5.4 差分與牛頓差分插值,三、差分的性質(zhì),顯然，向前差分表各項(xiàng)與向后差分表各項(xiàng)按位置對應(yīng)相等。,計(jì)算方法,等距節(jié)點(diǎn)情況下xi= x0+ih ，用差分表示差商：,=,y1 y0,h,=,y0,1!h,fx1 , x2=,y2 y1,h,=,y1,1!h,fx0,x1,x2=,fx1

17、,x2- fx0,x1,x2 x0,=,2h,=,y1-y0,2h2,=,2y0,2!h2,fx1,x2,x3=,fx3,x2- fx2,x1,x3 x1,=,2h,=,=,ny0,n!hn,nNn(x)=常量,5.4 差分與牛頓差分插值,四、牛頓差分插值函數(shù)和余項(xiàng),設(shè)插值節(jié)點(diǎn)為x0,x1,xn，且xixi-1=h（i=1,2,n），步長h0，那么xi=x0ih（i=0,1,2,n），且x0 x1xn, 若插值點(diǎn)x=x0th，插值節(jié)點(diǎn)為(x0,y0)，(x1,y1)，(xn,yn)，則n次牛頓前插公式的一般形式為：,Nn(x)=Nn(x0+th)=y0+ty0+ 2y0+ 3y0 + ny0,

18、余項(xiàng)函數(shù)Rn(x)=Rn(x0+th)= hn+1f(n+1)()。, 若插值點(diǎn)x=xnth，插值節(jié)點(diǎn)為(x0,y0)，(x1,y1)，(xn,yn)，則n次牛頓后插公式的一般形式為：,Nn(x)=Nn(xn+th)=yn+tyn+ 2yn+ 3yn + nyn,余項(xiàng)函數(shù)Rn(x)=Rn(xn+th)= hn+1f(n+1)()。,某些插值問題不僅給出了插值節(jié)點(diǎn)的坐標(biāo)位置，還給出了某些插值節(jié)點(diǎn)處的若干階導(dǎo)數(shù)值。它不僅要求插值曲線經(jīng)過插值節(jié)點(diǎn)，還要求插值曲線在插值節(jié)點(diǎn)處的各階導(dǎo)數(shù)值與給出的各階導(dǎo)數(shù)值相等。滿足這種要求的多項(xiàng)式插值稱為埃爾米特（Hermite）插值。,5.5 埃爾米特插值,一、埃爾

19、米特插值簡介,定義：若存在不超過2n1次的多項(xiàng)式函數(shù)H(x)，使H(x)與被插函數(shù)f(x)在插值節(jié)點(diǎn)x=x0,x1,xn（設(shè)x0 x1xn）處的函數(shù)值和1階導(dǎo)數(shù)值相等，即H(xi)=f(xi)且H(xi)=f(xi) ，其中i=0,1,2,n，則稱H(x)為帶1階導(dǎo)數(shù)的埃爾米特插值函數(shù)，稱這種插值為帶1階導(dǎo)數(shù)的埃爾米特插值。,帶1階導(dǎo)數(shù)的埃爾米特插值函數(shù)是唯一的。,由埃爾米特插值的定義，可以由待定系數(shù)法求解埃爾米特插值函數(shù)。,2點(diǎn)3次埃爾米特插值是一種使用廣泛的插值方法。僅有2個插值節(jié)點(diǎn)的帶1階導(dǎo)數(shù)的埃爾米特插值函數(shù)是1個3次代數(shù)多項(xiàng)式函數(shù)，因此又稱為2點(diǎn)3次埃爾米特插值。,5.5 埃爾米特插

20、值,二、2點(diǎn)3次埃爾米特插值,設(shè)插值節(jié)點(diǎn)在x=x0,x1處，對被插函數(shù)f(x)的2點(diǎn)3次埃爾米特插值函數(shù)的一般形式為：,H(x)=h0(x)f(x0)+h1(x)f(x1)+0(x)f(x0)+1(x)f(x1),上述2點(diǎn)3次埃爾米特插值可以推廣到n1個插值節(jié)點(diǎn)的帶1階導(dǎo)數(shù)的埃爾米特插值。,5.5 埃爾米特插值,三、帶1階導(dǎo)數(shù)的埃爾米特插值,設(shè)插值節(jié)點(diǎn)在x=x0,x1,xn,處，對被插函數(shù)f(x)的帶1階導(dǎo)數(shù)埃爾米特插值函數(shù)的一般形式為：,H(x)= +,其中輔助函數(shù)hi(x)=(1-2li(xi)(x-xi)li2(x)，i(x)=(x-xi)li2(x),li(x)為拉格郎日插值基函數(shù)，即

21、li(x)=,式中i=0,1,2,n。,5.5 埃爾米特插值,n個插值節(jié)點(diǎn)帶1階導(dǎo)數(shù)的埃爾米特插值的算法,5.5 埃爾米特插值,n個插值節(jié)點(diǎn)帶1階導(dǎo)數(shù)的埃爾米特插值的程序（1/2）,#include #define MAXSIZE 50 void input(double x,double f,double df,long n); void main(void) double xMAXSIZE,fMAXSIZE,dfMAXSIZE,_x,_y,l,dl; long n,i,j; printf(n請輸入插值節(jié)點(diǎn)的個數(shù)：);scanf(%ld,5.5 埃爾米特插值,n個插值節(jié)點(diǎn)帶1階導(dǎo)數(shù)的埃爾米特插值的程序（2/2）,void input(double x,double f,double df,long n) long i; for(i=0;i=n-1;i+) printf(n請輸入插值節(jié)點(diǎn)x%ld,f%ld,df%ld