函数的插值法

1、北京科技大学数理学院北京科技大学数理学院 卫宏儒卫宏儒计算方法计算方法分段多项式插值分段多项式插值引言引言 我们已经知道插值有多种方法：我们已经知道插值有多种方法：Lagrange Lagrange 插插值、值、 NewtonNewton插值、插值、Hermit Hermit 插值等多种方式。插值插值等多种方式。插值的目的就是数值逼近的一种手段，而数值逼近，为的目的就是数值逼近的一种手段，而数值逼近，为的是得到一个数学问题的精确解或足够精确的解。的是得到一个数学问题的精确解或足够精确的解。那么，是否那么，是否插值多项式的次数越高，越能够达到这插值多项式的次数越高，越能够达到这个目的呢个目的呢？

2、现在，我们来讨论一下这个问题。？现在，我们来讨论一下这个问题。 我们已经知道：我们已经知道：f(x)f(x)在在n+1n+1个节点个节点x xi i(i=0(i=0，1 1，2 2，n) n) 上的上的n n次插值多项式次插值多项式Ln (x) Ln (x) 的余项为的余项为 (1)1( )( )( )( )(1)!nnnfR xf xL xxn 设想当节点数增多时会出现什么情况。由插值余项可知，当由插值余项可知，当f(x)充分光滑时，余项随充分光滑时，余项随n增大增大而趋于而趋于0的，这说明可用增加节的，这说明可用增加节点的方法达到这个目的，那么实点的方法达到这个目的，那么实际是这样吗？际是

