数学专业毕业论文拉格朗日插值和牛顿插值多项式的c程序算法

数学专业毕业论文-拉格朗日插值和牛顿插值多项式的C程序算法 目 录拉格朗日插值多项式的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摘 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;1引言插值法是一种古老的数学研究方法，他的产生来自与社会的生产实践活动。在我国，早在一千多年前的隋唐时期，制定历法时，就应用了二次插值的方法。隋朝刘焯将等距节点二次插值应用于天文计算。但是，终究没有形成系统的理论。插值理论都是10世纪微积分产生以后渐渐发展起来的。拉格朗日插值和牛顿插值都是优秀的重要研究成果。数值分析1对此作了详细介绍，最近50多年来计算机技术的飞速发展和广泛应用，以及轻重工业等各方面实际问题的需要，促使插值法得到了更进一步的发展。之前也有不少关于拉格朗日插值和牛顿插值的C程序算法，但是，经过实际运用发现都有各种各样的缺点，主要分为以下两种：1、每次只能执行一次，算完一次之后，就会出现“press anykey to continue”，从而没法在进行下一次的计算；2、没有纠错功能，通常情况下，为了计算的精确，我们这一个程序一般只用于计算20组以内的（即不超过20个节点的），当超过之后，会产生较大误差，甚至用户输入负组数之后，程序崩溃，即程序的健壮性没有设计好；本算法在尽量弥补这两个不足的同时，也注意尽量优化程序，使占用的资源和运算的时间不会明显增加。在实际生活中，我们常用来表示某种内在的数量关系，其中很多数据可以通过实验或观测得到。这样虽然在给定的区间上是存在的，但是也仅仅能够得到上的一系列点的函数值。但这也只能刻画有限的情形。为了研究函数整体的变化规律，以及实际的需要，我们往往要求出不再上的情形。因此我们常常会试着找出一个既能方便运算，又能和比较接近的函数。为了计算的方便，我们一般选一类比较简单的函数作为，使得满足 。这样确定的函数就是我们想要得到的插值函数。拉格朗日平均插值法2介绍，当一些实际问题用数学函数关系来描述时,往往没有明显的解析表达式,只能根据实验观测或其他途径提供一些离散点处的函数值和导数,有时尽管有表达式,却比较复杂,不便于研究和使用对此,人们希望构造一个简单的连续函数p x 来近似替代所考察的函数f x ,使问题得到简化+1个点的函数表以后，我们要构造一个函数，这样的满足两个条件：第一，是一个不超过次的多项式；第二，在给定的点（）上的值必须与给定的值相同。 设函数在区间上有定义，且已知在点上的值，。如果有一个简单的函数，使得 ，成立，就称是的插值函数，点称为插值节点，包含插值节点节点的区间称为插值区间，求得函数的方法称为插值法。几何意义：从几何上看，插值法就是求曲线 ,使其通过给定的个点，并用它近似已知曲线 。已知在区间上有个点，以及他们对应的函数值，下面我们求次数不超过的多项式，使得 。根据已知的条件，我们可以得到关于系数,，的元线性方程组其系数矩阵为 称为范德蒙德矩阵，由于互异，所以 因此，线性方程组的解，存在且唯一，从而满足条件的是存在且唯一的。直接求解上面的方程组就可以得到插值多项式，但这是球插值多项式最繁杂的方法。从范德蒙行列式到拉格朗日插值公式3中描述的则更为贴切，范得蒙行列式与拉格朗日插值公式看来没什么关系但仔细思索可得结论应用范得蒙行列式可推得拉格朗日值公式。插值是一种逼近的方法。拉格朗日插值法是一种较为简单的多项式插值构造性方法，其计算复杂度并不高，得到拉格朗日插值法的途径不止一种。通用教材北大版高等代数以习题的形式从多项整式整除的角度得到拉格朗日插值公式。用代数多项式作为研究插值的工具,就是所谓的代数插值。当给定一张有个点的函数表以后,要构造一个函数满足两个条件,即 1 是一个不超过次的多项式 2 ：在给定点上与取相同值即 。我们称为的拉格朗日插值函数次多项式在个节点上满足条件 这是称这个次多项式上的次插值基函数。通过推倒，我们已经得到次插值基函数可表示为，为节点 ，故插值多项式可表示为 .令,所以拉格朗日插值多项式可以写为：.3牛顿插值法利用插值基函数很容易得到拉格朗日插值多项式，它的公式结构紧凑，整齐，很方便我们的记忆与使用，这在理论分析中非常重要。但是，当插值节点删减时，计算就要全部重新开始，这一点非常不方便。为了能方便的进行节点删减后的运算，我们可以重新设计一种逐次生成插值多项式的方法。这就是牛顿插值多项式。在牛顿插值公式的拓展使用7中可以看出，通过对牛顿插值公式与泰勒公式的比较把牛顿插值公式拓展到埃尔米特插值公式和样条函效插值的使用领域从而可以把插值问题都归结到牛顿插值公式上而且在解决插值问题上很简单、高效、方便为函数关于点,的一阶均差。称为的二阶均差。一般地，我们称下面的函数为阶均差。阶均差可以表示成函数值，的线性组合，如下： 3.2牛顿插值多项式：借助均差的定义，一次插值多项式可以表示为而二次插值多项式可以表示为根据均差定义，将x看成是上的一点，可以得到,将上面的式子，后一式带入前一式，得到,其中以上 x 我们称为牛顿插值多项式。为插值余项。4 C程序设计基于静态分析的C语言缓冲区溢出漏洞检测研究8中明确指出：C语言是一种广泛流行的高级计算机语言，即使现在已经有像java这样可以检查数组越界的语言，C语言还被使用于很多的系统开发中。学以致用是每一门学科都致力追求的境界,数学自然也不例外。可人们往往淹没于一堆高深的数学理论及烦琐的分析、论证之中,早已失去了数学的乐趣!特别是用数学来解决实际的问题更是感到无所适从。介绍拉格朗日插值法在现实分析中的应用,并通过C语言程序来实现这一数学分析法的自动化,为复杂的工程分析研究提供了一条数学算法的捷径,用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，则直接退出程序；#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 j 20|j 0 printf 请输入0,20之间的数据。n ;printf 输入的数据为几组:n ;scanf %d,&j ; else for 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语言是应用较广泛的一种程序设计语言,其程序格式灵活、简洁、代码执行效率高。由于其语法限制不严,且采用了一些用以提高执行效率的措施,因而在调试时经常会出现莫明其妙的错误,这种错误需要仔细检查和分析才能发现。， ，；经过运算，我们可以得到如下的结果：我们可以看到，计算的结果为0.330 374，这个结果和6位有效数字的正弦函数表完全一样。说明这个算法的精度很高。我们同样引用一个例子对牛顿插值的精确性进行检验：例2：给出的函数和均差表如下：0.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致 谢感谢。2