第4章插值與曲線擬合

第4章插值法與曲線擬合南京中醫(yī)藥大學(xué)信息技術(shù)學(xué)院制作:張季第4章插值法與曲線擬合4.1Lagrange插值法

4.2埃特金算法

4.3Newton插值法4.4差分與等距結(jié)點(diǎn)插值4.5埃爾米特插值法4.6有理分式插值法4.7函數(shù)逼近4.8曲線擬合內(nèi)容提要：插值是數(shù)值逼近的重要方法之一。是根據(jù)給定的一組自變量和函數(shù)值，求取未給出的結(jié)點(diǎn)處函數(shù)值的近似值。本章主要介紹拉格朗日插值，牛頓插值和分段低階多項(xiàng)式插值方法。概述設(shè)是在上有一定光滑性的函數(shù)，是上個(gè)互不相同的點(diǎn)，在這個(gè)點(diǎn)上的取值分別。所謂的插值法就是求一個(gè)形式簡(jiǎn)單的函數(shù)

,使得i=0,1,2,…,n通常稱給定的點(diǎn)為插值節(jié)點(diǎn)，稱函數(shù)為函數(shù)關(guān)于插值節(jié)點(diǎn)xi的插值函數(shù)(插值多項(xiàng)式)，稱為被插函數(shù)。插值多項(xiàng)式的存在唯一性設(shè)函數(shù)在區(qū)間上的代數(shù)插值多項(xiàng)式是且滿足，其中只要系數(shù)確定，則就確定了。求a0,a1,…an可通過求解此線性方程組，一般而言，所要求的n次多項(xiàng)式的解是唯一的，證明此唯一性。證明：

設(shè)有兩個(gè)多項(xiàng)式Pn(x)和Qn(x)都滿足插值要求，則對(duì)于R(x)=Pn(x)-Qn(x)就有R(xi)=0,i=0,1,2,…,n

由此可知其在插值區(qū)間上有n+1個(gè)零點(diǎn)，R(x)也是一個(gè)多項(xiàng)式，而且只是一個(gè)n次多項(xiàng)式，由此可斷定R(x)≡0也即有Pn(x)=Qn(x)即唯一性得證4.1.1線性插值基本思想：在插值區(qū)間上，用一次插值多項(xiàng)式近似代替被插函數(shù)f(x)來(lái)求取非結(jié)點(diǎn)處函數(shù)值。從幾何意義上就是在插值區(qū)間上用一條直線近似地代替被插函數(shù)曲線f(x)。插值公式：其中：

Lk(x),Lk+1(x)稱為線性插值基函數(shù)，P1(x)稱為線性插值函數(shù)，也稱為線性插值多項(xiàng)式。程序框圖設(shè)計(jì)讀入x0,x1,y0,y1讀入x計(jì)算L0計(jì)算L1計(jì)算y=y0?L0+y1?L1輸出y4.1.2拋物插值基本思想：用二次插值多項(xiàng)式P2(x)近似代替被插函數(shù)f(x)計(jì)算函數(shù)值。從幾何意義上就是在插值區(qū)間上用拋物線近似地代替被插函數(shù)曲線f(x)。插值公式：其中：程序框圖設(shè)計(jì)讀入x0,x1,x2,y0,y1,y2讀入x計(jì)算L0計(jì)算L1計(jì)算y=y0?L0+y1?L1+y2?L2輸出y計(jì)算L24.1Lagrange插值方法設(shè)給定函數(shù)y=f(x)有n+1個(gè)數(shù)據(jù)點(diǎn)(x0,y0),(x1,y1),…,(xn,yn)。今定義函數(shù)由此可知：反推：根據(jù)給定的條件可知，Li(x0)=0,Li(x1)=0,…Li(xi-1)=0,Li(xi+1)=0,…,Li(xn)=0。則可判定x0,x1,x2,…,xi-1,xi+1,…,xn均為方程Li(x)=0的根。依據(jù)有關(guān)定理，有：Li(x)=λ(x-x0)(x-x1)…(x-xi-1)(x-xi+1)...(x-xn)再依據(jù)Li(xi)=1則有Li(xi)=λ(xi-x0)(xi-x1)...(xi-xi-1)(xi-xi+1)...(xi-xn)=1已知：Li(x)，若令則當(dāng)x=xi時(shí)有

