数值分析导论2——插值

1、第二章：插值考虑一个单变量函数族 ，它具有 n + 1 个参数，它们的值定出这个族中一个确定的函数。给定的n + 1 个实数或者复数, 对应的插值问题是确定参数 满足,。注意，我们可以称为支撑点，是横坐标，为纵坐标。有时确定参数也涉及的导数。总的说来，如果是的线性函数： 则称插值为一个线性插值问题。例如经典的多项式插值问题（2.1）和三角插值问题（2.3） （）。过去，多项式插值的求值需要用表格进行频繁的迭带，现在计算机技术大大减弱了这个烦琐的过程。然而多项式插值在基本的数值积分当中仍然很重要它通常作为若干类数值积分公式的理论基础。在现在的发展中，多项式和有理插值（请参看下文）用于“外推方法”

2、，可处理微分方程和相关问题（参看3.4和3.3 的事例部分）。 一般说来， 三角插值广泛被用于序列的数字的fourier分析的和循环的现象。就此而论，所谓的“快速fourier变换”是特别重要和有用的（2.3.2）。 线性插值问题还包括样条插值（2.4）以及特殊的三次样条插值，若函数在区间上是二阶连续可导，且对于每个子区间上是一个三次多项式，则称为一个三次样条函数。 样条插值是是一个新兴并且越来越重要的科学，他为经验曲线和逼近复杂的数学函数提供了一个有价值的工具。并且在处理常微分方程和偏微分方程时，它的作用也越来越大。 有两个非线性的插值问题非常重要：有理插值 和指数插值有理插值（2.2）是用

3、数据计算给出最佳逼近函数的过程。指数插值也是如此，例如，分析的中的放射衰变。 对于给定的函数逼近，插值法是一个基本工具。对于此问题的一个全面讨论和有关问题请参看Davis（1965）。.多项式插值.1理论基础：Lagrange插值在下面的讨论中，我们用为所有次数不超过n次的多项式构成的线性空间。的维数为n+1. 是的一组基，则定理（.）对于任意的n+1个插值节点当时，存在唯一的使得即证明：唯一性；设对任意两个有多项式存在性；我们将借助于Lagrange多项式来显示的构造差值多项式P，次数最高只能到达n，并且有至少n+个，对与， （.2）（.）其中注意：到此我们证明了Lagrange多项式是由（

4、.）唯一确定的现在的解的插值问题可一直接的由多项式给出，使得Lagrange多项式（.）成立。上面所有的插值公式证明了p的系数线性的依赖节点。而理论是很重要的。Lagrange公式就只这样，一般的，与后面叙述的一些方法来比较，他并不适合于实际计算，尤其是对于很大的数n作为节点。然而，在一些情形中，Lagrange公式被用来解决插值问题对于已给定的，而节点集合不同。例：给定 n=2 013132求，这里2.1.2 Nevilles 算法代替求解插值问题，我们会立刻想到在更小的支撑点集上解这个插值问题，然后校正这些解来求得整个插值问题的解。在以下的两节中我们来探索这个想法。 Nevilles 算法

5、是一种逐次线性插值方法，用于计算插值多项市在某一点处的函数值，对给定的插值节点可以构造一组函数，多项式在处 有 多项式可用下面的递归（2.1.2.1a） （2.1.2.1b） 证明：（2.1.2.1a）是显然的。现在来证明（2.1.2.1b）右边计为，继续证明R，这里R的次数明显的大学k。定义和，并且， ，因此R=考虑到单一的多多项式插值（定理（2.1.14.1）就有Nevilles 算法目的在于求出单变量x多项式插值P 。运算法则更有效，如果P的值被若干个节点同时确定，我们将在2.1.3中说明。 在（2.1.2.1）的基础上，Nevilles 算法可以表示为关于的多项式插值。k=0123最先

