当前位置:文档之家› 计算方法第1章_绪论

计算方法第1章_绪论

计算方法第1章_绪论
计算方法第1章_绪论

第一章绪论

1.1数值计算

现代科学的发展,已导致科学与技术的研究从定性前进到定量,尤其是现代数字计算机的出现及迅速发展,为复杂数学问题的定量研究与解决,提供了强有力的基础。

通常我们面对的理论与技术问题,绝大多数都可以从其物理模型中抽象出数学模型,因此,求解这些数学模型已成为我们面临的重要任务。

一、本课程的任务:

寻求解决各种数学问题的数值方法——如何将高等数学的问题回归到初等数学(算术)的方法求解——了解计算的基础方法,基本结构(否则只须知道数值软件)——并研究其性质。

立足点:

面向数学——解决数学问题

面向计算机——利用计算机作为工具

充分发挥计算机的功能,设计算法,解决数学问题

例如:迭代法、并行算法

二、问题的类型

1、离散问题:例如,求解线性方程组b

Ax=——从离散数据:矩阵A和向量b,求解离散数据x;

2、连续问题的离散化处理:例如,数值积分、数值微分、微分方程数值解;

3、离散问题的连续化处理:例如,数据近似,统计分析计算;

1.2数值方法的分析

在本章中我们不具体讨论算法,首先讨论算法分析的基础——误差。

一般来讲,误差主要有两类、三种(对科学计算):

1)公式误差——“截断误差”,数学?计算,算法形成——主观(人为):数学问题-数值方法的转换,用离散公式近似连续的数学函数进行计算时,一般都会发生误差,通常称之为“截断误差”;——以后讨论

2)舍入误差及输出入误差——计算机,算法执行——客观(机器):由于计算机的存储器、运算器的字长有限,在运算和存储中必然会发生最末若干位数字的舍入,形成舍入误差;在人机数据交换过程中,十进制数和二进制数的转换也会导致误差发生,这就是输入误差。这两种误差主要是由于计算机的字长有限,采用浮点数系所致。

首先介绍浮点数系

一、计算机上的运算——浮点运算

面向计算机设计的算法,则先要讨论在计算机上数的表示。科学记数法——浮点数:约定尾数中小数点之前的数全为零,小数点后第一个数不能为零。 目前,一般计算机都采用浮点数系,一个存储单元分成首数和尾数:

首数 尾数(位)

其中首数存放数的指数(或“阶”)部分,尾数存放有效数字。对于β进制,尾数字长为t 位的浮点数系),,,(U L t F β中的(浮点)数,可以用以下形式表示:

t j j

d d l t

t d d

d x fl ,,3,2,

01

1)221()( =<≤<≤?++±=ββ

ββββ

此处,指数l (称为阶)限制在U l L ≤≤范围内。

以下记实数系中的实数为R x ∈,它在浮点数系),,,(U L t F β中对应的浮点数记为),,,()(U L t F x fl β∈——β进制,t 尾数位数,U L ,阶的范围。

几乎所有近代计算机都采用“二进制”(即2=β):位、字节和字分别是指位数不同的二进制数。例如

位是一个二进制数(即0或1);字节是8个二进制数字;上表的最后一列是字节。

单精度浮点数(single precision )按32位存储,双精度浮点数(double precision )按64位存储。精度用于指明每个浮点数保留多少位以及尾数和阶数各分配多少位。单精度浮点数的尾数为23位、阶数为8位;双精度浮点数的尾数为53位(包含符号位)、阶数为11位(包含符号位)。双精度浮点数的等价二进制数如下所示:

位位尾数

符号位

位指数(含符号位)645211ddddd ddd f bb bbbb 浮点数的特点:

1、 实数转换到浮点数——浮点化,〈缺点:〉总会产生误差(除极个别的情况:

,2,1,0,2±±==l x l )

按 四舍五入,绝对误差:t l x fl x -≤-β2

1

)((举例),

〈优点:〉浮点化产生的相对误差有界(与数字本身的数量级无关)

t x x fl x x -≤-=

12

1

)()(βδ 注:设实数R x ∈,则按β进制可表达为:

1,,,3,2,01

1)11221(+=<≤<≤?++++++±=t t j j

d d l

t t d t t d d

d x ββ

βββββ按四舍五入的原则,当它进入浮点数系),,,(U L t F β时,若β2

1

1<

+t d ,则 l t

t d d

d x fl ββββ?++±=)221()(

若β211

≥+t d ,则 l

t

t d d d x fl ββββ?+++±=)1221()(

对第一种情况:

t l l

t

l t t d x fl x -++=?≤

?+=-βββββ21)2

