数值分析第二章 插值法

第二章插值法§1引言

在生产和科研中出现的函数是多种多样的，常遇到这样的情况：在某个实际问题中，虽可断定所考虑的函数f(x)在区间[a,b]上存在且连续，但却难以找到它们的解析表达式，只能通过实验和观测得到在这有限个点上的函数值（即一张函数表)来分析函数f(x)的性态，甚至直接求出其它一些点上的函数值可能是十分困难的。

在有些情况下，虽然可以写出函数f(x)的解析表达式，但由于结构相当复杂，使用起来很不方便。面对这些情况，总希望根据所得函数表（或结构复杂的解析表达式），构造某个简单函数P(x)作为

f(x)的近似。

插值法是解决这类问题的一种比较古老，然而却是目前常用的方法，它不仅直接广泛应用于生产实际和科学研究中，而且也是进一步学习数值分析计算方法的基础。

插值函数类Φ的取法不同，所求得的插值函数p(x)逼近f(x)的效果就不同。而它的选择主要取决于使用需要。常用的代数多项式、三角多项式和有理函数等。当选用代数多项式作为插值函数时，相应的插值问题就称为多项式插值。本章讨论的即为此类问题。在多项式插值中，最常见、最基本的问题是：求一个次数不超过n的代数多项式：使（2）（3）其中为变数意义同前满足插值条件（3）的多项式（2）称为函数f(x)在节点（i=0，1…n）

求函数f(x)的n次插值多项式的几何意义是：通过曲线y=f(x)上的n+1个点（处的n次插值多项式。）（i=0,1…n）作一条n次代数曲线y=(x)作为曲线y=f(x)的近似。如下图。设p(x)是形如（2）的插值多项式，用代表所有次数不超过n的

多项式集合，于是p(x)，所谓插值多项式p(x)存在唯一，就是

指在集合中有且只有一个p(x)满足（3）。由（3）得：y0xba§2Lagrange插值一插值多项式的存在唯一性(4)

这是一个关于的n+1元线性方程组。

要证明插值多项式存在且唯一，只要证明方程组（4）存在唯一的解，也就是证明方程组（4）的系数行列式（5）不为零，式中称为范德蒙（Vandermonde)行列式。

利用行列式性质可得：定理1：若节点互不相同，则满足插值条件（3）的n次插值多项式（2）存在且唯一。由定理1的证明可见，要求插值多项式p(x)，可以通过求方程组（4）的解:时由于，故所有因子，于是故方程组（4）存在唯一的一组解由此有结论：二线性插值与抛物插值得到。但这样做不但计算复杂，而且难于得到P(x)的简单表达式。为求得便于使用的简单插值多项式p(x)，我们先讨论n=1的情形。y0x要求线性插值多项式

假定已知区间（6）的线性组合得到的。其系数分别为（7）（点斜式）（两点式）yx010xy1（j=k-1,k)

(j=k-1,k+1)(j=k,k+1)从而：同理可得：y10xy1xy01x定义1：若n次多项式(11)上面找的对n=1及n=2的情况，得到了一次与二次插值多项式(10)(12)(k=0,1…n)三拉格朗日插值多项式

四插值余项(15)(13)(14)（16）定理2：n=2，抛物插值的余项为：(17)

在许多情况下，直接用插值余项公式（16）来估计误差是困难的。下面以线性插值为例，介绍另一种估计误差的方法。(18)五插值误差的事后估计法§3逐次线性插值法由（18）可见，可以通过两个结果的偏差来估计插值误差为克服这一缺点，通常可用逐次线性插值方法求得高次插值。例如在前例中：则现在令表示函数关于节点的n-1次插值多项式，是零次多项式,,i1,…,in均为非负整数。一般地，两k次插值多次式可通过线性插值得到（k+1）次插值多项式：(19)是关于x插值多项式，显然