3、这样吗？ 1901 1901年龙格年龙格(Runge) (Runge) 给出一个例子给出一个例子: : 定义在区间定义在区间-1-1，11上，这是一个上，这是一个光滑函数，它的任意阶导数都存在，对光滑函数，它的任意阶导数都存在，对它在它在-1-1，11上作等距节点插值时，插上作等距节点插值时，插值多项式情况，见图值多项式情况，见图: :22511xxf )( 从图中，可见，在靠近从图中，可见，在靠近-1或或1时，余项会随时，余项会随n值增大而增大，如值增大而增大，如P12(0.96)=36!但但f(0.96)=0.25 从图中，还可看见，在从图中，还可看见，在0附近插附近插值效果是好的，即余项

4、较小，另一值效果是好的，即余项较小，另一种现象是插值多项式随节点增多而种现象是插值多项式随节点增多而振动更多。振动更多。 这种插值多项式当节点增加时这种插值多项式当节点增加时反而不能更好地接近被插之数的现反而不能更好地接近被插之数的现象，称为象，称为龙格现象龙格现象。 这个任意阶可导的光滑函数之所以出这个任意阶可导的光滑函数之所以出现这种现象，跟它在复平面上有现这种现象，跟它在复平面上有x=x=1/51/5是是奇点有关。奇点有关。 俄罗斯数学家伯恩斯坦在俄罗斯数学家伯恩斯坦在19161916年还给年还给出如下定理：出如下定理：定理：定理：函数函数f(x)=|x|f(x)=|x|在在-1-1，1

5、1上取上取n+1n+1个个等距节点等距节点x x0 0=-1, x=-1, xn n=1,=1,构造构造n n次插值多项式次插值多项式L Ln n (x)(x)，当，当n n增大时，除了增大时，除了-1-1，0 0，1 1，三点，三点外，在外，在-1-1，11中任何点处中任何点处L Ln n(x)(x)都不收敛都不收敛于于|x|x|。 上述现象和定理，告诉我们用高上述现象和定理，告诉我们用高次插值多项式是不妥当的，从数值计次插值多项式是不妥当的，从数值计算上可解释为高次插值多项式的计算算上可解释为高次插值多项式的计算会带来舍入误差的增大，从而引起计会带来舍入误差的增大，从而引起计算失真。因此，

6、实践上作插值时一般算失真。因此，实践上作插值时一般只用一次、二次最多用三次插值多项只用一次、二次最多用三次插值多项式。式。 那么如何提高插值精度呢？采用那么如何提高插值精度呢？采用分段插值分段插值是一种办法。是一种办法。 设设f(x)是定义在是定义在a,b上的函数，在上的函数，在a,b上节点上节点 a= x0 x1x2xn-1xn=b,的函数值为的函数值为 y0 , y1 ,y2 ,yn-1 ,yn ,若函数若函数 (x)满足满足条件条件 (1) (x)在区间在区间a , b上连续上连续; (2) (x)在每个子区间在每个子区间xi , xi+1(i=0,1,2,n-1)上是上是次数为次数为m

7、的多项式的多项式; 则称则称 (x)是是f(x)在在a ,b上的上的分段分段m m次插值多项式。次插值多项式。 m=1称为分段线性插值称为分段线性插值 m=2称为分段抛物线插值称为分段抛物线插值定义：分段线性插值的构造分段线性插值的构造： 由定义，由定义， (x)在每个子区间在每个子区间xi , xi+1(i=0,1,2,n-1)上是一次插值多上是一次插值多项式项式;分段线性插值的余项：分段线性插值的余项：定理：定理：设设f(x)在在a,b上有二阶连续导数上有二阶连续导数f(x) ，且，且| f(x)| m2,记：记： h = max |xi+1-xi|,就有估计：就有估计： |f(x)- (

8、x) |=|R(x)| m2h2/8， xa, b。注意到注意到h随分段增多而减少，因此用分段法提高精度是很好的途径随分段增多而减少，因此用分段法提高精度是很好的途径.证明：证明：由由Lagrange 余项公式，当余项公式，当xxi, xi+1时时 |f(x)- (x) |=|R(x)| = |f( )(x-xi)(x- xi+1 )|/2! m2max |(x-xi)(x- xi+1 )|/ 2m2h2/8，上式右端与小区间的位置无关，证毕。上式右端与小区间的位置无关，证毕。11111 iiiiiiiiiixxxxxxxyxxxxyx,)(分段线性插值曲线图：分段线性插值曲线图：例：设例：设

9、 -1 x 1 (1)将将-1，1 10 等份，用分段线性插值近似计算等份，用分段线性插值近似计算f(-0.96)。 (2)将将-1，1 n 等份，用分段线性插值近似计算等份，用分段线性插值近似计算,问如何选择问如何选择步长步长h可使近似计算误差可使近似计算误差R10-4?解：解：(1)插值节点为插值节点为xi=-1+ i/5 (i=0,1,10),h=1/5因为因为 -0.96-1,-0.8,取此区间为线性插值区间，其上的插值取此区间为线性插值区间，其上的插值函数为函数为所以f(-0.96) (-0.96)=0.0425322511xxf )(801129410801923020180208

10、01.)(.).(.).(.)()( xxxxfxfx(2)插值节点为插值节点为xi=-1+ ih (i=0,1,n),h=(b-a)/2=2/n由分段线性插值的余项估计：由分段线性插值的余项估计： |f(x)- (x) |=|R(x)| m2h2/8002801051210025117550251504211232222.)()(max|)(|)(|)()( hhxRxfmxxxfxxxfx 分段二次插值分段二次插值即：选取跟节点即：选取跟节点x最近的三个节最近的三个节点点xi-1,xi, xi+1进行二次插值，即在区间进行二次插值，即在区间xi-1, xi+1，取：取： 这种分段的低次插值

11、叫分段二次插值，在几这种分段的低次插值叫分段二次插值，在几何上就是用分段抛物线代替何上就是用分段抛物线代替y=f(x)y=f(x)，故分段二次，故分段二次插值又和分段抛物插值。插值又和分段抛物插值。 11112iikikjijikjikxxxxyxLxf)()()()( 实际上，上面介绍的分段低次插值，实际上，上面介绍的分段低次插值，虽然具有计算简便，收敛性有保证，数值虽然具有计算简便，收敛性有保证，数值稳定性又好且易在计算机上实现等优点，稳定性又好且易在计算机上实现等优点，但它却不能保证整条曲线的光滑性，从而但它却不能保证整条曲线的光滑性，从而不能满足某些工程技术上的要求，从六十不能满足某些

12、工程技术上的要求，从六十年代开始，首先由于航空、造船等工程设年代开始，首先由于航空、造船等工程设计的需要而发展起来的样条插值（计的需要而发展起来的样条插值（spline)spline)方法，既保留了分段低次插值的各种优点，方法，既保留了分段低次插值的各种优点，又提高了插值函数的光滑性，在许多领域又提高了插值函数的光滑性，在许多领域显得越来越广泛的应用。显得越来越广泛的应用。样条插值样条插值 分段插值存在着一个缺点分段插值存在着一个缺点,就是会导致插值函数就是会导致插值函数在子区间的端点在子区间的端点(衔接处衔接处)不光滑不光滑,即导数不连续即导数不连续,对于对于一些实际问题一些实际问题,不但要