1(1)(

)(1

1

对第二种情况:

t l l

t l t t d x fl x -++=?≤?--=

-ββββββ21)2

1(1)(11

就是说总有: t

l x fl x -≤

-β2

1)( 另一方面,由浮点数要求的 β<≤11d , 有l x ββ

1

,将此两者相除,便得

t x x fl x -≤-12

1

)(β

2、每一个浮点数系的数字有限: 1)1()1(21++---L U t ββ

3、浮点数系中的运算非自封闭,(因为数字有限等)

例:在)5,5,4,10(-F 中,32102001.,105420.?=?=-y x ,运算y x *和y x /,的结果显然已不在此浮点数系内,而y x +或y x -也不在此浮点数系内,需)(y x fl 结果才在此浮点数系内。

浮点运算应注意:

1)避免产生大结果的运算,尤其是避免小数作为除数参加运算; 2)避免“大”“小”数相加减;

3)避免相近数相减,防止大量有效数字损失; 4)尽可能简化运算步骤,减少运算次数。 原因:

记t

x x fl x x -=-==12

1)(max

)(max βδ?,由x x fl x ?≤-)(,可得: y x y x fl y x ?≤-)()( (“。”表示任意一种四则运算)

此处 ? 是由机器字长(实质上是尾数字长t 的大小)确定的常数(它反映了实际运算的精度)。

显然,若要求运算的舍入误差小,应使运算结果(如:y

x y x y x ,,?±)较小。 尤其是小分母运算:

y

y x y x δ

δ=-+,小y ?大误差。 其次,当浮点数系中两个数量级相差较大的数相加(或减),注意到由于浮点数系中数字字长的有限性,可能导致“大数吃小数”。例如,)5,5,4,10(-F 中

13102317.,108231.-?=?=y x ,则

x y x =?±?=?±?=±-3313100000.108231.102317.108231.

似乎)(x y y <<没有参加运算。

第三,同样,由于浮点数系中数字字长的有限性,当两个相近数相减时:例如,在)5,5,8,10(-F 中,331082317832.,1082317844.?=?=y x ,两数相减:

31012000000.-?=-y x ,计算结果仅剩2位有效数字,而原来参加运算的数字有8

位有效数字,这将严重影响最终计算结果的精度。

二、 算法分析

作为一个可用的算法,必须考虑其效率和可靠性,

定义:计算机完成一个乘法和一个加法,称为一个浮点运算(记为flop ); 注:由于计算机在运算时,加(减)法所耗时间远少于乘(除)法,所以通常只须计算乘法的次数,因此也有“一个算法需要多少个‘乘法’”这一提法。

1、计算效率——可计算性(计算复杂性——空间、时间) 例:解线性方程组b Ax =的Grammar 方法:A

A i

i x =

,其中A 是方程

组系数矩阵A 对应的行列式,而i A 则是以右端向量b 替代A 的第i 列所得矩阵对应的行列式。由线性代数知识可知,若)(ij α=A ,则

∑-=

n n

ni i

i i i i J ααα 2

1

2

121),()1(A ,

其中),,,(21n i i i J 是由{n ,,2,1 }变换到{n i i i ,,21}所需的置换次数。可见每计算一个行列式,需要!)1(n n ?-个浮点运算;因此,按Grammar 方法解方程组约需

!)1(2n n N ?-= 个浮点运算。当20=n 时

201070728.9?≈N ,用一个运算速度

为秒/108的计算机进行求解,约需510078.3?年(日前报道我国计算机已达到/1038408?秒,这仍需近10年)

。而n=20的方程组应该说是一个小型的方程组。因此Grammar 方法是一个不能接受的算法,它缺乏可计算性。第二章将介绍的Gauss 消去法和迭代法就有较高的效率,具有很好的可计算性。

2、计算可靠性

作为算法,除了考虑其效率外,必须重视可靠性,它包括两方面: 问题的性态 和 方法的稳定性 问题的性态

所计算的问题当原始数据发生小扰动时,问题的解一般也发生扰动。问题的性态——问题的解对原始数据发生变化的敏感性。

原始数据小扰动?问题解 ???—问题是病态的

—大变化—问题是良态的

—小扰动

例:线性方程组:

?????????=

++=++=++604751413

1121341312

1

6113121321321321x x x x x x x x x 的解是:????? ??=111X

若将方程组的系数改写成具有2位有效数字的小数:

?????=++=++=++78

.020.025.033.01.125.033.050.08.133.050.000.132132121x x x x x x x x x 的解则变成:???? ??--=65.3325.3822.6~X ;

这是一个典型的病态方程组。

一般:由原始数据 ?x 计算结果)(x f ,

扰动后的数据 ?x ~计算结果)~(x f , 若对问题f 存在常数m ,满足关系式:

x

x

x m x f x f x f ~)()~()(-≤-

或 x

x

x m ~ f(x)

)