6、计算出来的节点和接下来的节点，可以计算出下一级的节点。用公式（2.1.1.1b）可以算出，例如，例：定义同样的节点在2.1.1节中有k=012=0=1=1=3=5=3=2=5/2=10/3我们现在要讨论一下单变量Nevilles 算法，我们会经常用到缩写（2.1.1.3） 式（2.1.2.2）变为箭头所指的方向就是求出，如果有更多的节点根据上面的方法也是可以很容易的迭代出来的。递归式（2.1.2.1）可以由下面的式子给出（2.1.2.5a） （2.1.2.5b） ， 接下来的ALGOL 运算法则可以由下面的程序给出：For i=0 step 1 until n do Begin t i = f

7、 i ; For j = i -1 step -1 until o do t j = t i+1 + ( t j =+1 - t j )（）（）(2.1.2.6) 当程序结束以后，t j = 用t0期望值可以求出多项式插值。 用改进的Nevilles 算法可以提高多项式插值的精确度。让定义为 （2.1.2.5）可以变换为 从开始，计算出，最后 如果 的值太接近，的值很小，和对比，从这些“改进”的首先应该和2.1.1.5相反，接着相加到，这样可以避免不必要的误差。记下最后的（2.1.2.5）这样的方法明显比前面所提到的简单。（2.1.2.7a） （2.1.2.7b） ， 类似于（2.1.2.6）

8、，接着我们可以用到推断方法。 追溯主要的原因，我们知道的Aitkens 算法，是基于式子（2.1.2.1），但是使用不同的插值作为它的基本算法公式。从下面的表格可以看出其中的第一列指定值，后面的每一个元素是从同一行中的前一个元素和前一列中顶上的元素按（2.1.2.1b）来导出的。2.1.3牛顿插值公式：差商Neville算法适合于决定插值多项式的值而不在于求插值多项式。多项式插值需要自己带入下一次计算，如果想要求出插值的本身，或者想要同时计算插值多项式在多个出的值，牛顿插值公式则更为好用，这里我们写出多项式插值，在下面的这个式子（2.1.3.） 记下方程（2.1.3.1）记 为递归变量有：比起

9、式（2.1.3.1）这只需要更少的运算。这符合所谓的 Horner 算法，下面我们给出他的一般形式。该方法通常表示成X的幂的形式，这就表明表示式（2.1.3.1）是很适合于计算的。余下的问题是决定（2.1.3.1）中的系数，特别是他们可以按下式逐个的进行计算这可以给出n 决定和n(n-1)乘法。然而，这又更好的办法，仅仅只需要n(n+1)/2迭代就可以产生中间结果。观察这两个多项式和，它们相差一个k次多项式和k个0点，因为两个多项式插值相应的节点，因此他们的插值多项式有k个零点，因此存在唯一的系数（2.1.3.2） 满足：（2.1.3.3）从这个恒等式直接的可以写为（2.1.3.4）这代表的只

10、是牛顿插值多项式的一部分，式子是一个牛顿表示式。系数（2.1.3.2）叫做k阶均差。对于本原插值多项式的递推关系（2.1.2.1）转变为均差的递推关系：（2.1.3.5） 有一定的差别，从式子（2.1.3.3），和分别书多项式和在计算各自的插值多项式和都是相当有用和高效的。所有的值都返回从k = 0 对给定的节点，。可以用不同的方式来计算不同的， ，接着可以给出计算出插值多项式的特征。 因为多项式是由插值节点单一确定的多项式定理（2.1.1.1），对于任何的变量和以及任意的的系数也是不变的。于是有（2.1.3.6）均差与指标的排列顺序是无关的。如果是指标的一个排列，则如果我们选用分类计算那么N

11、eville算法也可以称为Aitkens方法，我们可以得出下面的差商表：K=0K=1K=2K=3 第二级差商的计算式为第三级差商的计算式为很明显 就是手边插值问题多要的解。上面展开式中的系数可以在均差（2.1.3.7）中从上往下的对角元中找到。例：用数值带入2.1.1和2.1.2我们有不用逐列的来产生均差表，而是想从它的左上角出发且逐次衍生加长的对角线行来实现的。这就相当于每一次对前面的支撑点做插值后增加一个新的支撑点。在以下ALGOL程序中，在i每增加（2.1.3.7）中延伸的对角元素放在数组i的第一个分量的单元中，而开头的i个系数可以在数组a中找到。For i=0 step 1 until

