计算方法概述课件.ppt

1、课程准备课程准备u数学基础 高等数学高等数学 线性代数线性代数u计算机基础 一种高级计算机语言一种高级计算机语言 数据结构数据结构第第1 1章章 绪论绪论计算方法的英文翻译putational puting putational procedure4.numerical method5.Calculation method6.Computational thoughts第第1章章 绪论绪论第第1章章 绪论绪论数值型问题数值型问题 解决工程计算问题解决工程计算问题非数值型问题非数值型问题 解决一般的计算机应用解决一般的计算机应用理论基础理论基础:高等数学高等数学,线性代线性代数数,数学模型数学模

2、型,计算方法等计算方法等理论基础理论基础:数据结构数据结构,离散数学等离散数学等1.1 1.1 数值计算数值计算第第1章章 绪论绪论1.1 1.1 数值计算数值计算建立数学模型计算问题的解实验验证第第1章章 绪论绪论1.1 1.1 数值计算数值计算第第1章章 绪论绪论1.1 1.1 数值计算数值计算第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析n定义定义 误差是指近似值与真正值之差误差是指近似值与真正值之差 误差分类误差分类模型误差模型误差在建立数学模型时，忽略次要因素而造成的在建立数学模型时，忽略次要因素而造成

3、的数据误差数据误差由于问题中的值通过观察得到的，从而产生误差由于问题中的值通过观察得到的，从而产生误差截断误差截断误差通过近似替代，简化为较易求解的问题通过近似替代，简化为较易求解的问题计算误差计算误差由于计算机中数的位数限制而造成的由于计算机中数的位数限制而造成的第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析n定义定义 通常以计算机完成操作通常以计算机完成操作 a+ba+b* *c ,c ,即一次浮点加法即一次浮点加法一次浮点乘法，所需的时间作为一个时间单位，称为一次浮点乘法，所需的时间作为一个时间单位，称为浮点运算，记为浮点运算，记为flop.flop.12341.3 ,

4、10 20,20 50,50 1,1 100A A A A例设分别为的矩阵,则按结合律,有 11500 flop 125000 flop 2200 flop1234()PA A A A1234()PA A A A1234()PA A AA第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析,1112 ( )()20,2,3,txddddltfl xtdjtj 任何一个 进制 具有 位有效数字的实数 可以表示为l其中: 称为指数部分,LlU12,.,td dd 称为尾数( , , ,)Ft L U 将计算机中能表示的全体数的集合称为计算机的浮点系,记为第第1章章 绪论绪论1.2 1.

5、2 数值方法的分析数值方法的分析 在计算机的浮点数系中,四则运算是非封闭的 为使经过算术运算产生的结果仍然以同一浮点数系中的数表示,须用接近的一个浮点数代替.因此会产生误差第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析223(2,3,-1,2)(0.100 2 ) (0.110 2 )0.110 2F上溢 在中 012(2,3,-1,2)(0.100 2 ) (0.110 2 )0.110 2F下溢 在中 第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析001(2,3,-1,2)(0.100 2 )(0.111 2 )0.1101 2F 在中 ( ),-( )

6、( )fl xxxfl xxx记为 的浮点近似 则相对误差为 第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析11( )2tx可以证明,在数系F( ,t,L,U)中,算术运算的相对舍入误差满足 第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析( ),( )(1) ,xfl xx设则有因此可得()(1- )()()(1- )()( )(1- )( )fl xyxyfl xyxyxxflyy-()()-()()-( )( )xyfl xyxyxyfl xyxyxxxflyyy第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析浮点运算应注意：浮点运算应注

7、意：(1)避免产生大结果的运算，尤其是避免小数作为除数参加运算；(2)避免“大”“小”数相加减；(3)避免相近数相减，防止大量有效数字损失；(4)尽可能简化运算步骤，减少运算次数。第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析n定义定义 第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析,.,( ),( ).0,( )0,( )( ) ( ),( )xxxf xf xxf xmf xf xxxmf xxmCond f 设一个问题的已知数据只有一个 用 表示 若有两个数据 和则可得到两个不同的结果当时

8、 有若存在满足则称这个数 为该问题的条件数 记为第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析n定义定义 第第1章章 绪论绪论1.3 1.3 数值方法的分析数值方法的分析n定义定义 n描述描述 算法可以使用框图、算法语言、伪代码、数学语言、算法可以使用框图、算法语言、伪代码、数学语言、自然语言来进行描述。自然语言来进行描述。第第1章章 绪论绪论n具有的特征具有的特征 算法应具有以下的特征：算法应具有以下的特征： 正确性正确性 有穷性有穷性 适用范围广适用范围广 运算工作量少运算工作量少 使用资源少使用资源少 逻辑结构简单逻辑结构简单 便于实现便于实现 计算结果可靠计算结果可靠