x ~f(-f(x)sup -= 则称(相对误差之比的上界)m 为该问题的条件数,记作 )(f cond m =;由

微积分中值定理知识容易计算出,当x x ~≈时,)

()

()(x f x f x

f cond '≈ 。 稍后我们在第二章将对线性方程组的性态作进一步的分析。 算法的数值稳定性:

例:计算8,,1,0,1

1 ==?-n dx e x e I x n n ;

解:由微积分知识,可得计算公式,① 11--=n n nI I ,②)1(1

1n n I n

I -=-,我们将准确值与计算结果列表如下:

由上表可见,方法①中,原始步的误差,随着计算步数的增加被严重地放大,特别是8I 竟变成负数(注意:被积函数是非负函数),而方法②则相反;这是因为

方法①中,若前步有误差δ:δ+=--11~

k k I I ,则

δδk I k kI I k I k k k k -=--=-=--111~

1~, 说明1-k I 的误差δ,经一步计算后被扩大了k 倍,随着k 的增大,误差将被大大地扩大;而通过同样的分析可知:方法②中k I 的误差则被缩小k 倍。

算法的数值稳定性:算法对初始误差导致的最终误差的可控性,如果最终误差被有效地控制,则称算法是稳定的,否则就是不稳定的。

计算方法的课后答案

《计算方法》习题答案 第一章 数值计算中的误差 1.什么是计算方法?(狭义解释) 答:计算方法就是将所求的的数学问题简化为一系列的算术运算和逻辑运算,以便在计算机上编程上机,求出问题的数值解,并对算法的收敛性、稳定性和误差进行分析、计算。 2.一个实际问题利用计算机解决所采取的五个步骤是什么? 答:一个实际问题当利用计算机来解决时,应采取以下五个步骤: 实际问题→建立数学模型→构造数值算法→编程上机→获得近似结果 4.利用秦九韶算法计算多项式4)(5 3 -+-=x x x x P 在3-=x 处的值,并编程获得解。 解:400)(2 3 4 5 -+?+-?+=x x x x x x P ,从而 所以,多项式4)(5 3 -+-=x x x x P 在3-=x 处的值223)3(-=-P 。 5.叙述误差的种类及来源。 答:误差的种类及来源有如下四个方面: (1)模型误差:数学模型是对实际问题进行抽象,忽略一些次要因素简化得到的,它是原始问题的近似,即使数学模型能求出准确解,也与实际问题的真解不同,我们把数学模型与实际问题之间存在的误差称为模型误差。 (2)观测误差:在建模和具体运算过程中所用的一些原始数据往往都是通过观测、实验得来的,由于仪器的精密性,实验手段的局限性,周围环境的变化以及人们的工作态度和能力等因素,而使数据必然带有误差,这种误差称为观测误差。 (3)截断误差:理论上的精确值往往要求用无限次的运算才能得到,而实际运算时只能用有限次运算的结果来近似,这样引起的误差称为截断误差(或方法误差)。 (4)舍入误差:在数值计算过程中还会用到一些无穷小数,而计算机受机器字长的限制,它所能表示的数据只能是一定的有限数位,需要把数据按四舍五入成一定位数的近似的有理数来代替。这样引起的误差称为舍入误差。 6.掌握绝对误差(限)和相对误差(限)的定义公式。 答:设* x 是某个量的精确值,x 是其近似值,则称差x x e -=* 为近似值x 的绝对误差(简称误差)。若存在一个正数ε使ε≤-=x x e * ,称这个数ε为近似值x 的绝对误差限(简称误差限或精度)。 把绝对误差e 与精确值* x 之比* **x x x x e e r -==称为近似值x 的相对误差,称

计算方法作业第一章

习题二 1. 用二分法求方程0134=+-x x 在区间【0.3,0.4】内的根,要求误差不超过2102 1-?。 3.方程0123=--x x 在1.5附近有根,把方程写成4种不同的等价形式,并建立相应的迭代公式。 (1)231x x +=,32 11n n x x +=+ (2)211x x + =,=+1n x 211n x + (3)1 1 2 -= x x ,=+1n x 1 1-n x

(4)132-=x x ,= +1n x 13-n x 4.用迭代法求02.05 =--x x 的正根,要求准确到小数点后第5位 解:迭代公式:512.0+=+x x n 7.用迭代-加速公式求方程x e x -=在x=0.5附近的根,要求准确到小数点后第4位 解:迭代公式:x n e x -+=1,n n x q q x q x ---= +1111 8用埃特金加速法求方程13 -=x x 在区间【1,1.5】内的根,要求准确到小数点后第4位 解:迭代公式:13 1-=+x x n ,13 12-=++n n x x ,n n n n n n n x x x x x x x +--= ++-++122 1 212

9.用牛顿法求方程0133=--x x 在20=x 附近的根,要求准确到小数点后第3位 解:迭代公式:3 31 32 31 ----=+n n n n n x x x x x 11.分别用单点和双点弦截法求方程013 =--x x 在【1,1.5】内的根,要求 51102 1 ||-+?≤ -n n x x 解:单点:)111() 111()1(1 13 1--------- =+n n n n x x x x 双点:)1() 1()1(3 13 1311--------- =---+n n n n n n n n n n x x x x x x x x x x

数值计算方法第一章

第一章 绪 论 本章以误差为主线,介绍了计算方法课程的特点,并概略描述了与算法相关的基本概念,如收敛性、稳定性,其次给出了误差的度量方法以及误差的传播规律,最后,结合数值实验指出了算法设计时应注意的问题. §1.1 引 言 计算方法以科学与工程等领域所建立的数学模型为求解对象,目的是在有限的时间段内利用有限的计算工具计算出模型的有效解答。 由于科学与工程问题的多样性和复杂性,所建立的数学模型也是各种各样的、复杂的. 复杂性表现在如下几个方面:求解系统的规模很大,多种因素之间的非线性耦合,海量的数据处理等等,这样就使得在其它课程中学到的分析求解方法因计算量庞大而不能得到计算结果,且更多的复杂数学模型没有分析求解方法. 这门课程则是针对从各种各样的数学模型中抽象出或转化出的典型问题,介绍有效的串行求解算法,它们包括 (1) 非线性方程的近似求解方法; (2) 线性代数方程组的求解方法; (3) 函数的插值近似和数据的拟合近似; (4) 积分和微分的近似计算方法; (5) 常微分方程初值问题的数值解法; (6) 优化问题的近似解法;等等 从如上内容可以看出,计算方法的显著特点之一是“近似”. 之所以要进行近似计算,这与我们使用的工具、追求的目标、以及参与计算的数据来源等因素有关. 计算机只能处理有限数据,只能区分、存储有限信息,而实数包含有无穷多个数据,这样,当把原始数据、中间数据、以及最终计算结果用机器数表示时就不可避免的引入了误差,称之为舍入误差. 我们需要在有限的时间段内得到运算结果,就需要将无穷的计算过程截断, 从而产生截断误差. 如 +++=! 21 !111e 的计算是无穷过程,当用 ! 1 !21!111n e n ++++= 作为e 的近似时,则需要进行有限过程的计算,但产生了 截断误差e e n -.

计算方法第一章习题

第一章习题 2.按四舍五入原则,将下列各数舍入成5位有效数字: 816.9567 6。000015 17。32250 1.235651 93。18213 0。01523623 答案:816。96 6。0000 17。323 1.2357 93。182 0。015236 3.下列各数是按四舍五入原则得到的近似数,它们各有几位有效数字? 81.897 0。00813 6。32005 0。1800 答案:5 3 6 4 4.若1/4用0。25来表示,问有多少位有效数字? 答案:任意多位 5.若a=1.1062 , b=0.947 是经过舍入后得到的近似值,问:a+b, ab 各有几位有效数字? 答案:3 , 3 因为45110211021--?=?= da 33102 11021--?=?=db 31234102 1102110211021)(----?=?≤?+?=+=+db da b a d 4)15(102110121---?=??=a d r ,2)13(1018 110921---?=??=b d r 22410181101811021)(---?≈?+?=+=b d a d ab d r r r 6.设y 1=0.9863, y 2=0.0062是经过舍入后作为x 1和x 2的近似值,求1/y 1和1/y 2的计算值与真值的相对误差限及y 1y 2和真值的相对误差限。 答案: 53)14()1(*1*111*11*1*11*11*1*1 1106.51018 110921102111 11------?=?=??=?≤-=-=-=-n y y y y y y y y y y y y y y α也可用5)14(111 121111106.5109 21111)1(1---?=??====y dy y dy y y y d y d r 同理 31)12()1(*2*22*2*2 2103.81012 11062110211 11------?=?=??=?≤-==-n y y y y y y α 3 35*2*22)1*11*2*1*2*12*12*121*2*1*2 *121104.8103.8106.5---?≈?+?≤-+-=-+-=-y y y y y y y y y y y y y y y y y y y y y y

