数值分析第2章 插值法.doc

第2章 插值法在科学研究与工程技术中，常常遇到这样的问题：由实验或测量得到一批离散样点，要求作出一条通过这些点的光滑曲线，以便满足设计要求或进行加工。反映在数学上，即已知函数在一些点上的值，寻求它的分析表达式。此外，一些函数虽有表达式，但因式子复杂，不易计算其值和进行理论分析，也需要构造一个简单函数来近似它。解决这种问题的方法有两类：一类是给出函数的一些样点，选定一个便于计算的函数形式，如多项式、分式线性函数及三角多项式等，要求它通过已知样点，由此确定函数作为的近似，这就是插值法；另一类方法在选定近似函数的形式后，不要求近似函数过已知样点，只要求在某种意义下在这些样点上的总偏差最小。这类方法称为曲线（数据）拟合法。设已知函数在区间上的个相异点处的函数值，要求构造一个简单函数作为函数的近似表达式，使得 (2-1)这类问题称为插值问题。称为被插值函数；为插值函数；为插值节点；(2-1)为插值条件。若插值函数类是代数多项式，则相应的插值问题为代数插值。若是三角多项式，则相应的插值问题称为三角插值。若是有理分式，则相应的插值问题称为有理插值。1 Lagrange 插值1.1 Lagrange 插值多项式设函数在个相异点上的值是已知的，在次数不超过的多项式集合中，求使得 (2-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.2 设，且在内存在，是以为插值节点函数的Lagrange插值多项，则对内的任意点，插值余项为 (2-9)证明 对上任意的点，且，构造辅助函数显然，又由插值条件可知，故函数在内至少有个零点。根据罗尔（Rolle）定理，函数在内至少存在个零点，反复应用罗尔（Rolle）定理，可以得出在内至少存在一个零点，设为，即由于所以有 推论1 设，在上存在，则有 (2-10)其中。证明 对上任意的，可设属于的一个子区间，由此可以得出从而有此不等式与式(2-9)相结合有由此可得到估计式(2-10)。证毕。算法2.1(1) 输入数据(2) 对，计算(3) (4) 输出，停机。例1 已给，用线性插值及抛物线插值计算的值，并估计截断误差。解 由题意取用线性插值计算，取及，由公式(2-4)得其截断误差由(2-9)得其中。因，可取，有用抛物插值计算时，由公式(2-4)得有这个结果与6位有效数字的正弦函数表完全一样，这说明查表时用二次插值精度已相当高了。其截断误差限由(2-9)得其中，于是2 均差与Newton插值公式2.1 均差及其性质Lagrange插值公式结构紧凑和形式简单，在理论分析中甚为方便。但Lagrange插值公式也有其缺点，当插值节点增加、减少或其位置变化时，全部插值基函数均要随之变化，从而整个插值公式的结构将发生变化，这在实际计算中是非常不利的。Newton插值公式可以克服这个缺点。定义2.1 设有函数，为称为关于点的一阶均差。为关于点的二阶均差。一般地，有了阶均差之后，称 (2-11)为关于点的阶均差（差商）。均差有如下的基本性质：性质1 各阶均差具有线性性，即若，则对任意正整数，都有性质2 阶均差可表示成的线性组合，即这个性质可用归纳法证明。它也表明均差与节点的排列次序无关，称为均差的对称性。性质3 若是次多项式，则一阶均差是次多项式。证明 如果是次多项式，则也是次多项式，且。于是可分解为，其中是次多项式。所以是次多项式。证毕。推论 设是次多项式，则恒等于零。2.2 牛顿插值多项式由各阶均差的定义，依次可得将以上各式分别乘以，然后相加并消去两边相等的部分，即得其中 (2-12) (2-13)显然，是至多次的多项式。而由即得。这表明满足插值条件(2-2)，因而它是的次插值多项式。这种形式的插值多项式称为Newton插值多项式。由插值多项式的唯一性知，次Newton插值多项式与Lagrange插值多项式是相等的，即，它们只是形式的不同。因此Newton与Lagrange余项也是相等的，即由此可得均差与导数的关系 (2-14)其中。由式(2-9)表示的余项称为微分型余项，式(2-13)表示的余项称为均差型余项。对列表函数或高阶导数不存在的函数，其余项可由均差型余项给出。Newton插值的优点是：每增加一个节点，插值多项式只增加一项，即因此便于递推运算。而且Newton插值的计算量小于Lagrange插值。注1：以上推导过程只强调是个不同的节点，并不意味着是按由小到大或由大到小的顺序排列。事实上，按任意大小排列，以上推导成立。作出Newton插值多项式的步骤：1）列表计算各阶均差，如表2-1；表2-1一阶均差二阶均差n阶均差12）将表2-1中下划线对角线项与最后一列的同行对应项相乘后相加，即得Newton插值多项式。算法2.2(1) 输入数据(2) 计算各阶差商。对(3) (4) 输出，停机。例2 设，并已知2.02.12.21.4142141.4491381.483240试用二次Newton插值多项式计算的近似值，并讨论其误差。解 先按均差表2-1对例2构造均差表，具体数据见表2-2表2-2一阶均差二阶均差2.01.4142142.11.4491380.349242.21.4832400.34102利用Newton插值公式(2-12)有取，得。由于在区间上充分光滑，因此可以利用误差估计公式(2-11)。注意到，从而得到的真值为，因此得出。由此看出，在较小区间上用式(2-10)，可得到一个较好估计。例3 给出的函数表2-3，求4次牛顿插值多项式，并由此计算的近似值。首先根据给定函数表造出均差表2-3。表 2.3一阶二阶三阶四阶五阶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)结合式(2-14)，可得差分与导数的关系 (2-24)由式(2-24)可看出，若是一个次多项式，则它的阶差分为常数。因此，如果一个列表函数的阶差分已接近常数，则用一个次多项式去逼近它是恰当的。3.2等距节点插值公式将Newton插值多项式(2-12)中各阶均差用差分代替，就可得到各种形式的等距节点插值公式。这里我们只推导常用的前插与后插公式。给定等距节点后，要计算附近点的函数值，可令，于是将此式及式(2-23)代入式(2-12)，则得 (2-25)此公式称为Newton前插公式。其余项为 (2-26)如果要求函数表示附近的函数值，此时应用牛顿插值公式(2-12)，插值点应按 的次序排列，有作变换，并利用公式(2-23)，代入上式得 (2-27)此式称为Newton向后插值公式。其余项为 (2-28)注2：1用相同节点进行插值，向前向后两种公式只是形式上的差别，其计算结果是相同的；2求节点附近的函数值时，由关系，同样可表示成向前差分的形式；3Newton向后插值公式(2-27)在推导微分方程数值解方面能起到很好的作用。构造Newton向前、向后插值公式的具体步骤：1）计算各阶差分，见表2-4表2-4一阶差分二阶差分三阶差分n阶差分1()()()12）将以上表中下划线对角线项与对应行右端因子乘积求和即得Newton向前插值多项式；Newton向后插值公式则为最后的节点所在行的各阶差分值与对应列下端因子乘积之和。例4 已知的函数表如下，分别用牛顿向前、向后插值公式求的近似值。0.40.50.60.70.389420.479430.564640.64422解 取，有。按表2-4计算得一阶差分二阶差分三阶差分0.40.3894210.50.479430.090010.60.564640.08521-0.004800.70.644220.07958-0.00563-0.000831Newton向前插值公式为将代入上式得由式(2-26)，误差为Newton向后插值公式为将代入上式得查表可得。如果取，用二阶Newton向后插值公式，则得代入上式得其误差为例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插值。设已知函数在个不同的插值节点上的函数值 和导数值，要求插值多项式，满足条件 (2-29)这里给出了个条件，可唯一确定一个次数不超过次的多项式。我们仿照与构造Lagrange插值公式相类似的方法来解决Hermite插值问题。定理2.3 存在惟一的满足插值条件(2-29)。证明 可以设想，如果我们能够构造出两组次多项式：，并满足条件 (2-30)则显然多项式 (2-31)满足插值条件(2-29)。余下的问题就是如何构造出插值基函数。由于在处函数值与导数值均为0，故它们应含因子，因此可以设为其中为Lagrange插值基函数，即。由条件(2-30)得由此有 (2-32)同理可得 (2-33)现在讨论惟一性问题，设还有一个次数的多项式满足插值条件(2-29)。令，则由(2-29)得是一个次数的多项式，且有个二重根，所以，即。仿照Lagrange插值余项的证明方法，可导出Hermite插值的误差估计。定理2.4 设为区间上的互异节点，为的过这组节点的次Hermite插值多项式。如果在内阶导数存在，则对任意，插值余项为 (2-34)特别地，当时为三次Hermite插值多项式，它在应用上特别重要，现列出详细计算公式。取节点，插值基函数是，两节点三次Hermite插值多项式为 (2-35)其插值余项为 (2-36)例6 求满足及的插值多项式及其余项表达式。解 按插值条件，所求是一个次数不高于3的多项式，它的曲线过点，故可设其中，为待定常数。由条件可确定常数，通过计算可得与的误差函数为由于以及，故可设其中为待定函数。为求引进辅助函数显然。且，故在内有五个零点（二重根算两个）。反复应用罗尔定理，得在内至少有一个零点，故由此可得余项表达式为式中位于和所界定的范围内。5 分段低次插值5.1 高次插值的病态性质在代数插值中，为了提高插值多项式对函数的逼近程度，自然希望增加节点个数，即提高插值多项式的次数。特别当时，期望插值多项式收敛于被插值函数。但是，令人遗憾的是事实并非如此。事实上，假设存在任意阶导数，当插值节点增加时，固然使得插值多项式在更多点上与相等，但是在两个插值节点之间不一定能很好地逼近，差异可能很大。在非插值节点上往往出现误差函数先递减，而后随着增加而增加，并且变得无界。当时，插值多项式终于变得发散的一个理由是与的阶导数增长得无界这一事实有关。例如，有，对固定的，当增加时呈指数增长。在本世纪初由Runge给出了等距节点的插值多项式不收敛于的例子。例如，对于函数，在区间上取节点，所作Lagrange插值多项式为，其中是Lagrange插值基函数。Runge证明了，当时，内收敛到，在这区间之外发散，这一现象称为Runge现象。当时，图给出了和的图形。从图上看到，仅在区间中部能较好地逼近函数，在其它部位差异较大，而且越接近端点，逼近程度越差。它表明通过增加节点来提高逼近程度是不宜的，一般插值多项式的次数在范围内。直观上容易想象，如果不用多项式曲线，而是将曲线的两个相邻的点用线段连接，这样得到的折线必定能较好地近似曲线。而且只要连续，节点越密，近似程度越好。由此得到启发，为提高精度，在加密节点时，可以把节点间分成若干段，分段用低次多项式近似函数，这就是分段插值的思想。用折线近似曲线，相当于分段用线性插值，称为分段线性插值。设已知函数在上的个节点上的函数值 ，作一个插值函数，使其满足(1) ；(2) 在每个小区间上，是线性函数。则称函数为上关于数据的分段线性插值函数。由Lagrange线性插值公式容易写出的分段表达式 (2-37) 图2-1 图2-2为了建立的统一表达式，我们需要构造一组基函数：，且在每个小区间上是线性函数。式(2-37)所表示的分段线性函数，在区间的部分由图2-1中的两段实线叠加而成。整个区间上的分段线性插值函数由所有这样的折线叠加而成，如图2-2所示。考虑对各节点的贡献就可得到基函数的图像，如图2-3所示。图2-3由图2-3，可写出基函数的表达式：， (2-38)因此可表示为 (2-39)式(2-38)中的基函数只在附近不为零，在其它地方均为零，这种性质称为局部非零性质。且对任意，必属于某个区间，于是 (2-40)下面定理表明式(2-39)的分段线性插值函数一致收敛于被插值函数。定理2.5设，为插值节点，且是的分段线性插值函数，则当时，一致收敛于。证明 由于，所以在上一致连续，即对，存在，使得当且时，有于是当，及时，有设，则一定属于某个子区间，注意到式(2-40)，有由的任意性可知从而证得 如果，则利用插值余项公式(2-9)，可以得到定理2.6 如果在上二阶连续可微，则分段线性插值函数的余项有以下估计其中。证明 因为在每个小区间上，是的线性插值，故对任意的有因为因此，对任意，都有 定理2.5，2.6表明，当节点加密时，分段线性插值的误差变小，收敛性有保证。另一方面，在分段线性插值中，每个小区间上的插值函数只依赖于本段的节点值，因而每个节点只影响到节点邻近的一、二个区间，计算过程中数据误差基本上不扩大，从而保证了节点数增加时插值过程的稳定性。但分段线性插值函数仅在区间上连续，一般地，在节点处插值函数不可微，这就不能满足有些工程技术问题的光滑要求。5.2分段三次Hermite插值分段线性插值函数在节点处左、右导数不相等，因而不够光滑。如果要求分段插值多项式在节点处导数存在，那么要求在节点上给出函数值及其导数值。假定已知函数在节点处的函数值和导数值分别为和，那么所要求的具有导数连续的分段插值函数满足(1) (2) 在每个小区间上，是三次多项式。可直接写出分段三次Hermite插值函数多项式 (2-41)类似分段线性插值基函数的建立方法，考虑到分段曲线对各节点的贡献，可写出如下分段三次Hermite插值的基函数为 (2-42) (2-43)于是分段三次Hermite插值函数为 (2-44)下面的定理给出了的一致收敛性。定理2.7设，为插值节点，且。是的分段三次Hermite插值多项式，则当时，一致收敛于。证明 由于，所以在上一致连续，即对，存在，使得当且时，有又因为在上连续，所以在上存在最大值，即令于是当时，对于任意，一定属于某个子区间，注意到，有容易证得，因此注意到的任意性，于是证得从而证得 如果，由式(2-36)，我们可导出分段三次Hermite插值的误差估计 (2-45)其中。分段三次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-5