计算方法-第1章.ppt

1、计算方法的内容,1. 第一章 引论：13,2. 第二章 线性方程组的直接法,14， 5- 6,3. 第三章 插值法与最小二乘法,14， 5- 7,4. 第四章 数值积分与微分,1，2， 5， 3,5. 第五章 常微分方程数值解法：,1，2,6. 第六章 逐次逼近法：13,2,第一章 计算方法引论,现代科学的三个重要组成部分: 科学理论, 科学实验, 科学计算。 仅靠数学理论的演绎和推导不能解决实际中的数值问题，只有计算机科学相结合，才能研制出实用的好算法。 好的算法变成数值软件以后才可能为社会创造更大的财富。,1. 计算机数值方法概述, 计算方法是数学与计算机科学的交叉学科。,1） 数学的发展

2、极大地促进了计算机科学的发展：, Leibniz发现二进制编码；, Von Neumann提出现代计算机建构理论；, Bohm和Jacopini为结构化程序设计奠定了基础。,2）计算机科学为数学提供先进手段，并对数学 发展产生了重大影响。, 为利用数学解决实际问题提供了工具；, 解决了一些数学难题，并提出了新的研究课题；, 促进了“并行算法”的研究和新一代计算机的发展。,2, 计算方法的发展，产生了大量适合计算机求解的现代数值方法，成为科学计算的主要方法。, 现代计算方法的一个显著特点： 已产生大量实用的“综合数学软件库”，并逐步 形成了数值软件产业。 例如：, Mathematica是综合数

3、学软件包，集符合演算、数值 计算和图形演示等；, STYR是一个集数学、统计、应用软件等大型综合 数值软件库；, Matlab是集数值计算、图形演示等一体的综合数值 软件库。, 计算方法的研究问题：将常见的数学模型转变成数值 问题，提出相应的数值方法，并设计数值算法，并利 用程序计算数值结果。,3, 严格来讲，需要掌握一定的程序设计方法,4,以计算机求解数学模型包含三个过程： 总体设计：模型的细化； 详细设计：算法的设计； 程序设计：利用某种计算机语言实现编写程序。, 学习本课程的基础知识： 微积分、线性代数、微分方程等基本知识。 了解某种计算机高级语言。,2 数值问题与数值算法, 利用数学和

4、计算机知识解决实际问题可分为两步：, 建立数学模型：需要利用有关专业知识和数学理论， 这属于应用数学范围；, 提出数值问题与数值方法： 将数学模型变成数值问题，进而研究该数值 问题的数值方法，并设计有效的数值算法的过程， 这属于计算方法的范围。, 数值方法：将求解“数值问题”在“计算机上可执行” 的一系列计算公式。数值问题的总体称为计算方法。, 数值问题：指“输入数据与输出数据之间函数关系的 一个确定而无歧义的描述”。,5, “计算机上可执行”的系列计算公式：这一系列公式中的 运算只能是四则运算和逻辑运算（与、或、非等）。, 什么“数学模型”是“数值问题”？,1) 求方程 的根。, 输入a,b

5、,c，则输出数据是根x1和x2，故是“数值问题”,2) 求常微分方程的解, 因输入数据为2和3，x=0和y=0等，输出是函数,，故不是“数值问题”。, 如何将数学模型变成“数值问题”,将不是“数值问题”转化为“数值问题”的方法：“离散化”。,3,例如，,将求解 的问题变成求,，,如可 x1， x2， x100 取为 0.1, 0.2, 0.3, ,10=a,2-1 数值方法, 计算公式不一定都是数值方法。如求 。,7,类似地， 求根公式,不能在计算机 上直接运行, 研究数值方法的任务有三条：,1）将计算机不能直接计算的运算化成计算机上可执行的 运算；利用等价或近似等价的方法转化；,2）研究在计

6、算机上可执行且有效的一系列计算公式；,3）误差分析：研究数值问题的性态和数值方法的稳定性。, 计算机上能直接进行的运算： 四则运算 和 逻辑运算, 计算机上不能直接执行的运算包括：,开方、超越函数、极限、微分、积分等, 几个转化例子,8, 本课程重点是介绍常见的行之有效的新的数值方法。,2-2 数值算法, 数值算法：有步骤地完成求解数值问题的过程。, 数值算法的解题过程必须具备以下四个特性：,1）目的性：算法目的明确，条件和结论均应明确；,2）确定性：算法必须精确地给出每一步的操作；,3）可执行性：算法中的每个操作都是可执行的；,4）有穷性：算法必须在有限步内结束解题过程。, 计算机上的算法分