13、求一阶导数连续不但要求一阶导数连续,而且要求二阶而且要求二阶导数连续。为了满足这些要求导数连续。为了满足这些要求,人们引入了人们引入了样条插值样条插值的概念。的概念。 所谓所谓“样条样条”(SPLINE)是工程绘图中的一种工是工程绘图中的一种工具具,它是有弹性的细长木条它是有弹性的细长木条,绘图时绘图时,用细木条连接相用细木条连接相近的几个结点近的几个结点,然后再进行拼接然后再进行拼接,连接全部结点连接全部结点,使之使之成为一条光滑曲线成为一条光滑曲线,且在且在结点处具有连续的曲率结点处具有连续的曲率。样。样条函数就是对这样的曲线进行数学模拟得到的。它条函数就是对这样的曲线进行数学模拟得到的。

14、它除了要求给出各个结点处的函数值外除了要求给出各个结点处的函数值外,只需提供两个只需提供两个边界点处导数信息边界点处导数信息,便可满足对光滑性的不同要求。便可满足对光滑性的不同要求。一、样条函数的定义一、样条函数的定义 设设f(x)是区间在是区间在a,b上的一个连续可微函数上的一个连续可微函数,在区间在区间a,b上给定一组基点上给定一组基点: a=x0 x1x2xn=b设函数设函数s(x)满足条件满足条件 (1) s(x)在每个子区间在每个子区间xi , xi+1(i=0,1,2,n-1)上是次上是次数不超过数不超过m的多项式的多项式; (2) s(x)在区间在区间a , b上有上有m-1阶连

15、续导数阶连续导数; 则称则称s(x)是定义在是定义在a ,b上的上的m m次样条函数次样条函数。x0，x1，x2, 称为称为样条结点样条结点,其中其中x1,xn-1称为称为内结点内结点, , x0 , xn 称为称为边界结点边界结点。当。当m=3时时, ,便成为最常用的便成为最常用的三次样条函数三次样条函数。 二、二、三次样条插值函数三次样条插值函数 设设y = f(x)在点在点 x0，x1，x2, xn的值为的值为y0，y1，y2, yn，若函数若函数S(x)满足下列条件满足下列条件 S(xi)=f(xi) =yi , i=0,1,2,n (1.1) 则称则称S(x)为函数为函数f(x)的的

16、三次样条插值函数三次样条插值函数, 简称简称三次样条三次样条。 构造三次样条插值函数的方法有很多，这里介绍一个常用构造三次样条插值函数的方法有很多，这里介绍一个常用的方法：的方法：三弯矩插值法三弯矩插值法 记记Mi = S(xi), f(xi)= fi= = yi , ,考虑它在任一考虑它在任一区间区间xi, ,xi+1上的上的形式形式.根据三次样条的定义可知根据三次样条的定义可知 ,S(x)S(x)的二阶导数的二阶导数S(x)S(x)在每一个在每一个子区间子区间xxi i,x,xi+1i+1 ( i=0,1,2, ( i=0,1,2,n-1),n-1)上都是线性函数。上都是线性函数。于是在于

