数值分析 插值法.doc

第二章 插值法在科学研究与工程技术中，常常遇到这样的问题：由实验或测量得到一批离散样点，要求作出一条通过这些点的光滑曲线，以便满足设计要求或进行加工。反映在数学上，即已知函数在一些点上的值，寻求它的分析表达式。此外，一些函数虽有表达式，但因式子复杂，不易计算其值和进行理论分析，也需要构造一个简单函数来近似它。解决这种问题的方法有两类：一类是给出函数的一些样点，选定一个便于计算的函数形式，如多项式、分式线性函数及三角多项式等，要求它通过已知样点，由此确定函数作为的近似，这就是插值法；另一类方法在选定近似函数的形式后，不要求近似函数过已知样点，只要求在某种意义下在这些样点上的总偏差最小。这类方法称为曲线（数据）拟合法。设已知区间上的实值函数在个相异点处的函数值，要求构造一个简单函数作为函数的近似表达式使得 (2-1)这类问题称为插值问题。称为被插值函数；为插值函数；为插值节点；(2-1)为插值条件。若插值函数类是代数多项式，则相应的插值问题为代数插值。若是三角多项式，则相应的插值问题称为三角插值。若是有理分式，则相应的插值问题称为有理插值。1 Lagrange 插值1.1 Lagrange 插值多项式设函数在个相异点上的值是已知的，在次数不超过的多项式集合中，求使得 (2-2)定理1 存在惟一的多项式满足插值条件(2-2)。证明 我们采用构造性的证明方法。假如我们能够构造出次多项式，使得 (2-3)那么 (2-4)是满足插值条件(2-2)的插值多项式。余下的问题就是如何构造出满足式(2-3)的次多项式。由于当时，即是的零点，因此必然具有形式又因，故，因此 (2-5)至于多项式的惟一性是极其简单的事实，只要注意到次多项式且有零点这一事实。公式称为Lagrange 插值公式，相应的称为Lagrange插值多项式，称为节点上的次插值基函数。令，由插值多项式的存在惟一性可得 (2-6)由(2-6)知，任取，那么均可用线性表出。由此看出，就是。在(2-6)中取，则。为了今后的需要，我们引入以下记号 (2-7)容易求得并有，将其代入插值基函数的表达式于是插值公式可写为 (2-8)1.2 插值余项及估计称为Lagrange 插值多项式的余项.定理2 设，且在内存在，是以为插值节点函数的Lagrange插值多项式，则对内的任意点，插值余项为 (2-9)证明 对上任意的点，且，构造辅助函数显然，又由插值条件可知 ，故函数在内至少有个零点。根据罗尔（Rolle）定理，函数在内至少存在个零点，反复应用罗尔（Rolle）定理，可以得出在内至少存在一个零点，设为，即由于所以有 证毕。推论1 设，在上存在，则有 (2-10)其中。证明 对上任意的，可设属于的一个子区间，由此可以得出从而有此不等式与式(2-9)相结合有由此可得到估计式(2-10)。证毕。例1已给, ,用线性插值及拋物线插值计算的值，并估计截断误差。解 由题意取用线性插值计算，取及，由公式(2-4)得其截断误差由(2-9)得其中。因，可取，有用抛物插值计算。由公式(2-4)得有这个结果与6位有效数字的正弦函数表完全一样，这说明用二次插值精度已相当高了.其截断误差限由(2-9)得其中，于是2 均差与Newton插值公式2.1 均差及其性质Lagrange插值公式结构紧凑和形式简单，在理论分析中甚为方便。但Lagrange插值公式也有其缺点，当插值节点增加、减少或其位置变化时，全部插值基函数均要随之变化，从而整个插值公式的结构将发生变化，这在实际计算中是非常不利的。Newton插值公式可以克服这个缺点，定义1 称为关于点的一阶均差。为关于点的二阶均差。一般地，有了阶均差之后，称(2-11)为关于点的阶均差（差商）。均差有如下的基本性质：性质1 各阶均差具有线性性，即若，则对任意正整数，都有性质2 阶均差可表示成的线性组合，即这个性质可用归纳法证明。它也表明均差与节点的排列次序无关，称为均差的对称性。性质3 设，并且，为相异节点，那么的阶均差与其阶导数有如下关系2.2 牛顿插值多项式由各阶均差的定义，依次可得将以上各式分别乘以 ，然后相加并消去两边相等的部分，即得其中(2-12) (2-13)显然，是至多次的多项式。而由即得。这表明满足插值条件(2-2)，因而它是的次插值多项式。这种形式的插值多项式称为Newton插值多项式。Newton插值的优点是：每增加一个节点，插值多项式只增加一项，即因此便于递推运算。而且Newton插值的计算量小于Lagrange插值。由插值多项式的唯一性知，次Newton插值多项式与Lagrange插值多项式是相等的，即，它们只是形式的不同。因此Newton与Lagrange余项也是相等的，即由此可得性质3。式(2-13)表示的余项称为均差型余项。由式(2-9)表示的余项称为微分型余项。作出Newton插值多项式的步骤：1） 列均差表，计算各阶均差一阶二阶n阶12）将以上表中对角线的下划线项与最后一列的同一行的对应项相乘后，相加即可得到Newton插值多项式。例2.1 设，并已知2.02.12.21.4142141.4491381.483240试用二次Newton插值多项式计算的近似值，并讨论其误差。解 构造均差表如下一阶均差二阶均差2.01.4142142.11.4491380.349242.21.4832400.34102利用Newton插值公式(2-12)有取，得。由于在区间上充分光滑，因此可以利用误差估计公式(2-11)，注意到。从而得到的真值为，因此得出。由此看出，在较小区间上用式(1.10)，可得到一个较好估计。例2 给出的函数表2-2，求4次牛顿插值多项式，并由此近似计算。首先根据给定函数表造出均差表。表 2-2一阶二阶三阶四阶五阶0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358930.197330.901.026521.384100.433480.213000.031341.051.253821.515330.524830.228630.03126-0.00012从均差表看到4阶均差近似常数，故取4次插值多项式作近似即可。于是截断误差这说明截断误差很下，可忽略不计。此例的截断误差估计中，5阶均差用近似。另一种方法是取，由，可求得的近似值，从而可得的近似。3 差分与等距节点插值公式前面所讨论的Lagrange插值多项式和用均差表示的Newton插值多项式，其节点可以是不等距的。如果函数在插值区间上变化很剧烈，则采用不等距节点插值多项式更适宜。如果在插值区间上变化平缓，采用等距节点可使插值多项式简化。3.1差分及其性质当节点等距分布时，即相邻两个节点之差（称为步长）为常数，此时关于节点间函数的平均变化率（均差）可用函数值之差（差分）来表示。定义2.2 设函数在等距节点上的值为已知，这里为一常数，称为步长，记号 (2-15) (2-16)(2-17)和分别称为在处以为步长的向前一阶差分、向后一阶差分和中心一阶差分。符号分别称为向前差分操作数，向后差分操作数及中心差分操作数。利用一阶差分可定义二阶差分为一般地，可定义阶差分为并规定，称其为零阶差分。为以后方便起见，再引入常用的操作数符号，称为步长的移位操作数，为单位操作数（也称为不变操作数）。显然,及，下面给出差分的一些基本性质：性质1各阶差分具有线性性，即若，则对任意正整数，有对于操作数具有类似的性质。性质2 各阶差分可表示成函数值的线性组合，例如(2-18)(2-19)(2-20)其中为二项式展开式的系数。性质3 可用各阶均差表示函数值，例如，可用向前差分表示 (2-21)性质4 各种差分之间可以转化 (2-22)性质5 可用差分表示均差，例如 (2-23)性质6 差分与导数之间满足关系 (2-24)由式(2-24)可看出，若是一个次多项式，则它的阶差分为常数。因此，如果一个列表函数的阶差分已接近常数，则用一个次多项式去逼近它是恰当的。3.2等距节点插值公式将Newton插值多项式(2-12)中各阶均差用差分代替，就可得到各种形式的等距节点插值公式。这里我们只推导常用的前插与后插公式。给定等距节点后，要计算附近点的函数值，可令，于是将此式及式(2-23)代入式(2-12)，则得(2-25)此公式称为Newton前插公式。其余项由(2-9)得 (2-26)如果要求函数表示附近的函数值，此时应用牛顿插值公式(2-12)，插值点应按的次序排列，有作变换，并利用公式(2-23)，代入上式得(2-27)此式称为Newton向后插值公式。其余项为 (2-28)注2.1：1通常求开头部分插值点（）附近函数值时使用牛顿前插公式，求插值节点末尾（）附近函数值时使用牛顿后插公式。如果用相同节点进行插值，则向前向后两种公式只是形式上的差别，其计算结果是相同的；2求节点附近的函数值时，由关系 ，同样可表示成向前差分的形式3Newton向后插值公式(2-27)在推导微分方程数值解方面能起到很好的作用。构造Newton向前、向后插值公式的步骤：1）计算各阶差分，见表2.4表2.4一阶二阶三阶n阶1()()()12）将以上表中对角线的下划线项与对应行右端因子乘积求和即得Newton向前插值多项式；Newton向后插值公式则为最后的节点所在行的各阶差分值与对应列下端因子乘积之和。例2.4 已知的函数表如下，分别用牛顿向前、向后插值公式求的近似值。0.40.50.60.70.389420.479430.564640.64422解 取，有。按表2.4计算得一阶差分二阶差分三阶差分0.3894210.479430.090010.564640.08521-0.004800.644220.07958-0.00563-0.000831Newton向前插值公式为将代入上式得由式(2-26)，误差为Newton向后插值公式为将代入上式得查表可得。如果取，用二阶Newton向后插值公式，则得将代入上式，得其误差为例2.5 给出在，处的函数值，试用4次等距节点插值公式计算及的近似值并估计误差。解 构造差分表2.5。用牛顿向前插值公式(2-25)计算的近似值，取，用表2.5上半部差分，得表 2.51.000000.995000.980070.955340.921060.877580.82534-0.00500-0.01493-0.02473-0.03428-0.04348-0.05224-0.00993-0.00980-0.00955-0.00920-0.008760.000130.000250.000350.000440.000120.000100.00009-0.00002-0.00001误差估计由(2-26)可得其中用牛顿向后插值公式(4.12) 计算。，用差分表2.5中下半部差分，得于是，误差估计由(2-28)得其中4 埃尔米特（Hermite）插值如果对插值函数，不仅要求它在节点处与被插值函数取值相同，而且要求它与函数有相同的一阶、二阶甚至更高阶的导数值，这就是Hermite插值问题。本节主要讨论在节点处插值函数与函数的值及一阶导数值均相等的Hermite插值。4.1 重节点均差与泰勒插值先给出一个关于均差的结论（不证）。定理3 设为上的相异节点，则是其变量的连续函数。如果上的节点互异，根据均差定义，若，则有由此定义重节点均差类似地可定义重节点的阶均差为 (4.1)在牛顿均差插值多项式中，若令 ，则由(4.1)式可得泰勒多项式 (4.2)它实际上是在点附近逼近的一个带导数的插值多项式，它满足条件 (4.3)称(4.2)式泰勒插值多项式，它就是一个埃尔米特插值多项式，其余项为 (4.4)它与插值余项(2.12)式中令 的结果一致。实际上，泰勒插值是牛顿插值的极限形式，只是在一点处给出个插值条件(4.3)得到的次埃尔米特插值多项式。一般地只要给出个插值条件（含函数值和导数值）就可造出次数不超过次的埃尔米特插值多项式，给出两个典型的例子。4.2两个典型的埃尔米特插值。例2.6 求满足及的插值多项式及余项表达式。解 按插值条件，所求是一个次数不高于3的多项式，它的曲线过点，,，故可设其中为待定常数。由条件可确定常数，通过计算可得与的误差函数为由于以及，故可设其中为待定函数。为求，引进辅助函数显然。且，故在内有五个零点（二重根算两个）。反复应用罗尔定理，得在内至少有一个零点，故由此可得余项表达式为式中位于和所界定的范围内。另一个典型例子是两点三次Hermite插值，插值节点为及，插值多项式为，满足条件 (4.6)采用构造基函数方法。假设我们能够构造出基函数，满足条件 (4.7)那么多项式便是满足条件(4.6)的插值多项式。余下的问题就是如何构造出插值基函数。由于在处函数值与导数值均为0，故它应含因子，因此可以设由条件(4.7)知，故由此有同理因此节点三次Hermite插值多项式为其插值余项为5 分段低次插值5.1 高次插值的病态性质在代数插值中，为了提高插值多项式对函数的逼近程度，自然希望增加节点个数，即提高插值多项式的次数。特别当时，期望插值多项式收敛于被插值函数。但是，令人遗憾的是事实并非如此。事实上，假设存在任意阶导数，当插值节点增加时，固然使得插值多项式在更多点上与相等，但是在两个插值节点之间不一定能很好地逼近，差异可能很大。在非插值节点上往往出现误差函数先递减，而后随着增加而增加，并且变得无界。当时，插值多项式终于变得发散的一个理由是与的阶导数增长得无界这一事实有关。例如，有 ，对固定的，当增加时呈指数增长。在本世纪初由Runge给出了等距节点的插值多项式不收敛于的例子。例如，对于函数，在区间上取节点，所作Lagrange插值多项式为其中是Lagrange插值基函数。Runge证明了，当时，内收敛到，在这区间之外发散，这一现象称为Runge现象。当时，图给出了和的图形。从图上看到，仅在区间中部能较好地逼近函数，在其它部位差异较大，而且越接近端点，逼近程度越差。它表明通过增加节点来提高逼近程度是不宜的，一般插值多项式的次数在范围内。直观上容易想象，如果不用多项式曲线，而是将曲线的两个相邻的点用线段连接，这样得到的折线必定能较好地近似曲线。而且只要连续，节点越密，近似程度越好。由此得到启发，为提高精度，在加密节点时，可以把节点间分成若干段，分段用低次多项式近似函数，这就是分段插值的思想。用折线近似曲线，相当于分段用线性插值，称为分段线性插值。给定上个节点及节点上的函数值，作一个插值函数，使其满足（1）；（2）在每个小区间上是线性函数。称函数为上关于数据 的分段线性插值函数。由Lagrange线性插值公式容易写出的分段表达式 (2-37)下面定理表明分段线性插值函数一致收敛于被插值函数。定理2.5设，为插值节点，且。是的分段线性插值函数，则当时，一致收敛于。证明 由于，所以在上一致连续，即对，存在，使得当且时，有于是当及时，有设，则一定属于某个子区间，注意到，有由的任意性可知从而证得在上一致成立。如果，则利用插值余项公式，可以得到定理2.6如果在上二阶连续可微，则分段线性插值函数的余项估计是其中。证明 在每个小区间上，是的线性插值，故对任意的，有因为所以。定理2.5-2.6表明，当节点加密时，分段线性插值的误差变小，收敛性有保证。另一方面，在分段线性插值中，每个小区间上的插值函数只依赖于本段的节点值，因而每个节点只影响到节点邻近的一、二个区间，计算过程中数据误差基本上不扩大，从而保证了节点数增加时插值过程的稳定性。但分段线性插值函数仅在区间上连续，一般地，在节点处插值函数不可微，这就不能满足有些工程技术问题的光滑要求。5.2分段三次Hermite插值上段考察的线性插值函数的导数是间断。若在节点上除已知函数值外，还已知导数值，我们可构造一个导数连续的分段插值函数，它满足(1) ;(2) (3) 在每个小区间上是三次多项式。根据两点三次Hermite插值多项式，在每个小区间的表达式是上式对于成立。利用三次Hermite插值多项式的余项，可得误差估计，于是可得下面定理定理2.7设，为在节点上的分段三次Hermite插值多项式，则有其中。6三次样条插值实际工程技术中许多问题不允许在插值节点处一阶和二阶导数的间断，例如高速飞机的机翼外形，内燃机进排气门的凸轮曲线，高速公路以及船体放样等等。以高速飞机的机翼外形来说，飞机的机翼一般尽可能采用流线型，使空气气流沿机翼表面形成平滑的流线，以减少空气阻力。若曲线不充分光滑，如机翼前部，曲线有一个微小的凸凹，就会破坏机翼的流线型，使气流不能沿机翼表面平滑流动，流线在曲线的不甚光滑处与机翼过早分离，产生大量的旋涡，以致使飞机产生震荡，阻力大大增加，飞行速度愈快问题就愈严重。因此，随着飞机向高速度发展的趋势，配置机翼外形曲线的要求也就愈高。解决这类问题用前面讨论的插值方法是显然无法做到的。前面讨论的高次Lagrange（Newton）多项式插值虽然光滑，但不具有收敛性，会产生Runge现象。分段线性插值与分段三次Hermite插值都具有一致收敛性，但光滑性较差。分段线性插值在节点处一阶导数不连续；若采用带一阶和二阶导数的Hermite分段插值，实践中由于事先无法给出（测量）节点处的导数值，也有本质上的困难，这就要求寻找新的方法，它无需事先给定节点上的导数值，而且插值函数二阶导数连续。早期工程上，绘图员为了将一些指定点（称为样点）联结成一条光滑曲线，往往用细长的易弯曲的弹性材料，如易弯曲的木条、柳条及细金属条（绘图员称之为样条，英文为Spline）在样点用压铁固定，样条在自然弹性弯曲下形成的光滑曲线称之为样条曲线。此曲线不仅具有连续一阶导数，而且还具有连续的曲率（即具有二阶连续导数）。从材料力学角度来说，样条曲线相当于集中载荷的挠度曲线，可以证明此曲线是分段的三次曲线，而且它的一阶、二阶导数都是连续的。I. J. Schoenberg（舒恩具格）在1946年把样条曲线引入数学中，构造了所谓“样条函数”的概念。在60年代左右受到广大数学工作者，特别是计算数学工作者的重视，他们不仅对样条函数理论作了很多研究，并且还把样条函数引进到数值分析的各个领域中去，而这种应用取得惊人的效果。这样一来，样条函数就成为现代数值分析中一个十分重要的概念和不可缺少的工具。后来发展了许多样条，如B样条，圆弧样条，三角样条等，内容十分丰富，应用非常广泛。本节我们仅就最常用的三次多项式样条的概念和稳定的计算，以及有关的一些性质，作简单的介绍。6.1三次样条插值函数的概念定义2.3 已知函数在区间上的个节点上的值，求插值函数，使得（1）；（2）在每个小区间上是三次多项式；（3）在上二阶连续可微。函数称为的三次样条插值函数。从定义知要求出，在每个区间上要确定4个待定系数，共有个小区间，故应确定个参数。根据函数一阶及二阶导数在插值节点连续，应满足条件 (2-46)及插值条件。共有个条件，因此还需要2个边界条件作补充才能确定。常见的边界条件是：1）已知两端的一阶导数值，即 (2-47)2）两端的二阶导数已知，即 (2-48)其特殊情况为称为自然边界条件。3）当是以为周期的周期函数时，则要求也是周期函数，这时边界条件应满足(2-49)这样确定的样条函数称为周期样条函数。6.2样条插值函数的建立设在节点处的一阶、二阶导数值分别为，即的表达式通常分两种形式：(1) 用做参数的表达式。这就需要先求，然后才能得到的确定的表达式。在力学上表示细梁在处的弯矩。(2) 用做参数的表达式。这就需要先求，然后才能得到的确定的表达式。在力学上表示细梁在处的转角。以节点处的二阶导数为参数的三次样条插值。设。因为在每个区间上是分段三次多项式，故在上是线性函数，可表示为其中。对积分两次并利用及，可定出积分常数，于是得三次样条表达式 (2-50)这里是未知参数。为了确定它们，对求导得因此 (2-51)用下标取代得到在区间 上的表达式，从而得 (2-52)利用可得, (2-53)其中 方程组含有个未知量，但却只有个方程，因此需要边界条件补充另外的两个方程。对第一型边界条件(2-47)，式(2-51)和(2-52)中的分别取1和，可导出两个方程 (2-54)如果令，那么将式(2-53)与(2-54)联立可得关于参数的阶线性方程组，其矩阵形式为 (2-55)其中对第二型边界条件(2-48)，直接得 (2-56)如果令，则(2-54)和(2-56)也可以写成式(2-55)的形式。对第三型边界条件(2-49)，式(2-51)和(2-52)中的分别取1和，可得从而 (2-57)其中。将方程(2-57)与(2-55)联立，得到阶方程组显然，这三种情形所得到的方程组的系数矩阵均为三对角方程，且是严格主对角占优的。因为。样条函数总结.doc例2.7 已知函数表012327.72829304.14.34.13.0求满足边界条件的三次样条插值函数