1、 本科毕业论文 （ 20 届） 自适应数值积分算法及其程序设计 所在学院 专业班级 信息与计算科学 学生姓名 学号 指导教师 职称 完成日期 年 月 I 摘要 数值积分已有大量的研究 , 并在各个领域都有广泛的应用 , 但是加快计算速度 , 提高数值精度的算法仍是我们在不断探究的 . 自 适应积分算法就是一种通过变步长来提高精度的算法 . 该算法可以根据各子区间不同的情况分别给予处理 , 以减少不必要的函数值计算 . 本文介绍了三种自适应积分算法 . 并给出数值例子 , 以表明自适应算法的有效性 . 关键词 : 数值积分 ; 自适应 ; 辛普森公式 ; 梯形公式 ; 龙贝格积分 II Abst
2、ract Approximate Computing of definite integral are widely used in some field. How to improve convergent speed and numerical precision is the research key of numerical methods. Adaptive algorithm is a variable step size algorithm and it can reduce computation amounts. In this thesis, three adaptive
3、algorithms are presented. Numerical example shows that the methods are very effective. Keywords: Adaptive integral algorithm; Matlab program; Simpson rule; Trapezoidal rule; Romberg integration III 目录 摘要 . Abstract . 1 引言 . 1 2 数值积分的基本知识 . 2 2.1 一般的数值求积公式 . 2 2.2 复化的数值求积方法 . 3 2.3 龙贝格积分法 . 4 3 自适应积分
4、算法 . 6 3.1 自适应辛普森算法 . 6 3.2 自适应梯形公式 . 8 3.3 龙贝格外推法和自适应辛普森相结合的新型自 适应算法 . 10 4 数值例子及 MATLAB 程序实现 . 12 5 小结 . 15 参考文献 . 16 致谢 . 17 1 1 引言 数值积分是工程师和科学家使用的工具 , 用来计算无法解析求解的定积分的近似解 . 计算定积分时 , 人们首先会想到牛顿 -莱布尼茨公式 , 问题似乎已经解决 . 可是当我们遇到这样的情形如 ()fx是由测量或数值计算给出数据表时或者用牛顿 -莱布尼茨需要大量的函数值计算时 , 如果用数值积分方法来解决要方便得多 , 既节省工作量
5、 , 又满足精度要求 . 而数值积分方法 的好坏取决于达到精度要求所需计算量的大小 , 主要依赖于所需计算函数值的个数多少 . 目前已有辛普森求积公式 , Newton-Cotes 求积公式等以及复化的求积公式 . 复化的求积方法比一般的求积方法精度更高 . 但是 复 化 求积 公式 通常适用于被积函数变化不太大的积分 , 如果在求积区间中被积函数变化很大 , 有的部分函数值变化剧烈 , 另一部分变化平缓 . 这时统一将区间等分用复合求积公式计算积分工作量大 , 因为要达到误差要求对变化剧烈部分必须将区间细分 , 而平缓部分则可用大步长 , 针对被积函数在区间上不同情形采用不同的步长 , 使得
6、在满足精度前提下积分计算工作量尽可能小 , 针对这类问题的算法技巧是在不同区间上预测被积函数变化的剧烈程度确定相应步长 , 这种方法称为自适应 求积 法 . 自适应辛普森数值求积公式是 由 G. F. Kuncir于 1962年在 数值积分方法 中提出的 . 2000年 , Walter Gander和 Walter Gautschi发表了 自适应积分再谈 . 文章介绍了一种基于Gauss-Lobatto求积和 Kronrod对 Gauss-Lobatto求积的扩展的新的求积方法 . 2005 年 , 曾玉华和蒋光彪在 一种自 适应的四阶 Newton-Cotes 求积方法中提出了四阶 New
7、ton- Cotes 自适应求积公式中 . 2007 年 , 孙海涛和王元汉基于节点计算的自适应数值积分及其程序实现 , 针对完全无网格法的计算要求 , 提出了一种能自动适应任意计算域上各种节点分布方式的数值积分算法 , 该算法能随计算点的位置不同自动确定积分域及积分域内的求积点计算出数值积分结果 . 2011 年 , 杨录峰与赵双锁等在 一种变步长和变阶计算的自适应数值积分算法 中介绍了一种将自适应辛普森算法和龙贝格外推算法相结合的新型自适应算法 . 本文 共分五 个部分 , 第一部分是引言 , 介绍了自适应积分算法目前的研究成果及本文的主要内容 ; 第二部分介绍了数值积分的基本知识 ; 第
8、三部分主要是研究自适应的三种 算法法 , 自适应的辛普森法梯形法 及 由龙贝格积分和自适应辛普森相结合的新型算法 ; 第四 部 分则是对自适应算法 的 matlab程序实现 , 并给出相应的数值例子 ; 最后测试结果 , 得出 结论 .2 2 数值积分的基本知识 2.1 数值积分的基本求积公式 计算数值积分 ( ) ( )baI f f x dx (2.1) 定义 2.12 设给定一组节点 01 ,na x x x b 且知函数 ()fx在这些节点上的值 , 作插值函数0( ) ( )nn k kkL x y l x. 由于代数多项式 ()nLx的原函数是容易求出的 , 我们取 ()bnnaI
9、 L x dx 作为积分 ()If的近似值 , 这样构造出的求积公式 0( ) ( )nn k kkI x A f x (2.2) 称为是 插值型求积公式 . 式中 kA 通过插值基函数 ()klx积分得出 , 即 ( ) , 0 , 1 , , .bkkaA l x d x k n 在插值求积公式中 , 用不同次数的插值多项式就可以得到不同阶数的插值求积公式 ; 并且 , 在积分区间 , ab 上取不同的 1n 个节点 , 所得到的插值求积公式也是不同的 , 其近似的程度是不一样的 . 如果在积分区间上取 1n 个等距节点 , 则得到的插值求积公式称为 n阶 Newton-Cotes 公式
10、()0( ) ( ) ( )nb nkka if x d x b a C f x 这里 ()nkC 为 Newton-Cotes 系数 , ()0 0( 1 ) ()! ( ) !jknk nnnk jC t j d tn k n k 当 1n 时 (有两个等距求积节点 ), h b a ， (1) (1)011/ 2CC, 相应的求积公式就是梯形公式 3 3 ( ) ( ) ( ) ( ) .2 1 2bahhf x d x f a f b f 当 2n 时 (有三个等距求积节点 ), ( ) / 2h b a ， ( 2 ) ( 2 ) ( 2 )0 1 21 / 6 , 4 / 6 ,
11、1 / 6C C C , 相应的求积公式就是 辛普森公式 5 ( 4 )( ) ( ) 4 ( ) ( ) ( )6 2 9 0bab a a b hf x d x f a f f b f 当 4n 时 , 相应的求积公式为 4阶 Newton-Cotes公式 , ( )/ 4h b a , 求积公式为 7 ( 6 )1 2 3 4 5 8( ) 7 ( ) 3 2 ( ) 1 2 ( ) 3 2 ( ) 7 ( ) ( )9 0 9 4 5ba b a hf x d x f x f x f x f x f x f 2.2 复化的数值积分公式 辛普森公式 , 梯形公式和 Newton-Cote
12、s公式是基本的数值求积公式 . 为了提高求积公式的精度 , 通常可以把积分区间分成若干子区间 , 再在每个子区间 上用低阶求积公式 , 这就是复化的求积方法 , 它的实质是利用分段低次插值多项式的积分 , 去逼近 ()fx的积分 . 上述介绍的几种公式都有复化的形式 . 复化的梯形公式 : 令 2 , , ( ) / , ,jf C a b h b a n x a jh 其中 0,1, , .jn 这里存在一个 , ab , 在 n 个子区间上复合的梯形公式可以表示为 1 2 1( ) ( ) 2 ( ) ( ) ( )2 1 2nbja jh b af x d x f a f x f b h
13、 f 复化的辛普森公式 : 令 2 , , ( ) / , ,jf C a b h b a n x a jh 其中 0,1, , .jn 这里存在一个 , ab , 在 n 个子区间上复合的辛普森公式可以表示为 ( / 2 ) 1 /2 4 ( 4 )2 2 111( ) ( ) 2 ( ) 4 ( ) ( ) ( )3 1 8 0n nbjja jjh b af x d x f a f x f x f b h f 复化的柯特斯公式 : 令 6 , , ( ) / , ,jf C a b h b a n x a jh 其中 0,1, , 1.jn 取4n 的复合柯特斯公式为 1 1 11 3
14、10 0 14 4 2( ) 7 ( ) ( ) 3 2 ( ) ( ) 1 2 ( ) 1 4 ( ) .90n n nbka k k kk k khf x d x f a f b f x f x f x f x 4 2.3 龙贝格积分法 本文中还将用到龙贝格算法 . 龙贝格算法是龙贝格积分以逐次对分区间和复化求积为出发点 , 逐次修正近似值的方法构造出一种新的求积算法 . 它的优点在于提高收敛速度 . 龙贝格积分的方法如下 : 第一步 , 对积分 ( ) ( )baI f f x dx在 , ab 区间上应用梯形公式求得 0 , 0 ( ) ( )2baT f a f b第二步 , 将区间
15、 , ab 对分 , 应用复化梯形公式求得 0,1T , 并按公式 0,1 0,01,0 4 41TTT 求得辛普森公式的值 . 令 1i , 转第四步 ; 第三步 , 对区间 , ab 作 2i 等分 , 记相应的复化梯 形公式求得值为 120 , 0 , 1 1 11 ( ) ( 2 1 ) , 1 , 2 , 3 , ,2 2 2iii iijb a b aT T f a j i m , 然后按下式构造新序列 (见表 ) 1 , 1 1 , 4 , 1 , 2 , , , .41m m k m kmk mTTT m i k i m 0,0T 0,1T 1,0T 0,2T 1,T 2,2T
16、 0,3T 1,2T 2,3T 3,2T 0, 1iT 1, 2iT 2, 1iT 3, 2iT 0,iT 1, 1iT 2,iT 3,1iT ,nnT 第四步 , 若 ,0 1,0|iiTT ( 是事先给定精度 ), 则计算停止 , 输出 ,0iT , 否则用 1i 代替 i ,转入第三步 . 5 3 自适应积分算法 3.1 自适应辛普森积分算法 自适应辛普森积分法是以辛普森公式为基本求积公式来实现自适应积分的一种算法 .其主要思想是如果在一给定子区间上的辛普森法则不能满足精度要求 , 则该区间将被等分为两部分 , 在每个长度减半的区间上应用辛普森法则 , 重复这个过程得到积分的一个近似 值
17、 . 计算积分 ( ) ( )baI f f x dx 的近似值 . 给定精度 0 . 先取步长 h b a , 应用辛普森公式 44( ) ( ) ( , ) ( ) ( ) , ( , )1 8 0 2ba b a hI f f x d x S a b f a b (3.1) 其中 ( , ) ( ) 4 ( ) ( ) 62h a bS a b f a f f b 若把区间 ,ab 对分 , 步长 2 / 2 ( ) / 2 ,h h b a 在每个小区间上应用辛普森公式 , 则得 4 ( 4 )22( ) ( , ) ( ) ( ) , ( , )1 8 0 2hbaI f S a b
18、 f a b (3.2) 其中 2 ( , ) ( , ) ( , ) ,22a b a bS a b S a S b 2( , ) 4 ( ) ( ) ,2 6 4 2ha b h hS a f a f a f a 2 3( , ) ( ) 4 ( ) ( ) .2 6 2 4ha b hS b f a f a h f b 与 (3.1)式比较 , 若 ( 4 ) ( 4 )( ) ( ),ff 从而可得 4 ( 4 )216 ( , ) ( , ) ( ) ( )1 5 1 8 0 2b a hS a b S a b f 与 (3.2)式比较 , 则得到 2 2 1 211( ) ( ,
19、) ( , ) ( , )1 5 1 5I f S a b S a b S a b S S 这里 1 ( , ),S S a b 22( , )S S a b . 如果有 1215 ,SS (3.3) 我们可以得到 6 ( ) ( , ) ( , ) .22a b a bI f S a S b 此时取 2( , )S ab 即 ( , ( ) / 2 ) ( ( ) / 2 , )S a a b S a b b 作为 ()If 的近似值 , 可达到给定的误差精度 . 若不等式 (3.3)不成立 , 则应分别对子区间 ,( ) / 2a a b 及 ( ) / 2, a b b 再用辛普森公式
20、, 此时步长 32/2hh , 得到 3 ( ,( ) / 2)S a a b 及 3 ( ) / 2, )S a b b . 只要分别考察3| ( , ( ) / 2 ) | / 2I S a a b 及 3| ( ( ) / 2 , ) | / 2I S a b b 是否成立 . 对满足精度要求的区间不再细分 , 对不满足要求的还要继续上述过程 , 直到满足要求为止 . 它的算法如下 : 输入项 节点 ,ab; 误差容限 TOL ; 最大循环层次限制 N . 输出项 近似值 APP 或者超过 N 的警告 . STEP 1 令 0APP ; 1;i 10 ;iTOL TOL ;iaa ( )
21、 / 2;ih b a ( );iFA f a ( );iiFC f a h ( );iFB f b ( 4 ) / 3 ;i i i i iS h F A F C F B ( 用辛普森法在整个区间求近似值 . ) 1.iL STEP 2 当 0i 时重复第 3-5步 . STEP 3 令 ( / 2);iiFD f a h ( 3 / 2 );iiFE f a h 1 ( 4 ) / 6 ;i i iS h F A F D F C (用辛普森法在半分后区间求近似值 .) 2 ( 4 ) / 6 ;i i iS h F C F E F B 1 ;iva ( 在这一步保存数据 . ) 2 ;iv FA 3 ;iv FC4 ;iv FB 5 ;ivh 6 ;iv TOL 7 ;ivS
