第4章插值與曲線擬合

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

4.2埃特金算法

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

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

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

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

Lk(x),Lk+1(x)稱為線性插值基函數(shù)，P1(x)稱為線性插值函數(shù)，也稱為線性插值多項式。程序框圖設計讀入x0,x1,y0,y1讀入x計算L0計算L1計算y=y0?L0+y1?L1輸出y4.1.2拋物插值基本思想：用二次插值多項式P2(x)近似代替被插函數(shù)f(x)計算函數(shù)值。從幾何意義上就是在插值區(qū)間上用拋物線近似地代替被插函數(shù)曲線f(x)。插值公式：其中：程序框圖設計讀入x0,x1,x2,y0,y1,y2讀入x計算L0計算L1計算y=y0?L0+y1?L1+y2?L2輸出y計算L24.1Lagrange插值方法設給定函數(shù)y=f(x)有n+1個數(shù)據(jù)點(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ù)有關定理，有：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)，若令則當x=xi時有

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

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

i=

k,當xk-1<x<xk時

n,當x>

xn-1時

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

分段拋物插值結點的確定：1,當x<x1時

i=

k-1,當xk-1<x<xk,且|x-xk-1|<|x-xk|k,當xk-1<x<xk,且|x-xk-1|>|x-xk|

n,當x>

xn-1時

算法設計：1)當x<x1時，取i=1，直接使用線性插值公式計算插值結果。2)當x>xn-1時，取i=n，直接使用線性插值公式計算插值結果。3)當x>x1時，則a.取i=1.b.使i=i+1c.判斷x<xi是否成立，若成立，則判斷|x-xi-1|<|x-xi|是否成立，若成立，則i=i-1,使用插值公式計算，若不成立，直接使用插值公式計算插值結果直接使用插值公式計算插值結果。否則返回步驟b執(zhí)行。4.3Newton插值方法差商：若對于函數(shù)y=f(x),有實驗數(shù)據(jù)那么－－一階差商－－二階差商－－n階差商差商的性質性質1：性質2：性質3：性質4：性質5：差商的計算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]牛頓插值多項式應用拉格朗日插值時，各階的插值公式差別很大，低階插值的結果不能為高階插值計算所利用，如果在低階插值計算公式的基礎上，加上一項修正項而得到高階插值公式，就能使計算具有承襲性，這種插值方法就是牛頓插值。假設：Pk(x)=Pk-1(x)+hk(x)式中：Pk(x)－－函數(shù)f(x)的k階插值多項式Pk-1(x)－－函數(shù)f(x)的k-1階插值多項式hk(x)－－修正項由上式得

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

若不成立，則返回步驟1執(zhí)行。程序框圖使用等距結點插值法求插值結點x處的函數(shù)值輸入使用等距結點插值法求插值結點x處的函數(shù)值輸出升階使a[i]=f[i],y=y1在i循環(huán)中計算差分f[i]=a[i]-a[i-1]計算連乘積q=q·(t-k+1)計算階乘值p=p·k計算插值結果y1=y1+q·f(k)/p判斷|y-y1|<E是否成立，若成立，則程序轉去輸出并結束，若不成立，則返回步驟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之值差分表如下：

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