數值分析插值法

第六章插值

/*Interpolation*/當精確函數y=f(x)非常復雜或未知時，在一系列節(jié)點x0…xn處測得函數值y0

=f(x0),…yn

=f(xn)，由此構造一個簡單易算的近似函數g(x)

f(x)，滿足條件g(xi)=f(xi)(i=0,…n)。這里的g(x)稱為f(x)的插值函數。最常用的插值函數是…?多項式x0x1x2x3x4xg(x)

f(x)§1拉格朗日多項式/*LagrangePolynomial*/niyxPiin,...,0,)(==求n次多項式使得條件：無重合節(jié)點，即n=1已知x0

,x1

;

y0

,

y1

，求使得111001)(,)(yxPyxP==可見P1(x)是過(x0,y0

)和(x1,y1

)兩點的直線。)()(0010101xxxxyyyxP---+=101xxxx--010xxxx--=y0

+y1l0(x)l1(x)==10)(iiiyxl稱為拉氏基函數

/*LagrangeBasis*/，滿足條件li(xj)=ij

/*KroneckerDelta*/§1LagrangePolynomialn

1希望找到li(x)，i=0,…,n使得

li(xj)=ij；然后令==niiinyxlxP0)()(，則顯然有Pn(xi)=

yi。li(x)每個li有n個根x0…

xi…xn=-=---=njjijiniiixxCxxxxxxCxl00)())...()...(()(-==jijiiiixxCxl)(11)(LagrangePolynomial與有關，而與無關節(jié)點f§1LagrangePolynomial定理(唯一性)滿足的n階插值多項式是唯一存在的。證明：(利用Vandermonde行列式論證)反證：若不唯一，則除了Ln(x)外還有另一n階多項式Pn(x)滿足Pn(xi)=yi。考察則Qn的階數n而Qn有個不同的根n+1x0…xn注：若不將多項式次數限制為n，則插值多項式不唯一。例如也是一個插值多項式，其中可以是任意多項式?！?LagrangePolynomial

插值余項/*Remainder*/設節(jié)點在[a,b]內存在,考察截斷誤差，且f

滿足條件,Rolle’sTheorem:若充分光滑，，則存在使得。推廣：若使得使得存在使得Rn(x)至少有個根n+1=-=niinxxxKxR0)()()(任意固定x

xi(i=0,…,n),考察=-=niixtxKtRnt0)()()()(j(x)有n+2個不同的根x0…

xn

x!)1()()()1(+-+nxKRxnnx注意這里是對t求導=+--++!)1)(()()()1()1(nxKLfxnnxnxx!)1()()()1(+=+nfxKxnx§1LagrangePolynomial注：

通常不能確定x

,而是估計,x(a,b)將作為誤差估計上限。當f(x)為任一個次數n

的多項式時，,可知，即插值多項式對于次數n的多項式是精確的。Quiz:給定xi=i+1,i=0,1,2,3,4,5.下面哪個是l2(x)的圖像？

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

ABC§1LagrangePolynomial例：已知分別利用sinx的1次、2次Lagrange插值計算sin50并估計誤差。解：n=1分別利用x0,x1以及x1,x2計算利用這里而sin50=0.7660444…)185(50sin10pL0.77614外推

/*extrapolation*/的實際誤差0.01001利用sin500.76008,內插

/*interpolation*/的實際誤差0.00596內插通常優(yōu)于外推。選擇要計算的x所在的區(qū)間的端點，插值效果較好?！?LagrangePolynomialn=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的實際誤差0.00061高次插值通常優(yōu)于低次插值但絕對不是次數越高就越好，嘿嘿……§2牛頓插值/*Newton’sInterpolation*/Lagrange插值雖然易算，但若要增加一個節(jié)點時，全部基函數li(x)都需重新算過。將Ln(x)改寫成的形式，希望每加一個節(jié)點時，只附加一項上去即可。????差商(亦稱均差)

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商§2Newton’sInterpolation11101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)階差商：事實上其中差商的值與xi的順序無關！§2Newton’sInterpolation牛頓插值

/*Newton’sInterpolation*/12…………n11+(x

x0)2+……+(x

x0)…(x

xn1)n1Nn(x)Rn(x)ai=

f[x0,…,xi]§2Newton’sInterpolation注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余項也相同，即實際計算過程為f(x0)f(x1)f(x2)…f(xn1)f(xn)f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]Newton插值多項式的計算表5-2

Newton插值多項式可按表5-2計算。xiyi=f(xi)一階差商二階差商…n階差商

x0y0

1x1y1f[x0,x1]

x-x0x2y2f[x1,x2]f[x0,x1,x2]

x3y3f[x2,x3]f[x1,x2,x3]

xnynf[xn-1,xn]f[xn-2,xn-1,xn]

f[x0,x1,…,xn]

n次Newton插值多項式Nn(x)為表5-2中對角線上的差商值與右端因子乘積的和。Newton插值公式計算舉例例3用Newton插值公式計算例1中的ln11.5。[解]

