第六章 函数插值.doc

第六章 函数插值实践中常有这样的问题：由实验得到某一函数y = f (x)在一系列点x0, x1, xn处的值y0, yi, yn，其函数的解析表达式是未知的，需要构造一个简单函数P(x)作为y = f (x)的近似表达式；或者y = f (x)虽有解析式，但计算复杂，不便于使用，需要用一个比较简单且易于计算的函数P (x)去近似代替它；本章所介绍的插值法就是建立这种近似公式的基本方法。1代数插值设已知某个函数关系y = f (x)在某些离散点上的函数值：（6.1）插值问题就是根据这些已知数据来构造函数y = f (x)的一种简单的近似表达式，以便于计算点的函数值，或计算函数的一阶、二阶导数值。一种常用的方法就是从多项式中选一个Pn(x)，使得（6.2）作为f (x)的近似。因为多项式求值方便，且还有直到n阶的导数。我们称满足关系（6.2）的函数Pn(x)为f (x)的一个插值函数，称x0, x1, xn为插值节点，并称关系（6.2）为插值原则。这种用代数多项式作为工具来研究插值的方法叫做代数插值。设x0 x1 0)为步长的向前差分和向后差分；df (xi)称为f (x)在点x = xi处以h为步长的中心差分；f（xi, xj）如前所定义称为f (x)在xi, xj处的一阶差商，于是，当h充分小或当xj充分靠近xi时，有这样，连续形式的f (xi)转化为离散的差分差商形式，而差分差商的极限则是f (xi)的连续形式。大家知道，电子计算机通常只能对有限位数字进行加、减、乘、除四则运算，函数的数值逼近的重要任务，就是将连续形式的函数离散化，而差分差商就是函数微商形式离散化的极重要工具。同样的道理，定积分是用求和的极限来定义的，故定积分的离散化工具是求和运算。积分和微分，差分与求和这几种相互矛盾互要转化的运算规律由下图说明，其中(A)(B)表式A近似于B，(A)(B)表示B为A的逆。图 6.3至于如何实现这些基本运算之间的联系和转化，途径是多种多样的，结果是丰富多采的。运用泰勒展开式，可以得出差分差商逼近于导数的误差关系式（6.20）仅举中心差商来验证一下：分别将，在xi处展开为泰勒级数，有：两式相减，得从而有可以看出，中心差商逼近微商精度最高。在几何图形上，这三种差商分别表示弦AB、AC和BC的斜率。将这三条弦线与过点A的切线相比较，从图形上可以看出，一般地说，弦BC的斜率更接近于切线斜率f (a)。图6.4对应于差商，我们给出n阶差分的定义：定义：y = f (x)在x = xk点的n阶差分为：下面给出差分的几个重要性质：（以向前差分为例）性质1：常数的差分等于零性质2：差分算子为线性算子即性质3：如果f (x)是n次多项式，那么k阶差分Dkf (x) (0kn)是n-k次多项式，并且Dn+lf (x) = 0（l为正整数）。事实上，由泰勒展开式上式右端是n 1次多项式。对于任意k，根据上述做法运用归纳法不难证明之。性质4：其中：这个性质类比于性质5：此性质类比于分部积分法则。性质6：当节点xk是等距时，（xk = x0 + kh yk = y0 + kh = f (xk)）差分差商存在着关系：（6.21）此处利用数学规纳法可以推得高阶差分和函数值之间的关系式其中如同高阶差商，高阶差分在计算时也可造差分表fkDD2D3D4f0f1Df0f2Df1D2f0f3Df2D2f1D3f0f4Df3D2f2D3f1D4f02等距节点插值公式在差商型的插值公式中，为了计算差商需要多次进行除法。当节点为等距时，我们可以用差分代替差商，从而节省计算次数。另一方面，给出了一个函数表，当要求插值时，当然不会将所有点都作为插值节点，我们总是希望，运用较少的节点达到应有的精度。所以当被插的点x靠近表头时，自然考虑用表头的几个点来插值；当x靠近表尾时，应尽量用靠近表尾的节点作插值点。本节就是利用差分给出牛顿前插公式和后插公式。一、 牛顿前插公式设f (x)在区间x0, xn上有n + 1阶导数。取xi = x0 + ih, (i = 0, 1, 2, n)为插值节点，由（6.21）牛顿插值公式可写为先考虑x含于表头的情况，设x0 x x1引入新变量t，将x写成于是余项为：二、牛顿后插公式下面考虑x含于表尾的情况。设x含于xn-1和xn之间，引入新变量t，设x为将插值节点按xn, xn-1, x0排列，于是有注意到就可将Nn (x)写成实际计算时，先造差分表，若x靠近表初时用上斜角差分Dy0，D2y0，若x靠近表尾时用下斜角分Dyn-1，D2yn-2,，D3yn-2，xyDD2D3xyDD2D3x0y0Dy0x1y1D2y0xn-3yn-3Dy1D3y0Dyn-3x2y2D2y1xn-2yn-2D2yn-3Dy2Dyn-2D3yn-3x3y3xn-1yn-1D2yn-2Dyn-1xnyn 5 Hermite插值多项式在实际问题中，对所构造的插值多项式，不仅要求通过点（xi, yi）i = 0, 1, 2, n，同时还要求在xi上，若干阶导数值也与被插函数的导数值相等。把此插值多项式称为埃米尔特（Hermite）插值多项式或称带导数的插值多项式，记为H (x)。其求法如同不带导数的插值多项式的求法，而且也有两种表达形式，拉格朗日型和牛顿型。当插值条件一样时，如不计舍入误差，其两种表达式虽然形式不同，但都对应同一多项式，并且可以从一种形式推出另一种形式。本节主要介绍牛顿埃米尔特多项式的构造方法。例1 已知函数表xx0x1yy0y1yy0求一个插值多项式H (x)，使其满足如下条件：（6.22）解：先由函数表xx0x1yy0y1作线性插值，即为（6.23）再注意到H (x)与P1 (x)在节点x0, x1上函数值相同，即：于是，它们的差可以设为其中K为待定常数，上式又可记为：（6.24）为确定K，对上式求导：令x = x0，代入上式，并且注意到插值条件得：于是有（6.25）将上式代入（6.24）得（6.26）可以验证（6.26）所确定的H(x)确实满足插值条件（6.22）。同时也可以看到，构造牛顿埃米尔特插值多项式，完全采用牛顿插值的构造思想。最后，也可以把（6.26）式整理成拉格朗日形式：（6.27）下面介绍一般的埃米尔特插值。已知函数表（6.28）求一个插值多项式H (x)，使其满足如下条件：i = 0, 1, 2, n （6.29a）i = 0, 1, 2, m （6.29b）为求此多项式，首先分析插值条件的个数，共为m+n+2个。那么，所构造的H (x)的次数，一般不超过m+n+1次。于是，按牛顿插值的构造思想，可设（6.30）其中Nn (x)是由（6.29）所作的牛顿基本插值多项式；Pm(x)为特定的m次多项式。显然：i = 0, 1, 2, n 为确定Pm (x)，对（6.30）求导（6.31）令x = xi, i = 0, 1, 2, m，且利用条件（6.29b），代入（6.31）得所以 i = 0, 1, 2, m （6.32）于是，把求Pm (x)的问题，变成已知Pm (x)的函数表xx0x1x2xmPm(x)Pm(x0)Pm(x1)Pm(x2)Pm(xm)确定一个次数不超过m的插值多项式Lm(x)，使其满足 i = 0, 1, 2, m的插值问题。其中Pm(xi)是由（6.32）式计算得来的。因为Pm(x)为小于等于m次多项式。所以，。即（6.33）其中令x x-1 = 1，将上式代入（6.30），便得到满足插值条件的埃米尔特插值多项式。此时，（6.30）式是牛顿式的。如果将（6.30）式中的Nn (x)，Pm(x)换成拉格朗日插值多项式Ln (x)，Lm(x)时，则（6.30）可改写成 （6.30a）其中 i = 0, 1, 2, m当然，我们也可以把它改写成完全拉格朗日形式（6.34）特别地当m = n = 1时，得到3次多项式。余项例：求满足条件x 1 2 3 y 2 4 12y 3的插值多项式及余项。解：设插值多项式H3(x)，满足所给的已知条件，按牛顿插值的构造思想：其中为确定k值，对前式求导，得：令x = 2，代入上式，且注意插值条件，得因为，所以k = 2，于是可以验证余项6 样条函数插值1多项式插值的缺陷与分段插值对于函数f (x)，（例：如连续函数或连续可微函数），当插值的次数逐步加高时，是否逼近程度也得到逐步改善呢？由拉格朗日插值多项式余项估计：其中。当代数插值的次数较高时，常有数值不稳定的现象，特别当插值节点数 时，插值多项式不一定收敛到被插值函数。本世纪初，德国数学家龙格（Runge）就给出了一个等距节点插值多项式不收敛于的例子。已知区间-1, 1上函数取等距节点 （i = 0, 1, 2, , 10）作拉格朗日插值多项式 -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 图6.5从图中可以看出，在x = 0附近，L10(x)能较好地逼近f (x)，但在有些地方，如图6.5所示在-1, -0.8和0.8, 1之间，L10(x)与f (x)差异很大。这种现象叫做龙格（Runge）现象。由于这个原因，在用多项式插值时不宜选取高次多项式插值。用低次代数多项式插值的一个途径是分段插值。当节点很多时，用分段低次插值，并希望在连接处保证连续性，这类方法克服了上述缺点。例如分段线性插值（折线插值）、过点（x0, y0）（x1, y1），,（xN , yN）作折线相连（如图 6.6 ）。y= f(x)xoyi = 0, 1, , Ny=p(x)图6.6分段插值有很好的局部性质。因为多项式是分段作成的，所以只保证了连续性。2三次样条函数插值：但是在生产和科学实验中，对所做的插值曲线即要简单，又要在曲线的连接处比较光滑，即所作的分段插值函数在分段上要求多项式次数低，而在节点上不仅连续，还存在连续的低阶导数，我们把满足这样条件的插值函数，称为样条插值函数，它所对应的曲线称为样条曲线，其节点称为样点，这种插值方法称为样条插值。样条函数是在生产和科学技术实践中产生的。如用方砖砌圆井、条石筑拱桥，这些都是最初的“样条函数”。但是现在因此得名的样条曲线并不是指折线而言，而是放样工人或绘图员借助样条（一种软木或塑料的长条）和压铁给出的那种曲线。这种曲线，在数学上是分段三次多项式的典型代表，它具有良好的力学性质。推而广之，今天把分段多项式，甚至分段解析函数统称为样条函数。样条函数的应用领域很广，早期在汽车、轮船、飞机制造方面的应和是手工放大样，在计算机的发展日前广泛深入后，它广泛地应用于各种制造业的计算机辅助设计（CAD），各种图形的绘制工作、地理信息系统、实验数据的拟合、以及现在“热门”的计算机动画制作。在样条函数中，应用最广的是三次样条函数，也是本章的重点内容。定义：设对y = f (x)在区间a, b上给定一组节点a = x0 x1 x2 0, li 0, l0 = li =1，故方程组系数严格对角占优，从而存在唯一解。求出了Mi (i = 0, 1, n)，也就求得了S (x)在各个小区间的表达式Si (x)（i = 0, 1, 2, n）若取等距节点 hi = h, i = 1, n 1则6算法（