《数值积分》第二章-插值法

1、第 二 章 插 值 法,1 引 言,在生产和科研中出现的函数是多种多样的，常遇到这样的情况：在某个实际问题中，虽可断定所考虑的函数 f (x) 在区间 a , b 上存在且连续，但却难以找到它们的解析表达式，只能通过实验和观测得到在这有限个点上的函数值（即一张函数表)来分析函数 f (x ) 的性态，甚至直接求出其它一些点上的函数值可能是十分困难的。,在有些情况下，虽然可以写出函数 f ( x ) 的解析表达式，但由于结构相当复杂，使用起来很不方便。面对这些情况，总希望根据所得函数表（或结构复杂的解析表达式），构造某个简单函数 P( x ) 作为 f ( x ) 的近似。,插值法是解决这类问题

2、的一种比较古老，然而却是目前常用的方法，它不仅直接广泛应用于生产实际和科学研究中，而且也是进一步学习数值分析计算方法的基础。,插值函数类的取法不同，所求得的插值函数p(x)逼近f(x)的效果就不同。而它的选择主要取决于使用需要。常用的代数多项式、三角多项式和有理函数等。,当选用代数多项式作为插值函数时，相应的插值问题就称为多项式 插值。本章讨论的即为此类问题。,2 Lagrange插值,一 插值多项式的存在唯一性,(4),由定理1的证明可见，要求插值多项式 p(x)，可以通过求方程组（4）的解:,二 线性插值与抛物插值,（6）,(12) (k=0,1n),三 拉格朗日插值多项式,四 插值余项,

3、n=2，抛物插值的余项为：,(17),在许多情况下，直接用插值余项公式（16）来估计误差是困难 的。下面以线性插值为例，介绍另一种估计误差的方法。,(18),五 插值误差的事后估计法,3 逐次线性插值法,则,现在令 表示函数 关于节点 的n-1次插值多 项式， 是零次多项式, , i1,in均为非负整数。一般地，两k次插值多次式可通过线性插值得到（k+1）次插值多项式：,(19)是关于x插值多项式，显然 i=0，1，2k-1时 而,从而证明了插值多项式(19)满足插值条件。我们称(19)为AITKEN （埃特金）逐次线性插值多项式 当k=0时为线性插值。 k=1时插值节点为 三点，公式为 计算

