数学与统计学院李义宝

1、数学与统计学院数学与统计学院 李义宝李义宝理科楼理科楼 312计算方法教程计算方法教程凌永祥凌永祥 陈明逵陈明逵 西安交通大学出版社西安交通大学出版社计算方法计算方法邓建中邓建中, ,西安交通大学出版社西安交通大学出版社数值分析数值分析李乃成李乃成, ,梅立泉梅立泉 科学出版社科学出版社参考书参考书课程基础课程基础数学基础数学基础 计算机基础计算机基础 高等数学高等数学 线性代数线性代数 计算机语言计算机语言 数据结构数据结构 课程成绩课程成绩 考试成绩考试成绩 70%70%上机成绩上机成绩 30%30%应用计算机解决问题应用计算机解决问题 1.1.建立数学模型建立数学模型2.2.计算问题的解

2、计算问题的解3.3.实验验证实验验证第第1章章 绪论绪论什么是计算方法什么是计算方法1.1 1.1 数值计算数值计算第第1章章 绪论绪论计算方法的任务计算方法的任务1.1 1.1 数值计算数值计算第第1章章 绪论绪论问题的类型问题的类型bAx计算方法的选择计算方法的选择 1.1.可行性可行性2.2.计算效率计算效率3.3.算法稳定性算法稳定性1.2 1.2 数值方法的分析数值方法的分析n定义定义 通常以计算机完成操作通常以计算机完成操作 a+ba+b* *c ,c ,即一次浮点加法即一次浮点加法和一次浮点乘法所需的时间作为一个时间单位，称为和一次浮点乘法所需的时间作为一个时间单位，称为浮点运算

3、浮点运算，记为，记为flopflop. .12341.3 ,1020,2050,50 1,1 100 A A A A例设分别为 的矩阵,则按结合律,有 11500 flop 125000 flop 2200 flop1234()PA A A A1234()PA A A A1234()PA A AA 运算顺序浮点运算量第第1章章 绪论绪论例:解线性方程组 的Grammar 方法： 其中 是方程组系数矩阵 对应的行列式，而 则是以右端向量 替代 的第 列所得矩阵对应的行列式。由线性代数知识可知，若 ，则其中 是由 变换到 所需的置换次数. 可见每计算一个行列式, 需要 个浮点运算；因此，按Gram

