数学系本科生毕业论文 拉格朗日插值和牛顿插值多项式的C 程序算法.pdf

题 目 拉格朗日插值和牛顿插值多项式的 C 程序算法 专业代码 070101 作者姓名 学 号 单 位 08 级 1 班 指导教师 2012 年 5 月 20 日原创性声明 本人郑重声明 所提交的学位论文是本人在导师指导下 独立进行研究取得的成果 除文中已经注明引用的内容外 论文中不含其他人已经发表或撰写过的研究成果 也不包含 为获得 大学或其他教育机构的学位证书而使用过的材料 对本文的研究做出重要贡献的个人和集体 均已在文中以明 确方式标明 本人承担本声明的相应责任 学位论文作者签名 日期 指 导 教 师 签 名 日期 目 录 拉格朗日插值多项式的 C 程序算法 1 1 引言 1 1 1 插值问题的提出 1 1 2 插值法 2 1 3 插值法思想 2 2 拉格朗日插值法 3 2 1 拉格朗日插值法的由来 3 2 2n 次插值基函数 4 2 3 拉格朗日插值多项式 4 3 牛顿插值法 5 3 1 均差 5 3 2 牛顿插值多项式 6 4C 程序设计 6 4 1 算法设计 7 4 2 程序源码编写 8 5 程序检测 12 5 1 对拉格朗日插值的检测 12 5 2 对牛顿插值的检测 13 总结 15 参考文献 16 致谢 17 摘 要 本论文着重研究了用 C 语言编写程序计算拉格朗日插值和牛顿插值的方法 在前人已有的研究成果的基础上 首先介绍了拉格朗日插值和牛顿插值的思想和 方法 通过添加可以循环计算功能和输入非法数值时的纠错功能 改进了已有文 献的方法 对其进行了推广 使之更加的合理和完美 并且通过实际的例子进行 了具体的验证 最后 总结了一下本论文的主要研究成果和应用前景 关键词 拉格朗日插值 牛顿插值 C 算法 精确解 Abstract This 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 拉格朗日插值多项式的 C 程序算法 1 引言 插值法是一种古老的数学研究方法 他的产生来自与社会的生产实践活动 在我国 早在一千多年前的隋唐时期 制定历法时 就应用了二次插值的方法 隋朝刘焯将等距节点二次插值应用于天文计算 但是 终究没有形成系统的理论 插值理论都是 10 世纪微积分产生以后渐渐发展起来的 拉格朗日插值和牛顿插值 都是优秀的重要研究成果 数值分析 1 对此作了详细介绍 最近 50 多年来计 算机技术的飞速发展和广泛应用 以及轻重工业等各方面实际问题的需要 促使 插值法得到了更进一步的发展 之前也有不少关于拉格朗日插值和牛顿插值的 C 程序算法 但是 经过实际 运用发现都有各种各样的缺点 主要分为以下两种 1 每次只能执行一次 算完一次之后 就会出现 press anykey to continue 从而没法在进行下一次的计算 2 没有纠错功能 通常情况下 为了计算的精确 我们这一个程序一般只用 于计算 20 组以内的 即不超过 20 个节点的 当超过之后 会产生较大误差 甚 至用户输入负组数之后 程序崩溃 即程序的健壮性没有设计好 本算法在尽量弥补这两个不足的同时 也注意尽量优化程序 使占用的资源 和运算的时间不会明显增加 1 1 插值问题的提出 在实际生活中 我们常用 yf x 来表示某种内在的数量关系 其中很多数据 可以通过实验或观测得到 这样虽然 f x在给定的区间 a b上是存在的 但是也 仅仅能够得到 a b上的一系列点 i x的函数值 ii yf x 0 1 2 in 但这也只 能刻画有限的情形 为了研究函数整体的变化规律 以及实际的需要 我们往往要求出不再 a b上 的情形 因此我们常常会试着找出一个既能方便运算 又能和 f x比较接近的函 数 P x 为了计算的方便 我们一般选一类比较简单的函数作为 P x 使得 P x 2 满足 i P x i f x 0 1 2 in 这样确定的函数 P x就是我们想要得到的插值 函数 1 2 插值法 拉格朗日平均插值法 2 介绍 当一些实际问题用数学函数关系来描述时 往往没有明显的解析表达式 只能根据实验观测或其他途径提供一些离散点处的 函数值和导数 有时尽管有表达式 却比较复杂 不便于研究和使用 对此 人们希 望构造一个简单的连续函数 p x 来近似替代所考察的函数 f x 使问题得到简 化 用代数多项式作为研究插值的工具 进而得出较为精确结果的方法 就是代 数插值 当给定一张具有n 1 个点的函数表以后 我们要构造一个函数 yf x 这样的 f x满足两个条件 第一 f x是一个不超过n次的多项式 第二 在给 定的点 i x 0 1 in 上 f x的值必须与给定的值相同 设函数 yf x 在区间 a b上有定义 且已知在点 01n axxxb 上的 值 0 y 1 y n y 如果有一个简单的函数 p x 使得 i P x i y 0 1 in 成立 就称 p x是 F x的插值函数 点 01 n x xx称为插值节点 包含插值节点 节点的区间 a b称为插值区间 求得函数 p x的方法称为插值法 几何意义 从几何上看 插值法就是求曲线y p x 使其通过给定的1n 个点 ii x y 0 1 in 并用它近似已知曲线y f x 1 3 插值法思想 已知在区间 a b上有1n 个点 01n axxxb 以及他们对应的函数值 ii yf x 0 1 2 in 下面我们求次数不超过n的 多项式 P x 使得 i P x i y 0 1 2 in 根据已知的条件 我们可以得到关于系数 0 a 1 a n a的1n 元线性方程 组 3 01000 01 111 01 n n n n n nnnn aa xa xy aa xa xy aa xa xy 其系数矩阵为 A 00 11 1 1 1 n n n nn xx xx xx 称为范德蒙德矩阵 由于 i x 0 1 2 in 互异 所以 det A 1 0 j n i x i j ij x 0 因此 线性方程组的解 0 a 1 a n a存在且唯一 从而满足条件的 P x是 存在且唯一的 直接求解上面的方程组就可以得到插值多项式 P x 但这是球插值多项式最 繁杂的方法 从范德蒙行列式到拉格朗日插值公式 3 中描述的则更为贴切 范 得蒙行列式与拉格朗日插值公式看来没什么关系 但仔细思索可得结论 应用范 得蒙行列式可推得拉格朗日插值公式 2 拉格朗日插值法 2 1 拉格朗日插值法的由来 在数值分析中 拉格朗日插值法是一种多项式差值方法 它的命名来源于法 国十八世纪大数学家约瑟夫 路易斯 拉格朗日 在很多实际问题中都倾向于函数 来表示某种内在联系或规律 但是呢 有相当的一部分函数都只能通过实验和观 测来了解 如对实践中的某个物理量进行观测 在若干个不同的地方得到相应的 观测值 拉格朗日插值法可以找到一个这样的一个多项式 这个多项式恰好在各 个观测的点取到观测到的值 这样的多项式称为拉格朗日插值多项式 从代数的 角度来说 拉格朗日插值法可以给出一个恰好穿过二维平面上若干个已知点的多 项式函数 拉格朗日插值法最早被英国数学家爱德华 华林于 1779 年发现 不久 4 后 1783 年 由莱昂哈德 欧拉再次发现 1795 年 拉格朗日在他的著作 师范 学校数学基础教程 中发表了这个插值方法 从此他的名字就和这个方法产生了 不解之缘 插值是一种逼近的方法 拉格朗日插值法是一种较为简单的多项式插值构造 性方法 其计算复杂度并不高 得到拉格朗日插值法的途径不止一种 通用教材 北大版 高等代数 4 以习题的形式从多项整式整除的角度得到拉格朗日插值公 式 2 2n 次插值基函数 插值基函数的描述在 拉格朗日插值基函数的相关性质 5 中十分详细 拉 格朗日插值是代数多项式插值中较为简单的一种 它具有格式整齐 对称和规范 的特点 是便于程序设计的一种形式 拉格朗日插值函数是拉格朗日插值基函数 的线性组合 因此探究拉格朗日插值基函数的性质就十分重要了 利用拉格朗日插值求余式的探讨 6 中 对代数插值做了概括 用代数多 项式作为研究插值的工具 就是所谓的代数插值 当给定一张有1n 个点的函数表 以后 要构造一个函数 x 满足两个条件 即 1 x 是一个不超过n次的多项 式 2 在给定点 i x 1 2 in 上与 i f x取相同值 即 i x i y 1 2 in 我们称 x 为 f x的拉格朗日插值函数 通常 若n次多项式 j lx 0 1 jn 在1n 个节点 01n xxx 上满足条件 jk lx 1 0 kj kj 0 1 j kn 这是称这1n 个n次多项式 01 n x xx上的n次插值基函数 2 3 拉格朗日插值多项式 通过推倒 我们已经得到n次插值基函数可表示为 0 lx 1 l x n lx为 节点 i l x 011 011 kkn kkkkkkn xxxxxxxx xxxxxxxx 0 1 kn 故插值多项式 L x可表示为 5 L x 0 n k k k y lx 令 01 1 n w xxxxxxx 011 2 kkkkkkkn wxxxxxxxxx 所以拉格朗日插值多项式可以写为 0 1 2 n nk k kk w x yL xy xx wx 3 牛顿插值法 利用插值基函数很容易得到拉格朗日插值多项式 它的公式结构紧凑 整齐 很方便我们的记忆与使用 这在理论分析中非常重要 但是 当插值节点删减时 计算就要全部重新开始 这一点非常不方便 为了能方便的进行节点删减后的运 算 我们可以重新设计一种逐次生成插值多项式的方法 这就是牛顿插值多项式 在 牛顿插值公式的拓展使用 7 中可以看出 通过对牛顿插值公式与泰勒 公式的比较 把牛顿插值公式拓展到埃尔米特插值公式和样条函效插值的使用领 域 从而可以把插值问题都归结到牛顿插值公式上 而且在解决插值问题上很简 单 高效 方便 3 1 均差 称 0 0 0 k k k f xf x f x x xx 为 函 数 f x关 于 点 0 x k x的 一 阶 均 差 001 01 1 k k k f x xf x x f x x x xx 称为的二阶均差 一般地 我们称下面的函数 02011 01 1 kkk k kk f xxxf x xx f x xx xx 为k阶均差 k阶均差可以表示成函数值 0 f x 1 f x k f x的线性组合 如下 01 k f xxx 0 011 k j j jjjjjjk f x xxxxxxxx 6 3 2 牛顿插值多项式 借助均差的定义 一次插值多项式可以表示为 100100010 P xP xf x xxxf xf x xxx 而二次插值多项式可以表示为 2101201 P xP xf x x xxxxx 001001201 f xf x xxxf x x xxxxx 根据均差定义 将 x 看成是 a b上的一点 可以得到 000 f xf xf x xxx 001011 f x xf x xf x x xxx 01010 nnnn f x xxf x xxf x xxxx 将上面的式子 后一式带入前一式 得到 00001010101 nn f xf xf x xxxf x x xxxxxf x xxxxxx 01 nnnn f x xxxP xR x 其中 0010012010101 nnn P xf xf xxxxf xx xxxxxf xxxxxxx 01 nnnn R xf xP xf x xxx 以上 n P x 我们称为牛顿插值多项式 n R x为插值余项 4 C 程序设计 基于静态分析的 C 语言缓冲区溢出漏洞检测研究 8 中明确指出 C 语言是 一种广泛流行的高级计算机语言 即使现在已经有像 java 这样可以检查数组越界 的语言 C 语言还被使用于很多的系统开发中 学以致用 是每一门学科都致力追求的境界 数学自然也不例外 可人们往 往淹没于一堆高深的数学理论及烦琐的分析 论证之中 早已失去了数学的乐趣 7 特别是用数学来解决实际的问题更是感到无所适从 拉格朗日插值法在工程应用 中的算法实现 9 介绍拉格朗日插值法在现实分析中的应用 并通过 C 语言程序来 实现这一数学分析法的自动化 为复杂的工程分析研究提供了一条数学算法的捷 径 4 1 算法设计 S1 选择两个变量控制选择项的实现 分别命名为 Flag 和 flag S2 为了计算的精确 定义 2 个不超过 20 祖的数组 x 20 和 y 20 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 表示 101 n w xxxxxxx 用 w2 表示 2011 kkkkkkkn w xxxxxxxxx d newx b1 表示对应每一个 k 值 的 k xx 用 L 表示对应每一个 k 值的 1 2 k k w y xx w 所以所有的 L 相加 就得到 了拉格朗日插值 n L newx S8 如果选择 2 计算牛顿插值的时候 同样先输入要计算插值的数值 newx 通过循环语句 分别用 w1 表示 1011 jjjjljk wxxxxxxxx 用 w2 表示 201 nn wxxxxxx l 2 1 b w L L l 另 d 2 L w c 因为牛顿插值法中 每一项只乘到 1 n xx 而不是 n xx 所以要把多余的 n xx 除掉 通过累加 p p d 最终用 P 表示 newx 的牛顿插值 S9 执行完 S7 和 S8 之后 由用户选择继续重新运算还是退出 S10 如果用户在 S6 中选择的是 0 则直接退出程序 8 4 2 程序源码编写 include stdio h int main int Flag 1 float x 20 y 20 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 if j 20 j 0 printf 请输入 0 20 之间的数据 n printf 输入的数据为几组 n scanf d else for i 0 i j 1 i printf 第 d 组为 n i 1 printf x 9 scanf f printf y scanf f printf 请选择 1 拉格朗日插值 2 牛顿插值 0 退出 n scanf d if flag 1 printf 请输入插入的数值 scanf f for k 0 k j 1 k b1 x k b2 y k for i 0 i j 1 i a x i c newx a w1 w1 c e b1 a if e 0 w2 w2 e if e 0 e e 1 w2 w2 e 10 d newx b1 f d w2 printf f f n f l b2 w1 f printf l f n l L L l w1 1 w2 1 printf newy f L if flag 2 printf 请输入插入的数值 scanf f for f 0 f j 1 f for k 0 k f k b1 x k b2 y k for i 0 i f i a x i e b1 a if e 0 w1 w1 e 11 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 printf n if Flag 2 return 0 if flag 0 12 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 的值 我们依次键入3 0 32 0 314567 0 34 0 333487 0 36 0 352274 1 0 3367 2 经过运算 我们可以得到如下的结果 13 我们可以看到 计算的结果为 0 330 374 这个结果和 6 位有效数字的正弦函 数表完全一样 说明这个算法的精度很高 5 2 对牛顿插值的检测 我们同样引用一个例子对牛顿插值的精确性进行检验 例 2 给出 0 596 f的函数和均差表如下 0 40 0 41075 0 55 0 57815 1 11600 0 65 0 69675 0 18600 0 28000 0 80 0 88811 1 27573 0 35893 0 19733 0 90 1 02652 1 38410 0 43348 0 21300 0 03134 1 05 1 25382 1 51533 0 52493 0 22863 0 03126 0 00012 计算出 0 596 f的近似值 解答 我们依次输入5 0 40 0 41075 0 55 0 57815 0 65 0 0 69675 0 8 0 88811 0 9 1 02652 2 2 14 运行结果如下 这个结果极近似于例题的答案 0 63192 从结果我们不难看出 通过这个算法所得到的结果与它的真是值之间的误差 很小 即通过算法算出的牛顿插值是法 0 596 f的近似值 这样这个算法的可行 性得证 15 总结 通过以上两个例题 可以看出 这样一个 C 程序可以使复杂难算的拉格朗日 插值和牛顿插值很方便的计算出 既不需要熟练的操作技巧 又不需要花费大量 的时间和精力 同时 我们可以看到 至少在数组的数量小于 20 组的时候 计算 的精确度是很高的 虽然用其他的大型计算工具 也会快速的计算出插值 例如 MATLAB 程序 但操作起来比较复杂 而且对设备有一定的要求 一般电脑上没有 装 MATLAB 环境 没法运行 但是这样的一个小程序 携带方便 运算和操作都很 简单 在工程技术中 经常会遇到插值之类的计算问题 例如在半 导体技术中 设计晶体管和分析其性能时 常常涉及到与半导体 的杂质浓度有关的参盘 在温 度自动控制系统中的热电偶和温 度的对应关系 当采用计算机辅助分析和控制 时 必须将这些关系曲线离散化 然后运用插值法进行数学分析 最终得到我们 需要的结果 16 参考文献 1 李庆扬 易