数值算法的稳定性

12
11
0.0129766
0.0140713
7
6
0.0212326
0.0233250
2
1
0.0580389
0.0883922
最后得: I0=0.182322 与我们开始计算的I0≈0.182322是一样的
1 1 I n 1 I n (n m, m 1,...,2,1) 5 5n
绝对误差限，相对误差限
线性代数一④
2/32
|e| = |x* - x| ， 称 为近似值x的绝对误差限，简称误差限或精度
e x * x | er || || | r x* x*
则称r 为近似值x的相对误差限。
线性代数一④
3/32
有效数字
近似数x=±0.a1a2…an×10m
如果|e| = |x* - x| 1/2 10m-n 称近似数x准确到小数点后第n位,从这小数点后 第n位数字直到最左边非零数字之间的所有数 字都称为有效数字. 有效数字越多,误差越小,计算结果越精确.
In
1
0
x dx x5
n
(1)In>0; (2)In单调递减
(3) lim I n 0;
n
见教材第2、10—11页
线性代数一④
(4)
1 1 I n1 (n 1) 6n 5n
有递推公式
在该例中,用上述公式计算积分的值,I0=ln6-ln5 ≈0.182322的舍入误差在计算过程迅速传播，每次扩大 5倍，致使I12= -0.32902110×10-2 严重失真，所以这一 公式是不稳定的。 而将公式变为
例7：设A、B、C、D分别是1020、 2050、 501、 1100的 矩阵，试按不同的算法求矩阵乘积E=ABCD. 解：由矩阵乘法的结合律，可有如下算法 1. E=((AB)C)D. 计算量N1=11500flop 2. E=A(B(CD)). 计算量N2=125000flop 3. E=(A(BC))D. 计算量N3=2200flop 线性代数一④
由:
1 1 (4) I n1 (n 1) 可取 6n 5n
1 1 I 20 6 21 5 21 0.00873061 自n=20计算到n=1, 2
线性代数一④
1 1 6(m 1) 5(m 1) Im (m 1) 2
17/32
n 20
In
0.00873016
线性代数一④
有递推公式
在该例中,用上述公式计算积分的值,I0=ln6-ln5 ≈0.182322的舍入误差在计算过程迅速传播，每次扩大 5倍，致使I12= -0.32902110×10-2 严重失真，所以这一 公式是不稳定的。 n 1 In
0.0883922
1 I n 5I n1 (n 1,2,...) n
然后取充分大的m对应的Im的一个估计值为计算初 值，再逐步用上式算出Im-1 ，Im-2 ，...，I1。
8/32
1 1 1 1 6(m 1) 5(m 1) In (n 1) 由: (4) 可取 I m 6n 1 5n 1 2
用上式计算 Im 可使计算的误差减少5倍，因而它对应 的算法是数值稳定的算法。
1 I n 5I n1 (n 1,2,...) n
14/32
1 1 I n 1 I n (n m, m 1,...,2,1) 5 5n
然后取充分大的m对应的Im的一个估计值为计算初 值，再逐步用上式算出Im-1 ，Im-2 ，...，I1。
用上式计算 Im 可使计算的误差减少5倍，因而它对 应的算法是数值稳定的算法。
1 1 I n 1 I n (n m, m 1,...,2,1) 5 5n
线性代数一④
该公式给 出的算法 就是稳定 的
下面通过例子给出算法数值稳定的几个原则：
10/32
Βιβλιοθήκη Baidu
控制误差传播的几个原则
一、防止相近的两数相减
(会耗失许多有效数字,可以用数学公式化简后再做)
例1: 各有五位有效数字的两个数23.034与22.993相减. 23.034-22.993=0.041 0.041只有两位有效数字,有效数字的耗失,说明准确度减 小,因此,在计算时需要加工计算公式,以免这种情况发生. 例2:当x较大时，计算
11 12 13 1s 21 22 23 2s n1 n2 nn-1
=[cij]ms
ns
1 1 自n=20计算到n=1, I 20 6 21 5 21 0.00873061 2
线性代数一④
n 20
In
0.00873016 0.00825397 0.00887552 0.00933601 0.00989750
n 15
In
0.0105205 0.0112292 0.0120399 0.0129766 0.0140713
线性代数一④
12/32
二、防止大数吃小数 当两个绝对值相差很大的数进行加法或减法运算时,绝对 值小的数有可能被绝对值大的数"吃掉"从而引起计算结果 很不可靠. 例4:求一元二次方程x2-(109 +4)x+4×109=0 的实数根. 采用因式分解法 , 很容易得到两个根为 x1=109,x2=4. 如采用 字长为8位的计算机来计算 ,求得根为 x1=109 ，x2=0.(怎样 计算可得较好的结果?) 两者结果不同 , 因为计算机计算时做加减法要 “对 阶” ,“ 对阶”的结果使大数吃掉了小数 . 产生了误差 . 为了 避免由于上述原因引起的计算结果严重失真 , 可以根据一 些具体情况 , 有时需要把某些算式改写成另一种等价的形 式. 线性代数一④
19/32
计算量：一个算法所需的乘除运算总次数，单位是flop. 计算量也是衡量一个算法好坏的重要标准。
矩阵乘积AB的计算量分析
a a a …a a a a …a ...... … ... a a a …a
11 12 13 21 22 23 m1 m2 mm-1 1n 2n
mn
b b b … b b b b … b ...... … ... b b b … b
n 16
In
-10.1569
2
3
0.058038
0.0431387
7
8
0.0188109
0.0212378
12
13
-0.00329022
-0.0933742
17
18
50.8433
-2540161
4
5
0.0343063
0.0284686
9
10
0.0170566
0.0147169
14
15
-0.395442
15/32
n 6
In
0.0243239
n 11
In
0.0173247
n 16
In
-10.1569
2
3
0.058038
0.0431387
7
8
0.0188109
0.0212378
12
13
-0.00329022
-0.0933742
17
18
50.8433
-2540161
4
0.0343063
9
0.0170566
6/32
见教材第2、10—11页 例：计算
In
1
0
x dx x5
n
In有以下性质
(1)In>0; (2)In单调递减
(3) lim I n 0;
1 1 (4) In (n 1) 6n 1 5n 1
n
有递推公式
1 I n 5I n1 (n 1,2,...) n
2.04388
19
20
1270.86
-6354.23
1 I n 5I n1 (n 1,2,...) n
舍入误差在计算过程迅速传播，每次扩大5倍. 所以此算法是不稳定的。
线性代数一④
1 而将公式变为 I n 5I n1 (n 1,2,...) n 1 1
I n 1 I n (n m, m 1,...,2,1) 5 5n
线性代数一④
该公式给 出的算法 就是稳定 的
五、简化计算步骤,减小运算次数,避免误差积累18/32
简化计算步骤是提高程序执行速度的关键，它不仅可以节省 时间，还能减少舍入误差。
例6：计算9255的值 若逐个相乘要用254次乘法, 9255 = 9•9•9•……•9 但若写成 9255 = 9• 92 • 94 • 98 • 916 • 932 • 964 • 9128 只需做14次乘法运算即可。 9255 = ((((((( 92 )2 )2 )2 ) 2 )2 )2 )2 /9 只需8次乘法和1次除法运算。
13/32
三、防止接近零的数做除数
分母接近零的数会产生溢出错误,因而产生较大的误差,此时 可以用数学公式化简后再做.
分母接近0，如何改进？ 如：|x|<<1时
也可以用等价无穷小替换
1 cos x sin x sin x 1 cos x
In有以下性质
四、要控制舍入误差的累积和传播
例5 计算
n 10
In
0.0153676 0.0169265 0.0933742 0.0212326 0.0233250
n 5
9/32 I n
0.0284684 0.0343063 0.0431387 0.0580389 0.0883922
19
18
14
13
9
8
4
3
17
16
12
11
7
6
2
1
最后得: I0=0.182322 与我们开始计算的I0≈0.182322是一样的
则它至少有n位有效数字。
线性代数一④
5/32
§1.4 算法的数值稳定性 (数值计算中值得注意的问题)
一个算法如果输入数据有误差，而在计算过 程中舍入误差不增长，则称此算法是数值稳定的， 否则称此算法为不稳定的。 换句话说：若误差传播是可控制的,则称此算法是 数值稳定的,否则称此算法为不稳定的。
线性代数一④
n 15
In
0.0105205
n 10
In
0.0153676
n 5
In
0.0284684
19
18
0.00825397
0.00887552
14
13
0.0112292
0.0120399
9
8
0.0169265
0.0933742
4
3
0.0343063
0.0431387
17
16
0.00933601
0.00989750
结果只有一位有效数字,有效数字大量损失,造成相 对误差扩大。这是由两个比较接近的数相减造成的。
1 1 1 1 5 0.1734 10 759 760 759 760 0.5768 10 6
结果仍然有四位有效数字。这说明了算法设计的 重要性。
注：数值计算中要避免有效数字减少。
0.0147169
14
15
-0.395442
2.04388
19
20
1270.86
-6354.23
0.0284686 5 线性代数一 10 ④
16/32
而将公式变为
1 1 I n 1 I n (n m, m 1,...,2,1) 5 5n
然后取充分大的m对应的Im的一个估计值为计算初 值，再逐步用上式算出Im-1 ，Im-2 ，...，I1。 用上式计算 Im 可使计算的误差减少5倍，因而它对应 的算法是数值稳定的算法。
线性代数一④
4/32
相对误差与有效数字的关系如下： 定理1.1 设近似数x=±0.a1a2…an×10m有n位有效数字, 则其相对误差限为
1 n 1 r 10 , 2a1 10 ,
定理1.2 设近似数x=±0.a1a2…an×10m的相对误差限 为 1 n1
r
2(a1 1)
x 1
x
化成
x 1
x
1 x 1 x
线性代数一④
11/32
例3:用四位浮点数计算 解:
1 1 759 760
1 1 759 760
1 1 0.1318 10 2 0.1316 10 2 0.2 10 5 759 760 1 1
759 760
在该例中,用上述公式计算积分的值,I0=ln6-ln5 ≈0.182322的舍入误差在计算过程迅速传播，每次扩大 5倍，致使I12= -0.32902110×10-2 严重失真，所以这一 公式是不稳定的。
线性代数一④
7/32
n 1
In
0.0883922
n 6
In
0.0243239
n 11
In
0.0173247
1/32
上节课内容回顾
设x*是准确数, x是x*的近似数，称e = x* - x 为近 似值x的绝对误差，简称误差。 ——反映是近似值与精确值的绝对差值
e x * x 称 er 为近似值x的相对误差 x* x*
——反映是近似值与精确值的近似程度
通常用百分数来表示，相对误差越小，近似程度越高