(西南交大戴克俭版)计算方法绪论.ppt

1、1,西南交通大学信息学院 计算机教育中心戴克俭,数值计算科学,2,自我介绍,姓名：戴克俭 Email：,3,教材及参考教材,教材：数值计算方法 作者：吕同富 康兆敏 出版社：清华大学出版社 参考教材： 数值分析(第四版) 作者：李庆扬 王能超 易大义 出版社：华中科技大学出版社 数值计算方法(第二版) 作者：林成森 出版社：科学出版社,4,第一章 绪 论,实际问题,数学模型,数值方法,程序设计,上机计算,1.1 科学计算的一般过程,数值计算是研究各种数学问题的数值计算方法。计,算机的问世和广泛使用，极大地刺激和促进了该学科的,发展。目前，科学计算方法已发展成为与科学理论、科,学实验相并列的第三

2、种科学方法，有着极为广泛的应用。,利用计算机解决科学计算问题，一般需要经过以下,几个步骤：,分析结果,5,1.1 科学计算的一般过程,1.1.1 对实际工程问题进行数学建模,应用有关学科知识和数学理论，将实际工程问题，,用精炼准确的数学语言对其核心部分进行描述并给出数学,模型，这一过程称为数学建模。,一个好的数学模型须符合以下两方面要求：,一是数学模型要能真实而准确地反映实际工程问题的本质,二是数学模型所用的数学算法能在计算机上实现，这两者,缺一不可。,6,1.1 科学计算的一般过程,1.1.2 对数学问题给出数值计算方法,计算机无论如何先进，它所能执行的计算也不过是简,单的算术运算和逻辑运算

3、，要想使计算机能够解决科学和,工程计算问题，需把从科学和工程实际问题中建立数学模,型数值化，也就是根据不同的数学问题，寻求不同的数值,计算方法。数值计算方法中只能有算术运算和逻辑运算，,否则计算机将无法计算，这将直接关系到能否把计算机用,于实际问题。,7,1.1 科学计算的一般过程,1.1.3 对数值计算方法进行程序设计,一个好的数值计算方法要通过程序设计才能在计算机,上实现。程序设计要求用最简练的计算机语言，最快的速,度、最少的存储空间来实现某种要求的计算结果。要到达,这样的要求，程序设计者不仅要掌握数值计算方法，而且,要熟悉并能熟练使用计算机语言，准确无误地描述每一个,算法，并能以最快的速

4、度发现和解决计算过程中出现的各,种问题。,8,1.1 科学计算的一般过程,1.1.4 上机计算并分析结果,前面三个阶段工作的结果如何？还需要上机实验才能,得出结论。上机计算的结果是否与工程实际相符合？所做,研究是否具有推广价值？都是必须关注的问题。若与工程,实际不相符合，则须找出原因，回到前面三个阶段，继续,研究，直到得出正确结论为止。,9,1.2 数值计算方法的研究内容和特点,1.2.1 数值计算方法的研究内容,数值计算方法使科学发展产生了巨大飞跃，它使各学,科领域从定性分析阶段走向定量分析阶段，从粗糙走向精,密。,数值计算方法是数学的一个分支，它以计算机为工具,以数值代数、数值逼近、常微分

5、方程数值解、偏微分方程,数值解、最优化理论与方法等为研究内容。,10,1.2 数值计算方法的研究内容和特点,1.2.2 数值计算方法的特点,例1.1 线性方程组Ax=b的行列式解法Cramer法则。,理论上可用来解线性方程组，用这种方法解一个n元线性,方程组，要计算n+1个n阶行列式的值，按Laplace展开法,计算n阶行列式，总共要计算,次乘法，不计加法，解一个n元线性方程组，需计算,次乘法。当n很大时，计算量是很大的。,11,1.2 数值计算方法的研究内容和特点,例如一个20元的线性方程组，大约需要,次以上,的乘法，每秒可做上百万次乘法的计算机，每年可做,所以，在每秒可做,次乘法，,上百万

6、次乘法的计算机上，用Cramer法则解一个20元线性,方程组，所需的计算时间是,万年,其实解线性方程组有很多方法，如Gauss消去法，一个20,元的线性方程组乘法次数不超过3000次，即使用一台微型,计算机。只需几秒钟就能完成计算。,12,1.2 数值计算方法的研究内容和特点,这个例子说明研究数值计算方法很有必要 ，因为数值,计算方法所研究的正是在计算效率上最佳的或近似最佳的,方法，而不是像Cramer法则这样的方法。,13,例1.2 计算下列积分的值：,通过直接计算可得In的递推公式：,(1-1),(1-2),由高数知识可推得In具有如下性质：, In0；, In单调递减；,1.2 数值计算