4、mar方法解方程组约需 个浮点运算。当 时 ，用一个运算速度为 秒的计算机进行求解，约需10年。而n=20的方程组是一个小型的方程组。因此Grammar方法是一个不能接受的算法，它缺乏可计算性。 bAx nixii, 2 , 1AAAAiAbAi)(ijAnnniiiiiiJ212121),()1(A),(21niiiJn, 2,1niii,21!) 1(nn!) 1(2nnN20n20107 . 9N/1038408 1.2 1.2 数值方法的分析数值方法的分析n定义定义 误差误差是指近似值与真正值之差是指近似值与真正值之差 误差分类误差分类模型误差模型误差在建立数学模型时，忽略次要因素而造

5、成的在建立数学模型时，忽略次要因素而造成的数据误差数据误差由于问题中的值通过观察得到的，从而产生误差由于问题中的值通过观察得到的，从而产生误差截断误差截断误差通过近似替代，简化为较易求解的问题通过近似替代，简化为较易求解的问题舍入误差舍入误差由于计算机中的性能限制而造成的由于计算机中的性能限制而造成的第第1章章 绪论绪论后两种误差主要是由于计算机的字长有限，采用浮点数系所致。所后两种误差主要是由于计算机的字长有限，采用浮点数系所致。所以首先介绍浮点数系以首先介绍浮点数系1.2 1.2 数值方法的分析数值方法的分析,1112 ()0,2,3,2xtddddltxdjttj 在任何一个 进制中 实

6、数 可以表示为以下具有 位有效数字的形式lLlU 其中: 称为指数部分,12,.,td dd 称为尾数( , , ,)Ft L U 将计算机中所能表示的全体数的集合称为计浮点数,系算机的记为 第第1章章 绪论绪论浮点数系浮点数系第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析 在计算机的浮点数系中,四则运算是非封闭的 为使经过算术运算产生的结果仍然以同一浮点数系中的数表示,必须用一个比较接近的浮点数代替.因此会产生误差 ,称此误差为舍入误差第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析223(2,3,-1,2)(0.100 2 ) (0.110 2 )0.11

7、0 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 在中 第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析11( )2tx 可以证明,在数系F( ,t,L,U)中,算术运算的相对舍入误差满足 ( )fl xx记为 的浮点近似 , 则其 相对误差为 -( )( )xfl xxx ,1112 ()0,2,3,2xtddddltxdjttj 在任何一个 进制中 实数 可以表

8、示为以下具有 位有效数字的形式第第1章章 绪论绪论-( )( )xfl xxx 第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析( ),( )(1) ,xfl xx设则有因此可得123()(1-)()()(1-)()( )(1-)( )fl xyxyfl xyxyxxflyy123-()()-()()-( )( )xyfl xyxyxyfl xyxyxxxflyyy第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析(1)(1)避免产生大结果的运算，尤其是避免小数作为除数避免产生大结果的运算，尤其是避免

9、小数作为除数 参加运算；参加运算；(2)(2)避免避免“大大”“”“小小”数相加减；数相加减；(3)(3)避免相近数相减，防止大量有效数字损失；避免相近数相减，防止大量有效数字损失；(4)(4)尽可能简化运算步骤，减少运算次数。尽可能简化运算步骤，减少运算次数。浮点运算原则浮点运算原则二、算法的可靠性二、算法的可靠性问题的性态：问题的性态： 例：方程组 的解是：若将方程组的系数改写成具有2位有效数字的小数： 的解： ；604751413112134131216113121321321321xxxxxxxxx111X78. 020. 025. 033. 01 . 125. 033. 050. 0

10、8 . 133. 050. 000. 132132121xxxxxxxxx65.3325.3822. 6X第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析n定义定义 第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方法的分析,( )mCond f条件则称这个数 为该问题的记为数( )f x设问题的已知输入数据 只有一个x,用 表示xx若有两个输入数据 和( ),( )f xf x,则可得到两个不同的结果0 x 当时,( )0f x 设有,0m 若存在数,满足以下关系式( ) ( ) ( ) f xf xxxmf xx第第1章章 绪论绪论1.2 1.2 数值方法的分析数值方

11、法的分析n定义定义 在执行某一数值方法时，如果由初始误差导致最终解在执行某一数值方法时，如果由初始误差导致最终解的误差能被有效地控制，这样的方法是的误差能被有效地控制，这样的方法是数值稳定数值稳定的的 方法的数值稳定性是指运算中由初始误差通过计算方法的数值稳定性是指运算中由初始误差通过计算导致的最终解的误差的可控性导致的最终解的误差的可控性反之，如果各个计算过程中的误差不断增长，且不能反之，如果各个计算过程中的误差不断增长，且不能被有效地控制，则该方法称为被有效地控制，则该方法称为数值不稳定数值不稳定的的算法的稳定性算法的稳定性 例:计算积分解：由微积分，有计算公式， 由上表可见，方法中，原始

12、步的误差，随着计算步数的增加被严重地放大，特别是竟变成负数（注意：被积函数是非负函数），而方法则相反；这是因为方法中，若前步有误差： ，则n步误差:8 , 1,0,101 ndxexeIxnn11nnnII)1(11nnInI方法 准确值.6321.36792462.2073.1709.1455.1268.1124.1010 .6321.3679.2462.2074.1704.1480.1120.2160-.7280 .6320.3680.2643.2073.1709.1455.1268.1124.10100I1I2I3I4I5I6I7I8I11:nnIInInnIInInnnn1111说明的

13、误差，经一步计算后被扩大了n倍，随着n增大，误差将被大大地扩大；而通过同样的分析可知：方法中的误差则被缩小倍 算法的数值稳定性算法的数值稳定性：算法对初始误差导致的最算法对初始误差导致的最终误差的可控性终误差的可控性，如果最终误差被有效地控制，则称算法是稳定的，否则就是不稳定的。 因此,方法是不稳定的,而则是稳定的.nIInInInnnn1)1 (1)1 (111第第1章章 绪论绪论1.3 1.3 数值方法的分析数值方法的分析n定义定义 算法算法是由有限个无二义性的法则组成的一个计算过程，是由有限个无二义性的法则组成的一个计算过程，这些法则明确规定了一串运算，以产生一个问题或者一这些法则明确规

14、定了一串运算，以产生一个问题或者一类问题的解类问题的解 第第1章章 绪论绪论n具有的特征具有的特征 算法应具有以下的特征：算法应具有以下的特征： 正确性正确性 有穷性有穷性 适用范围广适用范围广 运算工作量少运算工作量少 使用资源少使用资源少 逻辑结构简单逻辑结构简单 便于实现便于实现 计算结果可靠计算结果可靠1.3 1.3 数值方法的分析数值方法的分析第第1章章 绪论绪论1.3 1.3 数值方法的分析数值方法的分析l算法算法SUM1(A,n,S)SUM1(A,n,S) 将数组将数组A A中的中的n n个数按顺序相加个数按顺序相加, ,并将和存放于并将和存放于S S中中1. 0-s1. 0-s

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

16、lse S2+ai-S23. S1+S2-S3. S1+S2-S第第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,2. For i=1,2,n,n 2.1 max-m 2.1 max-m 2.2 for k=1,2, 2.2 for k=1,2,n,n 2.2.1 If ak0 and abs(ak)m then 2.2.1 If ak0

17、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第第1章章 绪论绪论1.3 1.3 数值方法的分析数值方法的分析l算法算法SUM4(A,n,S)SUM4(A,n,S) 将数组将数组A A中的数按其符号分成两组中的数按其符号分成两组, ,分别按算法分别按算法SUM3SUM3求和求和, ,最后计算和最后计算和S S1. 0-n1;0-n2;1. 0-n1;0-n2;2. For i=1,2,2. For i=1,2,n,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