交大硕士研究生必修基础数学-数值分析-插值与拟合方法.doc

第5章 插值与拟合方法插值与拟合方法是用有限个函数值去推断或表示函数的方法，它在理论数学中提到的不多。本章主要介绍有关解决这类问题的理论和方法，涉及的内容有多项式插值，分段插值及曲线拟合等。对应的方法有Lagrange插值，Newton插值，Hermite插值，分段多项式插值和线性最小二乘拟合。1 实际案例2 问题的描述与基本概念先获得函数（已知或未知）在有限个点上的值 由表中数据构造一个函数P(x)作为f (x) 的近似函数，去参与有关f (x)的运算。科学计算中，解决不易求出的未知函数的问题主要采用插值和拟合两种方法。1）插值问题的描述已知函数在a,b上的n+1个互异点处的函数值，求f (x) 的一个近似函数P (x)，满足 （5.1）l P (x) 称为f (x)的一个插值函数;l f (x) 称为被插函数;点为插值节点;l 称为插值条件;l 称为插值余项。当插值函数P (x)是多项式时称为代数插值（或多项式插值）。一个代数插值函数P (x)可写为 若它满足插值条件（5.1），则有线性方程组 （5.2）当m=n，它的系数行列式为范德蒙行列式因为插值节点互异，故线性方程组（5.2）有唯一解，于是有定理5.1 当插值节点互异时，存在一个满足插值条件的n次插值多项式。定理 满足插值条件(5.1)的n次插值多项式是唯一的。证明 设是两个满足插值条件(5.1)的n次插值多项式，于是有令显然有是次数n的多项式，且说明有n+1个零点，由代数基本定理有H (x) 0，由此得。插值的一个目的是对函数作近似计算。假设a, b 是包含插值点的最小闭区间，当用插值函数P(x)来近似计算x在a, b的函数值时，称为内插计算，否则称为外插或外推计算。2）拟合问题的描述已知在a,b上的n+1个(互异或不互异)点处的函数值，求f (x) 的一个近似函数，满足拟合条件这里是n+1维向量，是某种范数，。求出的称为拟合函数。3）插值函数和拟合函数的几何解释1) 插值函数图示 2）拟合函数图示5.3插值法1. Lagrange插值Lagrange插值是 n次多项式插值。基本思想将待求的n次多项式插值函数改写成用已知函数值为系数的n+1个待定n次多项式的线性组合型式，再利用插值条件和函数分解技术确定n+1个待定n次多项式形式求出插值多项式。1) 构造原理已知数表 设n次插值多项式 （5.3）式中是与无关的n次多项式。由插值条件（5.1），有由于与无关，可得 （5.4）为确定，注意到是n次多项式，由式（5.4）可知式中a为待定常数，由确定，于是有 （5.5）代入式（5.3），有 （5.6）由n次插值多项式的唯一性，可知就是所求的n次插值多项式。式（5.6）称为n次Lagrange插值多项式，而称为 Lagrange插值基函数。2) 分析定理3. 设函数在a,b上有n+1阶导数，是满足插值条件的n次插值多项式，则有对任何成立 式中。证明 因为，故有于是Rn（x）可分解为 （5.8）为求出k(x)，做辅助函数 （5.9） 则有在时，g(t)=0，即g(t)在a,b上有n+2个零点。显然g(t)在由组成的n+1个小闭区间上满足Rolle中值定理，故g(t) 在a,b上有n+1个零点。类似的有g(t) 在a,b上有n个零点，反复运用Rolle中值定理，有在a,b上有1个零点，设为x，则有。在式（5.9）两边对t求n+1阶导数，有将t =x 代入上式，解得代入式（5.8），即得定理结果。定理3中若能算出在a,b上的最大值，则有余项估计式 （在一点的误差估计）若想估计函数在插值区间a,b上的误差，要计算出，此时有区间a,b上的误差估计为 由n次插值多项式的唯一性及式（5.7），得到有如下重要结果定理4 若函数f ( x )在a,b上有n+1阶导数，则f ( x )可表示为对n=1的插值多项式，称为线性插值；n=2的插值多项式称为抛物线插值或辛普森插值.例1 已知的函数表为x3.03.13.23.33.4y=f(x)1.0986121.1314021.1631511.1939221.223775试用线性插值和抛物线插值分别计算的近似值，并估计相应的误差。解 线性插值需要两个节点，内插比外推好，因为，故选，由的Lagrange 插值公式，有所以有为保证内插，对抛物线插值，选取三个节点为由n=2的Lagrange 插值公式，有故有考虑误差.当时，有，所以线性插值计算的误差估计为而当时，故抛物线插值计算的误差估计为例2在上给出的等距节点函数表，若想用二次插值来计算的近似值，并要求截断误差不超过，问此函数表的步长h应为多少？解 设为上的等距节点。二次插值需要三个节点，为满足一般性，这里取三个相邻的节点构造二次插值函数。设是上的任何三个相邻节点，则当时，有注意到。利用n=2的Lagrange余项定理，有函数在的插值余项为因为 ,所以 要，只需，得取h=0.0057可满足要求.由得，故造表时取1405个等距节点来计算函数值即可。2. Newton 插值Newton插值也是n次多项式插值。1) 构造原理已知数表 设n次插值多项式为为求出 的系数，借助插值条件有当时，有，得出;当时，有,得依次取并利用插值条件就可依次解出，从而求出的具体形式。为将解出的系数用公式表示出来，引进差商的概念。定义 已知函数f(x)在互异节点上的值分别为，记式中是中互不相同的k+1个节点，称为f(x)关于节点的k阶差商。规定零阶差商是函数值本身，于是一阶差商可写为表.1 差商表xf(x)一阶差商二阶差商n阶差商.2) 分析定理5 满足插值条件的n次Newton插值多项式的余项为 （5.14）证明 设xa,b，且是异于的任一点，则有以为插值节点的n+1次Newton插值多项式注意到，上式当t = x时，有。将t = x代入上式有显然（5.14）式对 时也成立。利用插值的唯一性，由可以得到差商与微商之间的关系。例3 给定数表x124568f(x)028121828试用二次和四次Newton插值多项式计算的近似值。解 作差商表xf(x)一阶差商二阶差商三阶差商四阶差商五阶差商1021/301/30-1/602231/31/6-1/124841-1/35126-1/36185828用二阶Newton插值近似计算，应选与5.8最近的3个节点。由表中行数据有所以有。要用来计算，取与5.8最近的5个节点由表中行数据有 所以。3. Hermite插值例4设有四阶导数，且，1）求函数的一个插值多项式，并用此近似函数来计算的近似值2）给出你所得插值多项式的误差关系式，估计近似计算的误差。解 仿照Lagrange插值函数的构造方法来做之。给定4个数据信息，选择3次多项式作为的插值多项式。令的3次插值多项式为式中都是与无关的3次多项式。插值的特点是插值函数要与给定的关于的所有数据相等，即满足插值条件由此可得有关的一组值利用这组数据，可得函数分解形式并求出。为求，找到与之有关的数据由该数据可知x=2是的二重根，且是3次多项式，故可设的分解形式为由，可以求出式中的a,b，最后求得类似地可以求出其它3个待定函数故有所求插值函数从而有，为求其余项，令由，有可分解为为求出k（x），做辅助函数 （5.18） 则有在t =1，2，x时，g(t)=0，g(t)在a,b上有3个零点。g(t)在由 1，2，x组成的2个闭区间上满足Rolle中值定理，故g(t) 在1,2上有2个零点，另一方面，有g(1)= g(2)=0，故g(t) 在1,2上有4个零点，类似的原因，有g(t) 在1,2上有3个零点，反复运用Rolle中值定理，就有在1,2上有1个零点,设为x，则有。在式（4.18）两边对t求4阶导数，有将t =x 代入上式，解得于是得出余项公式近似计算的误差为上面的例子反映了Hermite插值的做法。Hermite插值提法提法为：给定n+1个互异的节点上的函数值和导数值 求一个2n+1次多项式满足插值条件 （5.19） 如上求出的称为2n+1次Hermite插值函数，它与被插函数一般有更好的密合度。基本思想仿照Lagrange插值函数的构造方法，先设定函数形式，再利用插值条件求出插值函数。例 5已知函数的4个数值为 试求的一个插值多项式，这里满足插值条件。 写出的误差估计式。解 因为有4个值，故取P（x）为三次多项式，令式中都是三次多项式。由插值条件有当时，得当x=2时，可得利用的4个值，及是三次多项式，可设由，得c = -1；由，得b = -1；由，得a =-1,于是有同理可设由在x =1,x =2的值可得于是所求 观察余项在x=1，x=2的信息，可写出误差关系为4.分段多项式插值被插函数在-5,5的n+1个等距节点计算出获得实验数据后，可以得到的Lagrange插值多项式。考虑-5,5上的一点，分别取n=2，6，10，14，18计算及相应的误差，得下表n261014180.1379310.0544630.0470590.0443340.0429200.7596150.6078791.5787215.33274320.123671-0.621684-0.533416-1.531662-5.288409-20.080751易见随n增加，没减小，却增大。Runge现象定义2 取a，b上n+1个节点及函数值 。若函数满足在a，b上连续；（k=0，1，n）；在每个小区间是m次多项式则称为在a，b上的分段m次插值多项式。基本思想将被插函数的插值节点由小到大排序，以每对相邻的两个节点为端点获得若干个小区间，然后在每个小区间上都用的m次插值多项式作为的近似函数。1) 构造原理(1）分段线性插值的构造原理分段线性插值是定义2中的m=1情形。设为任何连个相邻插值点，于是在上分段线性插值函数是一次多项式。利用上的插值数据用n=1的Lagrange插值构造，于是有易验证，满足定义2，故是所求的分段线性多项式插值。(2）分段三次Hermite插值设是任何两个相邻节点构成的区间，在上的插值数据为要使分段插值函数满足且在是三次多项式，自然想到两点Hermite插值公式。取对应的两点Hermite插值作为所求在上的插值多项式，有式中 .此满足定义4.2，且在每点导数连续，在整个区间上还有连续导数，称为分段三次Hermite插值函数。2）分析定理 8 假设出现在如下不等式中的函数的高阶导数存在，记，则有1. 分段线性插值的误差估计为2. 分段三次Hermite插值函数的误差估计为证明 只对结果2给出证明，结果1可类似证明。由两点的Hermite插值余项可知，在区间上，分段三次Hermite插值函数与被插值函数的误差关系式又因为故对k= 0，1，n有 注意到上式右端与x属于哪个小区间无关，这就证明了结果2。分段插值的编程计算简单，只要先编写一个在任一段上的低次插值通用子程序，然后根据要计算的自变的值选定所属的子区间，再调用子程序计算即可。5. 三次样条插值分段线性插值在连接点处常有“尖点”出现；分段三次 Hermite插值在连接点处不一定曲率连续，且要求知道所有节点处的一阶导数值。能否找到只用节点的函数值和一些较少的信息就可以构造出具有更好几何特性的分段插值函数呢？三次样条插值给出了肯定的回答。样条（Spline）是一种细长有弹性的软木条，常用来做工程设计中的绘图工具绘出一条光滑曲线。将它进行数学描述，就得到如下三次样条函数的定义。定义3 设函数定义在区间上，对给定的一个分划若满足下列条件在上有二阶连续导数；在每个小区间都是一个三次多项式。则称函数是关于分划的一个三次样条函数，若同时还满足则称是在上关于划分的三次样条插值函数。基本思想利用三次样条插值函数定义的条件及在内节点的函数和导数的连续性质，建立关系式来确定样条插值函数。1) 构造原理要知道的事情：1.三次样条插值函数在每个上都是三次多项式，故在每个上有4个待定系数；2.因为共有n个小区间，故共有4n个待定系数要确定；3.在n-1个内结点有直到二阶的连续导数，可以得到个条件；4.由插值条件可有n+1个条件故共有4n-2个条件，要想唯一确定还应另加两个条件才行。三次样条函数插值常引入边界条件来作为所需的两个条件。常用的边界条件有如下三类）给定两个端点二阶导数值，并令当时，称为自然边界条件。）给定两个端点一阶导数值，并令）给定第类边界条件称为周期性边界条件，专用于是以为周期的函数的样条插值。l 构造三次样条插值函数的M方法推导过程：设， ，考虑在任一个小区间上的表示形式。由定义，是三次多项式，故在是一次多项式，可以表示为 做两次积分，并利用，有于是只要求出，就求得了。l 求的处理方法利用在内节点处一阶导数连续的条件来做由式表达关系有 有再由，得对型边界条件，可得另外两个方程为若令则的关系式可写为矩阵形式对型边界条件，由于与已知，可得方程组对型边界条件，由可得方程组都称为M关系式，易验证它们都是严格对角占优的。l 求三次样条插值函数的算法计算出 （k=0，1，n）；对不同的边界条件选择相应的M关系式，并进行求解，得的值；求三次样条插值函数。定理 9 设在上有4阶导数，是具有边界条件或的三次样条插值函数，则有估计式 ，5.4曲线拟合法曲线拟合也是一种求近似函数的方法，本节主要介绍线性最小二乘拟合方法，这里的线性指所求的拟合函数是某些已知函数组的线性组合。该方法是曲线拟合中最简单最常用的方法。记M常称为拟合函数类，M中的函数称为基函数，它们应该是线性无关的。若M中的基函数，则M就是m次多项式函数类。由离散数据获得的曲线拟合函数称为经验公式。基本思想根据给定的数据点，选择合适的拟合函数类M，再利用最小二乘法确定具体的拟合函数。1. 构造原理设所求的拟合函数，则有为确定系数，考虑函数与在节点处差的平方加权和式中是已知的数。由极值必要条件有化简得到关于系数的线性方程组：引入内积符号，上式可写为这个方程组称为法方程组或正规方程组。可以证明当线性无关时，法方程组是对称正定的，因此有唯一解。于是多元函数有唯一驻点。注意到的最小值是存在的，因此就是的最小值点，从而函数就是所要的曲线拟合函数。讨论的问题归为求解法方程组问题。定义5 设，给定n+1个节点，若有函数，满足则称为在n+1个节点上关于权的最小二乘解，而称求的方法为最小二乘法。曲线拟合的误差常用所求出的拟合函数在所给拟合点与被拟合函数误差加权平方和来表示，它称为平方误差。l 求曲线拟合的算法1)由数据点绘出散点图；2)选择合适的拟合函数类M；3)构造对应的法方程组，并求解得到具体的拟合函数。2. 分 析当是多项式集时，由求出的最小二乘解称为最小二乘多项式。当时，拟合函数（m次多项式）对应的法方程组为在m4可用来最小二乘多项式，但当m4时，它往往是病态的，不能用最小二乘多项式。为避免病态，把基函数组选为正交函数组即可。定义4.6 设函数组在区间a，b上有定义，点集，权系数，如果内积则称函数组是关于的带权正交函数组。比较向量正交定义！当是关于的带权正交函数组时，其法方程组就变为对角方程组它不涉及病态方程组问题，可以很容易解出其对应的最小二乘解用Gram-Schmidt正交化方法构造正交函数组的算法，其中符号。l Gram-Schmidt正交化算法该算法得到首项系数为1的关于点集的带权正交多项式组。当曲线拟合函数是m次多项式时，称为m次拟合曲线。例7给定数据表xi-3-1013yi-1.21.31.51.92求二次拟合曲线。解 求二次拟合曲线就是求2次最小二乘多项式，由于没给出权系数，可选。下面用两种方法求解。方法1取基函数，则二次拟合曲线函数形式为本题有5对数据，故，计算得法方程组解之得 ，故所求二次拟合曲线为方法2 选用正交基函数由正交化算法，有， ， ，故有 ，所求的二次拟合曲线为3.可用线性最小二乘拟合求解的非线性拟合类型1) 指数曲线拟合此时的拟合函数具有形式 （a，b为待定常数）对取自然对数，有令，则有线性模型：用本节方法求出其最小二乘解再回代，求出原问题所要的曲线拟合函数2) 多变量线性拟合若拟合函数具有形式这里是待定常数，是自变量。注意到第k个自变