上式表明，當(dāng)x=xi時(shí)，Pn(xi)=f(xi)(i=1,2,…,n),這說明n次多項(xiàng)式Pn(x)滿足插值條件，即Pn(x)就是所求的插值多項(xiàng)式。一般稱形如Pn(x)的多項(xiàng)式為拉格朗日插值多項(xiàng)式。4.1.3插值余項(xiàng)用插值多項(xiàng)式Pn(x)作為被插函數(shù)f(x)的逼近，除了在插值節(jié)點(diǎn)處以外，Pn(x)與被插函數(shù)f(x)是有差別的，這個(gè)差別可以用函數(shù)：Rn(x)=f(x)-Pn(x)來(lái)表示，并且稱之為插值余項(xiàng)。4.2分段插值

根據(jù)所給條件，選擇盡可能小的插值區(qū)間，使用低階的插值（如線性插值和拋物插法進(jìn)行插值）以獲取符合計(jì)算精度要求的計(jì)算結(jié)果。選擇插值結(jié)點(diǎn)的原則應(yīng)進(jìn)行內(nèi)插插值區(qū)間盡可能小4.2.1分段線性插值分段線性插值公式：其中：分段線性插值結(jié)點(diǎn)的確定：1,當(dāng)x<x1時(shí)

i=

k,當(dāng)xk-1<x<xk時(shí)

n,當(dāng)x>

xn-1時(shí)

算法設(shè)計(jì)：1)當(dāng)x<x1時(shí)，取i=1，直接使用線性插值公式計(jì)算插值結(jié)果。2)當(dāng)x>xn-1時(shí)，取i=n，直接使用線性插值公式計(jì)算插值結(jié)果。3)當(dāng)x>x1時(shí)，則a.取i=1.b.使i=i+1c.判斷x<xi是否成立，若成立，則直接使用插值公式計(jì)算插值結(jié)果。否則返回步驟b執(zhí)行。4.3.2分段拋物插值分段拋物插值公式：其中：

分段拋物插值結(jié)點(diǎn)的確定：1,當(dāng)x<x1時(shí)

i=

k-1,當(dāng)xk-1<x<xk,且|x-xk-1|<|x-xk|k,當(dāng)xk-1<x<xk,且|x-xk-1|>|x-xk|

n,當(dāng)x>

xn-1時(shí)

算法設(shè)計(jì)：1)當(dāng)x<x1時(shí)，取i=1，直接使用線性插值公式計(jì)算插值結(jié)果。2)當(dāng)x>xn-1時(shí)，取i=n，直接使用線性插值公式計(jì)算插值結(jié)果。3)當(dāng)x>x1時(shí)，則a.取i=1.b.使i=i+1c.判斷x<xi是否成立，若成立，則判斷|x-xi-1|<|x-xi|是否成立，若成立，則i=i-1,使用插值公式計(jì)算，若不成立，直接使用插值公式計(jì)算插值結(jié)果直接使用插值公式計(jì)算插值結(jié)果。否則返回步驟b執(zhí)行。4.3Newton插值方法差商：若對(duì)于函數(shù)y=f(x),有實(shí)驗(yàn)數(shù)據(jù)那么－－一階差商－－二階差商－－n階差商差商的性質(zhì)性質(zhì)1：性質(zhì)2：性質(zhì)3：性質(zhì)4：性質(zhì)5：差商的計(jì)算iXif(xi)一階差商二階差商三階差商…n階差商0x0y0…1x1y1f[x0,x1]…2x2y2f[x1,x2]f[x0,x1,x2]…3x3y3f[x2,x3]f[x1,x2,x3]f[x0,x1,x2,x3]…………………nxnynf[xn-1,xn]f[xn-2,xn-1,xn]f[xn-3,

xn-2,xn-1,xn]…f[x0,

x1,…,xn]牛頓插值多項(xiàng)式應(yīng)用拉格朗日插值時(shí)，各階的插值公式差別很大，低階插值的結(jié)果不能為高階插值計(jì)算所利用，如果在低階插值計(jì)算公式的基礎(chǔ)上，加上一項(xiàng)修正項(xiàng)而得到高階插值公式，就能使計(jì)算具有承襲性，這種插值方法就是牛頓插值。假設(shè)：Pk(x)=Pk-1(x)+hk(x)式中：Pk(x)－－函數(shù)f(x)的k階插值多項(xiàng)式Pk-1(x)－－函數(shù)f(x)的k-1階插值多項(xiàng)式hk(x)－－修正項(xiàng)由上式得

