牛頓插值法算法

1、牛頓插值法(算法)NewtonInterpolation牛頓插值算法是根據(jù)n+1個(gè)點(diǎn)x,x,.x(xx.x)與函數(shù)値f(x),f(x),.,f(x)求出n次多項(xiàng)式p(x)。再通過(guò)次多項(xiàng)式p(x)求出任意的點(diǎn)x所對(duì)應(yīng)的fx)的算法。1n1求n階差分商fx,X,.xo使用遞歸調(diào)用。01n#defineN20typedefstructTagXYVALUEdoublex;doubley;XYVALUE;XYVALUEvalN+1;階差分商(DividedDifferences)doublef(intn0,intni)if(n0=ni)returnvaln0.y;if(n0+1=ni)return(va

2、lni.y-valn0.y)/(valni.x-valn0.x);elsereturn(f(n0+1,ni)-f(n0,ni-1)/(valni.x-valn0.x);2牛頓插值算法的主程序，求p(xn)的程序。doubleNewtonInterpolation(doublex)doublet=1.0;doubleft;doublep=val0.y;/P(0)=f0for(inti=1;i=N;i+)t=t*(x-vali-1.x);ft=f(0,i)*t;p=p+ft;returnp;3.測(cè)試。用正弦波的20個(gè)采樣點(diǎn)，還原出正弦波曲線。計(jì)算速度很慢，需要改進(jìn)程序。voidCNewtonInt

3、erpolationTestView:OnDraw(CDC*pDC)for(inti=0;iRectangle(int)(vali.x*20)-2,150-(int)(vali.y*50)-2,(int)(vali.x*20)+2,150-(int)(vali.y*50)+2);for(intj=0;jSetPixel(int)(x*20)-2,150-(int)(y*50)-2,0 x000000ff);4.n階差分商的計(jì)算方法的改善。上面的遞歸算法雖然很好讀，但速度太慢不能實(shí)用。n階差分商與、x和f(x)沒(méi)有關(guān)系，所以可以事先把它一次算好，以提高整體処理速度。因?yàn)槭鞘孪扔?jì)算，所以用遞歸算法，或迭代算法都無(wú)所謂。不過(guò)為了記錄算法，用迭代算法計(jì)算。這回速度提高了。doubleddN+1;voidCallDividedDifferences()for(intn=0;n=N;n+)ddn=valn.y;for(inti=1;i=i;j-)ddj=(ddj-ddj-1)/(valj.x-valj-i.x);doubleNewtonInterpolation_DD(doublex)doublet=1.0;doubleft;doublep=val0.y;/P(0)=f0