拉格朗日插值和牛顿插值多项式的C程序算法【毕业论文，绝对精品】

本科生毕业论文 题 目 : 拉格朗日 插 值 和牛顿插值 多项式的 专业代码 : 070101 作者姓名 : 学 号 : 单 位 : 08级 1 班 指导教师 : 2012 年 5 月 20 日 原创性声明 本人郑重声明 : 所提交的学位论文是本人在导师指导下 , 独立进行研究取得的成果 . 除文中已经注明引用的内容外 , 论文中不含其他人已经发表或撰写过的研究成果 , 也不包含为获得 *大学或其他教育机构的学位证书而使用过的材料 . 对本文的研究做出重要贡献的个人和集体 , 均已在文中以明确方式标明 . 本人承担本声明的相应责任 . 学位论文作者签名 : 日期 指 导 教 师 签 名 : 日期 目 录 拉格朗日插值多项式的 C 程序算法 . 1 1 引言 . 1 值问题的提出 . 1 值法 . 2 值法思想 . 2 2 拉格朗日插值法 . 3 格朗日插值法的由来 . 3 插值基函数 . 4 格朗日插值多项式 . 4 3 牛顿插值法 . 5 差： . 5 顿插值多项式： . 6 4C 程序设计 . 6 法设计： . 7 序源码编写 . 8 5 程序检测 . 12 拉格朗日插值的检测 . 12 牛顿插值的检测 . 13 总结 . 15 参考文献 . 16 致谢 . 17 摘 要 本论文着重研究了用 C 语言编写程序计算拉格朗日插值和牛顿插值的方法。在前人已有的研究成果的基础上，首先介绍了拉格朗日插值和牛顿插值的思想和方法，通过添加可以循环计算功能和输入非法数值时的纠错功能，改进了已有文献的方法，对其进行了推广，使之更加的合理和完美，并且通过实际的例子进行了具体的验证。最后，总结了一下本论文的主要研究成果和应用前景。 关键词 ： 拉格朗日插 值，牛顿插值， C 算法，精确解 to on of by it it it up of C 1 拉格朗日 插 值多项式的 C 程序算法 1 引言 插值法是一种古老的数学研究方法，他的产生来自与社会的生产实践活动。在我国，早在一千多年前的隋唐时期，制定历法时，就应用了二次插值的方法。隋朝刘焯将等距节点二次插值应用于天文计算。但是，终究没有形成系统的理论。插值理论都是 10世纪微积分产生以后渐渐发展起来的。拉格朗日插值和牛顿插值都是优秀的重要研究成果。 数值分析 1对此作了详细介绍， 最近 50 多年 来计算机技术的飞速发展和广泛应用 ，以及轻重工业等各方面实际问题的需要，促使插值法得到了更进一步的发展 。 之前也有 不少关于拉格朗日插值和牛顿插值的 C 程序算法，但是，经过实际运用发现都有各种各样的缺点，主要分为以下两种： 1、每次只能执行一次，算完一次之后，就会出现“ to 从而没法在进行下一次的计算； 2、没有纠错功能，通常情况下，为了计算的精确，我们这一个程序一般只用于计算 20组以内的（即不超过 20个节点的），当超过之后，会产生较大误差，甚至用户输入负组数之后， 程序崩溃，即程序的健壮性没有设计好； 本算法在尽量弥补这两个不足的同时，也注意尽量优化程序，使占用的资源和运算的时间不会明显增加。 值问题的 提出 在实际生活中，我们常用 ()y f x 来表示某种内在的数量关系，其中很多数据可以通过实验或观测得到。这样虽然 () ,是存在的，但是也仅仅能够得到 ,的一 系列点)f x ( 0 ,1, 2 , ) ，。但这也只能刻画有限的情形。 为了研究函数整体的变化规律，以及实际的需要，我们往往要求出不再 ,的情形。因此我们常常会试着找出一个既能方便运算，又能和 ()了计算的 方便，我们一般选一类比较简单的函数作为 ()得 () 满足 ()() 0 ,1, 2 , ) ，。这样确定的函数 () 值法 拉格朗日平均插值法 2介绍， 当一些实际问题用数学函数关系来描述时 ,往往没 有明显的解析表达式 ,只能根据实验观测或其他途径提供一些离散点处的函数值和导数 ,有时尽管有表达式 ,却比较复杂 ,不便于研究和使用 。 对此 ,人们希望构造一个简单的连续函数 p(x)来近似替代所考察的函数 f(x),使问题得到简化 。 用代数多项式作为研究插值的工具，进而得出较为精确结果的方法，就是代数插值。当给定一张具有 n +1个点的函数表以后，我们要构造一个 函数 ()y f x ，这样的 ()一， ()n 次的多项式；第二，在给定的点0,1, ， ）上 () 设函数 ()y f x 在区间 ,有定义，且已知在 点01 na x x x b 上的值0y，1y，果 有一个简单的函数 ()使得 () 0,1, ， 成立，就称 () ()01, , , nx x 含插值节点节点的区间 ,为插值区间，求得函数 ()方法称为插值法。 几何意义：从几何上看，插值法就是求曲线 y = ()使其通过给定的 1n 个点( , ) 0,1, ， ，并用它近似已知曲线 y = () 值法思想 已知在区间 ,有 1n 个点，01 na x x x b 以及他们 对应的函数值 ()f x ( 0 ,1, 2 , ) ，下面我们求次数不超过 n 的多项式 ()得 () 0 ,1, 2 , ) ，。 根据已知的条件，我们可以得到关于 系数0a,1a,，n 元线性方程组 3 0 1 0 0 00 1 1 1 101n n na a x a x ya a x a x ya a x a x y 其系数矩阵为 A =0011111于 0 ,1, 2 , ) ，互 异，所以 1,0()jn 0 因此，线性方程组的解0a，1a，而满足条件的 () 直接求解上面的方程组就可以得到插值多项式 ()这是球插值多项式最繁杂的方法。 从范德蒙行列式到拉格朗日插值公式 3中描述的则更为贴切， 范得蒙行列式与拉格朗日插值公式看来没什么关系 ， 但仔细思索可得结论 ： 应用范得蒙行列式可推得拉格朗日 插 值公式。 2 拉格朗日插值法 格朗日插值法的由来 在数值分析中，拉格朗日插值法 是一种多项式差值方法，它的命名来源于 法国十八世纪 大数学家约瑟夫路易斯拉格朗日 。 在很多 实际问题中都 倾向于函数来表示某种内在联系或规律， 但是呢，有相当的一部分 函数都只能通过实验和观测来了 解。如对实践中的某个 物理 量进行观测，在若干个不同的地方得到相应的观测值，拉格朗日插值法可以找到一个 这样的一个多项式 ， 这个多项式 恰好在各个观测的点取到观测到的值。这样的多项式称为拉格朗日插值多项式。 从代数的角度来说 ，拉格朗日插值法可以给出一个恰好穿过二维平面上若干个已知点的多项式函数。拉格朗日插值法最早被英国数学家爱德华华林于 1779 年 发现 ，不久 4 后（ 1783年）由莱昂哈德欧拉再次发现。 1795年，拉格朗日在 他的 著作师范学校数学基础教程中发表了这个插值方法，从此他的名字就和这个方法 产生了不解之缘。 插值是一种逼近的方法。拉格朗日插值法是一种较为简单的多项式插值构造性方法，其计算复杂度并不高，得到拉格朗日插值法的途径不止一种。通用教材北大版高等代数 4以习题的形式从多项整式整除的角度得到拉格朗日插值公式。 插值基函数 插值基函数的描述在拉格朗日插值基函数的相关性质 5中十分详细。 拉格朗日插值是代数多项式插值中较为简单 的一种 ， 它具有 格式整齐、对称和规范的特点 ， 是 便于程序设计的一种形式。拉格朗日插值函数是拉格朗日插值基函数的线性组合，因此 探究 拉格朗日插值基函数的性质就十分重要了。 利 用拉格朗日插值求余式的探讨 6中，对代数插值做了概括。 用代数多项式作为研究插值的工具 ,就是所谓的代数插值。当给定一张有 1n 个点的函数表以后 ,要构造一个函数 ()x 满足两个条件 ,即 (1)： ()x 是一个不超过 n 次的多项式 ； (2)： 在给定点 1, 2, , )与 () 即 () 1, 2, , )我们称 ()x 为 () 通常， 若 n 次多项式 ()0,1, ) 1n 个节点01 nx x x 上满足条件 ()1, ,0, , , 0,1, ,j k n 这是称这 1n 个 n 次多项式01, , , nx x n 次插值基函数。 格朗日插值多项式 通过推倒，我们已经得到 n 次插值基函数可表示为0()()， ()() 0 1 10 1 1( ) ( ) ( )( ) ( )k k nk k k k k k nx x x x x x x xx x x x x x x x ， 0,1, ， 故插值多项式 ()表示为 5 ()0()n l x. 令011 ( ) ( ) ( ) ( )nw x x x x x x x , 0 1 12 ( ) ( ) ( ) ( ) ( )k k k k k k k nw x x x x x x x x x , 所以拉格朗日插值多项式可以写为： 01 ( )()( ) 2 ( ) x yx x w x . 3 牛顿插值法 利用插值基函 数很容易得到拉格朗日插值多项式，它的公式结构紧凑，整齐，很方便我们的记忆与使用，这在理论分析中非常重要。但是，当插值节点删减时，计算就要全部重新开始，这一点非常不方便。为了能方便的进行节点删减后的运算，我们可以重新设计一种逐次生成插值多项式的方法。这就是牛顿插值多项式。 在牛顿插值公式的拓展使用 7中可以看出， 通过对牛顿插值公式与泰勒公式的比较 ， 把牛顿插值公式拓展到埃尔米特插值公式和样条函效插值的使用领域 ， 从而可以把插值问题都归结到牛顿插值公式上 ， 而且在解决插值问题上很简单、高效、方便 。 差： 称000( ) ( ) , kk kf x f xf x x 为函数 ()于点 0x , 一阶均差。0 0 1011 , , , , kk kf x x f x xf x x x 称为的二阶均差。一般地，我们称下面的函数 0 2 0 1 1011 , , , , , , , , , k k kk x x x f x x xf x x x 为 k 阶均差。 k 阶均差可以表示成函数值 0() 1()， ()线性组合，如下： 01, , , kf x x x =0 0 1 1()( ) ( ) ( ) ( )k jj j j j j j j x x x x x x x 6 顿插值多项式： 借助均差的定义，一次插值多项式可以表示为 1 0 0 1 0 0 0 1 0( ) ( ) , ( ) ( ) , ( )P x P x f x x x x f x f x x x x 而二次插值多项式可以表示为 2 1 0 1 2 0 1( ) ( ) , , ( ) ( )P x P x f x x x x x x x 0 0 1 0 0 1 2 0 1( ) , ( ) , , ( ) ( )f x f x x x x f x x x x x x x 根据均差定义，将 ,的一点，可以得到 0 0 0( ) ( ) , ( )f x f x f x x x x , 0 0 1 0 1 1 , , , , ( )f x x f x x f x x x x x , 0 1 0 1 0 , , , , , , , , , ( )n n n nf x x x f x x x f x x x x x , 将上面的式子，后一式带入前一式，得到 0 0 0 0 1 0 1 0 1 0 1( ) ( ) , ( ) , , ( ) ( ) , , , ( ) ( )x f x f x x x x f x x x x x x x f x x x x x x x 01 , , , ( ) ( ) ( )n n n nf x x x x P x R x , 其中 0 0 1 0 0 1 2 0 1 0 1 0 1( ) ( ) , ( ) , , ( ) ( ) , , , ( ) ( )n n nP x f x f x x x x f x x x x x x x f x x x x x x x 01( ) ( ) ( ) , , , ( )n n n nR x f x P x f x x x x 以上nP(x)我们称为牛顿插值多项式。 () 4 C 程序设计 基于静态分析的 8中明确指出： 使现在已经有像 多的系统开发中。 “ 学以致用 ” 是每一门学科都致力追求的境界 ,数学自然也不例外。可人们往往淹没于一堆高深的数学理论及烦琐的分析、论证之中 ,早已失去了数学的乐趣 ! 7 特别是用数学来解决实际的问题更是感到无所适从。 拉格朗日插值法在工程应用中的算法实现 9介绍拉格朗日插值法在现实分析中的应用 ,并通过 为复杂的工程分析研究提供了一条数学算法的捷径 。 法设计： 择两个变量控制选择项的实现，分别命名为 了计算的精确，定义 2个不超 过 20祖的数组 x20和 y20; 义 3个控制循环的变量， i、 f、 k； 义几个过程变量， a， c， d， e， j， l， L， ； 入已知的数组的组数，用 0,20之间时，继续，当输入的数不在此范围时，提示错误，并重新输入，知道正确为止 。并通过循环语句输入所有的数组 ； 选择要计算的插值类型，或退出； 如果选择 1，计算 拉格朗日插值时，先输入要插入的新数值 过循环语句，分别用 1( ) ( ) ( ) ( )nw x x x x x x x ,用 1 1( ) ( ) ( ) ( ) ( )k k k k k k k nw x x x x x x x x x ， d=用 k x x w ，所以所有的 L 相加，就得到了拉格朗日插值 ()nL 果选择 2，计算牛顿插值的时候，同样先输入要计算插值的数值 过循环语句，分别用 1 1( ) ( ) ( ) ( )j j j j l j kw x x x x x x x x ，用 1( ) ( ) ( )x x x x x x ， l=21L=L+l,另 d= 2因为牛顿插值法中，每一项只乘到1()，而不是 ()以要把多余的 ()掉） ,通过累加，p=p+d,最终用 行完 由用户选择继续重新运算还是退出； 果用户在 ，则直接退出程序； 8 序源码编写 # 1; x20,y20; k,j,i,a,b1,b2,c,d,e,f,w1,w2,l,L,; ; ; L=0; P=0; = 1) 请输入 0,20之间的数据。 n); 输入的数据为几组 :n); %d,&j); if(j20|j=0) 请输入 0,20之间的数据。 n); 输入的数据为几组 :n); %d,&j); i=0;i=i+) 第 %n,i+1); x=); 9 %f,&xi); y=); %f,&yi); 请选择 :1,拉格朗日插值。 2,牛顿插值。 0,退出。 n); %d,& if(1) 请输入插入的数值： ); %f,& k=0;k=k+) b1=xk; b2=yk; i=0;i=i+) a=xi; c=w1=w1*c; e=if(e!=0) w2=w2*e; if(e=0) e=e+1; w2=w2*e; 10 d=f=d* f=%fn,f);*/ l=b2*w1/f; /* l=%fn,l);*/ L=L+l; ; ; f,L); if(2) 请输入插入的数值： ); %f,& f=0;f=f+) k=0;k=f;k+) b1=xk; b2=yk; i=0;i=f;i+) a=xi; e=if(e!=0) w1=w1*e; 11 if(e=0) e=e+1; w1=w1*e; l=b2/L=L+l; ; c=w2=w2*c; d=L*w2/c; ; P=P+d; L=0; f,P); n); 请选择 ： 1 继续 。 2 退出 。 n); %d,& n); = 2) ; if(0) 12 ; 5 程序检测 10高度概括了程序检测的重要性。 写完一个程序只能说完成任务的一半（甚至不到一半）。调试程序往往比写程序更难，更需要精力、时间和经验。常常有这样的情况：程序花一天就写完了，而调试程序两三天也未能完成。有事一个小小的程序会出错五六处，而发现和排除一个错误，有时竟需要半天，甚至更多。 C 语言是应用较广泛的一种程序设计语言 ,其程序格式灵活、简洁、代码执行效率高。 正如 C 程序调试中常见错误分析 11中介绍的， 由于其语法限制不严 ,且采用了一些用以提高执行效率的措施 ,因而在调试时经常会出现莫明其妙的错误 ,这种错误需要仔细检查和分析才能发现。 在本论文中，主要对程序计算结果的精确性进行检验。 拉格朗日插值的检测 在对拉格朗日插值的精确性进行检测时，我们用下面的一个例子： 例 1： 已知 67 ,87 ,74,2用线性插值及抛物线插值计算 我们依次键入 3 ， 1 ， 2 ； 经过运算，我们可以得到如下的结果： 13 我们可以看到，计算的结果为 74，这个结果和 6位有效数字的正弦函数表完全一样。说明这个算法的精度很高。 牛顿插值的检测 我们同样引用一个例子对牛顿插值的精确性进行检验： 例 2： 给出 (f 的函数和均差表如下： 算出 (f 的近似值。 解答：我们依次输入 5 ， 2 ， 2 。 14 运行结果如下： 这个结果极近似于例题的答案： 从结果我们不难看出：通过这个算法所得到的结果与它的真是值之间的误差很小，即通过算法算出的牛顿插值是法 (f 的近似值。这样这个算法的可行性得证。 15 总结 通过以上两个例题 ， 可以看出，这样一个 C 程序可以使复杂难算的拉格朗日插值和牛顿插值很方便的计算出。既不需要熟练的操作技巧，又不需要花费大量的时间和精力。 同时，我们可以看到，至少在数组的数 量小于 20组的时候，计算的精确度是很高的。虽然 用其他的大型计算工具， 也会快速的计算出插值， 例如但操作起来比较复杂，而且对设备有一定的要求。 一般电脑上没有装 法运行。但是这样的一个小程序，携带方便，运算和操作都很简单。 在工程技术中，经常会遇到插值之类的计算问题，例如在半 导体技术中，设计晶体管和分析其性能时，常常涉及到与半导体 的杂质浓度有关的参盘 ;在温度自动控制系统中的热电偶和温 度的对应关系，当采用计算机辅助分析和控制时，必须将这些关系曲线离散化 ，然后运用插值法进行数学 分析，最终得到我们需要的结果。 16 参考文献 1李庆扬，易大义，王能超 北京：高等教育出版社 ,1995. 2符锡成，郭学品