如果仍取點x0=11,x1=12,x2=13,作拋物線插值，按表5-2計算，結果如下：xiyi=

lnxi一階差商二階差商

112.3979

1122.48490.0870

x-11132.56490.0800-0.0035(x-11)(x-12)Newton插值公式計算例3續(xù)

若加節(jié)點x=10,14,ln10=2.3026,ln14=2.6391，用ln

x的四次Newton插值多項式近似,則:xiyi=f(xi)一階差商二階差商三階差商四階差商

102.3026

1112.39790.0953

x-10122.48490.0870-0.00415

(x-10)(x-11)132.56490.0800-0.003500.00022

142.63910.0742-0.002900.00020-0.000005

按表5-2計算結果如下:對于此題可以按下面方法估計N2（11·5）截斷誤差：另外一種方法是?。簒=11·5，由f(11.5)≈2.442275,可求得即從而可求得§2Newton’sInterpolation等距節(jié)點公式

/*FormulaewithEqualSpacing*/向前差分/*forwarddifference*/iiifff-=+1ikikikikffff1111)(-+---==向后差分/*backwarddifference*/111----=ikikikfffi1iifff-=中心差分/*centereddifference*/其中當節(jié)點等距分布時:Moregivenonp.113-114.差分計算——造表計算時可分別造表計算：表5-3向前差分表

xkfk=f(xk)fk2fk3fk4fk…x0f0

x1f1f0

x2f2f12f0

x3f3f22f13f0

x4f4f32f23f14f0

差分計算——造表（續(xù)1）表5-4xkfk=f(xk)

▽fk

▽2fk▽3fk▽4fk……x0f0x1f1▽f1x2f2▽f2▽2f2x3f3▽f3▽2f3▽3f3x4f4▽f4▽2f4▽3f4▽4f4差分計算——造表（續(xù)2）表5-5δ4f2δ3f2δ2f3δf3f4x4δ3f1δ2f2δf2f3x3δ2f1δf1f2x2δff1x1f0x0……δ4δ3

δ2

δfk=f(xk)xk1|21|21|21|21|21|2表5-6差分計算舉例例4-0.1053610.9060.117783-0.015748-0.2231440.8050.0048720.133531

-0.002678-0.020620-0.3566750.7040.0024250.0075500.154151

-0.003534-0.005103-0.028170-0.5108260.6030.0059590.0126530.182321

-0.011062-0.040823-0.6931470.5020.0237150.223144

-0.064538-0.9162910.4010.287682-1.2039730.300△6△5△4△3△2△lnxixii向后線中心差線0.007550注：（1）前差，后差，中心差之間是

緊密聯系的，都在一個表中，差分值所在

的列數為差分的階數。要確定某個差分值

是哪個點的差分，則：對向前差分：要看左上斜線上函數值對應的自變量值對向后差分：要看左下斜線上函數值對應的自變量值對中心差分：要看左方水平線上的自變量值，若正好

是空檔，則是相鄰兩個自變量值的算術

平均值。作y=lnx的差分表，步長h=0.1向前線差分的性質差分有一些重要性質，常用的有（與微分形式相似）：（2）各階差分均可表成函數值的線性組合。（1）各階差分均具有線性性，即若f(x)=a

(x)+b

(x)，則對任意正整數m，都有：差分的性質（續(xù)1）（3）各種差分之間可以互化，這由差分表即可看出。向后差分與中心差分化成向前差分的公式如下：（4）可用差分表示差商。

差分的性質（續(xù)2）一般地有：

結合式（5-14），可得差分與導數的關系：2.4等距節(jié)點插值公式設已知節(jié)點xk

=x0+kh(k=0,1,2,…,n)，將式（5-15）代入插值公（5-12），得：

如果插值節(jié)點是等距的，則插值公式可用差分表示。但在進行插值時，一般不可能將給出的所有點都作為插值點，總是希望運用較少的點達到應有的精度，所以，當被插值點靠近數據表頭時，當然考慮用表初的那些點作為插值點，而當被插值點接近數據表尾時，應先選用表尾的那些點作插值點，這樣就有Newton向前及向后插值公式。Newton向前插值公式式（5-17）稱為Newton向前插值公式，其余項為：若令x

=x0+th，則上式又可變形為：Newton向后插值公式

完全類似地，也可以用向后差分表示Newton插值公式。令x=xn+th

x

[x0,xn]，則有：式（5-19）稱為Newton向后插值公式，其余項為：

Newton向前、向后插值公式均是Newton插值公式在等距節(jié)點時的變形。實際計算時，也可列表進行。將表5-7中對角線上的差分值與對應行右端因子乘積求和即得Newton向前插值公式，而Newton向后插公式則為最后的節(jié)點所在行的各階差分值與對應列下端因子乘積之和。表5-7見下屏：表5-7…t1△

nf

0(▽

nfn)…△3f

n-3(▽

3fn)△2f

n-2(▽

2fn)△f

n-1(▽

fn)fnxn………………