12、 n doBegin ti=fi; For j=i-1 step -1 until 0 do ti=(tj+1-tj)/(xi-xj); ai=t0end之后插值多项式（2.1.3.1）就可以计算出 P=am For i=n-1 step -1 until 0 do P=p*(z-xi)+aj一些牛顿插值多项式的误差可以的式子来约束或者说估计出来（2.1.3.8）所有的牛顿差之方法都可以找到相应的计算式子，给定节点变量他们之间的长度定义为接着产生迭代序列接着对这样的每一个插入。更重要的是或者因此差商（2.1.3.8）系数是沿着均差表中锯齿形路径，而不是均差表中从上网下的对角线寻找的。从出发，若

13、则此路径通到右上相邻的一个，若，则此路径通道游侠相邻的一个。例：在先前的例子中，一个迭代序列让，得出下面的计算式子所要求的牛顿插值为：通常的，节点纵坐标被赋予值对于给定的函数，我们想要计算插值的方法来近似它，在这种情况下，由节点变量我们记为这个函数满足式子（2.1.3.5）例如 我们可以立即的道下面的式子（2.1.3.6）定理（2.1.3.9）差商是关于其自变量的对称函数，即任意改变其值是不变的。如果行数是一个多项式函数我们有：定理（2.1.3.10）如果是一个n次多项式，那么当时证明：因为定理2.1.1.1差值问题解的唯一性定理，所以当时，节点的系数因而必定为只要这可以由接下来的是（2.1.

14、3.3）给出例：K=01222001112431395104167100如果函数有充分可微的，那么插商可有不同的插值节点来定义，例如如果在处可微，那么其微分式定义如下 插值经过相应的修改可以的道2.1.5节中的Hermite 插值2.1.4插值多项式的误差估计我们来考虑一个函数，其值为，插值多项式，我们要考虑用 来求出重新产生通过不同的节点参数，误差为，这里，能很容易的求出一个任意大的合适的函数，除非在边界条件下，很可能出现分歧误差，例如：定理（2.1.4.1）设在区间上有n+1阶导数，则对任意给定的都存在在包含I的最小区间上使得这里的证明：令插值函数在节点，且节点（对于的情况这里不作介绍），

15、我们能够找到一个K使得函数而当时有一般的，至少有n+2个零点 在区间，有罗尔定理，反复求导之后可以得出有至少n+1个零点在上述区间上，而有至少n各零点，最后有的一零点在区间上因为，所以或者 这个证明了 用（2.1.3）节中的牛顿插值多项式可以得到不同的截断误差。这里的是任意可谓的函数，如果增加n+1个节点 ，我们可以求出（n+2）个节点 这里 那么牛顿插值多项式有如下形式： 或者（2.1.4.2） 不同在于左边的式子有定理（2.1.4.1），又因为时有对所有的这依然服从（2.1.4.3） 对所有的这就是插值与导数之间的关系。例： ， n=5,在本章的末尾，我们有两个忠告，一个是不要相信在区间内

16、的插值多项式，另一个是区间外的多项式。在-区间外，值在定理（2.1.4.1）增长的很快，使用插值多项式P来接近f 在区间外来拟合，叫做推断必须尽可能的避免。另一方面，在区间，我们可以找一个更好更简单的函数来做插值多项式的数据拟合。考虑一个实函数f在给定的不同的区间a,b，对每一个间隔存在一个插值多项式有，在，A序列在区间间隔给出一个上升的序列的插值多项式，一种可能的多项式覆盖了f如果有合适的，当是上述值趋近于0一般这是错误的，例如，下面的函数，=，或者，多项式再多有点都是一致分割的2.1.5 Hermite插值考虑一个实数， 关于这些数的Hermite插值问题就是用数据组成多项式来拟合P次数不

