2004-10-25 zhwang@nwpu.edu.cn 1
工科研究生公共课程数学系列之
《数值分析》
教师：王振海
2004-10-25 zhwang@nwpu.edu.cn 2
null教材
null封建湖，车刚明，聂玉峰，数值分析原理，
科学出版社，2001
null参考书
null1、车刚明，聂玉峰，封建湖，欧阳洁，数值分析典型题解析及自测试题，西北工业大学出版社，2002
null2、封建湖，车刚明，计算方法典型题分析解集（第二版），西北工业大学出版社，2001
null3、封建湖，聂玉峰，王振海，数值分析导教导学导考，西北工业大学出版社，2003
2004-10-25 zhwang@nwpu.edu.cn 3
第一章绪论
null内容提要
1 算法的概念、可靠性以及优劣评判
2 误差的度量以及传播
3 算法设计应注意的问题
2004-10-25 zhwang@nwpu.edu.cn 4
一、科学与工程计算过程
null提出实际问题辨析其中的主要矛盾和次要矛盾，并在合理假设的条件下，运用各种数学理论、工具和方法，
建立起问题中不同量之间的联系，
即得到数学模型。
建立数学模型数学模型解的存在性（模型内部没有蕴含矛盾）、惟一性（模型是完备的)以及对相关数据的连续依赖性统称为模型的适定性。
null提出数值问题数值问题是指有限个输入数据
（问题的自变量、原始数据）与有限个输出数据（待求解数据）
之间函数关系的一个明确无歧义的描述。这正是数值分析所研究的对象。
2004-10-25 zhwang@nwpu.edu.cn 5
数值问题举例
=
∈+=
0
2
0
10
yy
xyx
dx
dy
)(
],[
是用一阶常微分方程初值问题表示的数学模型，要求无穷多个输出，因而它不是数值问题。但当我们要求出有限个点处函数值的近似值时，便成为一数值问题。
2004-10-25 zhwang@nwpu.edu.cn 6
科学与工程计算过程（续）
分类方法1：若算法包含有一个进程则称其为串行算法，
否则为并行算法。
分类方法2：从算法执行所花费的时间角度来讲，若算术运算占绝大多数时间则称其为数值型算法，否则为非数值型算法。
本课程介绍数值型串行算法。（其它类型算法参阅数据结构、并行算法等课程）
null设计高效可靠的算法数值分析的任务之一就是提供求得数值问题近似解的方法—
算法。
概念：从程序设计的角度来讲，所谓算法是由一个或多个进程组成；每个进程明确无歧义地描述由操作及操作对象合成的按一定顺序执行的有限序列；所有进程能够同时执行并且协调地在有限个操作步内完成一个给定问题的求解。这里操作可以是计算机能够完成的算术运算（加减乘除）、逻辑运算、字符运算等。
2004-10-25 zhwang@nwpu.edu.cn 7
设计高效可靠的算法（续1）
优劣评价：可靠算法的优劣，应该考虑其时间复杂度（计算机运行时间）、空间复杂度
（占据计算机存储空间的多少）以及逻辑复杂度（影响程序开发的周期以及维护）。这是数值分析研究的第三个任务。
可靠性：所谓算法的可靠性包括如下几个方面：算法的收敛性、
稳定性、误差估计等。
这些是数值分析研究的第二个任务。
一个算法在保证可靠的大前提下再评价其优劣才是有价值的。
2004-10-25 zhwang@nwpu.edu.cn 8
设计高效可靠的算法（续2）
鉴于实际问题的复杂性，通常将其具体地分解为一系列子问题进行研究，本课程主要涉及如下几个方面问题的求解算法：
null函数的插值和逼近
null数值积分和数值微分
null线性方程组求解、非线性方程（组）求解
null代数特征值问题
null常微分方程数值解。
2004-10-25 zhwang@nwpu.edu.cn 9
算法应用状态数值分析研究对象以及解决问题方法的广泛适用性，著名流行软件如Maple、Matlab、
Mathematica等已将其绝大多数内容设计成函数，简单调用之后便可以得到运行结果。
但由于实际问题的具体特征、复杂性,
以及算法自身的适用范围决定了应用中必须选择、设计适合于自己特定问题的算法，因而掌握数值方法的思想和内容是至关重要的。
2004-10-25 zhwang@nwpu.edu.cn 10
本课程的学习方法
null尽管本课程所讲算法是很有限的，但许多初学可能仍会觉得公式多，理论分析复杂。在此，我们提出如下的几点学习方法，仅供初学者参考。
null 1、认识建立算法和对每个算法进行理论分析是基本任务，
主动适应公式多和讲究理论分析的特点。
null 2、注重各章节所研究算法的提出，搞清楚问题的基本提法、
逐步深入的层次及提法的正确性。
null 3、理解每个算法建立的数学背景、数学原理和基本线索，
而且对一些最基本的算法要非常熟悉。
null 4、从各种算法的理论分析中学习推理证明方法，提高推理证明能力。
null 5、认真进行数值计算的训练。
2004-10-25 zhwang@nwpu.edu.cn 11
科学与工程计算过程小结
提出实际问题
建立数学模型
提出数值问题
设计可靠、高效的算法
程序设计、上机实践计算结果
计算结果的可视化在具体问题的求解过程中，上述步骤形成一个循环。
科学计算（数值模拟）已经被公认为与理论分析、实验分析并列的科学研究三大基本手段之一。
2004-10-25 zhwang@nwpu.edu.cn 12
二、误差基础知识内容提要：
1.误差的来源及其分类
2.误差的度量
3.误差的传播
2004-10-25 zhwang@nwpu.edu.cn 13
1.误差来源及其分类
1)模型误差（描述误差）
2)观测误差
2
21
r
mm
GF =
在数值分析中不研究这两类误差，总是假定数学模型是正确合理的反映了客观实际问题。
2004-10-25 zhwang@nwpu.edu.cn 14
误差来源及其分类(续1)
3)截断误差（方法误差）
数值方法精确解与待求解模型的理论分析解之间的差异。
它是由于算法必须在有限步内执行结束而导致的，它需要将无穷过程截断为有限过程。
例如：
n
eeee?++++=+++=,
!n
1
!2
1
!1
1
1,
!2
1
!1
1
1
n
LL
2004-10-25 zhwang@nwpu.edu.cn 15
误差来源及其分类(续2)
4)舍入误差在实现数值方法的过程中，由于计算机表示浮点数采用的是有限字长，因而仅能够区分有限个信息，准确表示某些数，不能准确表示所有实数，这样在计算机中表示的原始输入数据、中间计算数据、以及最终输出结果必然产生误差，称此类误差为舍入误差。
如利用计算机计算e的近似值e
n
时，实际上得不到e
n
的精确值，只能得到e
n
的近似e
*；这样e
*
作为e的近似包含有舍入误差和截断误差两部分：
)()(
nn
**
eeeeee?+?=?
2004-10-25 zhwang@nwpu.edu.cn 16
2,误差的度量
1)绝对误差
2)相对误差
3)有效数字
4)度量间的关系
2004-10-25 zhwang@nwpu.edu.cn 17
1）绝对误差
null绝对误差定义：近似值---真值，用符号记为
)(
**
xexx
=?
在不引起混淆时，简记
)(
*
xe
为
*
e
,
强、弱近似：
误差有正有负，当误差为正时，近似值较真值偏大，称此近似为“强近似”；当误差为负时，
近似值较真值偏小，称此近似为“弱近似”。
2004-10-25 zhwang@nwpu.edu.cn 18
绝对误差（续）
绝对误差限：
如果存在正数
)(
**
xε=ε
，使得有绝对误差
***
ε≤?= xxe
,
则称
*
ε
为x
*
近似x的一个绝对误差限。
],[
**
ε+ε?∈
**
xxx
，
*
ε±=
*
xx
。
null Remark,通常计算中所要求的误差，是指估计一个尽可能小的绝对误差限。
2004-10-25 zhwang@nwpu.edu.cn 19
2）相对误差
Remark,绝对误差限虽然能够刻划对同一真值不同近似的好坏，
但它不能刻划对不同真值近似程度的好坏。
null 定义 设x
*
是对准确值x（
0≠
）的一个近似，称
x
xe
x
xx
xe
r
)(
)(
**
*
=
=
为x
*
近似x的相对误差。不引起混淆时，简记
)(
*
xe
r为
*
r
e
.
2004-10-25 zhwang@nwpu.edu.cn 20
相对误差（续1）
相对误差的另一计算公式：
( )
)(
2
*
*
*
*
*
*
**
*
*
*
r
exx
e
xx
xx
e
x
e
x
e
x
e
e
+
=
=?=?
知
*
r
e
与
*
*
x
e
相差一个较
*
r
e
高一阶的无穷小量，故时常也用后者来计算相对误差
*
r
e
,
()( )
2
2
1
1
*
r
*
*
eO
x
e
xe
=
+
=
2004-10-25 zhwang@nwpu.edu.cn 21
相对误差（续2）
null 相对误差限：数值
*
r
e
的上界，记为
)(
*
x
r
ε
。
相对误差限也可以通过
*
r
x
**
ε=ε
来计算。
null Remark,当要求计算相对误差，是指估计一个尽可能小的相对误差限。
2004-10-25 zhwang@nwpu.edu.cn 22
3）有效数字为规定一种近似数的表示法，使得用它表示的近似数自身就直接指示出其误差的大小。
为此需要引出有效数字和有效数的概念。
null 定义 设x的近似值x
*
有如下标准形式
p1nn21
m*
xxxxx.010 LL
+
×±=x
,
其中m为整数，
},,,,{}{ 9210x
i
L?
且
0x
1
≠
，
np ≥
,如果有
nm
2
1
*
10e
×≤?= xx
*
,
则称x
*
为x的具有n位有效数字的近似数，或称x
*
准确到
nm
10
位，
其中数字
n21
xxx,,,L
分别被称为x
*
的第一、二、…、n个有效数字。
2004-10-25 zhwang@nwpu.edu.cn 23
有效数字（续1）
null有效数：当x
*
准确到末位，即n=p，则称x
*
为有效数
null举例：x=π,x1*=3.141,x2*=3.142
31*
1
10
2
1
005.000059.0
=≤=? Lxx
3位有效数字，非有效数
41*
2
10
2
1
0005.000040.0
=≤=? Lxx
4位有效数字，有效数
2004-10-25 zhwang@nwpu.edu.cn 24
有效数字（续2）
null Remark1,有效数的误差限是末位数单位的一半，可见有效数本身就体现了误差界。
null Remark2,对真值进行四舍五入得到有效数。
null Remark3,从实验仪器所读的近似数（最后一为是估计位）不是有效数，估计最后一位是为了确保对最后一位进行四舍五入得到有效数。
null例从最小刻度为厘米的标尺读得的数据123.4cm是为了得到有效数123.cm,读得数据156.7cm是为了得到有效数157.cm。
2004-10-25 zhwang@nwpu.edu.cn 25
4）误差度量间的联系
null绝对误差与相对误差
null e(x*)/x=er(x*)
null绝对误差与有效数字
null |e(x*)|<=
nm?
10
2
1
null 定理 1
0
若x
*
具有n位有效数字，则相对误差
n1
1
10
x2
1
×≤
*
r
e；
2
0
若相对误差
n1
1
10
)1x(2
1
×
+
≤
*
r
e
，则x
*
至少具有n位有效数字。
相对误差与有效数字相对误差与有效数字
2004-10-25 zhwang@nwpu.edu.cn 26
误差度量间的联系(续)
null Remark
null 1、该定理实质上给出了一种求相对误差限的方法。
null 2、仅从并不能保证x
*
一定具有n
位有效数字。如设其近似值a=0.484，其相对误差为：
我们并不能由此断定a有两位有效数字，因为
n
r
x
e
×≤
1
1
*
10
2
1
4900.00229sin =
′
=
o
A
21
10
42
1
0125.0012397.0
484.0
484.04900.0
×
×
=<=
20
10
2
1
005.00060.0484.04900.0
×=>=?=? aA
2004-10-25 zhwang@nwpu.edu.cn 27
定理证明
o
1
nm
10
2
1
×
≤=
*
*
*
*
r
x
x
e
e
n1
1
nm
1
m
10
x2
1
10
x0102
1
×=×
××
≤
.
o
2
n21
mn1
1
xxx.01010
)1x(2
1
K×××
+
≤?=
**
r
*
xee
nm
1
n1m
1
10
2
1
1x010
1x2
1
+
×=+××
+
≤ ).(
)(
2004-10-25 zhwang@nwpu.edu.cn 28
例题1
为使
5=x
的近似值x
*
的相对误差不超过1%，问查开方表时至少要取几位有效数字？
设近似数x
*
保留n位有效数字可满足题设要求,解：
对于
5=x
，有x
1
=2,
依据定理1
o
有
n1n1
1
*
r
10
4
1
10
x2
1
e
×=×≤
令
01.010
4
1
n1
≤×
，解得
2.4n ≥
,取n=3位有效数字。
#
2004-10-25 zhwang@nwpu.edu.cn 29
3,初值误差传播
null概念：近似数参加运算后所得之值一般也是近似值，含有误差，将这一现象称为误差传播。
null误差传播的表现：
null算法本身可能有截断误差；
null初始数据在计算机内的浮点表示一般有舍入误差；
null每次运算一般又会产生新的舍入误差，并传播以前各步已经引入的误差；
null误差有正有负，误差积累的过程一般包含有误差增长和误差相消的过程，并非简单的单调增长；
null运算次数非常之多，不可能人为地跟踪每一步运算。
2004-10-25 zhwang@nwpu.edu.cn 30
初值误差传播（续）
null初值误差传播：假设每一步都是准确计算，即不考虑截断误差和由运算进一步引入的舍入误差，仅介绍初始数据的误差传播规律。
null研究方法：
null泰勒（Taylor）方法
null n元函数
null二元函数（算术运算）
null一元函数（计算函数值的条件数）
null区间分析法（工科研究生不要求）
2004-10-25 zhwang@nwpu.edu.cn 31
复习泰勒公式记点
),,,(
**
2
*
1 n
xxx L
为p
*
,点
),,,(
21 n
xxx L
为p，n元泰勒公式：
[ ]+?++?+= ))(())((
!1
1
)()(
*
*
*
11
*
1
*
nnn
xxpfxxpfpfpf L
[
]
L
L
L
L
+
+++
++++
+++?
2*
*
2
*
11
*
*
1
**
22
*
2
*
11
*
22
*
21
**
11
*
1
2*
11
*
11
))(())()((
))()(())()((
))()(())((
!2
1
nnnnnn
nnn
nnn
xxpfxxxxpf
xxxxpfxxxxpf
xxxxpfxxpf
2004-10-25 zhwang@nwpu.edu.cn 32
1）泰勒公式分析初值误差传播设n元可微函数
),,,(
n21
xxxfy L=
中的自变量x
1
、x
2
、…、
x
n
是相互独立的。
用自变量的近似值进行准确计算，得y
*
=
),,,(
***
n21
xxxf L
。
当
*
1
x
、
*
2
x
、…、
*
n
x
很好地近似了相应真值时，利用多元函数一阶Taylor公式求得
y
*
的绝对误差,
∑
=
≈?=
n
1i
i
*
i
*
n
*
1
'
i
**
))(,,()( xxxxfyyye L
∑
=
=
n
1i
*
i
*
n
*
1
'
i
)(),,( xexxf L
2004-10-25 zhwang@nwpu.edu.cn 33
泰勒方法（n元函数）
以及相对误差
∑
=
≈=
n
1i
*
i
*
i
*
n
*
1
'
i
*
*
i
*
*
*
)(
),,(
)(
)(
x
xe
xxf
y
x
y
ye
ye
r
L
∑
=
=
n
1i
*
i
*
n
*
1
'
i
*
*
i
)(),,( xexxf
y
x
r
L
进而得到如下绝对误差限和相对误差限传播关系：
∑
=
≈
<
n
1i
*
i
*
n
*
1
'
i
*
)(),,()( xxxfy εε L
∑
=
≈
<
n
1i
*
i
*
n
*
1
'
i
*
*
i
*
)(),,()( xxxf
y
x
y
rr
εε L
2004-10-25 zhwang@nwpu.edu.cn 34
泰勒方法（二元函数）
null二元函数算术运算误差传播规律
null绝对误差限null相对误差限
)()()(
*
2
*
1
*
2
*
1
xxxx εεε +≈±
)()()(
*
2
*
1
*
1
*
2
*
2
*
1
xxxxxx εεε +≈
)0(
)()(
)(
*
2
2
*
2
*
2
*
1
*
1
*
2
*
2
*
1
≠
+
≈
x
x
xxxx
x
x
εε
ε
)}(),({max)(
*
2
*
1
*
2
*
1
xxxx
rrr
εεε ≈+
)(
**
0
21
>xx
)()()(
*
2
*
1
*
2
*
1
xxxx
rrr
εεε +≈
)(
**
0
21
≠xx
)()()(
*
2
*
1
*
2
*
1
xx
x
x
rrr
εεε +≈
)(
**
0
21
≠xx
2004-10-25 zhwang@nwpu.edu.cn 35
泰勒方法（一元函数）
null Remark,对于具体的一组数据，上面给出的误差限传播公式是实际误差的一个粗糙偏大的估计,如对于加法运算的估计，它包括了误差源同号且同时均达到了误差限这一最坏的情况，实际情况往往并非这么坏.
null一元函数：y=f(x)
null绝对误差传播分析
null关系式推导由微分中值定理知
10 <θ<θ+=? ),))((()()(
**'*
xxxxxfxfxf
))((
*'
xxxf?≈
即有
)()())((
*'*
xexfxfe ≈
2004-10-25 zhwang@nwpu.edu.cn 36
泰勒方法（一元函数）（续1）
null讨论：当|f’(x)|<1时，函数值的扰动比自变量的微小变化还要小；而当|f’(x)|很大时，自变量的微小变化，将引起函数值较大的扰动，此时，称x是函数在绝对误差意义下的坏函数值点。
null定义绝对误差意义下的条件数：
)()(Cond
'
xff
a
=
null相对误差传播分析
关系式推导)(
)(
)(
)(
))((
))((
*
'*
*
xe
xf
xf
x
xf
xfe
xfe
rr
≈=
类似的讨论，可如下定义相对误差意义下的条件数：
)(
)(
)(Cond
'
xf
xf
xf
r
=
2004-10-25 zhwang@nwpu.edu.cn 37
泰勒方法（一元函数）（续2）
null条件数与误差传播的关系：
)()(Cond))((
**
xefxfe
a
≈
)()(Cond))((
**
xefxfe
rrr
≈
null结论：条件数是函数自身在一点处固有的特性,对于相同的自变量扰动，条件数越大，计算出的函数值误差越大,要提高函数值的计算精度，通常需要通过提高初值精度来实现.
2004-10-25 zhwang@nwpu.edu.cn 38
2）区间分析法分析初值误差传播
(工科硕士不要求)
知道初始数据的误差范围，我们可以用区间分析法分析初值误差的传播规律。
设],,[],,[
2211
baybax ∈∈
则有如下结论成立：
],,[
2121
bbaayx ++∈+
1
0
],,[
11
abx∈?
2
0
,0],1,1[1
1111
>∈ baabx
3
0
。},,,{],max,[min
21212121
bbabbaaayx =ΞΞΞ∈
4
0
2004-10-25 zhwang@nwpu.edu.cn 39
规定如下的区间运算规则：
],,[],[],[
21212211
bbaababa ++=+
1
0
],,[],[
1111
abba=?
2
0
,0],1,1[],[1
111111
>= baabba3
0
。]max,[min],[],[
2211
ΞΞ=× baba4
0
考虑到
,),(
1
y
xyxyxyx ×=÷?+=?
]),[(],[],[],[
22112211
babababa?+=?
],[
2121
abba=
5
0
2004-10-25 zhwang@nwpu.edu.cn 40
续
]),/[1(],[],/[],[
22112211
babababa ×=
6
0
0,
1
,
1
],[
22
22
11
>
×= ba
ab
ba
对于精确数p和近似数x之间的算术运算(代表加、
减、乘、除中任一种运算)有
],[],[
11
bappxp oo ∈
7
0
2004-10-25 zhwang@nwpu.edu.cn 41
三、舍入误差分析及数值稳定性
1.浮点数系
2.舍入误差的产生
3.舍入误差分析
4.数值稳定性
5.算法设计注意事项
2004-10-25 zhwang@nwpu.edu.cn 42
一浮点数系及其运算的舍入误差计算机中通常配置有两种类型的算术运算,
定点数运算和浮点数运算,所谓点是指小数点,
用浮点数进行计算是指用常数个数字进行工作;
而用定点数进行计算是指用常数个小数位数进行工作,这里我们仅介绍较多使用的浮点数系及其运算的舍入误差.
2004-10-25 zhwang@nwpu.edu.cn 43
1 浮点数系以及舍入误差的产生一个浮点数的表示由正负号、小数形式的尾数、以及确定小数点位置的阶三部分组成,单精度实数用32位的二进制数据表示浮点数的这三个信息,其中数值符号占1位,尾数占23位,
阶数占8位.
对于规范化的浮点数（除零外）,23位的二进制尾数形式是,
() },1,0{,221.0
i
i
23
2i
i
1
2
2332
∈+=
=
∑
ααααα L
2004-10-25 zhwang@nwpu.edu.cn 44
浮点数系以及舍入误差的产生（续）
式中表示尾数中小数点后第i位的权,当尾数的首位小于5时,可通过不断乘以2使之首位大于或等于5,相应的二进制阶数需要减去乘以2的次数,
在8位的阶数中,有1位表示阶数的符号,7位表示二进制的阶数数值,于是阶数数值的范围是
,
i
2
12~0
7
单精度实数集合为,
≤∈?
+±=∪=
=
∑
12,222}0{
7i
23
2i
i
1
pZpaaR
p
S
且α
2004-10-25 zhwang@nwpu.edu.cn 45
浮点数系以及舍入误差的产生（续）
其中元素是能够准确表示的数,称之为机器数,
设,与之相邻的能够准确表示的机器数是和,这样,在区间和上的实数无法准确表示,
S
Ra∈
23
2
+=
p
ab
23
2
=
p
ac
),( ac
),( ba
规定,不能精确表示的实数用与之最近的机器数表示,我们将实数在机器中的浮点(float)表示记为,
)(xfl
2004-10-25 zhwang@nwpu.edu.cn 46
浮点数系以及舍入误差的产生（续）
将由此表示产生的误差称之为舍入误差,xxfl?)(
如当
)2,2[
2
,
2
231231
+?=
++
∈
pp
aa
baac
x
时用表示,即有,
axfl =)(
相对误差满足:
*
r
e
923.623
1
231
*
102
2
2
)(
)(
≈=≤
=
p
p
r
xfl
xxfl
e
二进制阶数数值上限相应于十进制的阶数数值上限是38 除零外,单精度实数的量级不大于不小于.
12
7
)23.382lg)12((
7
≈?
38
10
30
10
2004-10-25 zhwang@nwpu.edu.cn 47
浮点数系以及舍入误差的产生（续）
设在某一浮点系统中,尾数占位二进制数(未计算尾数的符号位),阶数占位二进制数(未计算阶数的符号位),实数的浮点表示共需要位的二进制数位,
t
s
x
)(xfl
2++st
2004-10-25 zhwang@nwpu.edu.cn 48
浮点数系以及舍入误差的产生（续）
当不出现溢出时,相对误差和绝对误差分别满足如下估计,
*
r
e
*
e
tt
r
xfl
xxfl
e
=?≤
= 22
2
1
)(
)(
1*
tp
xxfle
≤?= 22)(
1*
由确定.上溢界和下溢界分别是和,对于单精度实数有,,
p
pp
x 22
1
<≤
2lg)12(12
102
=
ss
2lg22
102
ss
=
23=t
7=s
2004-10-25 zhwang@nwpu.edu.cn 49
2 浮点运算舍入误差分析设实数满足且,
则的浮点表示满足
x
pp
x 22
1
<≤
12?≤
s
p
x
)(xfl
t
xxfl
≤+= 2),1()( δδ
其中,分别为浮点系统中给二进制阶数数值以及尾数数值的表示所分配的二进制数位.
s t
2004-10-25 zhwang@nwpu.edu.cn 50
浮点运算舍入误差分析（续）
设,则有,进而由式(1.18)得
)1()( δ+= xxfl
x
xxfl?
=
)(
δ
t
p
tp
x
xxfl
=≤
= 2
2
2)(
1
1
δ
用符号表示加减乘除四种算术运算之一
。
t
yflxflyflxflfl
≤+= 2),1))(()(())()(( δδoo
2004-10-25 zhwang@nwpu.edu.cn 51
浮点运算舍入误差分析（续）
例1.6 对三同号数的算术运算作舍入误差分析.
cba ++
解这里对运算作误差分析,
cba ++ )(
)1))(()(())()((
3
δ++=+ bflaflbflaflfl
),1))(1()1((
321
δδδ ++++= ba
))())()((( cflbflaflflfl ++
2004-10-25 zhwang@nwpu.edu.cn 52
浮点运算舍入误差分析（续）
)1)}(())()(({
5
δ+++= cflbflaflfl
)1)}(1()1)](1()1({[
54321
δδδδδ +++++++= cba
++++++++++= )(
531535153131
δδδδδδδδδδδδacba
)(
532535253232
δδδδδδδδδδδδ +++++++b
)(
5454
δδδδ +++c
。5,4,3,2,1,2 =≤≤
i
t
i
εδ
设于是得到
)())())()((( cbacflbflaflflfl ++?++
( )。)2()33(
232
εεεεε +++++≤ cba
2004-10-25 zhwang@nwpu.edu.cn 53
浮点运算舍入误差分析（续）
表明:数学上等价的算法在数值上并不总是等效的.
这种将误差估计转化为原始数据摄动的方法,称之为向后误差分析法.
这种将误差估计转化为原始数据摄动的方法,称之为向后误差分析法.
通常的思路,对每一步找出舍入误差界,随着计算过程逐步向前分析,直到估计出最后结果的误差界,这一方法称之为向前误差分析法,
2004-10-25 zhwang@nwpu.edu.cn 54
3,数值稳定性
null定义：一个算法,如果在运算过程中舍入误差在一定条件下能够得到控制,或者舍入误差的增长不影响产生可靠的结果,则称该算法是数值稳定的,否则称其为数值不稳定.
dx
x
x
I
n
n
∫
+
=
1
0
5
null例：计算如下积分近似值的两种方案比较
),,( L215
1
1
=?=
nI
n
I
nn
null方法1：
1823.0
5
6
ln
5
1
1
0
0
≈=
+
=
∫
dx
x
I
2004-10-25 zhwang@nwpu.edu.cn 55
n
方法1计算结果
n
*
n
I
nn
II?
*
0 0.1823 0.00002
1 0.0885 0.0001
2 0.0575 0.0005
3 0.0458 0.0027
4 0.0208 0.0135
5 0.0958 0.0673
6 －0.3125 0.3368
7 1.7054 1.6842
8 －8.4018 8.4206
9 42.1200 42.1031
10 －210.5002 210.5156
2004-10-25 zhwang@nwpu.edu.cn 56
方法一结果分析
null 方法一分析：计算结果表明,舍入误差的传播近似依5
的幂次进行增长,因而是一种不稳定的方法.
*
1
*
5
2
1
=
nn
II
1
5
2
1
=
nn
II
*
0
*
2
2*
1
*
555 eeee
n
nnn
===
null方法二：
55
1
*
*
1
n
n
I
n
I?=
55
1
1
n
n
I
n
I?=
*
5
1
*
1 nn
ee =
由此分析知，该方法是稳定的。关于初值的近似可由下面式子得到：
)1(5
1
56)1(6
1
1
0
1
0
+
=≤≤=
+
∫∫
n
dx
x
Idx
x
n
n
n
n
2004-10-25 zhwang@nwpu.edu.cn 57
方法2计算结果
n
*
n
I
nn
II?
*
0 0.1823 0.2156
×
10
-6
1 0.0884 0.7784
×
10
-7
2 0.0580 0.3892
×
10
-6
3 0.0431 0.3873
×
10
-6
4 0.0343 0.6330
×
10
-7
5 0.0285 0.3165
×
10
-6
6 0.0243 0.2491
×
10
-6
7 0.0212 0.3262
×
10
-6
8 0.0189 0.6308
×
10
-6
9 0.0167 0.2265
×
10
-5
10 0.0167 0.1332
×
10
-4
01670
66
1
55
1
2
1
10
.
*
≈
+=I
2004-10-25 zhwang@nwpu.edu.cn 58
4.算法设计注意的问题
null相近数相减的误差传播
null例x=52.127 x*=52.129 四位有效数字
y=52.123 y*=52.121 四位有效数字
A=x-y=0.004 A*=x*-y*=0.008 零位有效数字
null结论：避免相近数相减
null一些避免相近数相减示例
当|x|>>1时
x
x
xx
1
lnln)1ln(
+
=?+
)( 1
1
1
11
+
=
+
xxxx
2004-10-25 zhwang@nwpu.edu.cn 59
算法设计注意的问题(续1)
xx
xx
++
=?+
1
1
1 )1ln()1ln(
22
+?= xxxx
当|x|<<1时
2
2
2
11
11
x
x
x
+
=
L?+?=?
53
arctan
53
xx
xx
L+?=?
!5!3
sin
53
xx
xx
2004-10-25 zhwang@nwpu.edu.cn 60
算法设计注意的问题(续2)
null合理安排量级相差很大的数之间的运算次序,尽可能避免大数“吃掉”小数。
null例
)10(987654321
1000000
1
≤<+
∑
=
k
k
k
δδ
null简化计算步骤以减少运算次数。
842
84228448816
3*3*3*3*3
3*3*3*33*3*33*33
=
===
null例1
2004-10-25 zhwang@nwpu.edu.cn 61
算法设计注意的问题(续3)
null例2 秦九韶算法
01
2
2
3
3
4
4
axaxaxaxa ++++
01234
)))((( axaxaxaxa ++++=
null尽可能避免绝对值很小的数做分母，防止出现溢出。
null选用数值稳定性好的算法。
2004-10-25 zhwang@nwpu.edu.cn 62
总之,除了算法的正确性之外,在算法设计中至少还应注意如下几个方面的问题:
1 尽量避免两个相近的近似数相减;
2 合理安排量级相差很大的数之间的运算次序,防止大数"吃掉"小数;
3 尽可能避免绝对值很小的数做分母;
4 防止出现溢出;
5 简化计算步骤以减少运算次数;
6 选用数值稳定性好的算法.
工科研究生公共课程数学系列之
《数值分析》
教师：王振海
2004-10-25 zhwang@nwpu.edu.cn 2
null教材
null封建湖，车刚明，聂玉峰，数值分析原理，
科学出版社，2001
null参考书
null1、车刚明，聂玉峰，封建湖，欧阳洁，数值分析典型题解析及自测试题，西北工业大学出版社，2002
null2、封建湖，车刚明，计算方法典型题分析解集（第二版），西北工业大学出版社，2001
null3、封建湖，聂玉峰，王振海，数值分析导教导学导考，西北工业大学出版社，2003
2004-10-25 zhwang@nwpu.edu.cn 3
第一章绪论
null内容提要
1 算法的概念、可靠性以及优劣评判
2 误差的度量以及传播
3 算法设计应注意的问题
2004-10-25 zhwang@nwpu.edu.cn 4
一、科学与工程计算过程
null提出实际问题辨析其中的主要矛盾和次要矛盾，并在合理假设的条件下，运用各种数学理论、工具和方法，
建立起问题中不同量之间的联系，
即得到数学模型。
建立数学模型数学模型解的存在性（模型内部没有蕴含矛盾）、惟一性（模型是完备的)以及对相关数据的连续依赖性统称为模型的适定性。
null提出数值问题数值问题是指有限个输入数据
（问题的自变量、原始数据）与有限个输出数据（待求解数据）
之间函数关系的一个明确无歧义的描述。这正是数值分析所研究的对象。
2004-10-25 zhwang@nwpu.edu.cn 5
数值问题举例
=
∈+=
0
2
0
10
yy
xyx
dx
dy
)(
],[
是用一阶常微分方程初值问题表示的数学模型，要求无穷多个输出，因而它不是数值问题。但当我们要求出有限个点处函数值的近似值时，便成为一数值问题。
2004-10-25 zhwang@nwpu.edu.cn 6
科学与工程计算过程（续）
分类方法1：若算法包含有一个进程则称其为串行算法，
否则为并行算法。
分类方法2：从算法执行所花费的时间角度来讲，若算术运算占绝大多数时间则称其为数值型算法，否则为非数值型算法。
本课程介绍数值型串行算法。（其它类型算法参阅数据结构、并行算法等课程）
null设计高效可靠的算法数值分析的任务之一就是提供求得数值问题近似解的方法—
算法。
概念：从程序设计的角度来讲，所谓算法是由一个或多个进程组成；每个进程明确无歧义地描述由操作及操作对象合成的按一定顺序执行的有限序列；所有进程能够同时执行并且协调地在有限个操作步内完成一个给定问题的求解。这里操作可以是计算机能够完成的算术运算（加减乘除）、逻辑运算、字符运算等。
2004-10-25 zhwang@nwpu.edu.cn 7
设计高效可靠的算法（续1）
优劣评价：可靠算法的优劣，应该考虑其时间复杂度（计算机运行时间）、空间复杂度
（占据计算机存储空间的多少）以及逻辑复杂度（影响程序开发的周期以及维护）。这是数值分析研究的第三个任务。
可靠性：所谓算法的可靠性包括如下几个方面：算法的收敛性、
稳定性、误差估计等。
这些是数值分析研究的第二个任务。
一个算法在保证可靠的大前提下再评价其优劣才是有价值的。
2004-10-25 zhwang@nwpu.edu.cn 8
设计高效可靠的算法（续2）
鉴于实际问题的复杂性，通常将其具体地分解为一系列子问题进行研究，本课程主要涉及如下几个方面问题的求解算法：
null函数的插值和逼近
null数值积分和数值微分
null线性方程组求解、非线性方程（组）求解
null代数特征值问题
null常微分方程数值解。
2004-10-25 zhwang@nwpu.edu.cn 9
算法应用状态数值分析研究对象以及解决问题方法的广泛适用性，著名流行软件如Maple、Matlab、
Mathematica等已将其绝大多数内容设计成函数，简单调用之后便可以得到运行结果。
但由于实际问题的具体特征、复杂性,
以及算法自身的适用范围决定了应用中必须选择、设计适合于自己特定问题的算法，因而掌握数值方法的思想和内容是至关重要的。
2004-10-25 zhwang@nwpu.edu.cn 10
本课程的学习方法
null尽管本课程所讲算法是很有限的，但许多初学可能仍会觉得公式多，理论分析复杂。在此，我们提出如下的几点学习方法，仅供初学者参考。
null 1、认识建立算法和对每个算法进行理论分析是基本任务，
主动适应公式多和讲究理论分析的特点。
null 2、注重各章节所研究算法的提出，搞清楚问题的基本提法、
逐步深入的层次及提法的正确性。
null 3、理解每个算法建立的数学背景、数学原理和基本线索，
而且对一些最基本的算法要非常熟悉。
null 4、从各种算法的理论分析中学习推理证明方法，提高推理证明能力。
null 5、认真进行数值计算的训练。
2004-10-25 zhwang@nwpu.edu.cn 11
科学与工程计算过程小结
提出实际问题
建立数学模型
提出数值问题
设计可靠、高效的算法
程序设计、上机实践计算结果
计算结果的可视化在具体问题的求解过程中，上述步骤形成一个循环。
科学计算（数值模拟）已经被公认为与理论分析、实验分析并列的科学研究三大基本手段之一。
2004-10-25 zhwang@nwpu.edu.cn 12
二、误差基础知识内容提要：
1.误差的来源及其分类
2.误差的度量
3.误差的传播
2004-10-25 zhwang@nwpu.edu.cn 13
1.误差来源及其分类
1)模型误差（描述误差）
2)观测误差
2
21
r
mm
GF =
在数值分析中不研究这两类误差，总是假定数学模型是正确合理的反映了客观实际问题。
2004-10-25 zhwang@nwpu.edu.cn 14
误差来源及其分类(续1)
3)截断误差（方法误差）
数值方法精确解与待求解模型的理论分析解之间的差异。
它是由于算法必须在有限步内执行结束而导致的，它需要将无穷过程截断为有限过程。
例如：
n
eeee?++++=+++=,
!n
1
!2
1
!1
1
1,
!2
1
!1
1
1
n
LL
2004-10-25 zhwang@nwpu.edu.cn 15
误差来源及其分类(续2)
4)舍入误差在实现数值方法的过程中，由于计算机表示浮点数采用的是有限字长，因而仅能够区分有限个信息，准确表示某些数，不能准确表示所有实数，这样在计算机中表示的原始输入数据、中间计算数据、以及最终输出结果必然产生误差，称此类误差为舍入误差。
如利用计算机计算e的近似值e
n
时，实际上得不到e
n
的精确值，只能得到e
n
的近似e
*；这样e
*
作为e的近似包含有舍入误差和截断误差两部分：
)()(
nn
**
eeeeee?+?=?
2004-10-25 zhwang@nwpu.edu.cn 16
2,误差的度量
1)绝对误差
2)相对误差
3)有效数字
4)度量间的关系
2004-10-25 zhwang@nwpu.edu.cn 17
1）绝对误差
null绝对误差定义：近似值---真值，用符号记为
)(
**
xexx
=?
在不引起混淆时，简记
)(
*
xe
为
*
e
,
强、弱近似：
误差有正有负，当误差为正时，近似值较真值偏大，称此近似为“强近似”；当误差为负时，
近似值较真值偏小，称此近似为“弱近似”。
2004-10-25 zhwang@nwpu.edu.cn 18
绝对误差（续）
绝对误差限：
如果存在正数
)(
**
xε=ε
，使得有绝对误差
***
ε≤?= xxe
,
则称
*
ε
为x
*
近似x的一个绝对误差限。
],[
**
ε+ε?∈
**
xxx
，
*
ε±=
*
xx
。
null Remark,通常计算中所要求的误差，是指估计一个尽可能小的绝对误差限。
2004-10-25 zhwang@nwpu.edu.cn 19
2）相对误差
Remark,绝对误差限虽然能够刻划对同一真值不同近似的好坏，
但它不能刻划对不同真值近似程度的好坏。
null 定义 设x
*
是对准确值x（
0≠
）的一个近似，称
x
xe
x
xx
xe
r
)(
)(
**
*
=
=
为x
*
近似x的相对误差。不引起混淆时，简记
)(
*
xe
r为
*
r
e
.
2004-10-25 zhwang@nwpu.edu.cn 20
相对误差（续1）
相对误差的另一计算公式：
( )
)(
2
*
*
*
*
*
*
**
*
*
*
r
exx
e
xx
xx
e
x
e
x
e
x
e
e
+
=
=?=?
知
*
r
e
与
*
*
x
e
相差一个较
*
r
e
高一阶的无穷小量，故时常也用后者来计算相对误差
*
r
e
,
()( )
2
2
1
1
*
r
*
*
eO
x
e
xe
=
+
=
2004-10-25 zhwang@nwpu.edu.cn 21
相对误差（续2）
null 相对误差限：数值
*
r
e
的上界，记为
)(
*
x
r
ε
。
相对误差限也可以通过
*
r
x
**
ε=ε
来计算。
null Remark,当要求计算相对误差，是指估计一个尽可能小的相对误差限。
2004-10-25 zhwang@nwpu.edu.cn 22
3）有效数字为规定一种近似数的表示法，使得用它表示的近似数自身就直接指示出其误差的大小。
为此需要引出有效数字和有效数的概念。
null 定义 设x的近似值x
*
有如下标准形式
p1nn21
m*
xxxxx.010 LL
+
×±=x
,
其中m为整数，
},,,,{}{ 9210x
i
L?
且
0x
1
≠
，
np ≥
,如果有
nm
2
1
*
10e
×≤?= xx
*
,
则称x
*
为x的具有n位有效数字的近似数，或称x
*
准确到
nm
10
位，
其中数字
n21
xxx,,,L
分别被称为x
*
的第一、二、…、n个有效数字。
2004-10-25 zhwang@nwpu.edu.cn 23
有效数字（续1）
null有效数：当x
*
准确到末位，即n=p，则称x
*
为有效数
null举例：x=π,x1*=3.141,x2*=3.142
31*
1
10
2
1
005.000059.0
=≤=? Lxx
3位有效数字，非有效数
41*
2
10
2
1
0005.000040.0
=≤=? Lxx
4位有效数字，有效数
2004-10-25 zhwang@nwpu.edu.cn 24
有效数字（续2）
null Remark1,有效数的误差限是末位数单位的一半，可见有效数本身就体现了误差界。
null Remark2,对真值进行四舍五入得到有效数。
null Remark3,从实验仪器所读的近似数（最后一为是估计位）不是有效数，估计最后一位是为了确保对最后一位进行四舍五入得到有效数。
null例从最小刻度为厘米的标尺读得的数据123.4cm是为了得到有效数123.cm,读得数据156.7cm是为了得到有效数157.cm。
2004-10-25 zhwang@nwpu.edu.cn 25
4）误差度量间的联系
null绝对误差与相对误差
null e(x*)/x=er(x*)
null绝对误差与有效数字
null |e(x*)|<=
nm?
10
2
1
null 定理 1
0
若x
*
具有n位有效数字，则相对误差
n1
1
10
x2
1
×≤
*
r
e；
2
0
若相对误差
n1
1
10
)1x(2
1
×
+
≤
*
r
e
，则x
*
至少具有n位有效数字。
相对误差与有效数字相对误差与有效数字
2004-10-25 zhwang@nwpu.edu.cn 26
误差度量间的联系(续)
null Remark
null 1、该定理实质上给出了一种求相对误差限的方法。
null 2、仅从并不能保证x
*
一定具有n
位有效数字。如设其近似值a=0.484，其相对误差为：
我们并不能由此断定a有两位有效数字，因为
n
r
x
e
×≤
1
1
*
10
2
1
4900.00229sin =
′
=
o
A
21
10
42
1
0125.0012397.0
484.0
484.04900.0
×
×
=<=
20
10
2
1
005.00060.0484.04900.0
×=>=?=? aA
2004-10-25 zhwang@nwpu.edu.cn 27
定理证明
o
1
nm
10
2
1
×
≤=
*
*
*
*
r
x
x
e
e
n1
1
nm
1
m
10
x2
1
10
x0102
1
×=×
××
≤
.
o
2
n21
mn1
1
xxx.01010
)1x(2
1
K×××
+
≤?=
**
r
*
xee
nm
1
n1m
1
10
2
1
1x010
1x2
1
+
×=+××
+
≤ ).(
)(
2004-10-25 zhwang@nwpu.edu.cn 28
例题1
为使
5=x
的近似值x
*
的相对误差不超过1%，问查开方表时至少要取几位有效数字？
设近似数x
*
保留n位有效数字可满足题设要求,解：
对于
5=x
，有x
1
=2,
依据定理1
o
有
n1n1
1
*
r
10
4
1
10
x2
1
e
×=×≤
令
01.010
4
1
n1
≤×
，解得
2.4n ≥
,取n=3位有效数字。
#
2004-10-25 zhwang@nwpu.edu.cn 29
3,初值误差传播
null概念：近似数参加运算后所得之值一般也是近似值，含有误差，将这一现象称为误差传播。
null误差传播的表现：
null算法本身可能有截断误差；
null初始数据在计算机内的浮点表示一般有舍入误差；
null每次运算一般又会产生新的舍入误差，并传播以前各步已经引入的误差；
null误差有正有负，误差积累的过程一般包含有误差增长和误差相消的过程，并非简单的单调增长；
null运算次数非常之多，不可能人为地跟踪每一步运算。
2004-10-25 zhwang@nwpu.edu.cn 30
初值误差传播（续）
null初值误差传播：假设每一步都是准确计算，即不考虑截断误差和由运算进一步引入的舍入误差，仅介绍初始数据的误差传播规律。
null研究方法：
null泰勒（Taylor）方法
null n元函数
null二元函数（算术运算）
null一元函数（计算函数值的条件数）
null区间分析法（工科研究生不要求）
2004-10-25 zhwang@nwpu.edu.cn 31
复习泰勒公式记点
),,,(
**
2
*
1 n
xxx L
为p
*
,点
),,,(
21 n
xxx L
为p，n元泰勒公式：
[ ]+?++?+= ))(())((
!1
1
)()(
*
*
*
11
*
1
*
nnn
xxpfxxpfpfpf L
[
]
L
L
L
L
+
+++
++++
+++?
2*
*
2
*
11
*
*
1
**
22
*
2
*
11
*
22
*
21
**
11
*
1
2*
11
*
11
))(())()((
))()(())()((
))()(())((
!2
1
nnnnnn
nnn
nnn
xxpfxxxxpf
xxxxpfxxxxpf
xxxxpfxxpf
2004-10-25 zhwang@nwpu.edu.cn 32
1）泰勒公式分析初值误差传播设n元可微函数
),,,(
n21
xxxfy L=
中的自变量x
1
、x
2
、…、
x
n
是相互独立的。
用自变量的近似值进行准确计算，得y
*
=
),,,(
***
n21
xxxf L
。
当
*
1
x
、
*
2
x
、…、
*
n
x
很好地近似了相应真值时，利用多元函数一阶Taylor公式求得
y
*
的绝对误差,
∑
=
≈?=
n
1i
i
*
i
*
n
*
1
'
i
**
))(,,()( xxxxfyyye L
∑
=
=
n
1i
*
i
*
n
*
1
'
i
)(),,( xexxf L
2004-10-25 zhwang@nwpu.edu.cn 33
泰勒方法（n元函数）
以及相对误差
∑
=
≈=
n
1i
*
i
*
i
*
n
*
1
'
i
*
*
i
*
*
*
)(
),,(
)(
)(
x
xe
xxf
y
x
y
ye
ye
r
L
∑
=
=
n
1i
*
i
*
n
*
1
'
i
*
*
i
)(),,( xexxf
y
x
r
L
进而得到如下绝对误差限和相对误差限传播关系：
∑
=
≈
<
n
1i
*
i
*
n
*
1
'
i
*
)(),,()( xxxfy εε L
∑
=
≈
<
n
1i
*
i
*
n
*
1
'
i
*
*
i
*
)(),,()( xxxf
y
x
y
rr
εε L
2004-10-25 zhwang@nwpu.edu.cn 34
泰勒方法（二元函数）
null二元函数算术运算误差传播规律
null绝对误差限null相对误差限
)()()(
*
2
*
1
*
2
*
1
xxxx εεε +≈±
)()()(
*
2
*
1
*
1
*
2
*
2
*
1
xxxxxx εεε +≈
)0(
)()(
)(
*
2
2
*
2
*
2
*
1
*
1
*
2
*
2
*
1
≠
+
≈
x
x
xxxx
x
x
εε
ε
)}(),({max)(
*
2
*
1
*
2
*
1
xxxx
rrr
εεε ≈+
)(
**
0
21
>xx
)()()(
*
2
*
1
*
2
*
1
xxxx
rrr
εεε +≈
)(
**
0
21
≠xx
)()()(
*
2
*
1
*
2
*
1
xx
x
x
rrr
εεε +≈
)(
**
0
21
≠xx
2004-10-25 zhwang@nwpu.edu.cn 35
泰勒方法（一元函数）
null Remark,对于具体的一组数据，上面给出的误差限传播公式是实际误差的一个粗糙偏大的估计,如对于加法运算的估计，它包括了误差源同号且同时均达到了误差限这一最坏的情况，实际情况往往并非这么坏.
null一元函数：y=f(x)
null绝对误差传播分析
null关系式推导由微分中值定理知
10 <θ<θ+=? ),))((()()(
**'*
xxxxxfxfxf
))((
*'
xxxf?≈
即有
)()())((
*'*
xexfxfe ≈
2004-10-25 zhwang@nwpu.edu.cn 36
泰勒方法（一元函数）（续1）
null讨论：当|f’(x)|<1时，函数值的扰动比自变量的微小变化还要小；而当|f’(x)|很大时，自变量的微小变化，将引起函数值较大的扰动，此时，称x是函数在绝对误差意义下的坏函数值点。
null定义绝对误差意义下的条件数：
)()(Cond
'
xff
a
=
null相对误差传播分析
关系式推导)(
)(
)(
)(
))((
))((
*
'*
*
xe
xf
xf
x
xf
xfe
xfe
rr
≈=
类似的讨论，可如下定义相对误差意义下的条件数：
)(
)(
)(Cond
'
xf
xf
xf
r
=
2004-10-25 zhwang@nwpu.edu.cn 37
泰勒方法（一元函数）（续2）
null条件数与误差传播的关系：
)()(Cond))((
**
xefxfe
a
≈
)()(Cond))((
**
xefxfe
rrr
≈
null结论：条件数是函数自身在一点处固有的特性,对于相同的自变量扰动，条件数越大，计算出的函数值误差越大,要提高函数值的计算精度，通常需要通过提高初值精度来实现.
2004-10-25 zhwang@nwpu.edu.cn 38
2）区间分析法分析初值误差传播
(工科硕士不要求)
知道初始数据的误差范围，我们可以用区间分析法分析初值误差的传播规律。
设],,[],,[
2211
baybax ∈∈
则有如下结论成立：
],,[
2121
bbaayx ++∈+
1
0
],,[
11
abx∈?
2
0
,0],1,1[1
1111
>∈ baabx
3
0
。},,,{],max,[min
21212121
bbabbaaayx =ΞΞΞ∈
4
0
2004-10-25 zhwang@nwpu.edu.cn 39
规定如下的区间运算规则：
],,[],[],[
21212211
bbaababa ++=+
1
0
],,[],[
1111
abba=?
2
0
,0],1,1[],[1
111111
>= baabba3
0
。]max,[min],[],[
2211
ΞΞ=× baba4
0
考虑到
,),(
1
y
xyxyxyx ×=÷?+=?
]),[(],[],[],[
22112211
babababa?+=?
],[
2121
abba=
5
0
2004-10-25 zhwang@nwpu.edu.cn 40
续
]),/[1(],[],/[],[
22112211
babababa ×=
6
0
0,
1
,
1
],[
22
22
11
>
×= ba
ab
ba
对于精确数p和近似数x之间的算术运算(代表加、
减、乘、除中任一种运算)有
],[],[
11
bappxp oo ∈
7
0
2004-10-25 zhwang@nwpu.edu.cn 41
三、舍入误差分析及数值稳定性
1.浮点数系
2.舍入误差的产生
3.舍入误差分析
4.数值稳定性
5.算法设计注意事项
2004-10-25 zhwang@nwpu.edu.cn 42
一浮点数系及其运算的舍入误差计算机中通常配置有两种类型的算术运算,
定点数运算和浮点数运算,所谓点是指小数点,
用浮点数进行计算是指用常数个数字进行工作;
而用定点数进行计算是指用常数个小数位数进行工作,这里我们仅介绍较多使用的浮点数系及其运算的舍入误差.
2004-10-25 zhwang@nwpu.edu.cn 43
1 浮点数系以及舍入误差的产生一个浮点数的表示由正负号、小数形式的尾数、以及确定小数点位置的阶三部分组成,单精度实数用32位的二进制数据表示浮点数的这三个信息,其中数值符号占1位,尾数占23位,
阶数占8位.
对于规范化的浮点数（除零外）,23位的二进制尾数形式是,
() },1,0{,221.0
i
i
23
2i
i
1
2
2332
∈+=
=
∑
ααααα L
2004-10-25 zhwang@nwpu.edu.cn 44
浮点数系以及舍入误差的产生（续）
式中表示尾数中小数点后第i位的权,当尾数的首位小于5时,可通过不断乘以2使之首位大于或等于5,相应的二进制阶数需要减去乘以2的次数,
在8位的阶数中,有1位表示阶数的符号,7位表示二进制的阶数数值,于是阶数数值的范围是
,
i
2
12~0
7
单精度实数集合为,
≤∈?
+±=∪=
=
∑
12,222}0{
7i
23
2i
i
1
pZpaaR
p
S
且α
2004-10-25 zhwang@nwpu.edu.cn 45
浮点数系以及舍入误差的产生（续）
其中元素是能够准确表示的数,称之为机器数,
设,与之相邻的能够准确表示的机器数是和,这样,在区间和上的实数无法准确表示,
S
Ra∈
23
2
+=
p
ab
23
2
=
p
ac
),( ac
),( ba
规定,不能精确表示的实数用与之最近的机器数表示,我们将实数在机器中的浮点(float)表示记为,
)(xfl
2004-10-25 zhwang@nwpu.edu.cn 46
浮点数系以及舍入误差的产生（续）
将由此表示产生的误差称之为舍入误差,xxfl?)(
如当
)2,2[
2
,
2
231231
+?=
++
∈
pp
aa
baac
x
时用表示,即有,
axfl =)(
相对误差满足:
*
r
e
923.623
1
231
*
102
2
2
)(
)(
≈=≤
=
p
p
r
xfl
xxfl
e
二进制阶数数值上限相应于十进制的阶数数值上限是38 除零外,单精度实数的量级不大于不小于.
12
7
)23.382lg)12((
7
≈?
38
10
30
10
2004-10-25 zhwang@nwpu.edu.cn 47
浮点数系以及舍入误差的产生（续）
设在某一浮点系统中,尾数占位二进制数(未计算尾数的符号位),阶数占位二进制数(未计算阶数的符号位),实数的浮点表示共需要位的二进制数位,
t
s
x
)(xfl
2++st
2004-10-25 zhwang@nwpu.edu.cn 48
浮点数系以及舍入误差的产生（续）
当不出现溢出时,相对误差和绝对误差分别满足如下估计,
*
r
e
*
e
tt
r
xfl
xxfl
e
=?≤
= 22
2
1
)(
)(
1*
tp
xxfle
≤?= 22)(
1*
由确定.上溢界和下溢界分别是和,对于单精度实数有,,
p
pp
x 22
1
<≤
2lg)12(12
102
=
ss
2lg22
102
ss
=
23=t
7=s
2004-10-25 zhwang@nwpu.edu.cn 49
2 浮点运算舍入误差分析设实数满足且,
则的浮点表示满足
x
pp
x 22
1
<≤
12?≤
s
p
x
)(xfl
t
xxfl
≤+= 2),1()( δδ
其中,分别为浮点系统中给二进制阶数数值以及尾数数值的表示所分配的二进制数位.
s t
2004-10-25 zhwang@nwpu.edu.cn 50
浮点运算舍入误差分析（续）
设,则有,进而由式(1.18)得
)1()( δ+= xxfl
x
xxfl?
=
)(
δ
t
p
tp
x
xxfl
=≤
= 2
2
2)(
1
1
δ
用符号表示加减乘除四种算术运算之一
。
t
yflxflyflxflfl
≤+= 2),1))(()(())()(( δδoo
2004-10-25 zhwang@nwpu.edu.cn 51
浮点运算舍入误差分析（续）
例1.6 对三同号数的算术运算作舍入误差分析.
cba ++
解这里对运算作误差分析,
cba ++ )(
)1))(()(())()((
3
δ++=+ bflaflbflaflfl
),1))(1()1((
321
δδδ ++++= ba
))())()((( cflbflaflflfl ++
2004-10-25 zhwang@nwpu.edu.cn 52
浮点运算舍入误差分析（续）
)1)}(())()(({
5
δ+++= cflbflaflfl
)1)}(1()1)](1()1({[
54321
δδδδδ +++++++= cba
++++++++++= )(
531535153131
δδδδδδδδδδδδacba
)(
532535253232
δδδδδδδδδδδδ +++++++b
)(
5454
δδδδ +++c
。5,4,3,2,1,2 =≤≤
i
t
i
εδ
设于是得到
)())())()((( cbacflbflaflflfl ++?++
( )。)2()33(
232
εεεεε +++++≤ cba
2004-10-25 zhwang@nwpu.edu.cn 53
浮点运算舍入误差分析（续）
表明:数学上等价的算法在数值上并不总是等效的.
这种将误差估计转化为原始数据摄动的方法,称之为向后误差分析法.
这种将误差估计转化为原始数据摄动的方法,称之为向后误差分析法.
通常的思路,对每一步找出舍入误差界,随着计算过程逐步向前分析,直到估计出最后结果的误差界,这一方法称之为向前误差分析法,
2004-10-25 zhwang@nwpu.edu.cn 54
3,数值稳定性
null定义：一个算法,如果在运算过程中舍入误差在一定条件下能够得到控制,或者舍入误差的增长不影响产生可靠的结果,则称该算法是数值稳定的,否则称其为数值不稳定.
dx
x
x
I
n
n
∫
+
=
1
0
5
null例：计算如下积分近似值的两种方案比较
),,( L215
1
1
=?=
nI
n
I
nn
null方法1：
1823.0
5
6
ln
5
1
1
0
0
≈=
+
=
∫
dx
x
I
2004-10-25 zhwang@nwpu.edu.cn 55
n
方法1计算结果
n
*
n
I
nn
II?
*
0 0.1823 0.00002
1 0.0885 0.0001
2 0.0575 0.0005
3 0.0458 0.0027
4 0.0208 0.0135
5 0.0958 0.0673
6 －0.3125 0.3368
7 1.7054 1.6842
8 －8.4018 8.4206
9 42.1200 42.1031
10 －210.5002 210.5156
2004-10-25 zhwang@nwpu.edu.cn 56
方法一结果分析
null 方法一分析：计算结果表明,舍入误差的传播近似依5
的幂次进行增长,因而是一种不稳定的方法.
*
1
*
5
2
1
=
nn
II
1
5
2
1
=
nn
II
*
0
*
2
2*
1
*
555 eeee
n
nnn
===
null方法二：
55
1
*
*
1
n
n
I
n
I?=
55
1
1
n
n
I
n
I?=
*
5
1
*
1 nn
ee =
由此分析知，该方法是稳定的。关于初值的近似可由下面式子得到：
)1(5
1
56)1(6
1
1
0
1
0
+
=≤≤=
+
∫∫
n
dx
x
Idx
x
n
n
n
n
2004-10-25 zhwang@nwpu.edu.cn 57
方法2计算结果
n
*
n
I
nn
II?
*
0 0.1823 0.2156
×
10
-6
1 0.0884 0.7784
×
10
-7
2 0.0580 0.3892
×
10
-6
3 0.0431 0.3873
×
10
-6
4 0.0343 0.6330
×
10
-7
5 0.0285 0.3165
×
10
-6
6 0.0243 0.2491
×
10
-6
7 0.0212 0.3262
×
10
-6
8 0.0189 0.6308
×
10
-6
9 0.0167 0.2265
×
10
-5
10 0.0167 0.1332
×
10
-4
01670
66
1
55
1
2
1
10
.
*
≈
+=I
2004-10-25 zhwang@nwpu.edu.cn 58
4.算法设计注意的问题
null相近数相减的误差传播
null例x=52.127 x*=52.129 四位有效数字
y=52.123 y*=52.121 四位有效数字
A=x-y=0.004 A*=x*-y*=0.008 零位有效数字
null结论：避免相近数相减
null一些避免相近数相减示例
当|x|>>1时
x
x
xx
1
lnln)1ln(
+
=?+
)( 1
1
1
11
+
=
+
xxxx
2004-10-25 zhwang@nwpu.edu.cn 59
算法设计注意的问题(续1)
xx
xx
++
=?+
1
1
1 )1ln()1ln(
22
+?= xxxx
当|x|<<1时
2
2
2
11
11
x
x
x
+
=
L?+?=?
53
arctan
53
xx
xx
L+?=?
!5!3
sin
53
xx
xx
2004-10-25 zhwang@nwpu.edu.cn 60
算法设计注意的问题(续2)
null合理安排量级相差很大的数之间的运算次序,尽可能避免大数“吃掉”小数。
null例
)10(987654321
1000000
1
≤<+
∑
=
k
k
k
δδ
null简化计算步骤以减少运算次数。
842
84228448816
3*3*3*3*3
3*3*3*33*3*33*33
=
===
null例1
2004-10-25 zhwang@nwpu.edu.cn 61
算法设计注意的问题(续3)
null例2 秦九韶算法
01
2
2
3
3
4
4
axaxaxaxa ++++
01234
)))((( axaxaxaxa ++++=
null尽可能避免绝对值很小的数做分母，防止出现溢出。
null选用数值稳定性好的算法。
2004-10-25 zhwang@nwpu.edu.cn 62
总之,除了算法的正确性之外,在算法设计中至少还应注意如下几个方面的问题:
1 尽量避免两个相近的近似数相减;
2 合理安排量级相差很大的数之间的运算次序,防止大数"吃掉"小数;
3 尽可能避免绝对值很小的数做分母;
4 防止出现溢出;
5 简化计算步骤以减少运算次数;
6 选用数值稳定性好的算法.