7、方法的研究内容和特点,14,下面用两种算法计算In。,算法A：按下列递推公式计算：,1.2 数值计算方法的研究内容和特点,计算结果如下：,15,1.2 数值计算方法的研究内容和特点,表1.1 算法A的计算结果,16,1.2 数值计算方法的研究内容和特点,由表1.1可见，该算法产生的数值解自n=7开始出现负,值，且绝对值逐渐增加，这显然与In固有的性质矛盾，因,此本算法所得的数值解不符合问题的要求。究其原因，在,构造算法时未能充分考虑原积分模型的性态，即由式(1.2),其计算从In-1到In每向前推进一步，其计算值的舍入误差便,增长5倍，误差由此积蓄传播导致最终数值解与原问题相,悖的结果。为了克

8、服这一缺点改进算法A为算法B。,算法B：按下列递推公式计算：,17,表1.2 算法B的计算结果,由于该算法每向后推一步，其舍入误差便减少5倍，,因此获得了符合原积分模型性态的数值结果。,1.2 数值计算方法的研究内容和特点,18,1.2 数值计算方法的研究内容和特点,上面两个例子表明，数值计算方法与纯数学有明显的,不同，这种不同主要是由于数值计算方法是纯数学与科学,工程实际以及计算机相结合而形成的一门数学分支。它既,有纯数学高度抽象性、严密科学性的特点，又有应用的广,泛性与实际实验的高度技术性的特点，是一门与计算机使,用密切结合的实用性很强的学科。,一个好的数值计算方法，概括起来有以下特点：,

9、 面向计算机数值计算方法理论的发展，与计算机技术,的发展密切相关。,19,1.2 数值计算方法的研究内容和特点, 数值计算方法的理论分析。, 一个好的数值算法不仅要节省运算时间，而且要节省,计算机的存储空间。, 实际验证数值计算方法。,20,1.3 计算过程中的误差及其控制,1.3.1 误差的来源, 模型误差,从实际问题建立的数学模型往往都忽略了许多次要,的因素，因此产生的误差称为模型误差。, 观测误差（参数误差）,一般数学问题包含若干参数，他们是通过观测得到,的，受观测方式、仪器精度以及外部观测条件等多种因,素不可能获得精确值，由此而来产生的误差称为观测误,差。,21,1.3 计算过程中的误

10、差及其控制, 截断误差（方法误差）,在求解过程中，往往以近似替代，化繁为简，这样,产生的误差称为截断误差。, 舍入误差,在计算机上运算时受机器字长的限制，一般必须,进行舍入，此时产生的误差称为舍入误差。,22,例1.3.1 试求摆长为L的单摆运动周期。,在物理学中我们知道单摆周期,其中：l为摆长；,g为自由落体加速度；m是质点的质量；如图所示。,由牛顿定律有：,1.3 计算过程中的误差及其控制,23,1.3 计算过程中的误差及其控制,24,1.3 计算过程中的误差及其控制,现在我们来分析单摆周期求解过程的误差情况：,25,1.3 计算过程中的误差及其控制,26,1.3 计算过程中的误差及其控制

11、,1.3.2 误差与有效数字, 误差概念,定义1 设 x* 为准确值，x 为其近似值，记,称 e 为近似值x的绝对误差或误差，er 为x 的相对误差。,若 |e|=|x*-x|，则称为 x的绝对误差限或误差限。,27,1.3 计算过程中的误差及其控制,则有：,，称,为x的相对误差限。,在实际应用中总是将下式作为x的相对误差。,记,28,1.3 计算过程中的误差及其控制, 有效数字,定义：如果一个数 x* 的近似值 x 的误差不超过某一位,的半个单位，该位到x 的第一位非零数字共有 n 位，,则称该近似值 x 具有 n 位有效数字。,x 有n位有效数字可写成如下标准形式：,(1-4),则有:,(

12、1-5),29,设Y0=28，按递推公式： 计算Y100。若取 （五位有效数字），则计算Y100的误差为多少。,解：,取 具有五位有效数字,由于原始数据有误差，由公式计算Yn时会产生误差,1.3 计算过程中的误差及其控制,30,1.3 计算过程中的误差及其控制,31,即计算Y100的误差为0.510-3,不稳定。因为随着n的增加，初始数据的误差也随之增加。,1.3 计算过程中的误差及其控制,32,1.3 计算过程中的误差及其控制,三、有效数字与误差限的关系,定理1.1 设 x 的近似值 x*由式(1-4)表示，若 x*具有 n 位,有效数字，则其相对误差限为：,(1-6),反之，若x*的相对误

