数学系本科生毕业论文.doc

本科生毕业论文题 目: 拉格朗日插值和牛顿插值多项式的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牛顿插值多项式：54C程序设计64.1算法设计：74.2程序源码编写75程序检测125.1对拉格朗日插值的检测125.2对牛顿插值的检测13总结15参考文献16致谢17摘 要本论文着重研究了用C语言编写程序计算拉格朗日插值和牛顿插值的方法。在前人已有的研究成果的基础上，首先介绍了拉格朗日插值和牛顿插值的思想和方法，通过添加可以循环计算功能和输入非法数值时的纠错功能，改进了已有文献的方法，对其进行了推广，使之更加的合理和完美，并且通过实际的例子进行了具体的验证。最后，总结了一下本论文的主要研究成果和应用前景。关键词：拉格朗日插值，牛顿插值，C算法，精确解AbstractThis article discuss the method to calculate Lagrange interpolation and Newton interpolation with C program. Base on the results of predecessors research, firstly, this article introduces the thoughts and methods of Lagrange interpolation and Newton interpolation. Improving the old method by adding functions which can repeatedly computing interpolation and correct illegal data. Then spreading it and making it more reasonable and perfect, checking it with some examples. Finally, summing up the main results of this article and application prospect.Key words：Lagrange interpolation; Newton interpolation ; C program;拉格朗日插值多项式的C程序算法1引言插值法是一种古老的数学研究方法，他的产生来自与社会的生产实践活动。在我国，早在一千多年前的隋唐时期，制定历法时，就应用了二次插值的方法。隋朝刘焯将等距节点二次插值应用于天文计算。但是，终究没有形成系统的理论。插值理论都是10世纪微积分产生以后渐渐发展起来的。拉格朗日插值和牛顿插值都是优秀的重要研究成果。数值分析1对此作了详细介绍，最近50多年来计算机技术的飞速发展和广泛应用，以及轻重工业等各方面实际问题的需要，促使插值法得到了更进一步的发展。之前也有不少关于拉格朗日插值和牛顿插值的C程序算法，但是，经过实际运用发现都有各种各样的缺点，主要分为以下两种：1、每次只能执行一次，算完一次之后，就会出现“press anykey to continue”，从而没法在进行下一次的计算；2、没有纠错功能，通常情况下，为了计算的精确，我们这一个程序一般只用于计算20组以内的（即不超过20个节点的），当超过之后，会产生较大误差，甚至用户输入负组数之后，程序崩溃，即程序的健壮性没有设计好；本算法在尽量弥补这两个不足的同时，也注意尽量优化程序，使占用的资源和运算的时间不会明显增加。1.1插值问题的提出在实际生活中，我们常用来表示某种内在的数量关系，其中很多数据可以通过实验或观测得到。这样虽然在给定的区间上是存在的，但是也仅仅能够得到上的一系列点的函数值。但这也只能刻画有限的情形。为了研究函数整体的变化规律，以及实际的需要，我们往往要求出不再上的情形。因此我们常常会试着找出一个既能方便运算，又能和比较接近的函数。为了计算的方便，我们一般选一类比较简单的函数作为，使得满足=。这样确定的函数就是我们想要得到的插值函数。1.2插值法拉格朗日平均插值法2介绍，当一些实际问题用数学函数关系来描述时,往往没有明显的解析表达式,只能根据实验观测或其他途径提供一些离散点处的函数值和导数,有时尽管有表达式,却比较复杂,不便于研究和使用。对此,人们希望构造一个简单的连续函数p(x)来近似替代所考察的函数f(x),使问题得到简化。用代数多项式作为研究插值的工具，进而得出较为精确结果的方法，就是代数插值。当给定一张具有+1个点的函数表以后，我们要构造一个函数，这样的满足两个条件：第一，是一个不超过次的多项式；第二，在给定的点（）上的值必须与给定的值相同。 设函数在区间上有定义，且已知在点上的值，。如果有一个简单的函数，使得=，成立，就称是的插值函数，点称为插值节点，包含插值节点节点的区间称为插值区间，求得函数的方法称为插值法。几何意义：从几何上看，插值法就是求曲线=,使其通过给定的个点，并用它近似已知曲线=。1.3插值法思想已知在区间上有个点，以及他们对应的函数值，下面我们求次数不超过的多项式，使得=。根据已知的条件，我们可以得到关于系数,，的元线性方程组其系数矩阵为=称为范德蒙德矩阵，由于互异，所以=因此，线性方程组的解，存在且唯一，从而满足条件的是存在且唯一的。直接求解上面的方程组就可以得到插值多项式，但这是球插值多项式最繁杂的方法。从范德蒙行列式到拉格朗日插值公式3中描述的则更为贴切，范得蒙行列式与拉格朗日插值公式看来没什么关系，但仔细思索可得结论：应用范得蒙行列式可推得拉格朗日插值公式。2拉格朗日插值法2.1拉格朗日插值法的由来在数值分析中，拉格朗日插值法是一种多项式差值方法，它的命名来源于法国十八世纪大数学家约瑟夫路易斯拉格朗日。在很多实际问题中都倾向于函数来表示某种内在联系或规律，但是呢，有相当的一部分函数都只能通过实验和观测来了解。如对实践中的某个物理量进行观测，在若干个不同的地方得到相应的观测值，拉格朗日插值法可以找到一个这样的一个多项式，这个多项式恰好在各个观测的点取到观测到的值。这样的多项式称为拉格朗日插值多项式。从代数的角度来说，拉格朗日插值法可以给出一个恰好穿过二维平面上若干个已知点的多项式函数。拉格朗日插值法最早被英国数学家爱德华华林于1779年发现，不久后（1783年）由莱昂哈德欧拉再次发现。1795年，拉格朗日在他的著作师范学校数学基础教程中发表了这个插值方法，从此他的名字就和这个方法产生了不解之缘。插值是一种逼近的方法。拉格朗日插值法是一种较为简单的多项式插值构造性方法，其计算复杂度并不高，得到拉格朗日插值法的途径不止一种。通用教材北大版高等代数4以习题的形式从多项整式整除的角度得到拉格朗日插值公式。2.2n次插值基函数插值基函数的描述在拉格朗日插值基函数的相关性质5中十分详细。拉格朗日插值是代数多项式插值中较为简单的一种，它具有格式整齐、对称和规范的特点，是便于程序设计的一种形式。拉格朗日插值函数是拉格朗日插值基函数的线性组合，因此探究拉格朗日插值基函数的性质就十分重要了。利用拉格朗日插值求余式的探讨6中，对代数插值做了概括。用代数多项式作为研究插值的工具,就是所谓的代数插值。当给定一张有个点的函数表以后,要构造一个函数满足两个条件,即(1)：是一个不超过次的多项式；(2)：在给定点上与取相同值，即= 。我们称为的拉格朗日插值函数。通常，若次多项式在个节点上满足条件= 这是称这个次多项式上的次插值基函数。2.3拉格朗日插值多项式通过推倒，我们已经得到次插值基函数可表示为，为节点=，故插值多项式可表示为=.令,所以拉格朗日插值多项式可以写为：.3牛顿插值法利用插值基函数很容易得到拉格朗日插值多项式，它的公式结构紧凑，整齐，很方便我们的记忆与使用，这在理论分析中非常重要。但是，当插值节点删减时，计算就要全部重新开始，这一点非常不方便。为了能方便的进行节点删减后的运算，我们可以重新设计一种逐次生成插值多项式的方法。这就是牛顿插值多项式。在牛顿插值公式的拓展使用7中可以看出，通过对牛顿插值公式与泰勒公式的比较，把牛顿插值公式拓展到埃尔米特插值公式和样条函效插值的使用领域，从而可以把插值问题都归结到牛顿插值公式上，而且在解决插值问题上很简单、高效、方便。3.1均差：称为函数关于点,的一阶均差。称为的二阶均差。一般地，我们称下面的函数为阶均差。阶均差可以表示成函数值，的线性组合，如下：=3.2牛顿插值多项式：借助均差的定义，一次插值多项式可以表示为而二次插值多项式可以表示为根据均差定义，将x看成是上的一点，可以得到,将上面的式子，后一式带入前一式，得到,其中以上(x)我们称为牛顿插值多项式。为插值余项。4 C程序设计基于静态分析的C语言缓冲区溢出漏洞检测研究8中明确指出：C语言是一种广泛流行的高级计算机语言，即使现在已经有像java这样可以检查数组越界的语言，C语言还被使用于很多的系统开发中。 “学以致用”是每一门学科都致力追求的境界,数学自然也不例外。可人们往往淹没于一堆高深的数学理论及烦琐的分析、论证之中,早已失去了数学的乐趣!特别是用数学来解决实际的问题更是感到无所适从。拉格朗日插值法在工程应用中的算法实现9介绍拉格朗日插值法在现实分析中的应用,并通过C语言程序来实现这一数学分析法的自动化,为复杂的工程分析研究提供了一条数学算法的捷径。4.1算法设计：S1：选择两个变量控制选择项的实现，分别命名为Flag和flag；S2：为了计算的精确，定义2个不超过20祖的数组x20和y20;S3：定义3个控制循环的变量，i、f、k；S4：定义几个过程变量，a，b1，b2，c，d，e，j，w1，w2，l，L，newx，newy，P；S5：输入已知的数组的组数，用j表示，当j在0,20之间时，继续，当输入的数不在此范围时，提示错误，并重新输入，知道正确为止。并通过循环语句输入所有的数组；S6：选择要计算的插值类型，或退出；S7：如果选择1，计算拉格朗日插值时，先输入要插入的新数值newx，通过循环语句，分别用w1表示,用w2表示，d=newx-b1表示对应每一个k值的，用L表示对应每一个k值的，所以所有的L相加，就得到了拉格朗日插值；S8：如果选择2，计算牛顿插值的时候，同样先输入要计算插值的数值newx，通过循环语句，分别用w1表示，用w2表示，l=,L=L+l,另d=（因为牛顿插值法中，每一项只乘到，而不是所以要把多余的除掉）,通过累加，p=p+d,最终用P表示newx的牛顿插值。S9：执行完S7和S8之后，由用户选择继续重新运算还是退出；S10：如果用户在S6中选择的是0，则直接退出程序；4.2程序源码编写#include stdio.hint main()int Flag = 1;float x20,y20;int k,j,i,flag;float a,b1,b2,c,d,e,f,w1,w2,l,L,newx,P;w1=1;w2=1;L=0;P=0;while(Flag = 1)printf(请输入0,20之间的数据。n);printf(输入的数据为几组:n);scanf(%d,&j);if(j20|j=0)printf(请输入0,20之间的数据。n);printf(输入的数据为几组:n);scanf(%d,&j);elsefor(i=0;i=j-1;i+)printf(第%d组为:n,i+1);printf(x=);scanf(%f,&xi);printf(y=);scanf(%f,&yi);printf(请选择:1,拉格朗日插值。2,牛顿插值。0,退出。n);scanf(%d,&flag);if(flag=1)printf(请输入插入的数值：);scanf(%f,&newx);for(k=0;k=j-1;k+)b1=xk;b2=yk;for(i=0;i=j-1;i+)a=xi;c=newx-a;w1=w1*c;e=b1-a;if(e!=0)w2=w2*e;if(e=0)e=e+1;w2=w2*e;d=newx-b1;f=d*w2;/*printf(f=%fn,f);*/l=b2*w1/f;/*printf(l=%fn,l);*/L=L+l;w1=1;w2=1;printf(newy=%f,L);if(flag=2)printf(请输入插入的数值：);scanf(%f,&newx);for(f=0;f=j-1;f+)for(k=0;k=f;k+)b1=xk;b2=yk;for(i=0;i=f;i+)a=xi;e=b1-a;if(e!=0)w1=w1*e;else if(e=0)e=e+1;w1=w1*e;l=b2/w1;L=L+l;w1=1;c=newx-b1;w2=w2*c;d=L*w2/c;w2=1;P=P+d;L=0;printf(newy=%f,P);printf(n);printf(请选择 ：1 继续 。2 退出 。n);scanf(%d,&Flag);printf(n);if(Flag = 2)return 0;if(flag=0)return 0;5程序检测C语言程序设计教程10高度概括了程序检测的重要性。写完一个程序只能说完成任务的一半（甚至不到一半）。调试程序往往比写程序更难，更需要精力、时间和经验。常常有这样的情况：程序花一天就写完了，而调试程序两三天也未能完成。有事一个小小的程序会出错五六处，而发现和排除一个错误，有时竟需要半天，甚至更多。C语言是应用较广泛的一种程序设计语言,其程序格式灵活、简洁、代码执行效率高。正如C程序调试中常见错误分析11中介绍的，由于其语法限制不严,且采用了一些用以提高执行效率的措施,因而在调试时经常会出现莫明其妙的错误,这种错误需要仔细检查和分析才能发现。在本论文中，主要对程序计算结果的精确性进行检验。5.1对拉格朗日插值的检测在对拉格朗日插值的精确性进行检测时，我们用下面的一个例子：例1：已知sin0.32=0.314 567 ,sin0.34=0.333 487 ,sin0.36=0.352 274,2用线性插值及抛物线插值计算sin0.3367的值。我们依次键入， ，；经过运算，我们可以得到如下的结果：我们可以看到，计算的结果为0.330 374，这个结果和6位有效数字的正弦函数表完全一样。说明这个算法的精度很高。5.2对牛顿插值的检测我们同样引用一个例子对牛顿插值的精确性进行检验：例2：给出的函数和均差表如下：0.400.410750.550.578151.116000.650.696750.186000.280000.800.888111.275730.358930.197330.901.026521.384100.433480.213000.031341.051.253821.515330.524930.228630.03126-0.00012计算出的近似值。解答：我们依次输入，。运行结果如下：这个结果极近似于例题的答案：0.63192。从结果我们不难看出：通过这个算法所得到的结果与它的真是值之间的误差很小，即通过算法算出的牛顿插值是法的近似值。这样这个算法的可行性得证。总结通过以上两个例题，可以看出，这样一个C程序可以使复杂难算的拉格朗日插值和牛顿插值很方便的计算出。既不需要熟练的操作技巧，又不需要花费大量的时间和精力。同时，我们可以看到，至少在数组的数量小于20组的时候，计算的精确度是很高的。虽然用其他的大型计算工具，也会快速的计算出插值，例如MATLAB程序，但操作起来比较复杂，而且对设备有一定的要求。一般电脑上没有装MATLAB环境，没法运行。但是这样的一个小程序，携带方便，运算和操作都很简单。在工程技术中，经常会遇到插值之类的计算问题，例如在半 导体技术中，设计晶体管和分析其性能时，常常涉及到与半导体 的杂质浓度有关的参盘;在温度自动控制系统中的热电偶和温 度的对应关系，当采用计算机辅助分析和控制时，必须将这些关系曲线离散化，然后运用插值法进行数学分析，最终得到我们需要的结果。参考文献1李庆扬，易大义，王能超.现代数值分析.北京：高等教育出版社,1995.2符锡成，郭学品，拉格朗日平均插值法，海南大学学报（自然科学版），2007年02期。3王洪玉，从范德蒙行列式到拉格朗日插值公式，沧州师范学院学报，1990年第04期。4 徐章韬，从矩阵的角度解读拉格朗日插值法，中国数学杂志（高中版），2011年第三期。5车明刚，拉格朗日插值基函数的相关性质，保山学院学报，2010年第2期。6黄涛，利用拉格朗日插值求余式的探讨，河南财政税务高等专科学校学报，2009年02期。7王森，牛顿插值公式的拓展使用，阜阳师范学院学报（自然科学版），2005年03期。8 沙月林，基于静态分析的C语言缓冲区溢出漏洞检测研究，TP311.52。9徐小丽，拉格朗日插值法在工程应用中的算法实现，林区教学，2010年01期。10谭浩强，张基温，唐永炎编著. C语言程序设计教程.北京：高等教育出版社，1992.11陈鑫，C程序调试中常见错误分析，长治学院学报，2009年02期。12戴聚岭，多项式差值在工程计算中的应用，福建电脑，2006年04期。13Golub G H,OLeary D P. Some history of the conjugate gradient and Lanczos methods .SIAM Review,1989,31:50-10214李岳生,齐东旭.样条函数方法.北京：科学出版社,197915关治,陆金甫.数值分析基础.北京：高等教育出版社,2000致谢我是*大学数学科学学院的一名学生，在此我非常感谢我的导师，*大学数学科学学院的*老师。正是在*老师的辛苦指导下,我的论文终于定稿.在整个论文撰写的过程中,*老师秉着严谨求实的治学态度,大胆创新的进取精神,高度负责的敬业精神,不仅对我的论文撰写提供了巨大的帮助甚至在对我以后的学习工作，都产生了巨大的影响，她教会我怎么去学习，而这正是我们要学习的精髓.她不仅知识渊博,而且视野开阔,思维敏锐,让我真正感觉到了一个导师的专业水平,在此我向*老师表示深深的感谢.同时,我要也感谢那些曾经给予过我帮助的老师、同学和朋友们,是他们让我不仅圆满完成了学习任务，而且学到了课堂上没有学到的东西。17