4、时可由k=0到k=n-1逐次求得所需的插值多项式。计算过程如下,公式(19)也可以改成下面的计算公式 (20)称之为NEVILLE（列维尔）算法，计算过程如下,从表上看每增加一个节点就计算一行，斜线上是1次到4次插值多项式的值，如精度不满足要求，再增加一个节点，前面计算完全有效，这个算法适用于计算机 上计算，且具有自动选节点并逐步比较精度的特点，程序也比较简单。算例见教材(略）。,4 均差与牛顿插值公式,其中 ak(k=0,1,2n ) 待定系数这种形式的插值多项式称为NEWTON插值多项式。即牛顿插值多项式是插值多项式的另一种表示形式。与Lagrange插值多项式相比，它不仅克服了增加一个节

5、点时整个计算工作必须重新开始的缺点，而且可以节省乘除法运算次数，另外，在牛顿插值多项式中用到的差分差商的概念又与数值计算的其他方面有着直接的关系。,一 向前差分与牛顿向前插值公式,设函数f（x）的等距节点,处的函数值f（xk）=yk为已知，h为正常数，称为步长。称俩个相邻点xk+1与xk处函数值之差yk+1-yk为函数f（x）在点xk处以h为步长的一阶向前差分（简称一阶差分）记为,从而函数f（x）在各节点处的一阶差分依次是： 又称一阶差分的差分 为二阶差分。,一般的，定义函数f（x）在点x处的m阶差分为: 为便于计算常, 采用下面表格形式计算差分,在等距节点 情况下，可以利用差分表示牛顿插值多

6、项式的系数，并将所得公式加以简化。这是因为：由插值条件,称之为牛顿向前插值公式。则插值余项为:,解：因0.12介于0.1与0.2之间。故取 为求 构造插分表如下。表中各数依次是sinx在x=0.1处的函数值和各阶差分。,用三次插值得,因此 很接近，且由插值表可以看出三阶差分接近于常数，故取 =0.11971为sin(0.12)的近似值,此时由余项公式可知截断误差为：,在等距节点 下，还可以引入向后差分和中心差分。定义如下：y=f(x)在xk处以h为步长的一阶中心差分和m阶向后差分为,二 向后差分与牛顿向后插值公式,利用插值公式的条件 与导出（2）的方法类似可得一个向后差分表示的插值多项式：,(

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

8、m阶差商如下：,又如：,和计算差分类似，在计算差商时常采用表格形式如下所示：,差商具有下列重要性质：,引入 差商的概念后可以像 确定前插公式中的系数 那样逐步地确定（1）的系数：,称之为Newton 的基本插值多项式。,Newton基本插值多项式的截断误差为：,由表可见Newton基本插值多项式（6）中各系数依次为：,故用线形插值所求的近似值为：,可以利用公式（7）计算上例中的截断误差。,最后，我们指出，在带有差商的差商型的插值公式中， 为了计算差商需要进行多次除法，因此当节点等距时，应 当用差分代替差商，若节点是可以随意取的，则自然应当 选为等距的。此外，利用差分作插值多项式，也要合理 地决

9、定差分的阶数，以避免高阶差分的误差积累，而这种 积累有时是很严重的。请看下例。,表中仅有一个微小误差 ，但在各阶差分中，随着差分的阶数的增高，误差影响增大很快，到了六阶差分时，误差积累已达 .,通常差分阶数选取的一般原则为，当差分表中 的k阶差分等于（或近似等于）0时，则插值多项式的差 分阶数只选取到k-1阶。,四 带重合节点的差商,解：方法一： 由于插值条件有5个，因此可令,对于n+1个相同的节点，则定义,（前一部分为Newton基本插值公式，后一部分为满足导数 要求及插值次数要求的最高形式）,计算结果同方法二，但计算过程简单得多。,若由条件（1）直接求 这2n+2个未知系数，其过程将非常复

10、杂。因此，我们仍采用Lagrange插值多项式的基函数方法。,不少实际问题不但要求在节点上的函数值相等，而且 还要求它的导数值也相等，甚至高阶导数也相等。满足这 种要求的插值多项式就是Hermite（埃尔米特）插值多项式。,6 Hermite插值,下面只讨论函数值与导数值个数相等的情况。设在节点,(4),由条件（2）有：,整理得：,由于在节点,由(4),(5)的一般形式可得：,7 分段低次插值,一 多项式插值的问题,二 分段线性插值,三 分段三次Hermite插值,综合示例,X 1 2 3 y 2 4 12,3,x y f0,1 f0,1,2 f0,1,2,3 1 2 2 1 2 2 4 3

11、5 2 4 8 3 12,8 三次样条插值,一 三次样条插值函数的定义,二 边界条件问题的提出与类型,因此要定这4n个待定系数，还缺少两个条件，这两个条件常在插值区间a,b的边界点a,b处给出，称为边界条件。,虽然可利用方程组(1)和边界条件求出所有待定系数 从而得到三次样条函数在 的表达式 ，但这样做工作量太大，不便于应用，下面介绍一种简便求法。 设在节点 处 的二阶导数为,因为在子区间 上 是不高于三次的多项式，其二阶导 数 必是线性函数（或常数），于是有：,三 三次样条插值函数的求法,.,在本例中，将 代入整理后可得：,故所求三次样条插值函数为：,上述三次样条插值的基本思想和特点是：先利

12、用一阶导数 在内节点 上的连续性以及边界条件列出确定二阶导 数 的线性方程组（力学上称为三弯矩方组），由此解出 ，再用 来表达S(x)。,实际上，还可以通过别的途径来求取三次样条插值函数。如：可以 先利用二阶导数在内节点上的连续性及边界条件，列出确定一阶导 数 的线性方程组（力学上称为三转角方程组）， 由此解出 ，再用 表达 S(x),在某些情况下，这种方法比前者更简 单适用，参见教材 。,2.8 正交多项式和最佳平方逼近,正交多项式是数值计算中的重要工具，这里只介绍正交多项式的基本概念、某些性质和构造方法。离散情形的正交多项式用于下节的数据拟合，连续情形的正交多项式用于生成最佳平方逼近多项式

13、和下章的高斯型求积公式的构造。它们在数值分析的其他领域中也有不少应用。,试用三项递推公式求关于该点集的正交多项式 。,从而有,它们的根都是在开区间 上的单根,并且与原点对称。,（3）Laguerre多项式。 Laguerre 多项式可由三项递推公式,给出。它们是在区间0，+)上带权 的正交多项式。前几个Laguerre多项式如下:,它们的根都是在区间（0，+）上的单根。,(4) Hermite 多项式,Hermite多项式可由三项递推公式 给出。它们是在区间（-，+）上带权 的正交多项式。前几个Hermite多项式如下：,它们的根都在区间（-，+）上的单根，并且与原点对称。,2.8.3连续函数

14、的最佳平方逼近,连续函数空间Ca,b上定义了内积（2.8.6）就形成了一个内积空间。在Rn空间中任一向量都可用它的线性无关的基表示，类似地，对内积空间任一元素f(x) Ca,b，也可用线性无关的基表示。,设 在a,b上连续，如果 当且仅当 时成立，则称 在a,b上是线性无关的。对于函数组 的线性无关性，有如下定理。,定理2.6 在a,b上线性无关的充要条件是它的Gramer行列式Gn，其中,下面我们先讨论在区间a,b上 一般的最佳平方逼近问题。 设 是Ca,b中的线性无关函数，记: 对于f(x)Ca,b,若存在子集 ，使得 则称 是 f(x) 在子集 中的最佳平方逼近函数。,求 等价于求多元函

15、数 的极小值。利用多元函数求极小值的必要条件有：,按内积的定义，上式可写为 这是关于 ak 的线性方程组，称为法方程。,由于 线性无关，故（2.8.12）的系数矩阵非奇异， 于是（2.8.12）有唯一解 。从而得到,该式满足（2.8.11），即对任意 ，有 事实上，由（2.8.12）知,因此，对任意 ，有 ，从而也有 。于是 这就证明了（2.8.14），从而也证明了f 在子集 中的最佳平方逼近的存在唯一性。,称 (2.8.15) 为平方误差。,考虑特殊情形，设a,b=0,1, 。对于fCa,b, 在 中最佳平方逼近多项式可以表示为 相应于法方程（2.8.12）中的系数矩阵为 称之为Hilber

16、t矩阵,例2.11 设 ，求0，1上的一次最佳平方逼近多项式。,平方误差: 由于Hilbert矩阵是病态的（见后面的章节），用 作基时，求法方程的解，舍入误差很大。实用的办法是采用正交多项式作基。,解 由于,若 是正交多项式组，则由（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的离散数据 和

17、权数 ，记 。 在连续函数空间Ca,b中选定n+1个线性无关的基函数 ，并记由它们生成的子空间 。,由求多元函数极值的必要条件有,由于 线性无关，故（2.9.3）的系数矩阵非奇异，方程组 （2.9.3）存在唯一的解 从而得,可以证明，这样得到的 ，对于任何 ，都有,故 是所求的最小二乘拟合。记 ，显然，平方误差 或 均方误差 越小，拟合的效果越好。平方误差有与（2.8.15）相同形式的表达式,2.9.2 多项式拟合,解 作数据点的图形如图2-2，从图形看出用二次多项式拟合比较合适。这时n=2，子空间 的基函数 。数据中没有给出权数，不妨都取为1，即 。,其平方误差 。拟合曲线 的图形见图2-2

18、。,在许多实际问题中，变量之间的关系不一定能用多项式很好的拟合。如何找到更符合实际情况的数据拟合，一方面要根据专业知识和经验来确定拟合曲线的形式，另一方面要根据数据点的图形性状及特点来选择适当的曲线拟合这些数据。,解 (1)观察数据点的图形(见图2-3),选择二次多项式作为拟合模型。取所有权数为1，按（2.9.3）有,(2)从数据的图形看，可以选用指数函数进行拟合。设 ，其中 。这是一个非线性模型， 不能直接用上面讨论的方法求解。对于一般的非线性最小二乘问题，用常规方法求解的难度较大。这里的非线性模型比较简单，可以把它转化成线性模型，然后用上面讨论的方法求解。,对说函数 的两边取自然对数，得 。若令 ，则有z=A+t。这是一个线性模型。将本题离散数据作相应的转换，见表2-9。,对表2-9种的数据，作线性拟合，这时n=1，子空间的基函数为 。易