hk(x)=Pk(x)–Pk-1(x)根據(jù)插值條件，當(dāng)x=xi(i=0,1,…,k-1)時(shí)有Pk(xi)=Pk-1(xi)=f(xi)=yi即有h(xi)=c∏(x-xj)其中(j=0,1,…,k-1)K-1j=0已知函數(shù)f(x)有n+1個(gè)結(jié)點(diǎn)xi(i=0,1,…,n)及結(jié)點(diǎn)處的函數(shù)值yi(i=0,1,…,n)。其中y0可看作函數(shù)f(x)的零階插值多項(xiàng)式，于是有：P0(x)=y0一次插值多項(xiàng)式：P1(x)=y0+h1(x)h1(x)=c1(x-x0)c1=(y1-y0)/(x1-x0)=f[x0,x1]P1(x)=y0+f[x0,x1](x-x0)二次插值多項(xiàng)式：P2(x)=y0+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)n次插值多項(xiàng)式：???設(shè)計(jì)牛頓插值算法牛頓插值程序框圖定義數(shù)組u[N],v[N],t[N]輸入x，E，u(N)和v(N)的原始數(shù)據(jù)C=1.0，y1=v(0)For(k=1;k<=N;k++)For(i=k;i<=N;k++)輸出插值結(jié)果t[i]=(v[i]-v[i-1])/(u[i]-u[i-k])c=c?(x-u[k-1])y1=y1+c?t[k]T|y-y1|<EF轉(zhuǎn)去輸出并結(jié)束程序for(i=k;i<=N;k++)v(i)=t(i)y=y1例題已知x=1,4,9y=1,2,3求321941xx123149二階差商一階差商x4.4等距結(jié)點(diǎn)插值差分：一般的，n階差分遞推地定義如下：即：并規(guī)定，稱之為零階差分。設(shè)等距結(jié)點(diǎn)xi=x0+ih(i=0,……)相應(yīng)的函數(shù)值為yi=f(xi),并定義為其一階差分。向后差分：差分的性質(zhì)性質(zhì)1性質(zhì)2性質(zhì)3性質(zhì)4等距結(jié)點(diǎn)插值公式將牛頓插值多項(xiàng)式中各階差商用相應(yīng)差分代替，就可以得到相應(yīng)的等距結(jié)點(diǎn)插值公式。牛頓前插公式：牛頓后插公式：向前差分遞推表函數(shù)值一階二階三階四階算法設(shè)計(jì)：1)升階。2)使a[i]=f[i],y=y1。3)進(jìn)入循環(huán)，使用公式f[i]=a[i]-a[i-1]計(jì)算差分值。4)在K循環(huán)中計(jì)算連乘積q=q·(t-k+1)5)在K循環(huán)中計(jì)算階乘p=p·k6)計(jì)算插值結(jié)果y1=y1+q·f(k)/p7)判斷|y-y1|<E是否成立，若成立，則程序轉(zhuǎn)去輸出并結(jié)束，

若不成立，則返回步驟1執(zhí)行。程序框圖使用等距結(jié)點(diǎn)插值法求插值結(jié)點(diǎn)x處的函數(shù)值輸入使用等距結(jié)點(diǎn)插值法求插值結(jié)點(diǎn)x處的函數(shù)值輸出升階使a[i]=f[i],y=y1在i循環(huán)中計(jì)算差分f[i]=a[i]-a[i-1]計(jì)算連乘積q=q·(t-k+1)計(jì)算階乘值p=p·k計(jì)算插值結(jié)果y1=y1+q·f(k)/p判斷|y-y1|<E是否成立，若成立，則程序轉(zhuǎn)去輸出并結(jié)束，若不成立，則返回步驟1執(zhí)行x0.00.10.20.30.40.50.6cosx1.000000.995000.980070.955340.921060.877580.82534xcosxΔyΔ2yΔ3yΔ4yΔ5yΔ6y00.10.20.30.40.50.61.000000.995000.980070.955340.921060.877580.82534-0.00500-0.01493-0.02473-0.03428-0.04348-0.05224-0.00993-0.00980-0.00955-0.00920-0.008760.000130.000250.000350.000440.000120.000100.00009-0.00002-0.000010.00001求cos0.048和cos0.575之值差分表如下：

計(jì)算cos0.048時(shí)，用牛頓向前插值公式，取代入公式得：計(jì)算cos0.575時(shí)，用牛頓向后插值公式，取代入公式得：小結(jié)本章按基本思想，計(jì)算公式、算法設(shè)計(jì)、程序框圖設(shè)計(jì)和源程序的順序分別介紹了線性插值、拋物插值、一般拉格朗日插值、分段線性和拋物插值、牛頓插值等插值方法。主要包括兩個(gè)部分：1）線性插值、拋物插值、一般拉格朗日插值、分段線性和拋物插值均屬于拉格朗日插值法。這類