17、是在xi, ,xi+1 上上S(x)=Si(x)的二阶导数表示成的二阶导数表示成 (1.2) 其中其中 hi= xi+1xi . 对对S(x)连续积分两次连续积分两次,并利用插值条件并利用插值条件S(xi)= yi ,得到得到 三、三次样条函数的构造三、三次样条函数的构造,)( 111S iiiiiiiixxxhxxMhxxMx x x i , x i+1 S”(x) M i , M i+1 )()()()()(iiiiiiiiiiiiiiiixxhMhyxxhMhyhxxMhxxMx 6666S1113131 因此，只要能求出所有的因此，只要能求出所有的 M M i i ，就能求出样条，就能

18、求出样条插值函数插值函数S(x). S(x). 下面考虑下面考虑M Mi i的求法的求法。,)()()(1112121622S iiiiiiiiiiiiiixxxhMMhyyhxxMhxxMx则由连续性则由连续性 S S (x(xi-i-)= S)= S (x(xi+i+) ,(i=1,2,) ,(i=1,2,n-1) ,n-1) 得得 i iM Mi-1i-1+2M+2Mi i+i iM Mi+1i+1= d= di i 其中其中 1111116)(,iiiiiiiiiiiiihhhyyhyydhhhu 上面的方程组有上面的方程组有n-1n-1个方程，但有个方程，但有n+1n+1个变量个变量

19、M Mi i，故需故需两个方程才能求唯一解，为此引入下列边界条件两个方程才能求唯一解，为此引入下列边界条件：下面介绍几种常用的边界条件下面介绍几种常用的边界条件 第一型边界条件第一型边界条件： 已知已知f(x)在两端点的导数在两端点的导数f(a)和和f(b) ，要求，要求S(a) = f(a) , S(b) = f(b)第二型边界条件第二型边界条件：已知已知f(x)在两端点的二阶导数在两端点的二阶导数f(a)和和f(b) ，要求，要求 S(a)=M0 = f(a) , S(b)=Mn= f(b) 特别当特别当 S(a)= S(b) =0时，时，S(x)称为自然三次样条。称为自然三次样条。 第三

20、型边界条件第三型边界条件： 已知已知f(x)是以是以b -a为周期的周期函数为周期的周期函数 ，要求，要求S(x)满满 足周期条件足周期条件 S (a) = S(b) , S(a+)= S(b-) , S(a+)= S(b-) 三次样条插值问题加上第三次样条插值问题加上第i i型边界条件称为第型边界条件称为第i i型插值问题（型插值问题（i i，）可以证明第，）可以证明第i i型插值问题的解是存在且唯型插值问题的解是存在且唯一的。他们对应如下的三对角方程组：一的。他们对应如下的三对角方程组： 2 0 0 M0 d0 1 1 2 1 M1 d1 . . . . . . . . . = . (*)

21、 . . . . . n-1 n-1 2 n-1 Mn-1 dn-1 n n 2 Mn dn 对于第一型插值问题，取对于第一型插值问题，取 0 0=1=1，n n=1,=1,对于第二型插值问题，取对于第二型插值问题，取0 0=0=0，n n=0=0 对于第三型插值问题，利用周期性，可导出对于第三型插值问题，利用周期性，可导出其中 , nnydyd2200 nnnnnndMMMMM2110)(),(nnnnnnhyyyhdyhyyhd101011066 11110116)(,nnnnnnnnnnhhhyyhyydhhhu 以上各组条件与方程组以上各组条件与方程组(*)联立，可以解出未知参联立，可

22、以解出未知参数数M M0 0，M M1 1 , ,M,Mn n，然后代入，然后代入S(x) S(x) 表达式，即可求表达式，即可求得样条函数得样条函数 。 上面构造方法中上面构造方法中MiMi相应于力学中细梁在相应于力学中细梁在x xi i处截面的处截面的弯矩，每一个方程中又至多出现相邻的三个弯矩，每一个方程中又至多出现相邻的三个M Mi i，通常，通常称为三弯矩法。称为三弯矩法。 总结以上论述，可得求三次样条的步骤为：总结以上论述，可得求三次样条的步骤为：（1 1）确定边界条件，判定是第几型插值问题；）确定边界条件，判定是第几型插值问题；（2 2）根据所确定的条件计算各值，形成方程组）根据所

23、确定的条件计算各值，形成方程组(*)；（3 3）解三对角方程组）解三对角方程组(*)，求得，求得M0， M1 ， M2, Mn ；（4 4）将求得的）将求得的Mi值代回值代回S(x)的表达式中，的表达式中， 从而可求得函数从而可求得函数y=f(x)在任一点的近似值在任一点的近似值S(x)。 四、例题四、例题 例例1 1 已知函数已知函数f(x）的数值表如下：的数值表如下： x x 2 2 4 4 6 6 f(x) 3 3 7 7 13 13 f(x) 1 1 -1 -1 试求试求f(x) 在在2,62,6上的三次样条插值函数。上的三次样条插值函数。解：这是第一类边界条件的问题这是第一类边界条件

24、的问题 ，n=2,hn=2,hi i=h,=h,由公由公式：式： 1 1 =1 =1/2 ，d1 =3/2=3/2； n n =0 =1 ， d0=3,=3,d2=-12=-12 得方程组得方程组 2 2 M0 + + M1 = 3= 3 0.5 0.5 M0 + + 2M1 +0.5+0.5 M2 = 1.5= 1.5 M1 +2+2 M2 = -12= -12解得解得 M0 =0.25 , =0.25 , M1 =2.5 =2.5 M2 = -7.25= -7.25故所求的三次样条插值函数故所求的三次样条插值函数 - (1/48)(x-41/48)(x-4）3 3 + (5/24)(x-2+ (5/24)(x-2）3 3 -(17/12) -(17/12)（x-4x-4）+(8/3)(x-2), x2+(8/3)(x-2), x2，44S(x)=S(x)= - (5/24)(x-65/24)(x-6）3 3 - (29/48)(x-4- (29/48)(x-4）3 3 -(8/3) -(8/3