1
学习方法学习方法
1.注意掌握各种方法的基
本原理
2.注意各种方法的构造手
法与程序实现
3.重视各种方法的误差分
析
4.做一定量的习题及上机
实践
5.注意与实际问题相结合
参考书参考书
1.<应用计算方法教程>, 张晓丹
等编,机械出版社,2008。(教材)
2. 《科学和工程计算基础》,施
妙根、顾丽珍 编著,清华大学
出版社。1999。
考试方法考试方法
1.开卷笔试占60%
2. 上机作业占40%
什么是什么是算法算法和计算量和计算量??
算法 从给定的已知量出发,经过有限次运算及
规定
关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定
的运算顺序,
最后求出未知量的数值解,这样构成的完整计算步骤称为算法。P2
计算量 一个算法所需四则运算总次数. P4
一个算法所需的乘除运算总次数,单位是flop.
计算量是衡量一个算法好坏的重要
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
。
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
三、防止接近零的数做除数
分母接近零的数会产生溢出错误,因而产生大的误差,此时可
以用数学
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
化简后再做.
四、注意计算步骤的简化,减小运算次数
简化计算步骤是提高程序执行速度的关键,它不
仅可以节省时间,还能减少舍入误差。
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
序言要点
算法与计算量
计算机数系
误差及其运算
数值计算中应注意的问题
问题的性态
方法的数值稳定性