17、超过n次，这里满足以下的插值条件（2.1.5.1），这个问题不同于一般的插值问题在节点，不仅是值，在该问题中，对于所要求的多项式第次微分的期望多项式。多项式插值在2.1.1节的特殊情形，有准确的情形（2.1.5.1）可以构造不同的差值多项式，我们可以用Hermite插值来解决一些问题。定理（2.1.5.2） 对任意的数， 这存在一个准确的多项式，满足（2.1.5.1）证明：我们首先证明唯一性。考虑两个不同的多项式，因为（2.1.2.1），从，是Q的的一个根，以便Q是所有的根。根据根的多重性这的Q必须具有小于n次的同一性！下面证明存在性，因为（2.1.5.1）线性方程组有n个未知的系数，对于系数

18、矩阵可知此方程组有唯一解。Hernite 插值多项式能够有拉格朗日插值（2.1.1.4）唯一给出，多项式由式子满足（2.1.5.1，多项式是拉格朗日多项式，他的定义有以下的式子给出 对比（2.1.1.3），给出 让。有以下式子给出： 其他因此P在（2.1.5.3）是Hermite 插值多项式。为了选择性的的得到P，将是有用的数据， ，在不同的序列n+1对不同的数连续的表示对：记下，数准确发生次，序列例1，假设且 这个问题描述了序列： 给定任意 一个Hermite 插值问题，它可以唯一的决定一个如上的序列,反之，n+1对数的美、每一序列，可以决定一个Hermite 插值问题，将简称为，也可以方便

19、的用 表示j 次多项式：（2.1.5.4）我们下一个目标是将上的插值多项式表示成牛顿型【与（2.1.3.1）比较】（2.1.5.5）并且在借助于均差（2.1.5.6）求出系数，然而，均差的递推定义（2.1.3.5）必须作修改，因为支撑横坐标中可能会有相同的点，例如，如果，那么均差就不能再定义为含有重复自变量的均差定义的推广涉及到极限运算，为此，令是互不相同的支撑横坐标，并考虑属于的均差其中多项式P是Hermite 插值问题的解，现在，这些均差是用递推关系（2.1.3.5）完全确定的，只要开始时取，因此,由（2.1.3.5）有（2.1.5.7a）， （2.1.5.7b） （2.1.5.7c）,因

20、为 ， 所以有极限都存在，如果对指标这些极限都存在，从（2.1.4.3）得知后面一式满足若，我们用表示满足，的最小指标。那么由于P 对于德插值性质。于是由（2.1.5.8），有若在的极限，（2.1.5.7）成为（2.1.5.9a） （2.1.5.9b）（2.1.5.9c）（注意：已经假设），这些公式允许均差的递推计算，从而得到牛顿型插值多项式P的系数例2：我们用例1中的数据（）来说明均差的计算，得到下列的均差表标上*的元素是用（2.1.5.9b）计算的，而不是用（2.1.5.9a）Hemite插值法引起的误差可以用于通常多项式插值法同样的方式来估计，尤其是以下定理的证明完全类似于定理（2.1.

21、4.1）的证明定理（2.1.5.10）设实函数f在区间上是n+1次可微的，考虑m+1个支撑坐标 若多项式至多是n次的并且满足差之条件，则对于每个，存在满足 其中Hermite插值常用于同多分段多项式函数来逼近一个一直是函数f，给定区间的一个划分相应的Hermite函数空间定义为由所有函数所组成，具有以下的性质：（2.1.5.11）（2.1.5.11a）的姐导数在区间上存在且连续。（2.1.5.11b）在每个子区间 ， 上，于每一个次数之多为2v-1的多项式一致。因此，函数有次数之多为2v-1的多项式段多组成，他在“节点”处是v-1次可微的。为了要用一个函数来逼近一个一直实函数，我们选取的分量多

22、项式使得，且使得Hermite插值条件 ， 成立在严格的条件之下，定理（2.1.5.10）提供了对于德一个插值差，他是用分量多项式代替f得到的（2.1.5.12） 将得这些结果结合起来，就得到前面已经定义的函数（2.1.5.13） 其中：是划分的“细度”。如果我们考虑区间的划分的一个序列，且，则逼近误差一细度的速度趋于0.这一点是于通常的多项式插值情形不同的，那里，逼近误差未必随着二趋于0（见2.1.4）Ciarlet,Schultz,Varga(1967)已经能证明，的前v个导数也能很好的逼近f的相应导数：（2.1.5.14），因此（2.1.5.15）2.2 有理函数插值2.2.1有力插值的