计算方法第一章作业

1.题目 (1)将ln(1+x)进行Taylor展开,展开到第11项,令x=1,计算ln2的近似值; (2)将ln(1+x)进行Taylor展开,展开到第11项,令x=-1/2,计算ln2的近似值; (3)将ln (1+x)/(1-x)进行Taylor展开,经过简单运算,求出ln2的近似值; (4)比较上述三种方法的计算精度,并给出简单的解释; (5)编写一段循环程序,对于(2) (3) 两种方法,使用累加和的方法求出ln2的近似值,循环结束的条件是累加和不再变化(使用双精度进行计算),统计累加次数并比较精度。 2.编程计算 (1) 计算结果: Out[6]: ln(1+x)的Taylor展开式; Out[7]: x=1时,ln2的近似计算结果; Out[8]:计算误差。 (2) 计算结果: Out[14]: ln(1+x)的Taylor展开式; Out[15]: x=-1/2时,ln2的近似计算结果;

Out[16]:计算误差。 (3) 计算结果: Out[22]: ln (1+x)/(1-x)的Taylor展开式; Out[23]: x=1/3时,ln2的近似计算结果; Out[24]:计算误差。 (4)比较分析 从上述三种计算结果,可以看出方法(3)计算误差最小,即计算精度:方法(1)<方法(2)<方法(3)。原因:利用泰勒公式进行数值的近似计算,根据泰勒公式: 其中是n阶泰勒公式的拉格朗日余项: 可见近似计算的误差即为。对于方法(1),方法(2) ,方法(3),可见三 种方法下的大小关系是:方法(1)>方法(2)>方法(3),所以说方法(3)的计算误 差最小。 此外,方法(3)计算结果out[22]可看出,在相同阶数的导数下,收敛速度更快,在有限的展开项中,原函数的导数收敛越快,结果越精确。 (5)方法(2)累加求和

