《分析05-插值法下》PPT课件.ppt

第五章 插值法,5-1,第五章,插值法 （下）,第五章 插值法,5-2,3 Hermite插值,不少实际问题不但要求插值 函数在节点上与原来的函数相等 （满足插值条件），而且还要求 在节点上的各阶导数值也相等， 满足这种要求的插值多项式，称 为Hermite插值多项式记为H(x)， 本节主要讨论已知节点的函数值 和一阶导数的情形。,第五章 插值法,5-3,3.1 Hermite插值,设已知函数y = f (x)在n +1个互异节点x0,x1,xn上的函数值yi = f (xi) (i=0,1,2,n)和导数值yi = f (xi)(i=0,1,2,n)，要求一个不超过2n+1次 的多项式H(x)，使其满足：,这样的H(x)称为 Hermite插值多项式。,第五章 插值法,5-4,引例（续1）,第五章 插值法,5-5,引例（续2）,第五章 插值法,5-6,引例的误差估计：,注意到x1是H(x)的二阶零点， x0,x2为其一阶零点， 所以：,为确定(x)，作辅助函数：,当t = x时，可选择(x)，使(x)=0t = x, x0,x2为(t)的一阶零点，t = x1为二重零点。因此(t)共五重零点，反复使用罗尔中值定理（对重零点也适合）可得到：存在x，使(4)(x)=0，即 ：,由于H(t)是t 的三次多项式， H (4)(x)=0,第五章 插值法,5-7,推广至n+1个点,推广至n+1个点的 yi , yi时，利用构造插值基函数的方法， 照上述引例，可设：,其中hi(x)和Hi(x) (i=0,1,2,n) 满足： （1）hi(x), Hi(x)(i=0,1,2,n)都是不超过2n+1次的多项式 ；,下面分别确定hi(x)和Hi(x)：,第五章 插值法,5-8,下面分别确定hi(x)和Hi(x)：,对hi(x)：x = xj(ji) 为其二重零点，故应含有因式 (xxj)2 ( ji)，因此可以设为,请注意：直观上应设hi(x)为：,这样来确定a,b较麻烦，上述引入li(x)后，较简单。 hi(x)还应满足：,第五章 插值法,5-9,对Hi(x):,对Hi(x) :由于 x = xj(ji)为其二 重零点，xi为一重 零点，故可设 :,这样，代回去得:,特别地，当n =1时，有:,第五章 插值法,5-10,两个节点的三次Hermite插值多项式,因此n =1的三次Hermite插值多项式可用标准化 的基函数表示为：,更便于上机使用，上式中h = x1-x0。,通常称之为 “标准化”的基函数， 而上述三次Hermite 插值基函数可由其 表示出：,第五章 插值法,5-11,3.2 误差估计,和引例类似，可导出Hermite插值的误差估计。,定理5.2,设x0,x1,xn为区间a, b上的互异节点，H(x)为f (x)的过这组节点的2n+1次Hermite插值多项式。若f (x)在a,b上2n+2连续可导，则对xa, b插值余项为：,特别地，n =1的三次Hermite插值余项为：,注意与引例的误差估计式，与Lagrange插值的误差 估计式相比较。,第五章 插值法,5-12,定理5.3,设x0,x1,xn为区间a, b上互异节点，f (x) C(1)a, b，则上述Hermite插值多项式是唯一的。,定理5.3,推论1：不超过2n+1次的多项式在任意n +1个互异节点上 的Hermite插值多项式就是其自身。,对于推论2，事实上，可令f(x)=1，f (xi)=0， (i=0,1,n)，显然 满足这组插值条件，即得结论。, H(x)为不超过2n+1次多项式， H(2n+2)(x)0 于是H(x) H(x) 0这表明Hermite插值多项式是唯一的。,第五章 插值法,5-13,Hermite插值举例,例6,按下表求Hermite插值：,第五章 插值法,5-14,Hermite插值举例（续）,例7,设：已知函数f (x)的如下值:f(-1)=-2，f(0)=-1，f(1)=0，f (0)=0，求不超过3次的Hermite插值多项式H (x),第五章 插值法,5-15,3.3 Hermite插值的一般形式,求一个不超过n+m+1次的多项式H (x)使得:,与前面的讨论类似，可以证明这样的Hermite插值多项式 是唯一存在的，其余项为:,这里的一般形式即是在节点处的一阶导数值没有全 部给出，与前面引例相似，举例说明方法。,第五章 插值法,5-16,Hermite插值一般形式（举例）,例8,按下表求Hermite插值多项式：,解法一：这里有5个条件，所以插值多项式不超过4次，用 构造插值基函数hi(x)(i=0,1,2)和Hi(x)(i=0,1)的方法，它们分 别应满足：,第五章 插值法,5-17,例8（解法2）,解法2： x = 0为二阶零点，故可设插值多项式为,代入条件：,所求四次Hermite插值多项式为：,第五章 插值法,5-18,4 多项式插值的缺陷与分段插值,4.1 多项式插值的缺陷,在插值方法中，为了提高插值多项式的逼近程度， 常常需要增加节点个数，即提高多项式的次数，当插 值节点增多，插值多项式的次数逐步提高时，是否逼 近程度也越来越好呢？一般总认为Ln(x)的次数n越高， 逼近f (x)的程度越好，实际上并非如此。因为： （1）节点的增多固然使插值函数Ln(x)在更多的地方 与f (x)相等，但另一方面在两个插值节点之间Ln(x)不 一定能很好地逼近f (x)，有时差异还很大，即高次插 值收敛性得不到保证。 （2）从计算的含入误差看，高次插值可能会产生严 重的误差积累，即稳定性得不到保证。 下面分别举例说明。,第五章 插值法,5-19,多项式插值的缺陷举例,例如， 在区间-1,1上给定函数f(x)=1/(1+25x2)，并将区 间-1,1分为n等分，以Pn(x)表n+1个节点的n次插值多项式， 图5-4给出了f (x)及P10(x)的图象，从中可以看出，P10(x)在 端点附近，误差很大，如f(0.95)=0.24244，而P10(0.95) =1.92363，并且还可画出P4(x)相比较，P10(x)在区间中间能 较好地逼近f (x)，比P4(x)好得多，但在端点附近P10(x)的波 动很大，可以证明：Pn(x)只在|x|0.726内收敛于f (x)。 在0.726|x|1内Pn(x) 与f (x)偏离很大，不收 敛于f (x)。高次多项式 插值产生的这种不收敛 现象称为龙格（Runge） 现象 。,第五章 插值法,5-20,多项式插值的缺陷举例（续1）,再以Lagrange插值为例，讨论其稳定性。不妨设数据yi误差yi，假定计算过程中不再产生误 差，此时，Lagrange插值多项式为：,故插值的实际误差为：,上式中右端第一项即为 插值余项，而第二项为：,这就是节点数据的误差yi所引起的插值误差。可见，yi 通过插值基函数li(x)而全面扩散，而插值基函数li(x)在基本 插值区间x0,xn内是上下波动的，在区间外，则按距离的n 次幂放大，如图5-5所示。当变大时，其波动频率与振幅也 随之增大。此时插值过程对节点数据误差非常敏感并将其 放大，这就是说高次插值不具有数值稳定性。,（紧接下屏）,第五章 插值法,5-21,多项式插值的缺陷举例（续2）,实际上在以Ln(x)近似f (x)时，由误差估计式：,第五章 插值法,5-22,几点启示,（3）因为高次插值不能用，而实际情况需要将给定的节点全部都用上( 区间长度所需要），此时常采用分段低次多项式插值。,以上分析给我们几点启示：,（1）增加节点并不一定能保证在两节点之间插值函 数 Ln(x)能很好地逼近f (x)，即高次插值（如7，8次上） 在 实际应用中很少被采用。,（2）插值多项式逼近f (x)时，当f (x)为多项式 时效果非常好，误差为零，而上述Runge现象中f (x)为有理函数，能否寻求用有理分式（而不用多项式）作插值函数。,第五章 插值法,5-23,启示（4）,（4）由于高次插值可能不收敛，若要精度高，能否考虑寻找一新的逼近函数P (x)，它不是插值函数（不满足插值条件），但却仍然是一简单函数，比如仍为多项式，但P (x)在xi处不一定等于f (x)，而是要求 在整个区间上每一点处P (x)都能在误差允许范围内逼近f (x)，比如 要求其在节点xi处的偏差ri = P(xi)yi(i = 0,1,2,n)按某种标准最小以反映所给数据的总体趋势，消除局部波动的影响。,由于高次插值不能用而引出了上面几点讨论，对出现的 问题进行分析而导致新的方法，新理论的产生，这也正我们在后面学习中的新起点。,第五章 插值法,5-24,4.2 分段多项式插值,在大范围且节点较多的情况下，常采用分段低 次多项式插值，大致可分为两类，一类为局部化分 段插值，即把插值区间分段后，在每个小区间上直 接构造低次插值多项式，也叫简单分段插值；另一 类是非局部化分段插值，即在整个区间上构造分段 插值多项式，如样条插值。 下面介绍几种简单分段插值：,以下几种分段插值都设为：,第五章 插值法,5-25,1、分段线性插值,已知yi = f(xi) (i = 0,1,n)，在每个子区间xi,xi+1上分 别作线性插值(i = 0,1,n1) 。,P1(x)在a, b上为分段一次多项式，它满足插值条件： P1(xi)= yi(i = 0,1,n)，在节点处连续，P1(x)的图形为一折 线，如图5-6，其几何意义就是用折线去逼近曲线f (x)。,第五章 插值法,5-26,2、分段抛物插值,P2(x)为a, b上的分段二次多项式，它满足插值条件P2(xi)= yi (i = 0,1,n)，在节点x2k处连续。,第五章 插值法,5-27,3、分段三次Hermite插值,已知 yi = f (xi)，yi = f (xi) (i = 0,1,2,n)，在每 个子区间xi,xi+1上作Hermite插值，由3中式(5-21) 可得：,其中hi = xi+1 xi，0(x) = (1+2x)(1x)2, 1(x) =x (1x)2, 显然分段三次Hermite插值多项式H (x)满足插值条件 H(xi)=yi,H (xi)= yi (i = 0 1,2,n)，在节点处一阶导数连 续，因此密合程度较好并且为分段光滑函数。,第五章 插值法,5-28,4. 分段插值的余项及收敛性和稳定性,（1）插值余项 利用插值余项结果可得分段线性插值多项式P1(x)在 子区间xi,xi+1上的余项估计式。,而在整个插值区间a,b上：,同理可得对分段三次Hermite插值多项式H (x)在xi,xi+1上：,在a, b区间上：,第五章 插值法,5-29,例9,构造函数y = ln x在x1,10上的等距数表，应如何 选取步长h，才能在利用该数表进行分段线性插值 时，使误差不超过10-6/2。,例9,第五章 插值法,5-30,分段插值的余项及收敛性和稳定性（续）,（2）收敛性 设f (x)在a, b上连续，则可以证明， 当h0时，上述分段插值多项式P1(x)， P2(x)，H (x)等都一致收敛于f (x)。 （3）稳定性 简单分段插值具有突出的局部性质， 其每个节点至多只影响到直接衔接的两 个子区间而不远及，因而，节点的数据 误差基本上不扩散，不放大。所以，简 单分段插值具有高度的数值稳定性。,第五章 插值法,5-31,5 样条插值,分段插值具有良好的稳定性和收敛性，有效地 避免了龙格现象的发生，且算法简单，因此在实际 应用中占有重要地位，但是，其光滑性较差。前 面所介绍的方法只保证函数连续或其一阶导数连 续，满足不了许多工程技术提出的对插值函数的 光滑性有较高要求的计算问题。,例如，船体、飞机的机翼外形，内燃机的进、 排气门的凸轮曲线，都要求曲线具有较高的光滑 程度，不仅要连续，而且要有连续的曲率，即二 阶导数连续。对于分段插值，要增加光滑度，就 要采用更高阶的导数值，而这一点实际应用中往 往是很难提供的。为解决这一类问题，导致产生 了样条插值。,第五章 插值法,5-32,5.1 样条函数的概念,所谓样条（Spline）本来是工程设计中使用的一种绘图 工具，它是一种富有弹性的细长木条，在飞机或轮船制 造过程中，被用于描绘光滑的外形曲线。使用时，用压 铁将其固定在一些给定的型值点上，在其它地方任其自 然弯曲，并稍作调整，使样条具有满意的形状（各段接 口处呈光滑状），然后沿样条画出曲线，称为样条曲线， 它实际上是由分段三次曲线拼接而成，在连接点即型值 点上，不仅函数自身是连续的，而且它的一阶和二阶导 数也是连续的。由此抽象出数学模型称为样条函数。,给定区间a, b的一个划分a = x0 x1xn = b， 如果函数S (x)满足（1）在每个小区间xi,xi+1(i=0,1,n-1)上S (x)是m次多项式； （2）S (x)在a, b上具有m1阶连续导数。 则称S(x)为关于上述划分的m次样条函数。,第五章 插值法,5-33,样条函数的概念(续1）,显然，按此定义，折线是一次样条函数。而用“样条”绘出 的图形为三次样条函数曲线，也是最常用的样条函数。那 么，确定一个三次样条函数需要多少个条件呢？由上述样 条函数定义（1）中知，S(x)在每个小区间xi,xi+1上是一个三次多项式，因此需要确定4个待定常数，一共有n个小区间，故应确定4n个参数。由定义中条件（2），S (x)应在n1个内点上具有二阶连续导数，即应满足条件：,共有3(n1)个条件。因此，要确定一个三次样条函数， 还需要另增加4n3(n1) = n+3 个条件。,第五章 插值法,5-34,利用样条函数进行插值，即取插值函数为样条函数，称为样条插值。 例如分段线性插值是一次样条插值。 已知函数y = f (x)在区间a, b上的n +1个节点a = x0x1 xn = b上的值yj=f (xj)(j=0,1,n)，求插值函数S (x)使其满足： （1）S(xj)=yj(j=0,1,n)； （2）在每小区间xj,xj+1(j=0,1,n-1)上S (x)是三次多项式，记为Sj (x)； （3）S (x)在a, b上二阶连续可微。 则S (x)称为f (x)的三次样条插值函数，它通过上述给定点，为二阶连续可导的分段三次多项式函数。,5.2 三次样条插值,第五章 插值法,5-35,三次样条插值（续）,（1）给定两端点处的导数值S (a) = y 0，S (b) = y n，特别地，当y 0 = y n = 0时，样条曲线在端点处呈水平状态。 （2）给定两端点处的二阶导数S (a) = y 0，S (b) = y n， 特别地，当y 0 = y n = 0时，称为自然边界条件。 （3）如果f (x)是以b a为周期的周期函数，则S (x)也是应具有同样周期 的周期函数，在端点处应满足S (a+0) = S (b0)，S (a+0) = S (b 0) .,由定义，这里增加了n +1个插值条件，要确定S (x)还需要补充两个条件。通常会根据问题的具体情况。在区间的两个端点处给出条件，称为边界条件。常用的边界条件有以下三种：,可以证明，在上述三种边界条件下，三次样条插值问题的解是存在且唯一的。三种边界条件都有它们的实际背景和力学意义。,第五章 插值法,5-36,三次样条插值举例,已知函数f (x)在三个点处的值为f (1)=1, f (0) = 0, f (1)=1，在区间1,1上，求f (x)在自然边界条件 下的三次样条插值多项式。,例10,第五章 插值法,5-37,三次样条插值举例（续）,这种解法称为待定系数法，当n较大时，由于要解4n阶的线性方程组，工作量太大，因此，一般不采用待定系数法，而考虑另外的较简单的方法，即取节点上的导数或二阶导数值为参数，来导出三次样条插值函数的表达式。,第五章 插值法,5-38,1. 以节点处的二阶导数值为参数的三次样条插值函数,其中积分常数c1,c2可由插值条件Sj(xj) = yj， Sj(xj+1) = yj+1确定：,（紧接 下屏）,第五章 插值法,5-39,这就是在每个小区间Sj(x)的表达式（M表达式）,建立M表达式,第五章 插值法,5-40,建立关于M的关系式,下面建立关于M的关系式（等式，即方程组）确定Mj， 插值条件已用，假定二阶导数已知，即二阶连续条件已用， 因此要用一阶导数连续来建立等式。对Sj(x)求一次导得：,因为是在xj,xj+1上，所以可代入x = xj ，x = xj+1,（紧接下屏）,第五章 插值法,5-41,建立关于M的关系式（续1）,Sj-1是xj的左边区间xj1, xj上的函数，故有等式：,第五章 插值法,5-42,建立关于M的关系式（续2）,整理得：,第五章 插值法,5-43,建立关于M的关系式（续3）,式（5-22）称为M关系式，对于所有内点j = 1,2,n1成 立 。式（5-22）展开后为,n 1个方程含有n +1个参数M0, M1, Mn, 按其力学意义，称为三弯矩方程，系数 j, j, cj可预先求出来。,第五章 插值法,5-44,M关系式的三种边界条件,要由上述M关系式确定所有参数，需要根据问题的具体 情况，利用边界条件补充两个方程。下面就三种边界条件， 分别进行讨论。,1）如果问题要求S (x)满足边界条件（1）由式（5-20）得,化简得：,第五章 插值法,5-45,M关系式的三种边界条件（续1）,式（5-25）与（5-23）联 立，即得到关于n +1个参 数M0, M1,Mn的n +1阶 线性方程组，其矩阵形式为 ：,（2）如果问题要求S (x)满足连界条件（2）即给出了：,此时方程组（5-23）实际上只有n 1个未知数，这仍是三 对角方程组，可直接用追赶法求解 。,第五章 插值法,5-46,M关系式的三种边界条件（续2）,（3）如果问题要求S (x)满足周期边界条件（3），f (x)以 b a为周期，则 S (x)也以b a为 周期，即在端点处应满足：,可转化为两个方程，补充到（5-23）中。,以上式作为最后一个方程进行整理，注意到M0 = Mn有：,（紧接下屏）,第五章 插值法,5-47,M关系式的三种边界条件（续3）,并且因M0 = Mn所以将（5-23）中第一个方程 1M0 + 2M1 + 2M2 = c1 改写为,这样，将式（5-27）代回（5-23）中并与（5-26）联立， 得到n阶方程组：,第五章 插值法,5-48,M关系式的三种边界条件（续4）,在上述三种情况下的线性方程组是三对角或广义三对角的，其系数矩阵均为严格对角占优，因此方程组有 唯一的一组解M0, M1, Mn，求出后代入“M表达式”（5-19），即得三次样条函数，方程组中每个方程都连系三个Mi，参数Mi在力学上的意义为细梁在xi 截面处的 弯矩，因此上述方法又称为三弯矩插值法。,第五章 插值法,5-49,2. 以节点处的导数值为 参数的三次样条插值函数,同前面讨论类似，也可以假定xj,xj+1上的一阶导数S(xj)=mj (i=0,1,2,n)为已知，以mj作参数表示S(x)（得到m表达式），再由m关系式确定mj，求出S (x)。 在xj,xj+1上；有对应的 yj，yj+1 和S (xj)=mj S(xj+1)=mj+1 首先利用前面的分段三次Hermite插值 可构造 ：,这样构造的Sj(x)已满足插值条件，在内点的连续条件：,第五章 插值法,5-50,以节点处的导数值为 参数的三次样条插值函数（续1）,为使Sj(x)为三次样条函数，即Sj(x)应连续，同时 为确定参数mj，对Sj(x)在xi,xi+1求二次导数：,第五章 插值法,5-51,以节点处的导数值为 参数的三次样条插值函数（续2）,第五章 插值法,5-52,以节点处的导数值为 参数的三次样条插值函数（续3）,称（5-30）为三次样条的m关系式，按其力学意义，mj为细梁在xj截面处的转角，也称为三转角方程，方程组（5-30）含有n +1个未知数，n1个方程，与对M关系式的讨论类似，增加边界条件（1），（2）后，可得关于参数mj 的三对角方程组，增加边界条件（3），得广义三对角方程组。这些方程组的系数矩阵同样为严格对角占优阵，故方程组有唯一解，求解出参数mj(j = 0,1,n)后代入（5-28），即得三次样条插值函数。,第五章 插值法,5-53,三次样条插值函数举例,例11,已知函数表：,求满足边界条y(0)=1, y(3) = 0,的三次样条插值函数。,解如果用三弯矩方程求解，由已知hj=1(j = 0,1,2,)，按式 （5-21）和（5-25）计算方程组的系数及右端顶，结果如下：,将上述数据代入式（5-23）和（5-25）得方程组:,第五章 插值法,5-54,例11(续),第五章 插值法,5-55,例11(续) 三转角方法求解,如果用三转角方程求解，由式（5-29）：,将上述数据及m0=1,m3=0代入 式（5-30），得三转角方程：,将此解代入式（5-28），即得三次样条插值函数 的分段表示式：,比较上面两种解法， 对第一种边界条件， 用三转角方程 计算较简便。,第五章 插值法,5-56,计算三次样条插值函数的步骤,（1）根据给定的点(xj,yj)及相应的边界条件 计算j,j,cj或dj。一般地，对第一种边 界条件用三转角方程，对第二种边界 条件用三弯矩方程较为简便； （2）解方程组（5-23）或（5-30），求出 参数Mj或mj； （3）将求得的参数代入式(5-19)或(5-28)， 即得三次样条插值函数S(x)的分段表 示式。,小结计算三次样条插值函数的步骤为：,第五章 插值法,5-57,三次样条插值函数的收敛性,设f (x)在a., b上四次连续可微，S(x)为f (x)在a, b上 的三次样条插值函数，则:,证明略。,定理5.4,第五章 插值法,5-58,三次样条插值函数的收敛性（续）,定理5.4表明，当分划小区间的长度趋于零时，S(x)及其 一至三阶导数分别一致收敛到f (x)及其一至三阶导数，因 而，为提高精度只需加密分划节点，不需要提高样条函数 的次数。由于样条插值有这样好的性质，因此它应用十分 广泛，在外形设计及计算机辅助设计的许多领域中，都是 十分有效的数学工具。 三次样条插值有明确的力学背景： 样条曲线可以看作是弹性细梁受集中载荷作用 而生成的挠度曲线，在扰度不大的情况下，这种 扰度曲线在数学上恰好表现为三次样条函数，集中 载荷的作用点就是三次样条函数的节点。,第五章 插值法,5-59,小 结,简单地比较前面所述的几种插值方 法，它们各有优缺点。多项式插值宜用 较低次多项式，例如：n 6，当次数较 高时，收敛性与稳定性均较差。分段线 性插值或分段低次插值具有较好的稳定 性与收敛性，且计算简便，但光滑程度 较差。样条插值克服了这一缺点，并具 有良好的收敛性，但其计算复杂，稳定 性不如分段插值。进一步的讨论可参看 有关资料。,第五章 插值法,5-60,例1求证：存在三次多项式满足下面函数表,证： 由于表中给出了六个点的函数值，根据Newton插值公式，一般情况下可以构造出一个5次插值多项式，这个5次多项式必然满足上面函数表。 构造差商表如下：,第五章 插值法,5-61,例1（续）,一般情况下，给定n+1个节点，可构造一个n次插值多项式，若得到低于n次的插值多项式，称为“退化”情况，利用Newton插值，很容易检查出是否为“退化”情况，因为利用差商（差分）表，当某一阶差商（差分）为常数时，则下一阶差商（差商）必定为0，此时必会出现“退化”情况。,由上表知，由于四阶差商以上均为0，所以这个5次多项式实际上是3次多项式 ：,故存在三次多项式满足是所给的函数表。,第五章 插值法,5-62,例2 Runge现象的发生和防止,对区间 作等距划分： ， 分别取 以 为节点， 对函数 ：,按下述方案进行插值计算，并比较其结果。,方案I 拉格朗日插值；方案II 分段线性插值； 方案III 三次样条插值。,解 这里只将求解后的部分数值结果列于表1中。由此可以看到，拉格朗日插值的效果并没有随n增大而变化，与此相反，在区间端点附近，反而发生了激烈的振荡，即出现了龙格现象。而分段线性插值、三次样条插值都能较好地逼近 ，且随着n的增大，逼近效果更好，反映了分段线性插值和三次样条插值的一致收敛性，防止了龙格现象的产生，从表中数据可以看到，三次样条插值的精度比分段线性插值更高。,第五章 插值法,5-63,表1,第五章 插值法,5-64,例3 反插值,给出函数 的函数表（表2），试利用此数表求使 的x值。,表2,解 插值是利用函数y=f(x)的已知数据求给定的自变量x所对应的函数y 的近似值。而本题则是求已知函数值y 所对应的自变量x之值。如果函数y=f(x)的反函数 存在，则可把所给数据值y视为自变量取值，而把x的值视为函数值，对反函数 进行插值，即可求得欲求的x，这样的问题称为反插