数值分析插值法

第六章插值

/*Interpolation*/当精确函数y=f(x)非常复杂或未知时，在一系列节点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次多项式使得条件：无重合节点，即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与有关，而与无关节点f§1LagrangePolynomial定理(唯一性)满足的n阶插值多项式是唯一存在的。证明：(利用Vandermonde行列式论证)反证：若不唯一，则除了Ln(x)外还有另一n阶多项式Pn(x)满足Pn(xi)=yi。考察则Qn的阶数n而Qn有个不同的根n+1x0…xn注：若不将多项式次数限制为n，则插值多项式不唯一。例如也是一个插值多项式，其中可以是任意多项式。§1LagrangePolynomial

插值余项/*Remainder*/设节点在[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内插通常优于外推。选择要计算的x所在的区间的端点，插值效果较好。§1LagrangePolynomialn=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的实际误差0.00061高次插值通常优于低次插值但绝对不是次数越高就越好，嘿嘿……§2牛顿插值/*Newton’sInterpolation*/Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过。将Ln(x)改写成的形式，希望每加一个节点时，只附加一项上去即可。????差商(亦称均差)

/*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=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）截断误差：另外一种方法是取：x=11·5，由f(11.5)≈2.442275,可求得即从而可求得§2Newton’sInterpolation等距节点公式

/*FormulaewithEqualSpacing*/向前差分/*forwarddifference*/iiifff-=+1ikikikikffff1111)(-+---==向后差分/*backwarddifference*/111----=ikikikfffi1iifff-=中心差分/*centereddifference*/其中当节点等距分布时:Moregivenonp.113-114.差分计算——造表计算时可分别造表计算：表5-3向前差分表

xkfk=f(xk)fk2fk3fk4fk…x0f0

x1f1f0

x2f2f12f0

x3f3f22f13f0

x4f4f32f23f14f0

差分计算——造表（续1）表5-4xkfk=f(xk)

▽fk

▽2fk▽3fk▽4fk……x0f0x1f1▽f1x2f2▽f2▽2f2x3f3▽f3▽2f3▽3f3x4f4▽f4▽2f4▽3f4▽4f4差分计算——造表（续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，都有：差分的性质（续1）（3）各种差分之间可以互化，这由差分表即可看出。向后差分与中心差分化成向前差分的公式如下：（4）可用差分表示差商。

差分的性质（续2）一般地有：

结合式（5-14），可得差分与导数的关系：2.4等距节点插值公式设已知节点xk

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

如果插值节点是等距的，则插值公式可用差分表示。但在进行插值时，一般不可能将给出的所有点都作为插值点，总是希望运用较少的点达到应有的精度，所以，当被插值点靠近数据表头时，当然考虑用表初的那些点作为插值点，而当被插值点接近数据表尾时，应先选用表尾的那些点作插值点，这样就有Newton向前及向后插值公式。Newton向前插值公式式（5-17）称为Newton向前插值公式，其余项为：若令x

=x0+th，则上式又可变形为：Newton向后插值公式

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

x

[x0,xn]，则有：式（5-19）称为Newton向后插值公式，其余项为：

Newton向前、向后插值公式均是Newton插值公式在等距节点时的变形。实际计算时，也可列表进行。将表5-7中对角线上的差分值与对应行右端因子乘积求和即得Newton向前插值公式，而Newton向后插公式则为最后的节点所在行的各阶差分值与对应列下端因子乘积之和。表5-7见下屏：表5-7…t1△

nf

0(▽

nfn)…△3f

n-3(▽

3fn)△2f

n-2(▽

2fn)△f

n-1(▽

fn)fnxn………………