7、类, 按求解问题的不同可分为两类：,数值算法和非数值算法（符号推理、公式推导）。,9, 按面向计算机的不同，可分为：,面向串行计算机的串行算法，只有一个进程；,面向并行计算机的并行算法，含两个以上的进程, 根据算法内部的特点可分为：,确定性算法，每完成一步确切知道下一步该做什么,非确定性算法（智能算法）。,注：计算机数值方法只研究计算机上串行确定型数值算法。,例1 给出等差数列1,2,3,10000的求和算法,1）取N=0, S=0 ；,2）N+1N, S+NS；,3）若N10000转2，否则,4）输出N和S,10, 对于大型数值问题，不同算法及其计算复杂性 有很大差异：例如, 利用Grame

8、r法则求解20阶线性方程组，需要乘、除法 运算次数 。, 利用Gauss消去法求解，只需2670次乘、除法, 算法设计的主要目的：,1）研制可靠性好的数值方法（精度要求）；,2）选择计算复杂性好的数值方法（速度快、存贮少）,3）为程序设计作好准备。,11,2-3 算法设计及其表达法, 目前流行的软件开发方法有两种：,1）面向过程的“自顶向下、逐步细化”的结构化方法；,2）面向对象的“自下而上”的组装开发方法，其主要 工具是“类”（特殊模块），利用它可组装数值算 法和求解程序。,注：本课程只介绍前者，, “自顶向下，逐步细化”法，其关键有三个方面：,1划分模块，主要原则是模块功能要单一，即独立性

9、好；,2设计或选择模块算法，先总体，后具体；,3充实细节，考虑计算公式的效率和其他要求。,12, 在数值软件中，算法常用的表达方法有两类：, 自然语言法 ；用文字有步骤的表示算法, 图示法：又分为“流程图”和“结构化框图”, 下面以求解二次方程为例说明算法设计, 解上述方程有两种方法：直接法、迭代法, 利用直接法需要考虑三个细节：,1）判别式： 大于0或小于0；,2）当 且 时，会出现两个近似数 相减而影响有效数字的位数；,3）若|a|比|b|和|c|相对小很多时，可能出现 舍入误差增大的问题。,13,一自然语言法,1. 输入数据a, b, c,2.如果a=0, 转3，否则转4,3.如果 ，则

10、,，转7；否则，无解停机,4. 设,，,如果,，转7,如果,，转7,否则,5. 如果b0不成立，,，,，转7,6.,，,7. 输出x1和x2,14,二图示法： 又 分 为 “流 程 图” 法 和 “结 构 化 框 图” 法。,流程图示法,15, 结构化框图法：N-S图示法,1顶层设计：,2第1层设计：细化 (II),3第2层设计：,a) 细化 (I),16,b) 细化 (II),4. 第3层设计：细化,17,3 误差,3-1 误差的基本概念, 数值计算中的误差来源有两种：,1) 舍入误差：由于计算机的字长有限，原始数据 在计算机中的表示、运算产生的误差；,2) 截断误差：由数学问题化成数值问题

11、产生的误差,例如：, 若计算机仅能表示6位十进制数，则将表示为, 误差,若将与数9.210 00进行加法运算，得,R1和R2都是舍入误差。,18, 计算 的数值。因,由算法的有限性，故利用截断部分和,来近似代替，由此产生的误差即为截断误差，估计为, 绝对误差与相对误差,19,定义3.1 设x为准确值， 为x的一个近似值，称 为近似值 的（绝对）误差，,简记为E。,圆周率的近似值a=3.14, 绝对误差E=0.00159, 一般来说，E的准确值很难求出，只能估计出|E|的 某个上界 ，即,称为近似值 的(绝对)误差限，简记为 。于是,， ：,可表示成,定义3.2 近似值 的误差与准确值x之比,称

12、为近似值 的相对误差，简记为,20,绝对值的任一上界 ，称为相对误差限，简记为, 由于x的准确值难以确定，通常利用,代替,注：绝对误差限与相对误差限不唯一；它们越小越好。, 对于准确值x取近似值最常用的方法是采用“四舍五入” 的原则。由此产生了一个专有名词有效数字。,21,定义3.3 如果近似值 的误差的绝对值不超过 某一位数字的半个单位，且该位数字到 的第一位 非零数字共有n位，则称用 （近似x时）具有n位 有效数字。,例如： 有5位有效数字， 而 有4位有效数字。, 确定有效数字的等价方法：, 数的规格化表示：,1),(3.2),2),(3.3),其中，k 是某个范围内的整数， ， 为0,