i=0，1，2~~~~~~k-1时而从而证明了插值多项式(19)满足插值条件。我们称(19)为AITKEN（埃特金）逐次线性插值多项式当k=0时为线性插值。k=1时插值节点为三点，公式为计算时可由k=0到k=n-1逐次求得所需的插值多项式。计算过程如下公式(19)也可以改成下面的计算公式(20)称之为NEVILLE（列维尔）算法，计算过程如下从表上看每增加一个节点就计算一行，斜线上是1次到4次插值多项式的值，如精度不满足要求，再增加一个节点，前面计算完全有效，这个算法适用于计算机上计算，且具有自动选节点并逐步比较精度的特点，程序也比较简单。算例见教材(略）。

的线性组合，即可以把满足插值条件P（xi）=yi的n次插值多项式写成

由线性代数知，任何一个不高于n次的多项式都可以表示成函数:§4均差与牛顿插值公式

其中ak(k=0,1,2…n)待定系数这种形式的插值多项式称为NEWTON插值多项式。即牛顿插值多项式是插值多项式的另一种表示形式。与Lagrange插值多项式相比，它不仅克服了增加一个节点时整个计算工作必须重新开始的缺点，而且可以节省乘除法运算次数，另外，在牛顿插值多项式中用到的差分差商的概念又与数值计算的其他方面有着直接的关系。一向前差分与牛顿向前插值公式设函数f（x）的等距节点处的函数值f（xk）=yk为已知，h为正常数，称为步长。称俩个相邻点xk+1与xk处函数值之差yk+1-yk为函数f（x）在点xk处以h为步长的一阶向前差分（简称一阶差分）记为从而函数f（x）在各节点处的一阶差分依次是：又称一阶差分的差分为二阶差分。一般的，定义函数f（x）在点x处的m阶差分为:为便于计算常,采用下面表格形式计算差分在等距节点情况下，可以利用差分表示牛顿插值多项式的系数，并将所得公式加以简化。这是因为：由插值条件称之为牛顿向前插值公式。则插值余项为:一般的，由可设：（利用归纳法证明）于是满足插值条件的插值多项式为解：因0.12介于0.1与0.2之间。故取为求构造插分表如下。表中各数依次是sinx在x=0.1处的函数值和各阶差分。=0.09983+0.2X0.09884=0.11960若用线性插值求sin（0.12）的近似值有：牛顿向前插值公式适合于计算函数表表头处附近的函数值。例：从给定的正弦函数表（见下表左边俩列）出发计算sin(0.12)并估计截断误差。Sin(0.12)用二次插值得:用三次插值得因此很接近，且由插值表可以看出三阶差分接近于常数，故取=0.11971为sin(0.12)的近似值此时由余项公式可知截断误差为：在等距节点下，还可以引入向后差分和中心差分。定义如下：y=f(x)在xk处以h为步长的一阶中心差分和m阶向后差分为二向后差分与牛顿向后插值公式y=f(x)在xk点处以h为步长的一阶中心差分和m阶中心差分:各阶向后差分与中心差分的计算均可类似如向前差分，构造向后差分与中心差分表来完成计算。

若将节点排列顺序，则（1）可以写为：利用向后差分也可用于构造牛顿插值公式，导出类似牛顿向后插值公式。这是因为：利用插值公式的条件与导出（2）的方法类似可得一个向后差分表示的插值多项式：(其中

t<0),称之为牛顿向后插值公式简称向后插值公式，（4）适合于计算函数值表表尾x处的函数值。例：已知函数表同上表，计算sin(0.58)的近似值，并估计截断误差.解：因x=0.58位于表尾附近，故用后插公式计算sin(0.58)的近似值。插值余项公式为:为了计算函数在处的各阶向后差分，应构造向后差分表。但由向前向后差定义可见，对于同一函数表来说，构造出来的向前差分向后差分再数值上完全相同，因此上表中的数据依次给出了sinx在x=0.6处的函数值和各阶向后差分值。于是由后插公式（4）可得：因三阶向后差分接近于常数，故用三次插值进行计算，且由（5）可知截断误差为：三差商与牛顿基本多项式

与自变量之差

的比值设f(x)在一串互异点上的值依次表示为

当插值节点非等距分布时，就不能引入差分来简化牛顿插值多项式。因此就要用到差商（又称均差）这个新概念。,称函数值之差为函数f(x)关于点的一阶差商。记为一般的可用f(x)的m-1阶差商定义f(x)的m阶差商如下：

的二阶差商记做如又称为一阶差商的差商为f(x)关于点又如：和计算差分类似，在计算差商时常采用表格形式如下所示：差商具有下列重要性质：的线形组合表示

,且：（1）函数f(x)的m阶差商可由函数值（2）差商具有对称性，即任意调换差商的节点的次序，不会影响差商的值，例如引入差商的概念后可以像确定前插公式中的系数那样逐步地确定（1）的系数：的n次插值多项式为：故满足插值条件称之为Newton的基本插值多项式。x一阶均差二阶均差

100101211114412解:利用此公式来计算非等距节点上的函数值。基本插值公式计算的近似值。

Newton基本插值多项式的截断误差为：由表可见Newton基本插值多项式（6）中各系数依次为：故用线形插值所求的近似值为：用抛物插值所求的近似值为：这里所求结果与前面例中计算一致。但计算量却明显减少。可以利用公式（7）计算上例中的截断误差。是我们要计算的，故不能准确的计算出确值，只能作出一种估计，例如，当四阶差商变化不大时

最后，我们指出，在带有差商的差商型的插值公式中，为了计算差商需要进行多次除法，因此当节点等距时，应当用差分代替差商，若节点是可以随意取的，则自然应当选为等距的。此外，利用差分作插值多项式，也要合理地决定差分的阶数，以避免高阶差分的误差积累，而这种积累有时是很严重的。请看下例。例：求序列{0，0，0，，0，0，0}的差分表

表中仅有一个微小误差，但在各阶差分中，随着差分的阶数的增高，误差影响增大很快，到了六阶差分时，误差积累已达.000000

通常差分阶数选取的一般原则为，当差分表中的k阶差分等于（或近似等于）0时，则插值多项式的差分阶数只选取到k-1阶。

上面讨论差商时，节点彼此相异。下面引入带重合节点的差商概念。若存在。则定义四带重合节点的差商解：方法一：由于插值条件有5个，因此可令对于n+1个相同的节点，则定义利用带重合节点差商的概念，为讨论带导数插值问题提供了一个方便的解决办法。例：求一个次数不高于4的多项式P(x)使：（前一部分为Newton基本插值公式，后一部分为满足导数要求及插值次数要求的最高形式）作差商表:0013339再利用题中给出的条件即可解方程组求出系数但此法很繁，不宜采用。方法三视重合节点为两个节点，并注意可作差商表：可得出：A=1，B=0因此计算结果同方法二，但计算过程简单得多。然后利用条件5，即P（3）=39定出A，但此过程不如方法三简炼。另外，也可以用前面4个条件作出Hermite插值多项式H(x)，再

若由条件（1）直接求这2n+2个未知系数，其过程将非常复杂。因此，我们仍采用Lagrange插值多项式的基函数方法。

不少实际问题不但要求在节点上的函数值相等，而且还要求它的导数值也相等，甚至高阶导数也相等。满足这种要求的插值多项式就是Hermite（埃尔米特）插值多项式。§6Hermite插值

下面只讨论函数值与导数值个数相等的情况。设在节点从而满足条件（1）的插值多项式H(x)=可写成：(3)由条件（2）显然下面就来求满足条件（2）的基函数令：为此，利用Lagrange插值多项式

先求插值基函数每个基函数都是2n+1次多项式。满足：(2)(4)由条件（2）有：整理得：同理可证(5)还可以证明满足条件（1）的插值多项式是唯一的。定理：y=f(x)在插值区间[a,b]存在2n+2阶导数。则Hermite插值公式的余项为：(6)利用反证法，设及上均有二重根，即有2n+2重根，但是不高于2n+1次的多项式。故。因此唯一性得证。均满足条件（1）。由于在节点的二重零点。故对插值区间中任一定点x，可设此处k(x)为待定函数。令：有2n+3个零点.的二重零点，（二重零点按二个零点计）。利用洛尔定理:在插值区间[a,b]中是首项系数为1的2n+2次多项式，H(z)是2n+1次多项式，因此可取节点为插值多项式为满足条件：作为带导数的插值多项式（3）的重要特例是n=1的情形。这时相应的插值基函数为它们满足条件：由(4),(5)的一般形式可得：

于是满足条件(7)的插值多项式是：插值余项例：求满足的插值多项式及余项表达式。项式通过故其形式为：解：由给定条件可确定次数不超过3的插值多项式。由于此多其中A为待定系数，可由条件确定，通过计算可得：§7分段低次插值一多项式插值的问题-5实线虚线yx0图2-11二分段线性插值三分段三次Hermite插值综合示例X-2-10123-5111725X2.42.52.6f(x)0.0025-0.0484-0.0968Xy2.40.0025-0.05092.5-0.04840.00252.6-0.0968-0.0484X123y24123x

yf[0,1]f[0,1,2]f[0,1,2,3]122122435248312§8三次样条插值一三次样条插值函数的定义二边界条件问题的提出与类型因此要定这4n个待定系数，还缺少两个条件，这两个条件常在插值区间[a,b]的边界点a,b处给出，称为边界条件。虽然可利用方程组(1)和边界条件求出所有待定系数从而得到三次样条函数在的表达式，但这样做工作量太大，不便于应用，下面介绍一种简便求法。设在节点处的二阶导数为因为在子区间上是不高于三次的多项式，其二阶导数必是线性函数（或常数），于是有：三三次样条插值函数的求法

.在本例中，将代入整理后可得：故所求三次样条插值函数为：上述三次样条插值的基本思想和特点是：先利用一阶导数在内节点上的连续性以及边界条件列出确定二阶导数的线性方程组（力学上称为三弯矩方组），由此解出，再用来表达S(x)。实际上，还可以通过别的途径来求取三次样条插值函数。如：可以先利用二阶导数在内节点上的连续性及边界条件，列出确定一阶导数的线性方程组（力学上称为三转角方程组），由此解出，再用表达S(x),在某些情况下，这种方法比前者更简单适用，参见教材。

2.8正交多项式和最佳平方逼近

正交多项式是数值计算中的重要工具，这里只介绍正交多项式的基本概念、某些性质和构造方法。离散情形的正交多项式用于下节的数据拟合，连续情形的正交多项式用于生成最佳平方逼近多项式和下章的高斯型求积公式的构造。它们在数值分析的其他领域中也有不少应用。2.8.1离散点集上的正交多项式

设有点集，函数和在离散意义下的内积定义为其中为给定的权数。在离散意义下，函数的2范数定义为(2.8.1)

有了内积，就可以定义正交性。若函数和的内积，则称两者正交。若多项式组在离散意义下的内积满足(2.8.2)(2.8.3)则称多项式组为在离散点集上的带权的正交多项式序列。下面给出离散点上正交多项式的构造方法.

给定点集和权数，并且点集中至少有个互异，则由下列三项递推公式

（2.8.4）给出的多项式序列是正交多项式序列，其中(2.8.5)

三项递推公式（2.8.4）是构造正交多项式的简单公式，此外，还有其他的特殊的情形，这里，不进一步讨论。

例2.10已知点集和权数试用三项递推公式求关于该点集的正交多项式。解先令，由此得由此得从而有2.8.2连续区间上正交多项式

连续区间上的正交多项式的概念与离散点集上的正交多项式概念相似，只要将内积的定义作相应的改变。函数和在连续意义下的内积定义为（2.8.6）其中的为给定的权函数。按连续意义下的内积，若多项式组满足条件(2.8.3)则称它为区间上的带权的正交多项式序列。

完全类似于离散情况下的正交多项式的构造方法,连续区间上的正交多项式序列同样可以由递推公式(2.8.4)和(2.8.5)构造,其中内积按(2.8.6)式定义。

下面给出几种常用的正交多项式。

(1)Legendre多项式。

Legendre多项式可由三项递推公式(2.8.7)给出.它们是在区间上的带权的正交多项式.前几个Legendre多项式如下:它们的根都是在开区间上的单根,并且与原点对称。(2)第一类Chebyshev多项式。第一类Chebyshev多项式可由三项递推公式(2.8.8)它们的根都在开区间（-1，1）上的单根，并且与原点对称。给出.它们是在区间上的带权的正交多项式。前几个第一类Chebyshev多项式如下:（3）Laguerre多项式。

Laguerre多项式可由三项递推公式给出。它们是在区间[0，+∞)上带权的正交多项式。前几个Laguerre多项式如下:它们的根都是在区间（0，+∞）上的单根。(4)Hermite多项式Hermite多项式可由三项递推公式给出。它们是在区间（-∞，+∞）上带权的正交多项式。前几个Hermite多项式如下：它们的根都在区间（-∞，+∞）上的单根，并且与原点对称。2.8.3连续函数的最佳平方逼近

连续函数空间C[a,b]上定义了内积（2.8.6）就形成了一个内积空间。在Rn空间中任一向量都可用它的线性无关的基表示，类似地，对内积空间任一元素f(x)∈C[a,b]，也可用线性无关的基表示。

设在[a,b]上连续，如果当且仅当时成立，则称在[a,b]上是线性无关的。对于函数组的线性无关性，有如下定理。

定理2.6

在[a,b]上线性无关的充要条件是它的Gramer行列式Gn≠０，其中

下面我们先讨论在区间[a,b]上一般的最佳平方逼近问题。设是C[a,b]中的线性无关函数，记:对于f(x)∈C[a,b],若存在子集，使得

则称是f(x)在子集中的最佳平方逼近函数。求等价于求多元函数的极小值。利用多元函数求极小值的必要条件有：按内积的定义，上式可写为这是关于ak的线性方程组，称为法方程。由于线性无关，故（2.8.12）的系数矩阵非奇异，于是（2.8.12）有唯一解。从而得到该式满足（2.8.11），即对任意，有事实上，由（2.8.12）知

因此，对任意，有，从而也有。于是这就证明了（2.8.14），从而也证明了f在子集

中的最佳平方逼近的存在唯一性。称

(2.8.15)为平方误差。

考虑特殊情形，设[a,b]=[0,1],。对于f∈C[a,b],在中最佳平方逼近多项式可以表示为相应于法方程（2.8.12）中的系数矩阵为称之为Hilbert矩阵例2.11设，求[0，1]上的一次最佳平方逼近多项式。平方误差:

由于Hilbert矩阵是病态的（见后面的章节），用作基时，求法方程的解，舍入误差很大。实用的办法是采用正交多项式作基。解由于得方程组解得a0=0.934,a1=0.426。从而最佳平方逼近为

若是正交多项式组，则由（2.8.12）得。于是f(x)的最佳平方逼近多项式为。

例2.12设f(x)=ex,在[-1,1]上用Legendre多项式作f

的三次多次最佳平方逼近多项式。

解用Legendre多项式Pk(x)(k=0,1,2,3),可得:于是最佳平方逼近为。平方误差2.9离散数据的曲线拟合2.9.1最小二乘拟合对于已知的m+1的离散数据和权数，记。在连续函数空间C[a,b]中选定n+1个线性无关的基函数，并记由它们生成的子空间。由求多元函数极值的必要条件有按内积的定义，上式可写为（2.9.3）这方程称为法方程(或正规方程)。这里，

由于线性无关，故（2.9.3）的系数矩阵非奇异，方程组（2.9.3）存在唯一的解从而得可以证明，这样得到的，对于任何，都有故是所求的最小二乘拟合。记，显然，平方误差或均方误差越小，拟合的效果越好。平方误差有与（2.8.15）相同形式的表达式2.9.2多项式拟合即在多项式空间中作曲线拟合，称为多项式拟合。这是一种特定的线性模型，因此可用上面讨论的方法求解。

前面讨论了子空间中的最小二乘拟合。这是一种线性拟合模型。在离散数据的最小二乘拟合中，最简单、最常用的数学模型是多项式

例2.13

用多项式拟合表2-7中的离散数据。yi0.100.350.811.091.96xi0.000.250.500.751.00i01234表2-7解作数据点的图形如图2-2，从图形看出用二次多项式拟合比较合适。这时n=2，子空间的基函数。数据中没有给出权数，不妨都取为1，即。oy1.961x****图2-2按（2.9.3）有

解此方程组得。从而，拟合多项式为其平方误差。拟合曲线的图形见图2-2。

在许多实际问题中，变量之间的关系不一定能用多项式很好的拟合。如何找到更符合实际情况的数据拟合，一方面要根据专业知识和经验来确定拟合曲线的形式，另一方面要根据数据点的图形性状及特点来选择适当的曲线拟合这些数据。

例2.14已知函数y=f(x)的数据如表2-8。试选择适当的数学模型进行拟合。yi4.006.418.018.799.539.8610.3310.4210.5310.61xi12346810121416i0123456789表2-8

解(1)观察数据点的图形(见图2-3),选择二次多项式作为拟合模型。取所有权数为1，按（2.9.3）有(2)从数据的图形看，可以选用指数函数进行拟合。设，其中。这是一个非线性模型，不能直接用上面讨论的方法求解。对于一般的非线性最小二乘问题，用常规方法求解的难度较大。这里的非线性模型比较简单，可以把它转化成线性模型，然后用上面讨论的方法求解。对说函数的两边取自然对数，得。若令，则有z=A+βt。这是一个线性模型。将本题离散数据作相应的转换，见表2-9。解得，从而拟合函数为平方差