计算方法第1章习题 - 参考答案

答案: 1.1 求下列各数的具有四位有效数字的近似值, 并指出其绝对误差限和相对误差限 根据绝对误差计算相对误差的公式: *2121** .0105.010 .01021 r n n m n n m a a a a a a x x x ε=?≤??≤--- (1) 05.10,0498756.10101* 11===x x 5 * * **52310975.4102 1 1012437.005.10101---?<= =?< ?=-x r εεε (2) 2* 22109901.0,990099009900.0101 1-?=== x x 5 * * **528-10055.0102 1109909900.0990100.01011---?<= =?

位效数字 ,有,位效数字或精确值 ,有位效数字,有位效数字 ,有位效数字,有2101,1021 100.54101,102 1 ,5000410159.0,1021 ,50.31410166.0,1021 ,3015.0310159.0,1021 ,0315.02*24*3*5 4*44**44*42**34*40**23*31**1-----------?=?=?=?=?==?=?==?=?==?=?==r r r r r x x x x x εεεεεεεεεε 1.3 为了使 3 1 的近似值的相对误差不超过0.1%, 问应取几位有效数字? %1.010105.1333.0105.03--* *=≤=?=?≤--n n x x x ,取n=4位有效数字 1.4 怎样计算下列各题才能使得结果比较精确? (1) 2 sin )2 cos(2sin )sin(ε ε ε+=-+x x x (2) )1(11arctan arctan )1arctan(11 2 ++=-+=+? +N N N N x dx N N 或2)5.0(11 ++N 三个公式计算结果比较 1e+001 9.00876529e-003 9.00876529e-003 8.98876404e-003 1e+002 9.90000987e-005 9.90000987e-005 9.89976488e-005 1e+003 9.99000001e-007 9.99000001e-007 9.98999751e-007 1e+004 9.99899998e-009 9.99900000e-009 9.99899998e-009 1e+005 9.99991042e-011 9.99990000e-011 9.99990000e-011 1e+006 1.00010961e-012 9.99999000e-013 9.99999000e-013 1e+007 1.00944643e-014 9.99999900e-015 9.99999900e-015 1e+008 -4.33680869e-019 9.99999990e-017 9.99999990e-017 1e+009 7.80625564e-017 9.99999999e-019 9.99999999e-019 1e+010 -6.94973593e-017 1.00000000e-020 1.00000000e-020 (3) x x x x x x x x x x x cos 1sin sin )cos 1(sin sin )cos 1()cos 1)(cos 1(sin cos 12+= +=++-=- (4) o o o o o o o 21sin 21cos 11cos 11sin 1cos 11cos 11cos 1222=-+=+-=-或 (5) +?+?+ =-9-6-3-001 .01031 1021101! !e (6) ) 11010(1 ln ) 11010() 11010)(11010(ln )11010ln(8 4 8 4 848484-+=-+-+--=--

相关主题
文本预览
相关文档 最新文档