9、1.3 1.3 数值方法的分析数值方法的分析第第1章章 绪论绪论1.3 1.3 数值方法的分析数值方法的分析l 了解算法的设计原理了解算法的设计原理l 熟悉算法的运算过程熟悉算法的运算过程l 掌握算法的长处和短处掌握算法的长处和短处l 分析算法的稳定性、时空特性分析算法的稳定性、时空特性l 改进算法的性能改进算法的性能 为解决实际问题为解决实际问题, ,应正确提出数学问题应正确提出数学问题, ,并针对具体问题选择并针对具体问题选择或改造适当的算法或改造适当的算法, ,清楚计算过程中可能发生的问题清楚计算过程中可能发生的问题. .第第1章章 绪论绪论1.3 1.3 数值方法的分析数值方法的分析l

10、算法算法SUM1(A,n,S)SUM1(A,n,S) 将数组将数组A A中的中的n n个数相加个数相加, ,并将和存放于并将和存放于S S中中1. 0-s1. 0-s2. For i=1,2,n2. For i=1,2,n 2.1 S+ai-S 2.1 S+ai-S3. 3. 输出输出S S算法实例算法实例: :求求n n个数的和个数的和第第1章章 绪论绪论1.3 1.3 数值方法的分析数值方法的分析l算法算法SUM2(A,n,S)SUM2(A,n,S) 将数组将数组A A中的中的n n个数中的正数与负分别相加个数中的正数与负分别相加, ,并将并将和存放于和存放于S S中中1. 0-s1;0-

11、S2;1. 0-s1;0-S2;2. For i=1,2,n2. For i=1,2,n 2.1 if ai S1 2.1 if ai S1 else S2+ai-S2 else S2+ai-S23. S1+S2-S3. S1+S2-S算法实例算法实例: :求求n n个数的和个数的和第第1章章 绪论绪论1.3 1.3 数值方法的分析数值方法的分析l算法算法SUM3(A,n,S)SUM3(A,n,S) 将数组将数组A A中的有相同符号的中的有相同符号的n n个数的和个数的和, ,按绝对值按绝对值递增的顺序将它们求和递增的顺序将它们求和1. 0-s;1. 0-s;2. For i=1,2,n2.

12、For i=1,2,n 2.1 max-m 2.1 max-m 2.2 for k=1,2,n 2.2 for k=1,2,n 2.2.1 If ak0 and abs(ak)m then 2.2.1 If ak0 and abs(ak)m;k-j; abs(ak)-m;k-j; 2.3 S+ai-s 2.3 S+ai-s 2.4 0-ai 2.4 0-ai算法实例算法实例: :求求n n个数的和个数的和第第1章章 绪论绪论1.3 1.3 数值方法的分析数值方法的分析l算法算法SUM4(A,n,S)SUM4(A,n,S) 将数组将数组A A中的数按其符号分成两组中的数按其符号分成两组, ,分别

13、按算法分别按算法SUM3SUM3求和求和, ,最后计算和最后计算和S S1. 0-n1;0-n2;1. 0-n1;0-n2;2. For i=1,2,n2. For i=1,2,n 2.1 if ai=0 then n1+1-n1; ai-bn1; 2.1 if ai=0 then n1+1-n1; ai-bn1; else n2+1-n2; ai-cn2; else n2+1-n2; ai-cn2;3. 3. 调用调用SUM3(B,n1,S1);SUM3(B,n1,S1);4. 4. 调用调用SUM3(C,n2,S2);SUM3(C,n2,S2);5. S1+S2-S5. S1+S2-S算法

14、实例算法实例: :求求n n个数的和个数的和第第1章章 绪论绪论1.3 1.3 数值方法的分析数值方法的分析类型 范围 格式Shortint -128.127 signed 8-bitSmallint -32768.32767 signed 16-bitLongint -2147483648.2147483647 signed 32-bitInt64 -263.263-1 signed 64-bitByte 0.255 unsigned 8-bitWord 0.65535 unsigned 16-bitLongword 0.4294967295 unsigned 32-bit第第1章章 绪论绪论1.3 1.3 数值方法的分析数值方法的分析 计算机计算过程中，由于原始数据可能有误差，每次运算也计算机计算过程中，由于原始数据可能有误差，每次运算也可能产生舍入误差，误差积累起来，很可能淹没真正解，使得结可能产生舍入误差，误差积累起来，很可能淹没真正解，使得结果根本不可靠。果根本不可靠。 可靠的算法，各步误差不应对计算结果产生可靠的算法，各步误差不应对计算结果产生过大影响，也即具有稳定性过大影响，也即具有稳定性.良态问题+稳定的计算方法可靠的计算结果