幾種常用的插值方法數學系信息與計算科學1班李平指導老師：唐振先摘要:插值在諸如機械加工等工程技術和數據處理等科學研究中有許多直接的應用，在很多領域都要用插值的辦法找出表格和中間值，插值還是數值積分微分方程數值解等數值計算的基礎。本文歸納了幾種常用的插值方法，并簡單分析了其各自的優(yōu)缺點。關鍵詞:任意階多項式插值，分段多項式插值。引言:所謂插值，通俗地說就是在若干以知的函數值之間插入一些未知函數值,而插值函數的類型最簡單的選取是代數多項式。用多項式建立插值函數的方法主要用兩種：一種是任意階的插值多項式，它主要有三種基本的插值公式：單項式，拉格朗日和牛頓插值；另一種是分段多項式插值,它有Hermite和spine插值和分段線性插值。一.任意階多項式插值：用單項式基本插值公式進行多項式插值：多項式插值是求通過幾個已知數據點的那個n-1階多項式，即P(X)二A+AX+???AXn-1，它是一個單項式基本函數X0，X1…Xn-1的集合來定義多項式,n-1 1 2 n由已知n個點(X，Y)構成的集合,可以使多項式通過沒數據點，并為n個未知系數Ai寫出n個方程，這n個方程組成的方程組的系數矩陣為Vandermonde矩陣。雖然這個過程直觀易懂，但它都不是建立插值多項式最好的辦法，因為Vandermonde方程組有可能是病態(tài)的，這樣會導致單項式系數不確定。另外，單項式中的各項可能在大小上有很大的差異，這就導致了多項式計算中的舍入誤差。拉格朗日基本插值公式進行插值：先構造一組插值函數L(X)=(X—%)(X—Xii)(X—￡J(X—I)，其中i=0,…i(x-x)(x-x)(x-x)(x-x)TOC\o"1-5"\h\zi0 i i-1ii+1 inn?容易看出n次多項式L(x)滿足L(x)=1,(i=j)；L(x)=0,(i#j),其i i i中i=0,1???n,令L(x)=￡yl(x)這就是拉格朗日插值多項式。與單項式基本i iii=0函數插值多項式相比，拉格朗日插值有2個重要優(yōu)點:首先,建立插值多項式不需要求解方程組；其次，它的估計值受舍入誤差要小得多。拉格朗日插值公式結構緊湊,在理論分析中很方便，但是，當插值節(jié)點增加、減少或其位置變化時全部插值函數均要隨之變化，從而整個插值公式的結構也將發(fā)生變化，這在實際計算是非常不利的。使用牛頓均差插值公式進行多項式進行插值：TOC\o"1-5"\h\z首先，定義均差f在Xi,xj上的一階均差f[x,x]=f(j—f(xi)，其中(iHj)。ij x—xjif在X,x,x的二階均差f[x,x,x]=f[xi，xj]—f[Xj，xk],k階均ijk ijk\o"CurrentDocument"f[x x]—f[x x]f[x???x]= 0 k—1 ik。ik x一x??? 0k???由此得出牛頓均值插值多項式的公式為Pn(x)=f[x]+f[x-x](x-x)+???+f[x,00100…X](X-X)???(X-X)。實際計算中經常利用下表給出的均差表直接構造牛頓插n 0 n-1值公式XkF(x)i一階均差二階均差三階均差X0X1F(x)0F(x)F[x,0x]1F[x,x,x]XF(x)F[x,x]012F[x,x,x,x]22i2F[x,x,x]0 12 3X3???F(x)3???F[x,2???x]31 2 3??????凡是拉格朗日插值解決的問題牛頓插值多項式都可以解決，不僅如此,更重要的是牛頓均值克服了拉格朗日插值多項式的缺點，當需要提高近似值的精確度而增加結點時,它不必重新計算,只要在后面再計算一項均插即可,減少了計算量,不用計算全部系數，節(jié)約了大量人力，物力，財力。增加插值多項式的階數并不一定能增加插值的精度，據定義，插值式,F(x)可以與結點(xi,yi),i=l,…，n處的實際函數匹配，但卻不能保證支點之間求F(x),

還能很好的逼近產生(xi,yi)數據的實際函數F(x)。例如，如果F(x)為一個已知的解析函數，而且定義F(x)的節(jié)點集合中數據點的數目可以增加(多項式F(x)的階數也增加)，但是，由于F(x)的起伏增加，那么插值式就可能在節(jié)點見振帶,基于當實際函數F(x)平滑時，這種多項式擺動也可能發(fā)生,這種振蕩不是由多項式擺動引起的，而是由多項式的項相加來求插值多項式時發(fā)生舍入誤差造成的。有時多項式擺動可通過謹慎選擇基礎函數的取樣來成為，但如果數據是由不容易重復實驗取得的，就不能這么做了，這會司會用下面介紹分段插值法。二、分段插值多項式1、分段線性插值:分段線性插值最簡單的插值方案，只要將每個相鄰的節(jié)點用直線接起來，如此形成的一條新的折線就是分段線性插值函數，記作In(xjh而且In(x)在每個區(qū)間[xx]上是線性函數(j=0,1???n-1)jj+1I(X)可以定義為I(xI(X)可以定義為I(x)=n￡yl(x)其中l(wèi)iii=00(x)—_，xG[x0,x1]x一x01其他，l(x)=00/、x-/、x-xl(x)=d,jx-xj j-1xG[xj-1x-x(x)=x-xj.斗，xG[x,x];其他，l(x)=0- jj+1 jj+1xG[x,x]；其他，xG[x,x]；其他，l(x)=0n-1n nnx—xnn-1I(x)具有很好的收斂性，即對于xe［a,b］有：當n趨向于無窮大時,I(x)=g(x)n j n成立。用I(x)計算x點的插值時,只用到x左右的兩個節(jié)點，計算量與節(jié)點個數n無n關，但n越大分段越多，插值誤差就越小，但是，該方法折線在節(jié)點處顯然不光滑,即I(X)在節(jié)點處導數不存在著影響它在需要光滑插值曲線的(如機械插值等領n域中的應用)。2分段三次Hermite插值為清楚起見，先用三次Hermite插值的構造方法加以解釋，三次Hermite插值的做法是，在［xx］上尋找一個次數不超過3的多項式H(x)它滿足插值條件kk+1 3

H(x)=f(x),H(x)=f(x)3k k3 k+1 k+1H'(x)=m,H'(x)=m3k k 3k+1 k+1相應的插值基函數為a(x)=kx-xa(x)=kx-x1+2 k-x-xk+1ka (x)=k+ix-x1+2x-xk k+1k+1x-x x-x丿k k+1丿、x-x—k—-xk丿八xk+1P(x)=P(x)=(x-x)k kP (x)=(x-x)k+1 k+1x-x k^、x-x丿、kk+17x-x k—、x-x丿、k+1 k7于是有H(x)=a(x)3 k如果函數屮滿足條件:f(x)+ak(x)k+1于是有H(x)=a(x)3 k如果函數屮滿足條件:f(x)+ak(x)k+1f(x)+mp(x)+mp(x)ok+1 kk k+1‘ k+1(1)屮GCi[a,b](2)滿足插值條件:(x)k=f(x),k9'(x)=f'(x),k=0,1,2,…，n.k k(3)在每個小區(qū)間[xk-1.],k=l,2,…，n上屮是三次多項式。x

k則稱屮為f的分段三次Hermite插值多項式。根據分段線性插值和三次Hermite插值公式可得到屮的表達式屮根據分段線性插值和三次Hermite插值公式可得到屮的表達式屮(x)=E[f(x)a(x)+f'(x)卩(x)]kk kkk=0其中a(x)=<0仁Cx-x丫1+2 Ix-x人

' 1 0八0,x電[x,x]01、x-x Hx-x丿

01丿a（x）=<nx一x1+2 k-a（x）=<nx一x1+2 k-x一x八k-i k八-Cx一x1+2 k-lx一x八

' k+ik八0,x電[x,x]k-1 k+1,cx一x1+2 klx一x八

' k-1k八0,x電[x,x]n-1n（、x一x 、x一x丿、01丿x一xk k-1x一x k+1x一xk k+1、x一x k-^x一x丿kk-1丿,xe[x,x]k-1 k,xe[x,x]k k+12,xe[x,x]n-1 n2,xe[x,x]k k-1x2,xe[x,x]k k-1 、x一x丿、k k-1丿2,xe[x,x]k k+1（2,xe[x,x]k k+1x一x 、x一x丿、k k+170,x電[x,x]k-1k+1x一x x一x n1Ix一x)n n-10,x電[x,x]n-1na,0 ， k=0,1,2,…,n稱為以節(jié)點x,k k ， 00（x）=<n2,xe[x,x]nn-1x,…，x的分段三次Hermite插值1 n基函數，對于給定n個插值點xVxV???Vx和其相應函數值f(x)和一階函數1 2 n k值f'(X),k=0,l,2,…，n.k顯然，分段三次Hermite插值可以產生平滑變化的插值式,但它有一個明顯的缺點，就是在每個界點處的函數斜率必須已知,而從實驗中獲得的數據,這個斜率就不存在。下面要介紹的三次樣條插值可以解決這個問題,同時能得到插值式所期望的光滑度。3、三次樣條插值樣條函數

在［a,b］上取n+1個插值結點a=x<x〈…幺=b已知函數f(x)在這n+1個點的函數0 1 n值為y=f(x)則在［a,b］上函數y=f(x)的m次樣條插值函數S(x)滿足：k kS(x)在(a,b)上直到m-1階導數連續(xù);S(x)=y,(k=0l-?n);kk在區(qū)間［x,x］(k=01???n-1)上,S(x)是m次多項式。kk+1三次樣條函數在［a,b］上函數y=f(x)的三次樣條插值函數S(x)滿足：⑴在(a,b)上0、1、2階導數連續(xù)，即：s'(x-0)=s'(x+0),s"(x—0)=s"(x+0)(k=01???n—1)k k k kS(x)=y(k=0,1,—n);kk在區(qū)間「xx］(k=0,1…n-1)上S(x)是三次多項式。kk+1三次樣條函數的計算由二階導數連續(xù)，設s"(x)=m,(k=0,1,…,n),m是未知待定的數。因S(x)是k k k分段三次多項式,則在每個區(qū)間「Xx］內,S"(x)是分段一次多項式，記h=x-xkk+1 kk+1kx一x x一x x一xx一x則：s〃(xk)=—k+i m+ 1m= 則：s〃(xk)=TOC\o"1-5"\h\zx-xkkx-xk+1 hkh k+1k+1 k+1 k k k將上式在區(qū)間［xx］上積分兩次,并且由S(x)=yS(x)=y，來確定兩個積分kk+1 kk k+1 k+1常數。當xe［xx］時，kk+1h2x—x一 km)k,6k+/hkh2x—x一 km)k,6k+/hks'(x)二 屮m+ km—(y—km) k+i+(y6h k 6h k+1 k6kh k+1k k k利用S(x)一階導數連續(xù)的性質，對上式求導，得：(x—x)2 (x—x)2 h 1s'(x)—J十丄m+J-k—m—十(m—m)+—(y—y)2hk 2h k+16 k+1 kh k+1 kk k k在上式中，令x=x得：khhy—ys'(x+0)二m m+—k+1 kk 6 k+1 3khk將上式中的k換成k-1,得:s'(x)在［x,x］上的表達式，將x=x代入,k—1k kh hy一ys'(x+0)———km——km+—k+1 k,k 6 k+1 3kh

而S'(x+O)=S'(X-0)聯立上述兩式，得到關于m的方程:k k-k■k-im-kk-ikk-ik-i兩邊乘以得:k-ik-ik-i+2m+k+i兩邊乘以得:k-ik-ik-i+2m