下载文档原格式
实验四 数值积分--Romberg 积分法实验目的:1、了解逐次分半法的基本原理和方法；2、了解Richardson 外推法的基本原理和方法；3、在1、2的基础上理解Romberg 积分法的基本原理和方法并编程实现；实验内容(自己填写相关公式和原理，以下仅作参考，个别符号与书中不一致) 考虑积分()()ba I f f x dx =⎰欲求其近似值，可以采用如下公式：（复化）梯形公式 110[()()]2n i i i h T f x f x -+==+∑ 2()12b a E h f η-''=- [,]a b η∈ （复化）辛卜生公式 11102[()4()()]6n i i i i h S f x f x f x -++==++∑ 4(4)()1802b a h E f η-⎛⎫=- ⎪⎝⎭[,]a b η∈ （复化）柯特斯公式 111042[7()32()12()90n i i i i h C f x f x f x -++==+++∑ 31432()7()]i i f x f x +++6(6)2()()9454b a h E f η-⎛⎫=- ⎪⎝⎭[,]a b η∈ 这里，梯形公式显得算法简单，具有如下递推关系121021()22n n n i i h T T f x -+==+∑ 因此，很容易实现从低阶的计算结果推算出高阶的近似值，而只需要花费较少的附加函数计算。
但是，由于梯形公式收敛阶较低，收敛速度缓慢。
所以，如何提高收敛速度，自然是人们极为关心的课题。
为此，记0,k T 为将区间[,]a b 进行2k等份的复化梯形积分结果，1,k T 为将区间[,]a b 进行2k 等份的复化辛卜生积分结果，2,k T 为将区间[,]a b 进行2k 等份的复化柯特斯积分结果。
根据李查逊（Richardson ）外推加速方法，可得到1,11,,0,1,2,40,1,2,41m m k m km k m k T T T m -+-=-⎛⎫= ⎪=-⎝⎭可以证明，如果()f x 充分光滑，则有,lim ()m k k T I f →∞= （m 固定） ,0lim ()m m T I f →∞= 这是一个收敛速度更快的一个数值求积公式，我们称为龙贝格积分法。
《计算方法》上机实验试题
1. (25分)计算积分
dx x x I n n ⎰
+=105， n=0,1,2,…,20 若用下列两种算法 (A) n I I n n 151+
-=- (B) ⎪⎭
⎫ ⎝⎛-=-n n I n I 1511 试依据积分I n 的性质及数值结果说明何种算法更合理。
2. (25分)求解方程f(x)=0有如下牛顿迭代公式
)()(111---'-
=n n n n x f x f x x ， n ≥1，x 0给定 (1) 编制上述算法的通用程序，并以ε<--1n n x x （ε为预定精度）作为终止迭
代的准则。
(2)
利用上述算法求解方程 0cos :)(=-=x x x f
这里给定x 0=π/4，且预定精度ε=10-10。
3. (25分) 已知)3()(x x e x e x f -=，
(1)
利用插值节点x 0=1.00，x 1=1.02，x 2=1.04，x 3=1.06，构造三次Lagrange 插值公式，由此计算f(1.03)的近似值，并给出其实际误差； (2) 利用插值节点x 0=1，x 1=1.05构造三次Hermite 插值公式，由此计算f(1.03)的近
似值，并给出其实际误差。
4. (25分) 利用Romberg 算法计算积分
⎰
+4802cos 1dx x
精确到10
－4
总体要求：打印各题的程序代码及数值结果。
《计算方法引论》-徐翠微主编2009 ~ 2010学年第一学期计算方法教案计0701-0703 4h第二章插值法知识点:拉格朗日插值法，牛顿插值法，余项，分段插值。
实际问题中，时常不能给出f(x)的解析表达式或f(x)解析表达式过于复杂而难于计算，能采集的只是一些f(x)的离散点值{xi,f(xi)}(i=0,1,2,…n)。
因之，考虑近似方法成为自然之选。
定义:设f(x)为定义在区间[a，b]上的函数，x0,x1,…,xn为[a，b]上的互异点，yi=f(xi)。
若存在一个简单函数,(x)，满足(插值条件),(xi)=f(xi)，i=0，1，…，n。
则称 ,(x)为f(x)插值函数，f(x)为被插函数,点x0,x1,…,xn为插值节点,点{xi,f(xi)},i=0,1,2,…n为插值点。
于是计算f(x)的问题就转换为计算 ,(x)。
构造插值函数需要解决:插值函数是否存在唯一;插值函数如何构造(L插值);插值函数与被插函数的误差估计和收敛性。
对插值函数 ,(x)类型有多种不同的选择，代数多项式常被选作插值函数。
P23(2.18)和(2.19)指出，存在唯一的满足插值条件的n次插值多项式p(x)。
但是需要计算范德蒙行列式，构造插值多n项式工作量过大，简单表达式不易得到，实际中不采用这类方法。
p(x)?f(x) n插值法是一种古老的数学方法，拉格朗日(Lagrange)、牛顿(Newton)等分别给出了不同的解决方法。
拉格朗日插值拉格朗日(Lagrange)插值的基本思想:把插值多项式p(x)的构造问题转化为n+1个插值基函数l(x)(i=0,1,…,n)的ni构造。
(1)线性插值?构造插值函数已知函数y=f(x)的两个插值点(x,y)，(x,y)，构造多项式y=p(x)，使p(x)=y,p(x)=y。
001111001111 《计算方法引论》、徐翠薇，高等教育出版社 2008年4月第三版第二章Lagrange插值法2009 ~ 2010学年第一学期计算方法教案计0701-0703 4h由直线两点式可知，通过A，B的直线方程为, y y 1 0 , , , y y ，， x x p ( x ) + 0 0 1 , x x 1 0变形为 x-x0 x-x1 y 1, ， p(x) y 10 x1-x0 x0-x1记 x-x0 x-x1 , l(x) , l(x) 10 x1-x0 x0-x1则p(x)=l(x)y+l(x)y10011插值完毕～注意性质:l(x)=l(x)=1，l(x)=l(x)=0，p(x)=y，p(x)=y。
2007年计算引论试题班级360602 学号36060203 姓名柴巧珍1. 正则表达式(a⋃b)*a*表示的语言L((a⋃b)*a*)是什么? 请写出计算过程. (5分)L((a⋃b)*a*)=L((a ∪b)*)L(a*)=L((a ∪b)*){a}*=L((a ∪b))*{a}*=(L(a) ∪L(b))*{a}*=({a} ∪{b})*{a}*={a,b}*{a}*={w∈{a,b}*| w以a结束}2. 设M为确定型有限自动机(K, ∑, δ, s, F), 其中K={q0, q1}, ∑={a,b}, s=q0, F={q0}, δ如下表1所示:问: M能否接受字符串aabbaa? 请将计算过程写出来, 并画出状态图. (15分)3. 设上下文无关文法G=(V, ∑, R, S), 其中V={a, b, S, A}, ∑={a, b}, R={S→AA, A→AAA, A→a, A→bA, A→Ab}, 请写出关于字符串babbab的两种推导过程.(20分)4. 设图灵机M＝(Q, C,A,δ,B,q1, q2), 其中Q={q1,q2}, C={0, 1, B}, A={0,1}, δ如表2所示请给出M关于01010和0110的计算, 并分别说明M是否接受它们.(20分)5. 已知上下文无关文法G=({A, B, C, S}, {a, b}, P, S), 其中：P中的产生式集合为：{S→AB, S → BC, B → CC, B → b, C → AB, C → a, A → BA, A → a}请用CYK算法检查S能否推导出ω=bbaaa, 请写出详细的过程. (20分)6. 请结合学过的计算模型简要阐述你对计算的理解, 并举例说明. (20分)。
计算方法引论课后答案第一章误差1.什么是模型误差，什么是方法误差？例如，将地球近似看为一个标准球体，利用公式 $A=4\pi r$ 计算其表面积，这个近似看为球体的过程产生的误差即为模型误差。
在计算过程中，要用到 $\pi$，我们利用无穷乘积公式计算 $\pi$ 的值：pi=2\cdot\frac{2}{1}\cdot\frac{2}{3}\cdot\frac{4}{3}\cdot\f rac{4}{5}\cdot\frac{6}{5}\cdot\frac{6}{7}\cdot\frac{8}{7}\cdot\ frac{8}{9}\cdot\cdots我们取前9项的乘积作为 $\pi$ 的近似值，得$\pi\approx3.xxxxxxxx5$。
这个去掉 $\pi$ 的无穷乘积公式中第9项后的部分产生的误差就是方法误差，也称为截断误差。
2.按照四舍五入的原则，将下列各数舍成五位有效数字：816.956，76.000，.322，501.235，.182，130.015，236.23.解：816.96，76.000，.501.24，.130.02，236.23.3.下列各数是按照四舍五入原则得到的近似数，它们各有几位有效数字？81.897，0.008，136.320，050.180.解：五位，三位，六位，四位。
4.若 $1/4$ 用 0.25 表示，问有多少位有效数字？解：两位。
5.若 $a=1.1062$，$b=0.947$，是经过舍入后得到的近似值，问：$a+b$，$a\times b$ 各有几位有效数字？已知 $da<\frac{1}{2}\cdot10^{-4}$，$db<\frac{1}{2}\cdot10^{-3}$，又 $a+b=0.\times10$。
begin{aligned}d(a+b)&=da+db\leq da+db=\frac{1}{2}\cdot10^{-4}+\frac{1}{2}\cdot10^{-3}=0.55\times10^{-3}<\frac{1}{2}\cdot10^{-2}end{aligned}所以 $a+b$ 有三位有效数字；因为 $a\timesb=0.xxxxxxxx\times10$。
第一章误差1问3.142, 3.141,乡分别作为兀的近似值各具有几位有效数字? 分析利用有效数字的概念可直接得出。
解 n =3.141 592 65-记 Xi=3.142, X 2=3.141 , x 尸乡. 由 n-X1=3.141 59--3.142=-0.000 40…知 因而X 】具有4位有效数字。
由 H -X 2=3.141 59--3.141=-0.000 59…知 因而X ：具有3位有效数字。
由—乡=3.141 59 —-3.142 85—-0.001 26…知 因而禺具有3位有效数字。
2 已知近似数x*有两位有效数字，试求其相对误差限。
分析本题显然应利用有效数字与相对误差的关系。
解 利用有效数字与相对误差的关系。
这里n=2,ai 是1到9之间的数字。
3已知近似数的相对误差限为0.3%,问x*至少有几位有效数字？分析本题利用有效数字与相对误差的关系。
解山是1到9间的数字。
设x*具有n 位有效数字，令-11+1=」，则n=2,从而x*至少具有2位有效数字。
4计算srnl.2,问要取几位有效数字才能保证相对误差限不人于0.01%。
分析本题应利用有效数字与相对误差的关系。
解 设取n 位有效数字,由sinl.2=0.93•••,故ai=9。
解 ^T^-^y7\ = 0.131 8X10亠0.131 6X 10—0.2X W 5/ jy /6U结果只有一位有效数字，有效数字大量损失，造成相对误差的扩犬，若通分后再计算: 就得到4位有效数字的结果。
此例说明，在数值计算中，要特别注意两相近数作减法运算时，有效数字常会严重损失, 遇到这种情况，一般采取两种办法：第一，应多留几位有效数字；第二，将算式恒等变形, 然后再进行计算。
例如，当X 接近于0,计算1 — C0SX 时,应先把算式变形为S111X 再计算。
又例如，当X 充分人时，应作变换6计算d = Q2 — l)6,取、2心1・4,采用下列算式计算:解不等式養 xlO-^1 <1(T 4知取n=4即可满足要求。
《计算方法》练习题一 参考答案练习题第1套参考答案 一．填空题 1．210- 2．))((!2)(b x a x f --''ξ ３．52４．按模最大 ５．]0,2[- 二．单选题１．Ｃ ２．Ａ ３．Ｃ ４．Ｂ ５．Ｃ 三．计算题１．22122122121)2()42()3(),(--+-++-+=x x x x x x x x ϕ，由0,021=∂∂=∂∂x x ϕϕ得：⎩⎨⎧=+=+9629232121x x x x ， 解得149,71821==x x 。
２．⎰≈++++≈21697.0]217868581[81x dx ，9611612)(2=⨯≤M x R 。
３．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡→⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡→⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡1142242644223214264426453426352回代得：Tx )1,1,1(-=４．因为Ａ为严格对角占优阵，所以雅可比法收敛。
雅可比迭代公式为：⎪⎪⎪⎩⎪⎪⎪⎨⎧=+=++=+=+++Λ,1,0,)1(41)3(41)1(41)(2)1(3)(3)(1)1(2)(2)1(1m x x x x x x x m m m m m m m 。
取T x )1,1,1()0(=计算得： T x )5.0,25.1,5.0()1(=。
５．因为0875.0)5.0(,01)0(<-=>=f f ，所以]5.0,0[*∈x ，在]5.0,0[上，06)(,043)(2≥=''<-='x x f x x f 。
由0)()(0≥''x f x f ，选00=x ，由迭代公式：Λ,1,0,4314231=-+--=+n x x x x x n n n n n 计算得：25.01=x 。
四．证明题１．设))()(()()()(),)()(()(10110x t x t x k t L t f t g x x x x x k x R ----=--=，有x x x ,,10为三个零点。