13、差限满足：,(1-7),定理1表明，有效数字位数越多，相对误差限越小；,则 x*至少具有 n 位有效数字。,反之亦然。,33,1.3 计算过程中的误差及其控制,例1.3.2 设x*=2.72表示e具有3位有效数字的近似值，求,此近似值的相对误差限。,解：,，,由定理1.1有,34,1.3 计算过程中的误差及其控制,例1.3.3 要使,的近似值的相对误差限小于 0.1%，应,至少取几位有效数字？,解：,的首位数字是4，设近似数x有n位有效数字，,由定理1.1知相对误差限,，,令,，解得,，,即取4位有效数字，近似数的相对误差限不,超过0.1%,35,1.3 计算过程中的误差及其控制,1.3.3

14、误差的传播,在科学研究和工程计算中每步都可能产生误差，而,一个问题的解决往往要经过成千上万次的运算，不可能,每一步都加以分析，只能通过对误差的某些传播规律进,行分析，指出在数值计算中应遵循的原则，这将有助于,鉴别计算结果的可靠性并防止误差危害现象的产生。, 误差分析的重要性,36,1.3 计算过程中的误差及其控制, 误差的传播,计算机的数值运算主要是加、减、乘、除四则运算,带有误差的数据经过四则运算后误差怎样变化，用微分,可以描述。由于精确值与近似值通常很接近，其差可以,认为是较小的增量，则可以把误差看作微分，由此可得,误差的微分近似关系：,37,即x 的微分表示x 的绝对误差，lnx 的微分

15、表示它的相对,误差。利用这两个关系式及微分运算可以得到一系列有,关四则运算的误差结果，例如：,由,可得两数之和（差）的误差等于两数,的误差之和（差）；,由,可得两数之积的相对误差等于,两数的相对误差之和；,由,可得两数商的相对误差等于两数,的相对误差之差。,1.3 计算过程中的误差及其控制,38,1.3 计算过程中的误差及其控制,1.3.4 误差的控制, 简化计算步骤，减少运算次数,同一个计算问题，如果能减少运算次数不但可节省,计算时间，提高计算速度，而且还能减少误差的积累。,例如计算,的值，如果逐个乘要做254次乘法。,但若写成：,只要做14次乘法运算即可。,39,1.3 计算过程中的误差及

16、其控制,又如计算下列多项式,的值，,再逐次相加，一共要做,次乘法和n次加法。,如果将多项式作如下变形：,若直接计算,令：,则可得到如下递推公式：,40,1.3 计算过程中的误差及其控制,则只需做n次乘法和n次加法运算。,上述算法（即(1-8)式）就是著名的秦九韶算法。,(1-8),41,1.3 计算过程中的误差及其控制, 避免两相近的数相减,在数值计算中两相近数相减有效数字会严重损失。,例如x=618.45和y=618.32都是5位有效数字，但x-y=0.13,只有两位有效数字，所以最好改变计算方法，避免这类,运算的发生。,例1.3.4 利用式,，计算,在x=2处的导数值。,42,1.3 计算

17、过程中的误差及其控制,以下各式用右端计算就不致严重损失有效数字：,43,3 误差分析的方法与原则, 防止大数“吃掉”小数,在数值运算中有时数量级相差很大，而计算机字长,有限，如不注意运算次序就有可能出现大数吃小数的现,象，影响计算结果的可靠性。,例如在8位10进制上计算x=54272401+0.6，由于计算机内,计算时，要写成浮点数形式，且要先对阶，对阶时,，,在8位机上,表示0，因此,44,3 误差分析的方法与原则, 绝对值太小的数不宜作除数,绝对值很小的数作除数也会影响数值计算结果的精度。, 控制误差的传播积累，选取数值稳定的,计算公式,45,4 典型例题分析,例6 二次方程求根计算方案比较 求方程 ax2+bx+x=0的根， 其中a=1, b=-(5108+1), c=5108。 解 采用如下两种计算方案，在八位十进制机上计算。 方案 方案,46,例7 级数求和计算及加速收敛方案 利用下列级数计算e9与e20的值，要求误差不超过10-4。 (1-11) 方案 独立算出级数各项的值，然后逐项求和得 方案 利用下列公式计算,4 典型例题分析