第二章：插值法

1、 描述事物之间的数量关系：函数。 有两种情况： 一是表格表格形式一组离散的数据离散的数据来表示函数关系；另一种是函数虽然有明显的有明显的表达式表达式，但很复杂，但很复杂，不便于研究和使用。 从实际需要出发：对于计算结果允许有一定的误差，可以把函数关系用一个简单的便于计算和处理的近似表达式近似表达式来代替，从而使问题得到简化。一般地，构造某种简单函数代替原来函数。插值法就是一种基本方法0 引言引言第二章第二章 插值插值（Interpolation）法法(1)(2)(2) 在在 x 为特殊时为特殊时, 是好计算的是好计算的, 则则 (2)可转化为可转化为(1)当精确函数当精确函数 y = f(x)

2、 非常复杂或未知时，在一非常复杂或未知时，在一系列节点系列节点 x0 xn 处测得函数值处测得函数值 y0 = f(x0), yn = f(xn)，由此构造一个简单易算的近似函，由此构造一个简单易算的近似函数数 g(x) f(x)，满足条件，满足条件g(xi) = f(xi) (i = 0, n)。这里的。这里的 g(x) 称为称为f(x) 的的插值函数插值函数。x0 x1x2x3x4xg(x) f(x) 根据实际需要，可以用各种不同的函数来近似原来的函数。最常用的插值函数是最常用的插值函数是 ?多项式：多项式： 代数多项式最简单，计算其值只需用到加、减乘运算，且积分和微分都很方便； 所以常用