13、1,9中的数字。, 若将近似值 表示成(3.2)式作为x的在第n+1位 数字进行四舍五入，则 具有n位有效数字，即,(3.5),如： ，有,，五位有效数字。,22, 有效数字的等价定义,定义3.4 如果x的近似值 满足不等式（3.5），即, 一种特殊情况：有效数字不唯一。如,则称 具有n位有效数字。,和,都是 的两位有效数字。, 一般情况：近似值的有效位数越多，误差的绝对值越小。 但也有个别例外，如,分别有3和4位有效数字。,，,，,23,（最大的n值）, 近似值的有效数字与相对误差之间的关系：,定理3.1 设 是x的近似值，它的表达式为:,则 的有效位数与 的相对误差之间有如下关系：,1）若

14、 具有n位有效数字，则 的相对误差 满足,2）若 的相对误差 满足,则 至少具有n位有效数字。,(证明略：P16-17),24,(3.6),(3.7), 例6 设x=1.986, x*=1.98, 则,故由(3.7)知，x*至少具有2位有效数字。,由（3.5），k-n=-1，k+1=2，所以x*具有2位有效数字。,25,另一方面： x*具有2位有效数字，故由(3.6)，得,因,注：上界 并不是最小的。,3-2 浮点基本运算的误差, 在计算机中，每个数x都用有限位二进制数表示， 其规格化浮点数形式由三部分组成：,1) 阶码：确定小数点的位置；(决定了数的取值范围),2) 数符：表示正、负号；,3

15、) 尾数：表示机器数字长；（长度与精度有关）,形式为：,其中，2称为浮点数的基,是0或1；称x*为x的浮点数, 记为,26,(0表示正，1表示负),其中，数符0表示正，1表示负。浮点数也称机器数。, 设原始数据 ，其尾数,若机器数fl(x)的尾数 是 t 位：,则,于是, fl(x)的绝对误差E和相对误差,（绝对误差E）,，故,因,27,一浮点数的四则运算的误差, 浮点数x和y的四则运算结果的浮点表示：,(3.9),(3.10),(3.11),其中，,。,二 连加和连乘的误差,设 为规格化浮点数，求,和,计算从左向右进行，每次运算都进行截取，再作下一次运算,28,1. 连加: 设,(3.12)

16、,则,(3.13),29,因为,其中，,(3.14), 各相对误差限的大小与运算先后有关； 先运算的数，误差也较大, 运算应先安排小数参加运算，可防止“大数吃小数”,30,2. 连乘:, 各相对误差限的大小与运算先后无关。,3-3 数值方法的稳定性与算法设计原则,设计和选择算法首要关心的问题是精度要求，要 建立一些定性分析准则用于判断结果的可靠性， 这是数值稳定性问题。,对于一个数值方法，若对原始数据或某一步有舍入误差， 在执行过程中，这些误差能得到控制，则称该数值方法 稳定。否则，称为不稳定的。,利用两种数值方法A和B解输入和舍入误差规则相同的 同一问题，若用A发比B法得到的计算解精度更高，

17、则 称A法比B法具有较大的稳定性。,例8 计算积分,解：由于,故,(3.16),方法一：利用公式(3.6)式，先计算I0，然后计算I1, I2, , I7,设计算值 的误差为 ，若I0时误差为 ，则,方法二：利用公式,，先计算I7，再计算I6,I5,I0,计算 I7 时产生误差 ，那么计算 I0 时的误差为,例9 求线性方程组,(3.17),其准确解为x1=x2=x3=1。但是，若对数据取3位有效数字， 利用Guass消去法求解，则计算解：,33,同样对方程,利用Guass消去法，取3位有效数字，则得到准确解：,“数值问题”计算解的精度，不但与数值方法的稳定有关， 而且还与数值问题的性态好坏有关。,在数值问题中，若输出数据对输入数据的扰动（误差） 很敏感（小的变化会引起较大的变化），称这类数值 问题为病态问题；否则称为良态问题。,34, 选用计算公式和设计算法时的普遍原则：,一四则运算中的稳定性问题,1）防止大数吃小数, 预防方法：先加小数，由小到大逐次相加。如,2）要避免两个相近数相减, 相近数相减会严重损失有效数值的位数,可改为,再如仿照前面求二次