数值计算课程设计报告(插值法)

数值计算方法课程设计报告课程设计名称：数值计算方法课程设计题目：插值算法年级专业：信计1302班组员姓名学号：高育坤1309064043王冬妮1309064044韩建1309064046李婧1309064047指导教师：刘丽华完成时间：2015年6月17日插值算法一、问题提出插值法是实用的数值方法，是函数逼近的重要方法。在生产和科学实验中，自变量x与因变量y的函数y=f(x)的关系式有时不能直接写出表达式，而只能得到函数在若干个点的函数值或导数值。当要求知道观测点之外的函数值时，需要估计函数值在该点的值。如何根据观测点的值，构造一个比较简单的函数y=φ(x)，使函数在观测点的值等于已知的数值或导数值，进而用简单函数y=φ(x)在点x处的值来估计未知函数y=f(x)在x点的值。寻找这样的函数φ(x)，办法是很多的。φ(x)可以是一个代数多项式，或是三角多项式，也可以是有理分式；φ(x)可以是任意光滑（任意阶导数连续）的函数或是分段函数；函数类的不同，自然地有不同的逼近效果。二、背景分析在许多实际问题及科学研究中，因素之间往往存在着函数关系，然而，这种关系经常很难有明显的解析表达，通常只是由观察与测试得到一些离散数值。有时，即使给出了解析表达式，却由于表达式过于复杂，不仅使用不便，而且不易于进行计算与理论分析。解决这类问题的方法有两种：一种是插值法插值法，另一种是一拟合法。插值法是一种古老的数学方法，它来自生产实践，早在一千多年前，我国科学家在研究历法上就应用了线性插值与二次插值，但它的基本理论却是在微积分产生之后才逐渐完善的，其应用也日益增多，特别是在计算机软件中，许多库函数，如,cos,sinex等的计算实际上归结于它的逼近函数的计算。逼近函数一般为只含有算术运算的简单函数，如多项式、有理分式（即多项式的商）。在工程实际问题当中，我们也经常会碰到诸如此类的函数值计算问题。被计算的函数有时不容易直接计算，如表达式过于复杂或者只能通过某种手段获取该函数在某些点处的函数值信息或者导数值信息等。因此，我们希望能用一个“简单函数”逼近被计算函数，然后用该简单函数的函数值近似替代被计算函数的函数值。这种方法就叫插值逼近或者插值法。插值法要求给出函数f（x）的一个函数表，然后选定一种简单的函数形式，比如多项式、分段线性函数及三角多项式等，通过已知的函数表来确定一个简单的函数作为f（x）的近似，概括地说，就是用简单函数为离散数组建立连续模型。三、基本算法思想与实现已知1n个数据节点:,,,...2,1,0),,(不相同其中jjjxnjyxbxxxan...10不妨设构造一个(相对简单)函数)(xfy(称为插值函数),通过全部结点即jjyxf)(（j＝0,1,…n）再用)(xf计算插值，即**)(yxf数学上插值方法非常多，这里介绍几种常用方法：1·Lagrange插值函数Lagrange插值函数的基本思想:将待求的n次插值多项式()nPx写成另一种表达方,式再利用插值条件()iiyfx(0,1,2...)i确定出插值基函()ilx由基函数条件()1iilx,确定多项式系数，进而可得插值函数()nPx.（1）已知0011(),()fxyfxy，求满足条件的插值函数。由题可知()yfx表示过两点0011(,),(,)xyxy的直线，这个问题是我们所熟悉的，它的解可表为下列对称式01010110xxxxyyyxxxx0x1xnx0y1y此类一次插值称为线性插值，若令01010110(),()xxxxlxlxxxxx（由此可得：00011110()1,()0,()1,()0lxlxlxlx））则有10011()()()Pxlxylxy这里的01(),()lxlx可以看作是满足条件00011110()1,()0()1,()0lxlxlxlx的插值多项式，这两个特殊的插值多项式称作上述问题的插值基函数。（2）求过三点001122(,),(,),(,)xyxyxy的插值函数。为了得到插值多项式先解决一个特殊的二次插值问题。求作二次式0()lx，使满足000102()1,()()0lxlxlx（2-1）这个问题是容易求解的，由式（2-1）的后两个条件知12,xx是0()lx的两个零点，因而012()()()lxcxxxx。再用条件00()1lx确定系数c.结果得：1200102()()()()()xxxxlxxxxx类似可以分别构造出满足条件111012222021()1,()()0()1,()()0lxlxlxlxlxlx的插值多项式12(),()lxlx；其表达式分别为0211012()()()()()xxxxlxxxxx，0122021()()()()()xxxxlxxxxx这样构造出的012(),(),()lxlxlx称作问题（2）的插值基函数。设取已知数据012,,yyy作为组合系数，将插值基函数012(),(),()lxlxlx组合得2001122()()()()Pxlxylxylxy020112012010210122021()()()()()()()()()()()()xxxxxxxxxxxxyyyxxxxxxxxxxxx验证可知，这样构造的2()Px满足已知条件，因而它就是问题（2）的解。(3)推广到一般：已知函数在n+1个不同点01,,...nxxx上的函数值分别为01,,...nyyy求一个次数不超过n的多项式()nPx,使其满足:()(0,1,..)niiPxyin即1n个不同的点可以决定的一个n次多项式。过1n个不同的点分别决定1n个n次插值基函数。01(),(),...,()nlxlxlx每个插值基多项式满足：a.()ilx是n次多项式;b.()1ilx,而在其它n个点()0,()iklxki由于()0,()iklxki故有因子:011()...()()...()iinxxxxxxxx因其已经是n次多项式，故而仅相差一个常数因子。令:011()()...()()...()iiinlxaxxxxxxxx由()1iilx,可以定出a,进而得到：011011()...()()...()()()...()()...()iiniiiiiiinxxxxxxxxlxxxxxxxxxn次拉格朗日型插值多项式()nPx()nPx是1n个n次插值基本多项式01(),(),...,()nlxlxlx的线性组合,相应的组合系数是01,,...nyyy。即:0011()()()...()nnnPxylxylxylx从而()nPx是一个次数不超过n的多项式,且满足()(0,1,..)niiPxyin2·Newton插值函数的构造Newton插值法的基本思想：已知节点处的函数值或一元函数代数方程，将待求的n次插值多项式()nPx改写为具有承袭性的形式，然后根据插值条件或选取初值以求()nPx得待定系数，进而求得所要的插值函数。实践中的许多问题归结为求一元代数方程()0fx的根，如果()fx是线性函数，则它的求根较容易；对非线性方程，只有不高于4次的代数方程有求根公式，经常需求出高于4次的满足一定精度要求的近似解。Newton法的简述设xkx（）是()fx的一个近似根，把()fx在kx处泰勒展开2()()()()()()...2kkkkfxfxfxfxxxxx若取前两项来近似代替()fx，则()0fx的近似线性方程()()()()0kkfxfxfxxx设'()fx0，设其根为1kx，则1kx的计算公式为1kx=kx-()'()kkfxfx（k=0,1,2.....）这即为牛顿法，上式为牛顿迭代公式，其迭代函数为()()()fxxxfx我们知道，牛顿法是解非线性方程最著名和最有效的方法之一，在单根附近它比一般的迭代格式有较快的收速度，但也要注意它也有缺点：首先，它对迭代初值选取要求较严，初值选取不好，可能导致吧收敛；其次，它每迭代一次要计算()kfx的值，这势必增加可计算量。为回避该问题，常用一个固定的()kfx迭代若干步后再求()kfx。这就是下面要讲的简化牛顿法的基本思想。简化牛顿法和下山牛顿法简化牛顿法的公式为1()kkkxxcfx(3-1)迭代函数()()xxcfx若()1()1xcfx。即0()2cfx在根*x附近成立。则迭代法（3-1）局部收敛。此法显然化简了计算量。牛顿下山法牛顿法的收敛依赖于初值0x的选取，若0x偏离*x较远，则牛顿法可能发散。为防止迭代发散，我们对迭代过程在附加一项条件，即具有单调性：1()()kkfxfx（3-2）保证函数值稳定下降，然后结合牛顿法加快收敛速度，即可达目的。将牛顿法的计算结果1()()kkkkfxxxfx（3-3）于前一步的近似值kx适当加权平均作为新的改进值11(1)kkkxxx（3-4）其中称（01）为下山因子，即为1()()kkkkfxxxfx（3-5）称为牛顿下山法。选择下山因子时，从1开始逐次将减半进行试算。直到满足条件（3-2）为止。3·Hermite插值法已知函数()fx在给定1n个互异的节点0x，1x...nx上的函数值和导数值，求一个21n次多项式21()nHx满足插值条件21nH（kx）=ky，21()nkkHxy.k=0,1,2...nHermite插值基本原理通常如上条件的Hermite型插值是通过构造相应的插值基函数来完成的，为方便起见以n=1为例，说明传统的求解方法，设给定的0x，1x和相应的函数值0()fx，1()fx及微商值0()fx，1()fx构造插值函数3()Hx。由构造函数的办法可知：对应于0x和1x点函数值的插值函数分别为20101001()(12)()xxxxhxxxxx及20110110()(12)()xxxxhxxxxx而对应的0x和1x点导数值的插值基函数分别为210001()()()xxHxxxxx和201110()()()xxHxxxxx，因此所要求的插值函数300110011()()()()()()()()()HxfxhxfxhxfxHxfxHx（2-1）由上可发现构造插值基函数比较复杂，尤其对具有高阶导数插值条件的情况，以下将基于newton插值方法提出构造上述条件的简单格式。此时传统方法可视为这里的特例。四、具体应用实例分析1已知42,93,用线性插值法求7的近似值.解:Matlab中有直接进行线性插值计算的命令interp1,直接使用interp1命令即可.x=[49];y=[23];f=interp1(x,y,7,'linear')%选项使用线性插值f=2.6000故插值计算结果为(7)2.6000f2设()lnfxx,给出数据如下,用Lagrange插值法求(0.6)f的近似值.ix0.40.50.70.8()ifx-0.916291-0.693147-0.356675-0.223144解:求解过程描述如下:formatlong;%输入初始数据x0=[0.40.50.70.8];y0=[-0.916291-0.693147-0.356675-0.223144];x=0.6;%插值点n=length(x0);s=0;%进入迭代计算过程forj=0:(n-1)t=1;fori=0:(n-1)ifi~=jt=t*(x-x0(i+1))/(x0(j+1)-x0(i+1));endends=s+t*y0(j+1);ends%显示输出结果formatshort;程序运行结果如下:s=-0.509975500000000因此利用Lagrange插值的计算结果为(0.