23、一般性质仍考虑给定的一组支撑点，我们讨论有理函数在这些支撑点上做插值。治理，整数，是多现实的最高次数。我们将整数对成为实数差值问题。有理函数是由他的歌系数，来决定的，反过来，完全有所决定。我们用来表示从（2.2.1.1）来解决问题。很显然，的系数，比覅那个是其次多项式。（2.2.1.2）的解，或者，完整的写出为我们用表示以上方程组。初一看，用代替似乎不会出现问题，我们举下一个例子就会看到并非如此，有力插值先天性比较复杂：例：对于支撑点：012122：由下面的系数可以算出所有的系统， 因此实函数表达式 在导致不确定的表达式0/0，出去了以上不确定的因素，我们可以得到表达式所有的表达式和代表了同一

24、实函数，叫做值是2的反函数。这个函数没有第一个节点，因此，这并不是的解。解需要任意解，我们总结概括为没有这样的解存在。 同样了例子证明是函数插值多项式是无解的，如果有解那么可以导出是函数无解在这种情形下的例子是差值多项式问题是无解的，为了检查这关于解的更多的相似性，我们必须区别来自于同一 实函数不同的表达式，从出现每一个多项式因子，我们可以的到是表达式：， ， 类似的可以写成： 如果：当两个是表达式代表同样的实函数是这是准确的。 一个实表达式叫做实基础，如果他的坟墓是实数，如果同样的多项式不可分，一个实表达式不是实基础，哪么一般的多项式插值因子不能使方程成立。我们说一个实表达式有解如果方程解有

25、解，注意，有解实差值多项式的的实际复合，是一个交互的过程。定理（2.2.1.3）同种类的线性方程组总有非零解，每一个形如，所有的非空解定义为实表达式。证明：一组线性方程组有个方程和个未知量，这组线性方程组有非空对任意解，有这说明了多项式有零点， 紧跟着有紧跟着有，多项式由最高次数，并且的 位置在消失，不同的位置接着我们可以指导是函数插值为题解的唯一性。定理（2.2.1.4）如果和是大型线性方程组的解，哪么他们的相似解（）代表了同一个实函数。证明：如果和的解，哪么多项式有个不同的零点 = 0 ， 多项式的次数不超过，误差会很快的消失，接着有综上所述：一个实表达式有解且解为鉴于以上的实表达式不是解

26、，先前的考虑把例子设为一种情形低昂。事实上，接下来我们将能够看到针对性的关于差值问题的解 综合以上所讲的（2.2.1.3）和（2.2.1.4）我们会发现，存在是插值问题有唯一的实数解，金额以有任何一个实表达式来近似的解出线性方程组的解，或者如果无解。在另一种情形下，我们将可以找到支撑点这是被“错过的”是函数，这种支撑点叫做奇点。因此的解有以下的情形假设：的一个解为，任意的我们可以分为两种情形：（1）（2）在第一种情况下，很明显，然而，在第二种情况下，支撑点无法达到，这里 必须依靠（2.2.1.2），因此，对于和条件下的因式和频繁的相似性，一般有以下的结果定理（2.2.1.6）支撑点的解，如果的解是哪么可唯一的解出。证明：如果的解是，哪么有（2.2.1.5）的解是，如果的解不是哪么可以推出实函数无解。即使线性方程组的秩是满秩，实多项式插值问题也许是无解的，然而，既然解是，另一种情况下，唯一的目的就是共同的相反的因素，此时我们有：（2.2.1.7）的必然结果（2.2.1.6），如果是满秩的，哪么有且仅有解的充要条件是的解是。我们之所以说支撑点，特殊位置，如果插值是由次数为，的实表达式决定。插值问题的解是次数跟小的非零的节点作为支撑点