_三次样条插值1

1、三次样条三次样条插值插值 我们知道我们知道, ,给定给定n+1+1个节点上的函数值可以作个节点上的函数值可以作n次次插插值多项式值多项式, ,但当但当n较大时较大时, ,高次高次插值不仅计算复杂插值不仅计算复杂, ,而且可而且可能出现能出现Runge现象现象, ,采用分段插值虽然计算简单、也有采用分段插值虽然计算简单、也有一致收敛性一致收敛性, ,但不能保证整条曲线在连接点处的但不能保证整条曲线在连接点处的光滑性光滑性, ,如分段线性插值如分段线性插值, ,其图形是其图形是锯齿形的折线锯齿形的折线, ,虽然连续虽然连续, ,但但处都是处都是“尖点尖点”, ,因而一阶导数都不存在因而一阶导数都不

2、存在, ,这在实用上这在实用上, ,往往不能满足某些工程技术的高精度要求。如在往往不能满足某些工程技术的高精度要求。如在船体、船体、飞机等外形曲线的设计中飞机等外形曲线的设计中, ,不仅要求曲线连续不仅要求曲线连续, ,而且要有而且要有二阶光滑度二阶光滑度, ,即有连续的二阶导数即有连续的二阶导数。这就要求分段插值。这就要求分段插值函数在整个区间上具有连续的二阶导数。因此有必要寻函数在整个区间上具有连续的二阶导数。因此有必要寻求一种新的插值方法求一种新的插值方法, ,这就是样条函数插值法这就是样条函数插值法 2.5.1 2.5.1 三次样条函数三次样条函数 定义定义5.4 5.4 .设函数定义

