搜索
题目:拉格朗日插值和牛顿插值多项式的C程序算法专业代码:070101作者姓名:学号:单位:08级1班指导教师:2012年5月20日原创性声明本人郑重声明:所提交的学位论文是本人在导师指导下,独立进行研究取得的成果.除文中已经注明引用的内容外,论文中不含其他人已经发表或撰写过的研究成果,也不包含为获得**大学或其他教育机构的学位证书而使用过的材料.对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明.本人承担本声明的相应责任.学位论文作者签名:日期指导教师签名:日期目录拉格朗日插值多项式的C程序算法........................................................11引言........................................................................................................11.1插值问题的提出.............................................................................................11.2插值法............................................................................................................21.3插值法思想.....................................................................................................22拉格朗日插值法....................................................................................32.1拉格朗日插值法的由来..................................................................................32.2n次插值基函数...............................................................................................42.3拉格朗日插值多项式.....................................................................................43牛顿插值法............................................................................................53.1均差�............................................................................................................53.2牛顿插值多项式�.........................................................................................64C程序设计.............................................................................................64.1算法设计�.....................................................................................................74.2程序源码编写.................................................................................................85程序检测..............................................................................................125.1对拉格朗日插值的检测................................................................................125.2对牛顿插值的检测.......................................................................................13总结.........................................................................................................15参考文献.................................................................................................16致谢.........................................................................................................17摘要本论文着重研究了用C语言编写程序计算拉格朗日插值和牛顿插值的方法。在前人已有的研究成果的基础上�首先介绍了拉格朗日插值和牛顿插值的思想和方法�通过添加可以循环计算功能和输入非法数值时的纠错功能�改进了已有文献的方法�对其进行了推广�使之更加的合理和完美�并且通过实际的例子进行了具体的验证。最后�总结了一下本论文的主要研究成果和应用前景。关键词�拉格朗日插值�牛顿插值�C算法�精确解AbstractThisarticlediscussthemethodtocalculateLagrangeinterpolationandNewtoninterpolationwithCprogram.Baseontheresultsofpredecessors'research,firstly,thisarticleintroducesthethoughtsandmethodsofLagrangeinterpolationandNewtoninterpolation.Improvingtheoldmethodbyaddingfunctionswhichcanrepeatedlycomputinginterpolationandcorrectillegaldata.Thenspreadingitandmakingitmorereasonableandperfect,checkingitwithsomeexamples.Finally,summingupthemainresultsofthisarticleandapplicationprospect.Keywords�Lagrangeinterpolation;Newtoninterpolation;Cprogram;1拉格朗日插值多项式的C程序算法1引言插值法是一种古老的数学研究方法�他的产生来自与社会的生产实践活动。在我国�早在一千多年前的隋唐时期�制定历法时�就应用了二次插值的方法。隋朝刘焯将等距节点二次插值应用于天文计算。但是�终究没有形成系统的理论。插值理论都是10世纪微积分产生以后渐渐发展起来的。拉格朗日插值和牛顿插值都是优秀的重要研究成果。《数值分析》[1]对此作了详细介绍�最近50多年来计算机技术的飞速发展和广泛应用�以及轻重工业等各方面实际问题的需要�促使插值法得到了更进一步的发展。之前也有不少关于拉格朗日插值和牛顿插值的C程序算法�但是�经过实际运用发现都有各种各样的缺点�主要分为以下两种�1、每次只能执行一次�算完一次之后�就会出现“pressanykeytocontinue”�从而没法在进行下一次的计算�2、没有纠错功能�通常情况下�为了计算的精确�我们这一个程序一般只用于计算20组以内的�即不超过20个节点的��当超过之后�会产生较大误差�甚至用户输入负组数之后�程序崩溃�即程序的健壮性没有设计好�本算法在尽量弥补这两个不足的同时�也注意尽量优化程序�使占用的资源和运算的时间不会明显增加。1.1插值问题的提出在实际生活中�我们常用()yfx�来表示某种内在的数量关系�其中很多数据可以通过实验或观测得到。这样虽然()fx在给定的区间��,ab上是存在的�但是也仅仅能够得到��,ab上的一系列点ix的函数值()iiyfx�(0,1,2,)in�…�。但这也只能刻画有限的情形。为了研究函数整体的变化规律�以及实际的需要�我们往往要求出不再��,ab上的情形。因此我们常常会试着找出一个既能方便运算�又能和()fx比较接近的函数()Px。为了计算的方便�我们一般选一类比较简单的函数作为()Px�使得()Px2满足()iPx=()ifx(0,1,2,)in�…�。这样确定的函数()Px就是我们想要得到的插值函数。1.2插值法《拉格朗日平均插值法》[2]介绍�当一些实际问题用数学函数关系来描述时,往往没有明显的解析表达式,只能根据实验观测或其他途径提供一些离散点处的函数值和导数,有时尽管有表达式,却比较复杂,不便于研究和使用。对此,人们希望构造一个简单的连续函数p(x)来近似替代所考察的函数f(x),使问题得到简化。用代数多项式作为研究插值的工具�进而得出较为精确结果的方法�就是代数插值。当给定一张具有n+1个点的函数表以后�我们要构造一个函数()yfx��这样的()fx满足两个条件�第一�()fx是一个不超过n次的多项式�第二�在给定的点ix�0,1,.in�…��上()fx的值必须与给定的值相同。设函数()yfx�在区间��,ab上有定义�且已知在点01naxxxb�����…上的值0y�1y�„„�ny。如果有一个简单的函数()px�使得()iPx=iy�0,1,.in�…�成立�就称()px是()Fx的插值函数�点01,,,nxxx称为插值节点�包含插值节点节点的区间��,ab称为插值区间�求得函数()px的方法称为插值法。几何意义�从几何上看�插值法就是求曲线y=()px,使其通过给定的1n�个点(,)iixy�0,1,.in�…��并用它近似已知曲线y=()fx。1.3插值法思想已知在区间��,ab上有1n�个点�01naxxxb�����…以及他们对应的函数值()iiyfx�(0,1,2,)in�…��下面我们求次数不超过n的多项式()Px�使得()iPx=iy(0,1,2,)in�…�。根据已知的条件�我们可以得到关于系数0a,1a,„„�na的1n�元线性方程组3010000111101nnnnnnnnnaaxaxyaaxaxyaaxaxy�������������������其系数矩阵为A=0011111nnnnnxxxxxx称为范德蒙德矩阵�由于ix(0,1,2,)in�…�互异�所以detA=1,0()jnixijijx�����0�因此�线性方程组的解0a�1a�„�na存在且唯一�从而满足条件的()Px是存在且唯一的。直接求解上面的方程组就可以得到插值多项式()Px�但这是球插值多项式最繁杂的方法。《从范德蒙行列式到拉格朗日插值公式》[3]中描述的则更为贴切�范得蒙行列式与拉格朗日插值公式看来没什么关系�但仔细思索可得结论�应用范得蒙行列式可推得拉格朗日插值公式。2拉格朗日插值法2.1拉格朗日插值法的由来在数值分析中�拉格朗日插值法是一种多项式差值