应用计算方法教程课件-张晓丹1

1 学习方法学习方法 Œ 1.注意掌握各种方法的基 本原理 Œ 2.注意各种方法的构造手 法与程序实现 Œ 3.重视各种方法的误差分 析 Œ 4.做一定量的习题及上机 实践 Œ 5.注意与实际问题相结合 参考参考书 Œ 1.<应用计算方法>, 张晓丹 等编,机械出版社,2008。（教材） Œ 2. 《科学和计算基础》，施 妙根、顾丽珍 编著，清华大学 出版社。1999。 ŒŒ 考试方法考试方法 Œ 1.开卷笔试占60% Œ 2. 上机作业占40% 什么是什么是算法算法和计算量和计算量？？ 算法 从给定的已知量出发，经过有限次运算及规定的运算顺序， 最后求出未知量的数值解，这样构成的完整计算步骤称为算法。P2 计算量 一个算法所需四则运算总次数. P4 一个算法所需的乘除运算总次数，单位是flop. 计算量是衡量一个算法好坏的重要。 255 .,x x R∀ ∈例1 计算 Algorithm ( ) ; ; 1 : 7 * ; * ; B Matlab s x y x for i s s s y y s end = = = = = A:x255=x·x···x B:x255=x·x2·x4·x8·x16·x32·x64·x128 14N flop= 254 ( input x, output y） 计算量 矩阵乘积AB的计算量 a11 a12 a13 … a1n a21 a22 a23 … a2n ... ...… ... am1 am2 amm-1 …amn b11 b12 b13 … b1s b21 b22 b23 … b2s ... ...… ... bn1 bn2 bnn-1 … bns =[cij]m×s A B 的计算量为N= (m ×n ×s )flop ,s1,j,m;1,ibaC n 1k kjikij "" ===∑ = A B 一般数制情况： k位规格化机器数 y= ± 0.a1 a2...ak×βc , β=2,8,10,16, ai∈{0,1,2,…, β-1}, L≤c ≤U,a1≠0 F(β,k.L,U)表示以上数集全体加数0，它是计算机中 使用的有限离散数集(机器数系）。 F(β,k,L,U)中的数称为机器数。 F(10,4,-33,33)， y= ± 0.a1 a2a3a4×10c 二进制机器数系 F(2,52,-1024,1024) 55计算机数系计算机数系 P5P5--77 例 在机器数系 F(10,4,-33,33)中表示 fl(π). ),33,33,4,10(1415926.3 −∉= F"π 3333 109999.0101000.0 ×<<× − π 若浮点数的阶码不在[L,U]内，则出现上溢 (overflow)或下溢(underflow)。 采用截断式 fl(π)=0.3141×10 采用四舍五入式 fl(π)=0.3142×10 但是 例如在4位机器数系 F(10,4,-33,33)中输入 2.8×10 -34 出现下溢，输入 1.99×1034 出现上溢。 2 符号位s占1位=1,0；（0正1负） 指数c占11位，底为2； c的最大值为211-1=2047 尾数f,分数占52位. •机器数转化为十进制浮点数的形式 (-1)s 2c-1023(1+f), 具有16位精度. 二进制数系: F(2,52,-1024,1024) 机器数为64位二进制数—s c f,双精度数。 0 10000000011 10111001000100…00 40 S=0 C=1·210+0·29+…+0·22+1·21+1·20=1027 1285431 ) 2 1(1) 2 1(1) 2 1(1) 2 1(1) 2 1(1) 2 1(1 ⋅+⋅+⋅+⋅+⋅+⋅=f 56640625.27 ) 4096 1 256 1 32 1 16 1 8 1 2 11(2)1( )1(2)1( 102310270 1023 = ++++++⋅−= +− − − fcs 例 设有二进制机器数 (64 bit) 最大规格化机器数: 21024(2-2-52) ≈10308 最小规格化正机器数： 2-1024(1+2-52) ≈10-308 在 F(2,52,-1024,1024)中， If ︱x︱< 10-308 ,导致下溢, fl(x) 令为零； If ︱x︱>10308, 导致上溢, 计算停止. 十进制数：x→ F(2,52,-1024,1024) →二进制数 s c f (对52位后面的数作舍入处理）→fl(x)=(-1)s2c-1023(1+f) x≈fl(x) 55误差定义误差定义 近似值x的绝对误差(absolute error) e = x*-x, x是近似数,x*是准确数 。 绝对误差限ε： | e | = | x*-x |≤ ε, x - ε ≤x* ≤x + ε 近似值x的相对误差(relative error) er =(x*-x )/ x* = e/x* 或 er = (x*-x)/x = e/x 相对误差限εr： ︱er︱= | x*-x |/|x*| ≤ εr 绝对误差及误差限是有量纲的，而相 对误差及误差限是没有量纲的． P9P9 例 计算 e0.5 的近似值，使相对误差不超过0.5×10-3. 解： n nn n S SSe 1−−= "" "" +++++== +∞<<∞−++++++= ! 5.0 !2 5.05.01,5.0 !!32 1 2 5.0 32 n ex x n xxxxe Maclaurine n n x x 时当 级数：的 迭代法的相对误差为 5.0 2 lim;1,0, ! 5.0 !2 5.05.01 eSn n S nn n n ==++++= ∞→则令 "" S0=1, S1=1+0.5=1.5 333.05.1 15.1 1 01 1 =−=−= S SSe 计算结果如表所示 e0.5≈S5=1.648698, ｜e5｜=0.000158<0.5×10-3 0.0001581.6486985 0.001581.64843754 0.01751.6458333 0.07691.6252 0.3331.51 10 enSnn 3 ▲ 四则运算的误差 x 的绝对误差: e(x)= x* -x= Δx ≈dx x 的相对误差： er(x)= (x*-x)/x ≈ dx/x=dlnx 设x,y同号，其四则运算的绝对误差 ︱e(x ± y )︱≈ ︱d(x ± y) ︱=︱dx±dy︱≤︱dx︱+︱dy︱ ︱ e(xy ) ︱ ≈ ︱d(xy) ︱=︱ydx+xdy︱ ︱ e(x/y ) ︱ ≈ ︱d(x/y) ︱=︱ (ydx-xdy)/y2︱, y≠0 利用这个关系可以讨论四则运算的误差和误差限。 P11P11--1313 .)()(,)()( f dxxf f dfyedxxfdfye r ′=≈′=≈ 特别地,若 y=f(x),则 例如, x dxn x dxnx f dffe dxnxdxxfdffe n n r n ==≈ =′=≈ − − 1 1 )( )()( ,)( nxxf = ( , ), ( ) ( , ) , ( , )( ) .r f fu f x y e u d f x y dx dy x y f fdx dy d f x y x ye u f f ∂ ∂= ≈ = +∂ ∂ ∂ ∂+∂ ∂≈ = 若 则 特别关注：特别关注： ( )2. ( )r d x y dx x dy ye x y x y x x y y x y −− ≈ ≤ +− − − 21. ( / ) ( / ) ydx xdye x y d x y y −≈ = 分母接近零会产生较大的绝对误差。 相近的两数相减会产生较大的相对误差。 数值计算中值得注意的问题 xx −+ 1 xx xx ++=−+ 1 11 化成 一、防止相近的两数相减 例1:当x>>1时,计算 例2 计算 D2, sin cos1 =− x x x 当x很小时，分子出现相近数相减，将以上算式变形 x x xx x xx xx cos1 sin )cos1(sin cos1 )cos1(sin )cos1)(cos1( 2 +=+ −=+ +− P18P18 二、防止大数吃小数 当两个绝对值相差很大的数进行加法或减法运算时,绝对值小 的数有可能被绝对值大的数"吃掉"从而引起计算结果很不可靠. 在上式中，重新排序计算 上式= 0.2+0.4+0.4+ 23456=1+ 23456= 0.00001 ×105+ 0.23456×105=23457 例:在F(10,5,-19,19)中，计算 23456+0.2+0.4+0.4 上式=0.23456×105+0.000002 ×105+ 0.000004 ×105+ 0.000004 ×105 =23456 三、防止接近零的数做除数 分母接近零的数会产生溢出错误,因而产生大的误差,此时可 以用数学公式化简后再做. 四、注意计算步骤的简化,减小运算次数 简化计算步骤是提高程序执行速度的关键，它不 仅可以节省时间，还能减少舍入误差。 4 问题的性态与数值稳定性 Œ良态与病态：在一个数学问题中，若初始数据的微小变化， 只引起计算结果的微小变化，则称问题是良态的；反之，若初 始数据的微小变化引起计算结果的较大变化，则称问题是病态 的。 例 1 求 p(x)=x2+x-1150 在 x=100/3 与 x=33 处的值。 解：p(100/3)=-(50/9) ≈-5.6, 而 p(33)=-28 初始数据的微小变化︱(100/3)-33︱<0.34,就引起计算结 果的较大变化︱-5.6+28︱=22.4,问题是病态的。 2、计算p(x)在x=1,x=1.1处的值。 解：p(1)=-1148, p(1.1)=-1147.7 初始数据的微小变化,只引起计算结果的微小变化，问题 是良态。 P13P13 55在计算机上是否根据数学公式编在计算机上是否根据数学公式编 程就能得到正确结果程就能得到正确结果?? 研究例子:求解线性方程组 ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ =++ =++ =++ 60 47 5 1 4 1 3 1 12 13 4 1 3 1 2 1 6 11 3 1 2 1 321 321 321 xxx xxx xxx ⎪⎩ ⎪⎨ ⎧ =++ =++ =++ 78.020.025.033.0 1.125.033.050.0 8.133.050.0 321 321 321 xxx xxx xxx 如把方程组的系数舍入 成两位有效数字 它的解为x1 =-6.222... x2=38.25… x3=-33.65... 此问题是病态的 其准确解为x1=x2=x3=1 Œ设R为计算结果的相对误差，e为初始数据的相对误差， 若能找 到一个正数m,使得 ︱R︱≤m︱e︱,则m是计算 结果的相对误差对初始数据的相对误差的放大倍数。 Œ 显然若问题是病态的，则m大，若问题是良态的， m就小。 m称为问题的条件数(condition number) 一个良态问题，采用数值稳定的方法计算，其结果 一定可靠。一个病态问题，即使采用数值稳定的方 法计算，结果也不一定可靠。关于病态问题，需要 讨论专门的方法，本课程基本不涉及这个问题。 P14P14 数值稳定性（Numerical Stability)：一个数值算法， 若输入数据的误差在计算过程不增长，并对最终结果 影响不大，就称该算法是数值稳定的算法；否则是不 稳定算法。P15 对某些数据算法是稳定的，称算法具有条件稳定性 (conditionally stable); 对任何数据算法均是稳定的 称算法具有无条件稳定性(unconditionally stable) 例 在F(10,4,-19,19)数系中，求解二次方程： 0163202 =+− xx 解法1 按求根公式 2 1,2 4 2 b b acx a − ± −= 解得，x1=0.3199×103, x2=0.1000 ×10 ; 解法2 2 1 2 1 2 1 ( ) 4 2 ( ) b sgn b b acx a c cx x x ax a − − −= = = 解得x1=0.3199 ×103 x2=0.5002 ×10-1 精确解为 x1=319.950 x2=0.0500078 b2>>4ac 2 0ax bx c+ + =求二次方程 的根。 2 1,2 2 41 2 4 b b acx a b ac − ± −= >> 方法 ： ， 当 时算法不稳定， 条件稳定。 2 1 2 1 sgn( ) 42 2 2 b b b ac cx x a x − − −= =方法 ： ， 此算法无条件稳定。 一般的， 5 定义 E0>0, 是初始误差，En是算法n步之后的误差。 若 En≈Cn E0 ,C是常数；称误差的增长是线性的 (linear)。若 En≈Cn E0 (C>1)，则称误差的增长是 指数级的(exponential)。 若算法的误差增长是指数级的，则它是不稳定的。 1 0 0 , 1 , , 2 3 5 n n xI d x n x = =+∫ "例计算 算法A 0 1 0 .182321556 1, 2 , , 2315n n I n I I n− =⎧⎪ =⎨ = − +⎪⎩ " " 解 1 11 1 0 0 11 11 0 0 ( 5 ) 5 5 5 5 5 n n n n n n n n 1 x x x xI d x d x x x x 1x d x d x 5 I x n − − − − − + −= =+ + = − = −+ ∫ ∫ ∫ ∫ 1 0 0 1 ln 6 ln 5 0 .1 8 2 3 2 1 5 5 6 5 I d x x = = − =+∫ " 1 0 2 1 15 1 , 5 , 2 I I I I= − + = − + " 由A算得的结果如下：n=0-- 11 0.1823 0.0884 0.0580 0.0431 0.0340 0.0285 0.0243 0.0212 0.0188 0.0169 0.0154 0.0141 n=12-- 23 0.0130 0.0120 0.0112 0.0105 0.0099 0.0093 0.0090 0.0075 0.0127 -0.0159 0.1252 -0.5824 I21以后正负交替，结果是错误的。 dx x xI n n ∫ += 10 5 ,15,, 0100000 +−=−=≈ IIIIeII 15 01 +−= II 设Īn 是 In 的近似，并设 en=In- Īn (n≥0) ，∵ In=-5In-1 +1/n Īn=-5 Īn-1 +1/n则有 en=-5en-1=(-5)ne0 误差增长是指数的，算法A不稳定。 0111 5eIIe −=−= 算法A 23,,2,1 " " = ⎪⎩ ⎪⎨ ⎧ +−= = − n n 15II 60.18232155I 1nn 0 算法A不稳定。 算法B 2 5 1 0 .0 0 7 1 1 , 2 5 , , 1 5 5 n n I II n n− ≈⎧⎪⎨ = − + =⎪⎩ " n=1 -- 14 0.1823 0.0884 0.0580 0.0431 0.0343 0.0285 0.0243 0.0212 0.0188 0.0169 0.0154 0.0141 0.0130 0.0120 n=15-- 24 0.0112 0.0105 0.0099 0.0093 0.0088 0.0084 0.0080 0.0076 0.0073 0.0069 0 ( 1) 5 n nne e −= 误差逐渐缩小。 算法B是稳定的。 25 1 1 1( ) 0.0071 2 6 26 5 26 I ≈ + ≈× × 算法B是稳定的。 n=1 -- 14 0.1823 0.0884 0.0580 0.0431 0.0343 0.0285 0.0243 0.0212 0.0188 0.0169 0.0154 0.0141 0.0130 0.0120 n=15-- 24 0.0112 0.0105 0.0099 0.0093 0.0088 0.0084 0.0080 0.0076 0.0073 0.0069 0 ( 1) 5 n nne e −= 误差逐渐缩小。 1 1 1 1 1 10 , 5 , 1 1 15 6 , 6 5 n n n n n n n I I I I n I I I n n n − − − − − ≤ ≤ + = ∴ ≤ ≤ ∴ ≤ ≤ ∵ 又 2 5 1 1 6 2 6 5 2 6 I≤ ≤× ×特别有： dx x xI n n ∫ += 10 5 2 5 1 0 .0 0 7 1 : 1 , 2 5 , , 1 5 5 n n I B II n n− ≈⎧⎪⎨ = − + =⎪⎩ " 作业 习题 1 P24: 1, 4, 6, 12, 14, 15 序言要点 算法与计算量 计算机数系 误差及其运算 数值计算中应注意的问题 问题的性态 方法的数值稳定性