3、在区间设函数定义在区间 a a, b b 上，给定上，给定n+1n+1个个 节点和一组与之对应的函数值，若函数节点和一组与之对应的函数值，若函数 满足满足: : （1 1）在每个节点上满足）在每个节点上满足 S( S(xi i)=)=f( (xi i)(i=0,1,n)(i=0,1,n) （2 2）在）在 a a, b b 上有连续的二阶导数上有连续的二阶导数 （3 3）在每个小区间）在每个小区间 xi i, ,xi+1i+1 (i=0,1,n-1)(i=0,1,n-1) 上是一个三次多项式。上是一个三次多项式。 则称则称S(S(x) )为为三次样条插值函数三次样条插值函数。 其中四个待定系数

4、为其中四个待定系数为 , ,子区间共有子区间共有n个个所以要确定所以要确定S(S(x) )需要需要4n个待定系数。个待定系数。 另一方面另一方面, ,要求分段三次多项式要求分段三次多项式S(S(x) )及其导数及其导数和和 在整个插值区间在整个插值区间 a,ba,b 上连续上连续, ,则要求它们在则要求它们在各个子区间的连接点各个子区间的连接点 上连续，上连续，即满足条件即满足条件 三次样条插值函数三次样条插值函数S(S(x) )是一个分段三次多项式是一个分段三次多项式, ,要求出要求出S(S(x),),在每个小区间在每个小区间 xi i, ,xi+1i+1 上要确定上要确定4 4个待定参数个

5、待定参数, ,若用若用S Si( (x) )表示它在第表示它在第i个子区间个子区间 xi i, ,xi+1i+1 上的表达式，则上的表达式，则332210)(xaxaxaaxSiiiii1, 1 , 0ni3210,iiiiaaaa)(xS)(xS 110,nxxx（1 1） 插值条件插值条件 （2 2） 连接条件连接条件 上述二式共给出了上述二式共给出了4 4n-2n-2个条件个条件, ,而待定系数有而待定系数有4 4n n个个, ,因此因此还需要还需要2 2个条件才能确定个条件才能确定S(x),S(x),通常在区间端点上通常在区间端点上 各加一个条件各加一个条件, ,称为称为边界条件边界条

6、件, 常用边常用边界条件有三种类型。界条件有三种类型。)()(iixfxSni, 1 , 0) 0() 0(1, 2 , 1) 0() 0() 0() 0( iiiiiixSxSnixSxSxSxSnxbxa,0第一种类型：给定两端点第一种类型：给定两端点f(x)的一阶导数值：的一阶导数值： 第二种类型：给定两端点第二种类型：给定两端点f(x)的二阶导数值：的二阶导数值：作为特例作为特例, , 称为称为自然边界条件自然边界条件。满。满足自然边界条件的三次样条插值函数称为足自然边界条件的三次样条插值函数称为自然样自然样条插值函数。条插值函数。 第三种类型：当第三种类型：当f(x)是以为是以为 周

7、期的函数时，周期的函数时，则要求则要求S(x)S(x)也是周期函数也是周期函数, ,这时边界条件应满足这时边界条件应满足当当 时，时， )()(),()(00nnxfxSxfxS)()(),()(00nnxfxSxfxS 0)()(0 nxSxS0 xxn)()(0nxfxf)()(),()(00nnxSxSxSxS 这样，由上给定的任一种边界条件加上插值条件这样，由上给定的任一种边界条件加上插值条件和连接条件，就能得出和连接条件，就能得出4n个方程，可以惟一确个方程，可以惟一确定定4n个系数。从而得到三次样条插值函数个系数。从而得到三次样条插值函数S(x)S(x)在各个子区间在各个子区间 x

8、i , xi+1 上的表达式上的表达式S(S(xi）( (i=1,2,)i=1,2,)。但是，这种做法当但是，这种做法当n较大时，计较大时，计算工作很大，不便于实际应用。因此我们希望找算工作很大，不便于实际应用。因此我们希望找到一种简单的构造方法。到一种简单的构造方法。 2.5.2 2.5.2 三次样条插值函数的求法三次样条插值函数的求法设设S(x)S(x)在节点在节点x xi i处的二阶导数为处的二阶导数为因为在子区间因为在子区间 x xi-1i-1,x,xi i 上上 是三次多项是三次多项式式, ,所以所以 在此小区间上是在此小区间上是x x的线性函数的线性函数, ,且因为且因为, ,用线

9、性插值用线性插值, ,可知其表达式为可知其表达式为), 1 , 0()(niMxSii )()(xSxSi)(xS iiiiMxSMxS )(,)(11iixxx,11iiixxh1111)( iiiiiiiiixxxxMxxxxMxS记记 ，则有，则有iiiiiiihxxMhxxMxS11)( 其中其中, ,A Ai i,B,Bi i为积分常数为积分常数, ,可利用插值条件可利用插值条件 确定确定, ,即要求即要求A Ai i,B,Bi i满足满足并记并记 ，则得，则得)()(6)(6)()(13131iiiiiiiiiiixxBxxAhxxMhxxMxS)()(),()(11iiiixfx

10、SxfxS)(61)(),(61)(21211iiiiiiiiiiiixfhBhMxSxfhAhMxSiiiiyxfyxf)(,)(112211611,611iiiiiiiiiihMyhBhMyhA连续两次积分得连续两次积分得(5.31)将其代入（将其代入（5.315.31）即得）即得 iiiiiiihxxMhxxMxS6)(6)()(3131iiiiiiiiiihxxhMyhxxhMy)(6)(612211（5.32） ),2, 1,(1nixxxii由上讨论可知由上讨论可知, ,只要确定只要确定 这这n+1n+1个值个值, , 就就可定出三样条插值函数可定出三样条插值函数S(x)S(x)。

11、 为了求出为了求出 , ,利用一阶导数在子区利用一阶导数在子区间连接点上连续的条件间连接点上连续的条件对式对式(5.32)(5.32)求导一次求导一次, ,得在区间得在区间 x xi-1i-1,x,xi i 上的表达式为上的表达式为 nMMM,10), 1 ,0(niMi)0()0(iixSxS)(62)(2)()(112121iiiiiiiiiiiiiMMhhyyhxxMhxxMxS（5.33） 也就是在右端点也就是在右端点x xi i上有上有 iiiiiiiiiihyyMMhMhxS11)(62)0(iiiiiiihyyMhMh1136在左端点在左端点x xi-1i-1上有上有 iiiii

12、iiiiihyyMMhMhxS1111)(62) 0(iiiiiiihyyMhMh1163将上式中的将上式中的i-1i-1改为改为i,i,即得在子区间即得在子区间 x xi i,x,xi+1i+1 上的表上的表达式达式 , ,并由此得并由此得 )(1xSi) 0(1iixS1111163iiiiiiihyyMhMh利用利用 在内接点的连续性在内接点的连续性, ,即即就可得到关于参数就可得到关于参数 的一个方程的一个方程)(xS)0()0(1iiiixSxS11,iiiMMMiiiiiiiiiiiiihyyhyyMhMhhMh1111111636（5.34） ) 1, 2 , 1(ni上式两边同

13、乘以上式两边同乘以 , ,即得方程即得方程 16iihhiiiiiiiiiiiiiiiiihyyhyyhhMhhhMMhhh111 11 111 162iiiiiiiiiiiiiiiixxfxxfhhghhhhhh,61111111若记若记 （5.35） 则所得方程可简写成则所得方程可简写成 iiiiiigMMM112)1,2, 1(ni11121232212121101222nnnnnngMMMgMMMgMMM（5.365.36） 即即 这是一个含有这是一个含有n+1n+1个未知数、个未知数、n-1n-1个方程的线性方程个方程的线性方程组组. .要完全确定要完全确定 的值还需要补充两个的值还

14、需要补充两个条件条件, ,这两个条件通常根据实际问题的需要，根据插这两个条件通常根据实际问题的需要，根据插值区间值区间 a,ba,b 的两个端点处的边界条件来补充。边界的两个端点处的边界条件来补充。边界条件的种类很多，常见的有以下条件的种类很多，常见的有以下3 3种：种： ), 1 ,0(niMi第一种边界条件：即已知插值区间两端的一阶导数值：第一种边界条件：即已知插值区间两端的一阶导数值： 则可得到包含则可得到包含M Mi i的两个线性方程的两个线性方程, ,由由(5.33)(5.33)知知, ,S(x)S(x)在子在子区间区间 上的导数为上的导数为)()(),()(00nnxfxSxfxS

15、10, xx)(62)(2)()(011101120112101MMhhyyhxxMhxxMxS由条件由条件 得得 000)()(yxfxS)(62011101100MMhhyyhMy)(620101110yhyyhMM即即 (5.37) (5.37) 同理同理, ,由条件由条件 得得 nnnyxfxS)()()(6211nnnnnnnhyyyhMM(5.38)(5.38) 将式（将式（5.365.36）和式（）和式（5.375.37）以及式（）以及式（5.385.38）合在一起）合在一起即得确定即得确定 的线性方程组的线性方程组 nMMM,10nnnnnnggggMMMM1101101111

16、212212(5.39) (5.39) ),(6),(6101010nnnnnxxfyhgyxxfhg其中其中第二种边界条件第二种边界条件: :即已知插值区间两端的二阶导数值即已知插值区间两端的二阶导数值: : , ,由于在区间端点处二阶导数由于在区间端点处二阶导数 ，所以方程（，所以方程（5.365.36）中实际上只包含有）中实际上只包含有n-1n-1个未知数个未知数 ，从而得方程组，从而得方程组 nnyxSyxS )(,)(00nnyMyM ,00121,nMMM nnnnnnnnnygggygMMMM112201112211222212222(5.40)(5.40) 第三种边界条件第三种

17、边界条件: :由由 与与 ，可得，可得 和和 )0()0(0 nxSxS)0()0(0nxSxSnMM0nnnnngMMM211),(61110111nnnnnnnnnnnxxfxxfhhghhhhhh(5.41) (5.41) (5.42) (5.42) (5.43) (5.43) 其中其中将式将式 ( 5.36 ), ( 5.41 ), ( 5.42 )合在一起，即得关于合在一起，即得关于 的线性方程组。的线性方程组。 nMMM,21nnnnnnnnggggMMMM1211211122112222(5.44)(5.44) 利用线性代数知识利用线性代数知识, ,可以证明方程组（可以证明方程组

18、（5.395.39）, ,（5.405.40）和（）和（5.445.44）的系数矩阵都是非奇异的，因此有）的系数矩阵都是非奇异的，因此有惟一解。惟一解。 例例2.20 2.20 已知的函数值如下：已知的函数值如下： x 1 2 4 5 x 1 2 4 5 f (x) 1 3 4 2 f (x) 1 3 4 2在区间在区间 1,51,5 上求三次样条插值函数上求三次样条插值函数S(x),S(x),使它满足边使它满足边界条件界条件 0)5(, 0) 1 ( SS解解: :这是在第二种边界条件下的插值问题，故确定这是在第二种边界条件下的插值问题，故确定 的方程组形如（的方程组形如（5.405.40）

19、所示，）所示， 由已知边界条件由已知边界条件, ,有有 则得求解则得求解 的方程组为的方程组为 3210,MMMM0)(, 0)(333000 MyxSMyxS21,MM21212122ggMM根据给定数据和边界条件算出根据给定数据和边界条件算出 与与 ii,ig121321hhh2,21,2,322110 xxfxxfxxf32,3232222121hhhhhh3)221(36),(61021211xxfxxfhhg5)212(36),(62132322xxfxxfhhg523233222121MMMM则得方程组则得方程组 解得解得 49,4321MM又又 030 MM即得即得S(x)S(x

20、)在各子区间上的表达式在各子区间上的表达式, ,由式（由式（5.325.32）知）知, ,S(x)S(x)在在 上的表达式为上的表达式为代入式代入式(5.32)(5.32)3,2,1)(ixSi10, xx1301131016)(6)()(hxxMhxxMxS102111112100)(6)(6hxxhMyhxxhMy将将 代入上式化简后得代入上式化简后得 43, 0, 1, 3, 1, 2, 11011010MMhyyxx1478381)(231xxxxS同理同理S(x)S(x)在在 上的表达式为上的表达式为 21, xx1478381)(232xxxxSS(x)S(x)在在 上的表达式为上

21、的表达式为 32, xx1949184583)(233xxxxS故所求的三次样条插值函数故所求的三次样条插值函数S(x)S(x)在区间在区间上的表达式为上的表达式为 5,1)54(1949184583)42(1478381)21 (1478381)(232323xxxxxxxxxxxxxS 用三次样条函数用三次样条函数S(x)S(x)逼近逼近f(x)f(x)是收敛的是收敛的, ,并并且也是数值稳定的，但其误差估计与收敛定理的且也是数值稳定的，但其误差估计与收敛定理的证明都比较复杂，这里只给出结论。证明都比较复杂，这里只给出结论。 定理定理5 5设设f(x)f(x)是是 a,ba,b 上二次连续

22、可微函数上二次连续可微函数, ,在在 a,ba,b 上上, ,以以 为节点的三次为节点的三次样条插值函数样条插值函数S(x)S(x)满足满足，其中，其中 证明证明 （略）（略） bxxxan1012max2)()(iiixxMxSxf)(max2xfMbxa 三、误差界与收敛性三、误差界与收敛性.83,241,3845(7.17) . 2 , 1 , 0 ,| )(|max| )()(|max),1, 1 , 0(,max ,)( , ,)( 42104)4()()(1104CCCkhxfCxsxfnixxhhhxSbaCxfkbxakkkbxaiiiini其中则有估计式令件满足第一或第二边界

23、条设定定理理 用三次样条绘制的曲线不仅有很好的光滑度用三次样条绘制的曲线不仅有很好的光滑度，而且当节点逐渐加密时，其函数值在整体上能，而且当节点逐渐加密时，其函数值在整体上能很好地逼近被插函数，相应的导数值也收敛于被很好地逼近被插函数，相应的导数值也收敛于被插函数的导数，插函数的导数，不会发生龙格现象不会发生龙格现象。因此三次样。因此三次样条在计算机辅助设计中有广泛的应用。条在计算机辅助设计中有广泛的应用。本章小结本章小结 本章介绍的插值法是实用性很强的方法。它们解本章介绍的插值法是实用性很强的方法。它们解决的实际问题虽然各式各样，但抽象为数学问题却有它决的实际问题虽然各式各样，但抽象为数学问

24、题却有它的共性，即利用已知的数据去寻求某个较为简单的函数的共性，即利用已知的数据去寻求某个较为简单的函数P(x)P(x)来逼近来逼近f(x)f(x)。插值法给出了寻求这种近似函数的原插值法给出了寻求这种近似函数的原则，以及构造近似函数的几种具体方法。插值法要求近则，以及构造近似函数的几种具体方法。插值法要求近似函数在已知的数据点必须与似函数在已知的数据点必须与f(x)f(x)完全一致，。完全一致，。 插值法中的拉格朗日插值多项式是研究数值微积插值法中的拉格朗日插值多项式是研究数值微积分与微分方程数值解的重要工具。牛顿插值多项式是拉分与微分方程数值解的重要工具。牛顿插值多项式是拉格朗日插值多项式

25、的变形，具有承袭性，比拉格朗日插格朗日插值多项式的变形，具有承袭性，比拉格朗日插值多项式节省计算量。分段低次多项式插值由于具有良值多项式节省计算量。分段低次多项式插值由于具有良好的稳定性与收敛性，且算法简单，便于应用。特别是好的稳定性与收敛性，且算法简单，便于应用。特别是应用广泛的三次样条插值，不但有较好的稳定性和收敛应用广泛的三次样条插值，不但有较好的稳定性和收敛性，而且具有较好的光滑性，从而满足了许多实际问题性，而且具有较好的光滑性，从而满足了许多实际问题的要求。需对样条函数作进一步了解的读者可参阅有关的要求。需对样条函数作进一步了解的读者可参阅有关文献文献 许多实际问题不但要求插值函数许

26、多实际问题不但要求插值函数p(x)在插值节点在插值节点处与被插函数处与被插函数f(x)有相同的函数值有相同的函数值p(xi)=f(xi) (i=0,1,2,n), 而且要求在有些节点或全部节点上而且要求在有些节点或全部节点上与与f(x)的导数值也相等，甚至要求高阶导数值也相的导数值也相等，甚至要求高阶导数值也相等，能满足这种要求的插值问题就称为等，能满足这种要求的插值问题就称为 bxxxan10)(ixf)(ixf ), 1 , 0()()(),()(nixfxHxfxHiiii上式给出了上式给出了2 2n+2+2个条件，可惟一确定一个次数不超过个条件，可惟一确定一个次数不超过2 2n+1+1

27、的多项式的多项式H2n+1( (x) )，采用类似于求采用类似于求Lagrange插值多插值多项式的基函数方法求埃尔米特项式的基函数方法求埃尔米特( (Hermite) )插值多项式插值多项式H2n+1( (x) ) 次数不超过次数不超过2n+1次的多项式的次的多项式的形式为：形式为： ， H2n+1(x)= H(x), H2n+1(x)=a0+ a1x+ a2x2+ + a2n+1x2n+1由由2n+2个条件来确定个条件来确定2n+2个系数个系数a0, a1, a2, a2n+1显然非常显然非常复杂复杂, 所以要用求所以要用求Lagrange插值多项式的基函数的方法插值多项式的基函数的方法,

28、 求求插值基函数插值基函数 i(x)及及 i(x) (i=0,1,2, ,n)共有共有2n+2个个, 设每一设每一个基函数为次数不超过个基函数为次数不超过2n+1次的多项式，且满足条件次的多项式，且满足条件0)(10)(0)(10)(jiijjijiijjixjijixxjijix(i, j =0,1,2, ,n)HermiteHermite插值多项式可写成插值基函数表示的形式插值多项式可写成插值基函数表示的形式)(0)()()()()()()()()(00012012jnijijninijjijjijnniiinxfxfxfxxfxxHyxyxxH)(0)(00)()()()()()()()

29、()()()()(0000012012jjniijnijjininijjinijjijjijnniiinxfxfxfxxfxxfxxfxxHyxyxxH 验证：验证：)()()()()(1)( 21)(0220012jnjjjjjnjnjkkkjjnxfxlxxxfxlxxxxxH)(1)(21)(20 xlxxxxxjnjkkkjjj)()()(2xlxxxjjj根据插值条件可求出根据插值条件可求出 和和)(xj),1 , 0)(njxjH2n+1( (x) )为满足条件为满足条件的的2 2n+1+1次次Hermite插值多项式。插值多项式。 ), 1 , 0()()(),()(nixfxH

30、xfxHiiii定理定理5.3 5.3 满足插值条件满足插值条件 的的HermiteHermite插值多项式是惟一的。插值多项式是惟一的。证证: : 设设 和和 都满足上述插值条件都满足上述插值条件, ,令令则每个节点则每个节点 均为均为 的二重根的二重根, ,即即有有2 2n+2+2个根，但个根，但 是不高于是不高于2 2n+1+1次的多项式次的多项式，所以，所以 ，即，即 惟一性得证。惟一性得证。 ), 1 , 0()()(),()(nixfxHxfxHiiii)(12xHn)(12xHn)()()(1212xHxHxnn), 1 , 0(nkxk)(x)(x)(x0)(x)()(1212xHxHnn定理定理5.4 5.4 若若f( (x) )在在 a, ,b 上存在上存在2 2n+2+2阶导数，则阶导数，则 2 2n+1+1次次Hermite插值多项式的余项为插值多项式的余项为 )()!22()()()()(2)22(1212xnfxHxfxRnnn)()()(10nxxxxxxx),( ba其中其中定理的证明可仿照定理的证明可仿照LagrangeLagrange插值余项的证明方插值余项的证明方法请同学们自行证明法请同学们自行证明 实际中使用最广泛的是三次