3、它来近似表示表格函数(或复杂函数),这样的插值方法叫做代数插值法代数插值法，简称插值法。1 拉格朗日多项式拉格朗日多项式 niyxPiin,., 0,)(= = =求求 n 次多项式次多项式 使得使得nnnxaxaaxP = =10)(条件：条件：无重合节点，即无重合节点，即jixx ji n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( = =使得使得111001)(,)(yxPyxP= = =可见可见 P1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。)(1xP101xxxx- - -010 xxxx- -

4、 -= y0 + y11.1 线性插值线性插值两点式两点式)()(0010101xxxxyyyxP- - - - = =点斜式点斜式)(001010 xxxxxxy- - - - = =()ff1.2 二次插值二次插值n = 2已知已知 x0 , x1 , x2; y0 , y1 ,y2 , 求求22102)(xaxaaxP = =使得使得002,)(yxP112)(yxP= = =222)(yxP= =, 为求为求P2(x),将三点代入其表达式将三点代入其表达式,即可得到三个方程式即可得到三个方程式,从而联立方程组解出系数从而联立方程组解出系数a0, a1, a2即可即可:2020100 x

5、axaay = =2121101xaxaay = =2222102xaxaay = =方程组的方程组的解是否存在解是否存在? 若存在解若存在解,是否是否唯一唯一?!当当 x0 , x1 , x2互异时互异时,方程组的解存在且唯一方程组的解存在且唯一.注：注：显然有显然有, 求求n 次插值时次插值时, 由由n +1个点可有个点可有n +1个方程个方程, 联立方程组即可求出插值多项式的联立方程组即可求出插值多项式的n +1个系数个系数. 然而然而,方程组的求解也并不是一件容易的事方程组的求解也并不是一件容易的事。1.2.1 待定系数法待定系数法 对于线性插值的对于线性插值的两种形式两种形式解解进行

6、适当的分析进行适当的分析, , 从中寻求规律而得到启发从中寻求规律而得到启发, ,就有了所谓的就有了所谓的拉格朗日拉格朗日插值法插值法( (公式公式) )和和牛顿插值牛顿插值( (公式公式).). 我们先来看看如何得到二次二次拉格朗日插值公式拉格朗日插值公式（和和牛顿插值公式牛顿插值公式（为讨论方便，留待后述）（为讨论方便，留待后述）. . 首先, 线性插值的两点式可看作是两个特殊的一次式可看作是两个特殊的一次式的一种线性组合的一种线性组合.101xxxx- - -010 xxxx- - -)(1xP= y0 + y1 = = =10)(iiiyxl两点式两点式l0(x)l1(x)实质上实质上

7、0l（x）和）和1l（x）即是满足函数表）即是满足函数表 的一次插值多项式的一次插值多项式 ,称称l0(x)和和l1(x)为以为以x0,x1为节点的基本插为节点的基本插值多项式，也称为值多项式，也称为线性插值的线性插值的插值基函数插值基函数 。 于是，线性插值即是用于是，线性插值即是用基函数的线性组合基函数的线性组合来构造的来构造的. 1.2.2 基函数法基函数法称为称为拉氏基函数拉氏基函数 ，满足，满足 li(xj)= ij 显然有显然有l0(x)+ l0(x)1.这里，这里， l0(x)和和l1(x)具有如下性质：具有如下性质：l0(x0)=1, l0(x1)=0, l1(x0)=0, l

8、1(x1)=1, 由此启发，我们希望二次插值也能由一些二次插值基由此启发，我们希望二次插值也能由一些二次插值基函数来线性组合函数来线性组合:这时，这时，l0(x), l1(x), l2(x)都是二次多项式，且应满足都是二次多项式，且应满足满足满足(2.1)式的式的 l i(x) 是否存在是否存在?若存在，具有什么形式呢若存在，具有什么形式呢?（2.1）同理可得同理可得 l1(x) 1(x x0)(x x2), l2(x) 2(x x0)(x x1),1(x1x0)(x1x2)12(x2x0)(x2x1)1此即此即二次二次拉格朗日插值公式拉格朗日插值公式, 其中其中, l0(x), l1(x),

9、 l2(x)是满足是满足(2.1)的特殊的特殊(基本基本)二次插值多项式二次插值多项式;称为称为二次插值基函数二次插值基函数.P2(x)= y0+ y1+ y2(x - -x0)(x - -x2)(x1- -x0)(x1- -x2)(x - -x1)(x - -x2)(x0- -x1)(x0- -x2)(x - -x0)(x - -x1)(x2- -x0)(x2- -x1) 先考虑先考虑 l0(x)。因。因 l0(x)是以是以 x1, x2 为零点的二次多项式为零点的二次多项式,所以它可写成所以它可写成 l0(x) 0(x x1)(x x2), 其中其中 0 是待定系是待定系数。数。 又因为又

10、因为 l0( x0)=1，所以，所以 0(x0 x1)(x0 x2)1，则可有，则可有0(x0 x1)(x0 x2)1 l0(x) 0(x x1)(x x2), n 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令 = = =niiinyxlxP0)()(，则显然有，则显然有Pn(xi) = yi 。li(x)每个每个 li 有有 n 个根个根 x0 xi xn = =- -= =- - - -= =njj i jiniiixxCxxxxxxCxl00)().().()( - -= = =j i jiiiixxCxl)(11)(= = - -

11、 -= =njijjijixxxxxl0)()()( = = =niiinyxlxL0)()( 拉格朗日拉格朗日 多项式多项式与与 有关，而与有关，而与 无关无关节点节点f1.3 n 次插值次插值定理定理 (唯一性唯一性) 满足满足 的的 n 阶插值多阶插值多项式是唯一存在的。项式是唯一存在的。niyxPii,., 0,)(= = =证明：证明： ( 存在性存在性可利用可利用Vandermonde 行列式行列式论证论证)反证：若不唯一，则除了反证：若不唯一，则除了Ln(x) 外还有另一外还有另一 n 阶多项阶多项式式 Pn(x) 满足满足 Pn(xi) = yi 。考察考察 则则 Qn 的阶数

12、的阶数, )()()(xLxPxQnnn- -= = n而而 Qn 有有 个不同的根个不同的根n + 1x0 xn注：注：若不将多项式次数限制为若不将多项式次数限制为 n ，则插值多项式，则插值多项式不唯一不唯一。例如例如 也是一个插值也是一个插值多项式，其中多项式，其中 可以是任意多项式。可以是任意多项式。= =- - = =niinxxxpxLxP0)()()()()(xp = = =niiinyxlxL0)()(设节点设节点)1( nf在在a , b内存在内存在, 考察截断误差考察截断误差)()()(xLxfxRnn- -= =, baCfn bxxxan 10，且，且 f 满足条件满足

13、条件 ,Rolles Theorem: 若若 充分光滑，充分光滑， ，则，则存在存在 使得使得 。)(x 0)()(10= = =xx ),(10 xx 0)(= = 推广：推广：若若0)()()(210= = = =xxx ),(),(211100 xxxx 使得使得0)()(10= = = = ),(10 使得使得0)(= = 0)()(0= = = =nxx 存在存在),(ba 使得使得0)()(= = nRn(x) 至少有至少有 个根个根n+1 = =- -= =niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 = =- - -= =n

14、iixtxKtRnt0)()()()( (t)有有 n+2 个不同的根个不同的根 x0 xn x),(, 0)()1(baxxn = = !)1()()()1(-nxKRxnn 注意这里是对注意这里是对 t 求导求导= = - - - !)1)()()()1()1(nxKLfxnnxn !)1()()()1( = = nfxKxn = = - - = =niixnnxxnfxR0)1()(! ) 1()()( 1.4 插值余项插值余项 (Remainder) 注：注： 通常不能确定通常不能确定 x , 而是估计而是估计 , x (a,b) 将将 作为误差估计上限。作为误差估计上限。1)1()(

15、 nnMxf= = - - niinxxnM01|)!1(当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时，时， , 可知可知 ，即插值多项式对于次数，即插值多项式对于次数 n 的的多项多项式是式是精确精确的。的。0)()1( xfn0)( xRn.)(应应用用的的高高阶阶导导数数存存在在时时才才能能余余项项表表达达式式只只有有在在xf,)()( )(61)(2,)( )(21)()(21)(1202102101021xxxxxxxxfxRnxxxxxxfxfxRn - - - - = = = - - - = = = = = ，时时，抛抛物物插插值值的的余余项项为为当当，时时，

16、线线性性插插值值余余项项为为当当例例1 求经过求经过A(0,1)，B(1,2)，C(2,3)三个插值点的插值多项式三个插值点的插值多项式.解：解：三个插值节点及对应的函数值为三个插值节点及对应的函数值为.322110221100= = = = = = =yxyxyx，；，；，13)12)(02()1)(0(2)21)(01()2)(0(1)20)(10()2)(1()()()()()()()(2120210121012002010212 = = - - - - - - - - - - - - - - -= =- - - - - - - - - - - - - - -= =xxxxxxxyxxx

17、xxxxxyxxxxxxxxyxxxxxxxxxL由抛物插值公式得由抛物插值公式得例例2：已知已知233sin,214sin,216sin= = = = 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：0 x1x2x185500 =n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算4,610 =xx利用利用216/4/6/214/6/4/)(1 - - - - - -= = xxxL这里这里)3,6(,sin)(,sin)()2( - -= = =xxxfxxf而而)4)(6(!2)(

18、)(,23sin21)2(1 - - -= = xxfxRxx00762. 0)185(01319. 01- - - - Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 (extrapolation ) 的实际误差的实际误差 - -0.010010.010013,421 = = =xx利用利用sin 50 0.76008, 00660. 018500538. 01 R内插内插 (interpolation ) 的实际误差的实际误差 0.005960.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点

19、，插值效果较好。端点，插值效果较好。n = 223)()(21)()(21)()()(4363463464363646342 - - - - - - - - - - - - - - -= = xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 - - - - -= =xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的实际误差次插值的实际误差 0.000610.00061高次插值通常优于高次插值通常优于低次插值低次插值但绝对不是次数越但绝对不是次数越高就越好，嘿高就越好，嘿嘿嘿 例例

20、3 考虑下述的插值法问题：求二次多项式考虑下述的插值法问题：求二次多项式P(x)，满足，满足P(x0) = y0, 其中其中 是已给的数据并给出使这一问题的解存在且唯一的条件是已给的数据并给出使这一问题的解存在且唯一的条件.，2211)()(yxPyxP=21020yyyxx、，解解：设：设 则则 由已知条件有由已知条件有，cbxaxxP=2)(.2)(baxxP=11222200202ybaxycbxaxycbxax0012111222020 xxxxx0)()(22220201-xxxxx)0(220201-xxxxx即即 所以所以故原问题的唯一可解性就归结为上述方程组的唯一可解性而后故原

21、问题的唯一可解性就归结为上述方程组的唯一可解性而后者唯一可解的充要条件为者唯一可解的充要条件为这就是这就是P（x）存在且唯一的条件。）存在且唯一的条件。 LagrangeLagrange插值插值公式公式( (利用利用插值基函数插值基函数很容易得到很容易得到):): 含义直观含义直观, ,结构紧凑结构紧凑, ,在理论分析中非常方便在理论分析中非常方便; ; 计算机上计算机上实现实现也很也很容易容易. . 也有一些也有一些缺点缺点： 一是一是计算量大计算量大，这是显然的；另外，还有一个更严，这是显然的；另外，还有一个更严重的缺点，当插值节点增加时，重的缺点，当插值节点增加时，全部插值基函数全部插值

22、基函数均要随之均要随之变变化化，整个计算工作必须从头开始：不仅原来的每一项都要改，整个计算工作必须从头开始：不仅原来的每一项都要改变，还要变，还要增加一项增加一项计算。计算。 为克服上述两个缺点为克服上述两个缺点, , 努力：把插值多项式变形为努力：把插值多项式变形为便于计算便于计算的形式。的形式。 希望：希望：计算改变的过程中计算改变的过程中, ,尽可能能利用已有的计算结尽可能能利用已有的计算结果果. . 下面我们将看到下面我们将看到, ,这是可能的。我们可以有具有这是可能的。我们可以有具有“承袭承袭性性”的所谓牛顿公式。的所谓牛顿公式。)()(0010101xxxxyyyxP- - - -

23、 = =)(001010 xxxxxxy- - - - = =()fffx0,x1 二次牛顿插值多项式二次牛顿插值多项式 我们再看线性插值线性插值的点斜式点斜式: )(00 xxy- - = =fx0,x1常数常数(差商差商) 由此启发，我们希望二次插值也能类似地有有规律的由此启发，我们希望二次插值也能类似地有有规律的组合表达式组合表达式:P2(x)= 0 + 1(x- -x0) + 2(x- -x0)(x- -x1)利用利用P2(x0)=y0有有: 0 = y0 ,利用利用P2(x1)=y1有有: 1 = 0101xxxx- - -()ff= fx0,x1 ,利用利用P2(x2)=y2有有:

24、 2 = fx0,x1 (x2- -x0)(x2- -x1) (x2- -x0)(x2- -x1)0 xx2- -()ff (x2- -x0)-fx0,x2fx0,x1 x2 - - x1 =-= fx0,x1,x2 ;P2(x)=f(x0) + (x- -x0) + (x- -x0)(x- -x1) fx0,x1 fx0,x1,x2 fx0,x2 x=x0时0注注: 1. 事实上事实上,从上述可看出二次牛顿插值公式是用从上述可看出二次牛顿插值公式是用待待定系数法定系数法求得的求得的; 2. 它也可看作是三个特殊函数的一种线性组合它也可看作是三个特殊函数的一种线性组合:P2(x)=f(x0)

25、+ (x- -x0) + (x- -x0)(x- -x1) fx0,x1 fx0,x1,x2 fx0,x1 , fx0,x1,x2 f(x0), 1 , (x- -x0) , (x- -x0)(x- -x1)即函数 的线性组合,组合系数为 本质上还是本质上还是基函数法基函数法. 更一般地，更一般地，n+1个节点的插值多项式，我们希望由上个节点的插值多项式，我们希望由上述类似的一组特殊函数：述类似的一组特殊函数：来线性组合为：来线性组合为： 1 , (x- -x0) , (x- -x0)(x- -x1)，(x- -x0)(x- -x1)(x- -xn).(.)()()(10102010- - -

26、 - - - - - - = =nnnxxxxaxxxxaxxaaxN那么其组合系数是什么样的呢？怎么求呢？那么其组合系数是什么样的呢？怎么求呢？我们同样可用待定系数法我们同样可用待定系数法. 容易发现容易发现,计算计算a0, a1, a2 , an 是很有规律的是很有规律的.一、均差及其性质一、均差及其性质2 牛顿插值牛顿插值当当x=x0时，时，Pn(x0)=a0=f0.当当x=x1时，时，Pn(x1)=a0+a1(x1- -x0)=f1, 推得推得a1=f1- -f0 x1- -x0当当x=x2时，时，Pn(x2)=a0+a1(x2- -x0)+a2(x2- -x0)(x2- -x1)=

27、f2,推得推得f1- -f0 x1- -x0- -f1- -f0 x1- -x0a2=x2- -x1 依次递推可得到依次递推可得到a3, , an. 为写出系数为写出系数 ak的一般表达式的一般表达式,先引进如下均差定义先引进如下均差定义. 定义定义2 称称 为函数为函数f(x)关于点关于点x0,xk的的一阶均差一阶均差.称称 为为f(x) 的的二阶均差二阶均差.一般地一般地, 称称 为为 f(x) 的的k 阶均差阶均差(差商差商). fx0,xk =f(xk)- -f(x0)xk- -x0 fx0,x1,xk=fx0,xk- - fx0,x1xk- -x1 fx0,x1,xk=fx0, xk

28、-2,xk- - fx0,x1, ,xk-1xk- -xk-1均差有如下的基本性质均差有如下的基本性质: 1 k 阶均差可表示为函数值阶均差可表示为函数值f(x0), f(x1), f(xk)的线性组合的线性组合,即即 fx0,x1,xk=f(xj)(xj- -xj+1)(xj- -xk)(xj- -xj+1)(xj- -x0) kj=0这个性质可用归纳法证明这个性质可用归纳法证明. 这个性质也表明均差与节点的排列这个性质也表明均差与节点的排列次序无关次序无关,称为均差的对称性称为均差的对称性,即即 fx0,x1,xk= fx1,x0,x2,xk= = fx1, , xk ,x0 fx0,x1

29、,xk=fx1, xk-1,xk- - fx0,x1, ,xk-1xk- -x02 由性质由性质1可得可得: fx0, x1,xk =f(n)()n!,ba 3 若若f(x)在在a,b上存在上存在n阶导数阶导数, 且节点且节点x0,x1,xn a,b,则则n阶均差与导数关系如下阶均差与导数关系如下: 这个公式可直接用罗尔定理证明这个公式可直接用罗尔定理证明.，0!)()(0)()(= =- -= =nnnxxfnfq .!)()(0nfxxfnn = =， 所以所以，使，使记为记为个零点个零点内至少有内至少有在在理，可知理，可知零点；反复应用罗尔定零点；反复应用罗尔定个个内至少有内至少有在在个

30、零点，故个零点，故的两个零点间至少有一的两个零点间至少有一在在，个零点，根据罗尔定理个零点，根据罗尔定理上有上有在在处均为零，所以处均为零，所以，在在，证明：设证明：设, , 1 ,)(,)()()(1,)()( ),()()( )(0100babaxqnbaxqxqxqnbaxqxxxqxxxxxxxxxfxqnnnn - - - -= = ,)()()(000 xxfxxxfxf- - = =,)(,101100 xxxfxxxxfxxf- - = =,.,)(,.,.,0010nnnnxxxfxxxxfxxxf- - = =- -).(.)()()(10102010- - - - - -

31、 - - - = =nnnxxxxaxxxxaxxaaxN12 n- -11+ (x - - x0) 2+ + (x - - x0)(x - - xn- -1) n- -1.)(,)(,)()(102100100 - - - - - = =xxxxxxxfxxxxfxfxf).(,.,100- - - - nnxxxxxxf)().(,.,100nnnxxxxxxxxxf- - - - - -Nn(x)Rn(x)ai = f x0, , xi 二、牛顿插值公式二、牛顿插值公式)().(,.,100nnnxxxxxxxxxf- - - -= =- -Rn(x).)(,)(,)(102100100

32、 - - - - - = =xxxxxxxfxxxxfxf).(,.,100- - - - nnxxxxxxfNn(x)n+1(x)10(0nkxxfakk，= = = 多项式多项式Nn(x)显然满足插值条件显然满足插值条件,即即Nn(xj)=f(xj),(j=1, n),且次数不超过且次数不超过n,由唯一性定理它就是前述的由唯一性定理它就是前述的Ln(x),其系数为其系数为 Nn(x)称为牛顿均差插值多项式称为牛顿均差插值多项式,它比拉格朗日插值多项式它比拉格朗日插值多项式计算量省计算量省,且便于程序设计且便于程序设计.注：注： 由由唯一性可知唯一性可知 Nn(x) Ln(x)， 只是算法不

33、同，故其只是算法不同，故其余项也相同，即余项也相同，即)(!)1()()(,.,1)1(10 xnfxxxxfkxnkn = = ),(,!)(,.,maxmin)(0 xxkfxxfkk = = 实际计算过程为实际计算过程为f (x0)f (x1)f (x2)f (xn- -1)f (xn)f x0, x1f x1, x2 f xn- -1, xnf x0, x1 , x2 f xn- -2, xn- -1, xnf x0, , xn f (xn+1) f xn, xn+1 f xn- -1, xn, xn+1 f x1, , xn+1 f x0, , xn+1均差计算可列均差表如下：均差计

34、算可列均差表如下：, 2, 1 , 1, 0 ,11 = = =- - -= =- - iikixxxxfxxfxxfikkikiki010110 xxxfxfxxf- - -= =)()(,232332xxxfxfxxf- - -= =)()(,021021210 xxxxfxxfxxxf- - -= =,243243432xxxxfxxfxxxf- - -= =,143214324321xxxxxfxxxfxxxxf- - -= =,043210432143210 xxxxxxfxxxxfxxxxxf- - -= =, 例例1 依据如下函数值表建立不超过依据如下函数值表建立不超过3次的拉格

35、朗日插值多次的拉格朗日插值多项式及牛顿插值多项式项式及牛顿插值多项式Nn(x),并验证插值多项式的唯一性并验证插值多项式的唯一性. 解解: (1)拉格朗日插值多项式拉格朗日插值多项式Ln(x).插值基函数插值基函数xk0124f (xk)19233拉格朗日插值多项式为拉格朗日插值多项式为:121445411 )(3)(23)(9)()()(233210303-=xxxxlxlxlxlyxlxLiii,12181241)24)(14)(04()2)(1)(0()(,4541)42)(12)(02()4)(1)(0()(,38231)41)(21)(01()4)(2)(0()(, 1478781)

36、40)(20)(10()4)(2)(1()(233232231230 xxxxxxxlxxxxxxxlxxxxxxxlxxxxxxxl-=-=-=-=-=-=-=-=xkf (xk) 一阶均差一阶均差二阶均差二阶均差三阶均差三阶均差0119822314343- -10- -8(2) 牛顿插值多项式牛顿插值多项式Nn(x).建立如下差商表建立如下差商表牛顿插值多项式为牛顿插值多项式为:121445411 )2)(1)(0(411) 1)(0(3)0(81)(233-=-=xxxxxxxxxxN411-(3) 唯一性验证唯一性验证.通过比较牛顿插值多项式和拉格朗日插值多项式通过比较牛顿插值多项式和

37、拉格朗日插值多项式,知知: Nn(x) = Ln(x)这一事实与插值多项式的唯一性一致这一事实与插值多项式的唯一性一致. 2已知等距节点已知等距节点nxxhnkkhxxnk00210- -= = = = =,三、三、NewtonNewton等距插值等距插值1 1、差分、差分定义定义)()()(kkkxfxfxf- -= = 1简记为简记为kkkfff- -= = 11- - -= = kkkfff)()()(1- - -= = kkkxfxfxf简记为简记为 - - - = =22hxfhxfxfkkk)( 22hkhkkfff- - - -= = 简记为简记为向前差分向前差分 向后差分向后差

38、分 中心差分中心差分 前差算子前差算子后差算子后差算子kmkmkmfff111- - - - - - = = 高阶向前差分高阶向前差分 111- - - - - - = = kmkmkmfff高阶向后差分高阶向后差分 如如)()(kkkkkkkfffffff- - - -= = - - = = 11212kkkfff - -= = 122)()(21112- - - - - - - -= = - - = = kkkkkkkfffffff212- - - - -= =kkkfff2、高阶差分、高阶差分 )()()()(kkkkkkkkffffffff- - - - - - - -= = 1121

39、223kkkkffff- - - -= = 12333)()(kkkkkkkfffffff - - - - - - = = - - = = 1122123又如又如 3、前差与后差的关系、前差与后差的关系 11 = =- -= = kkkkffff)()(kkkkkkkfffffff- - - -= = - - = = 112122212 = = - - = =kkkfffmkmkmff = = 一般有一般有再定义再定义1 = =kkfEf前移算子前移算子kkffI= =不变算子不变算子11- - -= =kkffE后移算子后移算子则有则有kkkkkkfIEIfEffff)(- -= =- -=

40、 =- -= = 1因此因此knknfIEf)(- -= = inkniinikniiininifCfIEC- - = = =- - - -= =- -= =0011)()(knknknfIEfEIf)()( - -= =- -= = - - -11nikniininkniniininfCfEC- - = =- -= =- - - - -= =- -= =0011)()( knnniniininnnfICIECEC0011)()(- - - - - -= =- - - - knnnniinininnnnfICIECIECEC)()(11110- - - - - -= =- - -4 差商与差分

41、的关系差商与差分的关系hfxxxfxfxxfkkkkkkk = =- - -= = 111)()(,hhfhfxxxxfxxfxxxfkkkkkkkkkkk21211221 - - = =- - -= = ,kfh2221 = =kmmmkkkfhmxxxf = = 111!,m阶向前差商与阶向前差商与m阶向前差分的关系阶向前差分的关系查看全部 m阶向后差商与阶向后差商与m阶向后差分的关系阶向后差分的关系kmmmkkkfhmxxxf = =- - -111!,又又!)(,)(mfxxxfmmkkk = = 1所以所以)(,!)( mmmkkkmkmfhxxxfmhf= = = 15、差分的计算

42、、差分的计算6、等距节点的、等距节点的Newton插值插值已知等距节点已知等距节点nxxhnkkhxxnk00210- -= = = = =,)(,)()(0100 xxxxfxfxNn- - = =)()(,1010- - - - nnxxxxxxxf)(,10210 xxxxxxxf- - - 得得)()(000001xthxfhfthxNn- - = = )(!hxthxxthxfh- - - - - 000002221)()(!hnxthxxthxfhnnn1100000- - - - - - 令令 由由Newton插值公式插值公式thxx = =0其中其中)(00 xff = =km

43、mmkkkfhmxxxf = = 111!,参参照照)()(000001xthxfhfthxNn- - = = )(!hxthxxthxfh- - - - - 000002221)()(!hnxthxxthxfhnnn1100000- - - - - - 即即htthfhthfhfthxNn)(!)(1211022000- - = = hntthfhnnn)(! - - 110002001121fnntttfttftfn - - - - - = =!)()(!)(前插公式前插公式同理可得后插公式同理可得后插公式（P27)P27)(thxNnn 0021121fnntttfttftfnnn -

44、- = =!)()(!)(3 厄尔米特插值厄尔米特插值 不仅要求函数值重合，而且要求若干阶不仅要求函数值重合，而且要求若干阶导数导数也重合。也重合。即：要求插值函数即：要求插值函数 (x) 满足满足 (xi) = f (xi), (xi) = f (xi), (mi) (xi) = f (mi) (xi).注：注： N 个条件可以确定个条件可以确定 阶多项式。阶多项式。N - - 1要求在要求在1个节点个节点 x0 处直到处直到m0 阶导数都重合的插阶导数都重合的插值多项式即为值多项式即为Taylor多项式多项式00)(!)(.)()()(000)(000mmxxmxfxxxfxfx- - -

45、 - = = 其余项为其余项为)1(00)1(00)()!1()()()()(-=-=mmxxmfxxfxR 一般只考虑一般只考虑 f 与与f 的值。的值。 当当 较大时用待定系数法求较大时用待定系数法求 是困难的是困难的 = = = =12012niiinxaxH)(n令令),()(),(njxxjj210= = 为为 次多项式次多项式12 n = = =0)( )(kjjkkjxx nkjxxjkkjkj,)( )(100= = = = = 且满足且满足 = = = =kjkjjk,10 其中其中且满足且满足),()( ,)(nkmxHyxHkkkk10= = = =令令 = = = =n

46、jjjjjmxyxxH0)()()( 为为 次多项式次多项式12 n所以所以 为为HermiteHermite插值多项式。插值多项式。)(xHKronecker（克罗内克）符号（克罗内克）符号柏林科学院院士，巴黎科学院通讯院柏林科学院院士，巴黎科学院通讯院士，伦敦皇家学会外籍会员。士，伦敦皇家学会外籍会员。 主张分析学应奠基于算术，而算术的主张分析学应奠基于算术，而算术的基础是整数。克罗内克名言：基础是整数。克罗内克名言：“上帝上帝创造了整数，其余都是人做的工作创造了整数，其余都是人做的工作”令令)()()(xlbaxxjj2 = = 则则)()()()(112= = = =baxxlbaxx

47、jjjjjj 其中其中)()()()()()()(110110njjjjjjnjjjxxxxxxxxxxxxxxxxxl-=-jkkjxl = =)(2又又)( )()()()( xlxlbaxxalxjjjj = =22 则则)( )()()()( jjjjjjjjjxlxlbaxxalx = =22 )()( )(202= = jjjxlbaxa由（由（1）（）（2）)( )( jjjjjxlxbxla212 = =- -= =得得所以所以 )()( )()(xlxlxxxjjjjj221- - -= = 其中其中)ln()ln()ln()(ln110 - - - - - - -= =jj

48、jxxxxxxxl则则 = = = =- -= = - -= =njkkkjjjjnjkkkjxxxlxlxxxl0011)( )()( )()()ln()ln(njjjjjjnxxxxxxxxxx- - - - - - - - -110所以所以)()()(xlxxxxxjnjkkkjjj20121 - - - -= = = = 令令)()()(xldcxxjj2 = = 则则)()()()(102= = = =dcxxldcxxjjjjjj 又又)( )()()()( xlxldcxxclxjjjj = =22 由由122= = = =)( )()()()( jjjjjjjjjxlxldcx

49、xclx 得得jxdc- -= = =1所以所以)()()(xlxxxjjj2- -= = 例例 已知已知,)(,)(,112211010= = = = =xfxfxx,)( ,)( 14510= = =xfxf求三次多项式求三次多项式 满足满足)(xH32133,)( )( )()(= = = = =kxfxHxfxHkkkk)()()(xlxxxxxjnjkkkjjj20121 - - - -= = = = 解解2101100021 - - - - - - -= =xxxxxxxxx)()( 412922121232- - - -= =- - - = =xxxxx)(2010011121

50、- - - - - - -= =xxxxxxxxx)()( 512921221232 - - - -= =- - - -= =xxxxx)(210100 - - - -= =xxxxxxx)()( )()()(xlxxxjjj2- -= = 48521232- - - -= =- - -= =xxxxx)(201011 - - - -= =xxxxxxx)()( 25412232- - - -= =- - -= =xxxxx)(12145112310103- - = = = =xxxxxxxH)()()()()( 所以所以验证：验证：14251112213333= = = = =)( ,)(

51、,)(,)(HHHH练习练习：（：（ P43（19）求四次多项式求四次多项式 满足满足,)(,)( )(,)( )(12111000= = = = = =PPPPPxxxxxxxL23212021021012022 - -= =- - - - - - - - - -= =)()()()()()(xP令令)()()(212322- - - - -= =xxxbaxxxxP解：解：在点在点0，1，2上做上做Lagrange插值函数插值函数)()()()( 212123- - - - - - - -= =xxbaxxxaxxxP)()()()(12- - - - xxbaxxxbax则则411123

52、11= = =- - - -= =abaP)()( 因此因此43021230- -= = =- - - = =bbP)()( )()(2143412322- - - - - - -= =xxxxxxxP)96(41234xxx-=所以所以4 分段低次插值分段低次插值 Remember what I have said? Increasing the degree of interpolating polynomial will NOT guarantee a good result, since high-degree polynomials are oscillating.例：例：在在- -

53、5, 5上考察上考察 的的Ln(x)。取。取211)(xxf=),., 0(105niinxi= = - -= = -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 n 越大，越大，端点附近抖动端点附近抖动越大，称为越大，称为Runge 现象现象Ln(x) f (x) 分段分段低次低次插值插值 分段线性插值分段线性插值 在每个区间在每个区间 上，用上，用1阶多项式阶多项式 (直线直线) 逼近逼近 f (x):,1 iixx11111)()( - - - - - -= = iiiiiiiiyxxxxyxxxxxPxf,for 1 iixxx记记

54、，易证：当，易证：当 时，时，|max1iixxh- -= = 0h)()(1xfxPh一致一致失去了原函数的光滑性。失去了原函数的光滑性。 分段分段Hermite插值插值 /* Hermite piecewise polynomials */给定给定nnnyyyyxx ,.,;,.,;,.,000在在 上利用两点的上利用两点的 y 及及 y 构造构造3次次Hermite函数函数,1 iixx导数一般不易得到。导数一般不易得到。How can we make a smooth interpolation without asking too much from f ?Headache 2 2、

55、分段线性插值、分段线性插值设函数设函数 在节点：在节点：)(xfy = =bxxxan 10)(,),(),(nxfxfxf10上的函数值为：上的函数值为：kkkkhhxxhmax,= =- -= = 1记步长记步长（1）,)(baCxIh 如果函数如果函数 满足满足)(xIhkkhfxI= =)(（2）1111 - - - - - -= =kkkkkkkkhfxxxxfxxxxxI)(在区间在区间 上上（3）,1 kkxx则称则称 为为分段线性插值分段线性插值)(xIh2= =h步长步长50.= =h步长步长50.= =h步长步长1= =h步长步长x0=-5:0.1:5;x0=-5:0.1:

56、5;y0=1./(1+x0.2); y0=1./(1+x0.2); x=-5:1:5; x=-5:1:5; y=1./(1+x.2);y=1./(1+x.2);y1=interp1(x,y,x0);y1=interp1(x,y,x0);plot(x0,y0,r);plot(x0,y0,r);hold on; hold on; plot(x0,y1,b); plot(x0,y1,b); 1= =h步长步长x0=-5:0.1:5;x0=-5:0.1:5;y0=1./(1+x0.2); y0=1./(1+x0.2); x=-5:1:5; x=-5:1:5; y=1./(1+x.2);y=1./(1+

57、x.2);plot(x0,y0,r);plot(x0,y0,r);hold on; hold on; plot(x,y,b); plot(x,y,b); 3 3、分段、分段HermiteHermite插值插值（1）,)(baCxIh1 如果函数如果函数 满足满足)(xIh)( ,)(kkhkkhfxIfxI= = =（2）已知数表已知数表)( )( )( )()()(nnnnnxfmxfmxfmxfyxfyxfyxxx= = = = = = =1100110010kkkkkkkhfxxxxxxxxxI - - - - - -= = 121121)()(在区间在区间 上上（3）,1 kkxx11

58、12121 - - - - - - kkkkkkkfxxxxxxxx)()(kkkkkfxxxxxx- - - - - 211)(1121 - - - - - kkkkkfxxxxxx)(xIh为分段为分段HermiteHermite插值插值5 5 三次样条三次样条定义定义设设 。三次样条函数三次样条函数 , 且在每个且在每个 上为上为三次多项式三次多项式 。若它同时还满足。若它同时还满足 则称为则称为 f 的的三次样条插值函数三次样条插值函数bxxxan= = = =.10,)(2baCxS ,1 iixx),., 0(),()(nixfxSii= = =注：注：三次样条与分段埃尔米特插值的

59、根本区别在于三次样条与分段埃尔米特插值的根本区别在于S(x)自自身光滑身光滑，不需要知道，不需要知道 f 的导数值（除了在的导数值（除了在2个端点可能需个端点可能需要）；而埃尔米特插值依赖于要）；而埃尔米特插值依赖于f 在所有插值点的导数值。在所有插值点的导数值。f(x)H(x)S(x)2 2、样条函数的求解、样条函数的求解分析：分析：1、区间、区间 上的三次多项式，共需待定系数上的三次多项式，共需待定系数 个。个。n4,1 kkxx,),()(njxfxSjj210= = = 2、已知条件有、已知条件有,),()(12100- -= = = =- -njxSxSjj,),( )( 12100

60、- -= = = =- -njxSxSjj,),( )( 12100- -= = = =- -njxSxSjj 个个1 n 个个1- -n 个个1- -n 个个1- -n共计共计 个个24 - -n（1）补充条件）补充条件)( )( ),( )( nnxfxSxfxS= = =001、边界条件边界条件)( )( ),( )( nnxfxSxfxS= = =002、特别特别00= = =)( )( nxSxS称自然边界条件称自然边界条件3、 周期性条件（略）周期性条件（略）（2）三转角方程）三转角方程),()( njmxSjj10= = =假定假定在区间在区间 上的上的HermiteHermit