上一页 下一页1
数值分析文立平
Lpwen@xtu.edu.cn
数学与计算科学学院 303室上一页 下一页2
第一章 引论上一页 下一页3
计算不仅仅只是作为验证理论模型的正确性的手段,大量的事实表明它已成为重大科学发现的一种重要手段 。
科学计算与实验,理论 三足鼎立,相辅相成,
成为当今科学活动的 三大方法 。
石钟慈：
,第三种科学方法 ----计算机时代的科学计算,
（ 2000）
上一页 下一页4
1.1 数值计算方法
1,数学的一个分支、数学与其它应用学科的桥梁；
2,其它学科发展迫切需要进行数值计算与仿真 ;
科学计算 已成为平行于 理论分析 和 科学实验 的第三种科学研究手段。
§ 1 数值计算方法及其主要内容
3．计算机软、硬件的发展为数值方法的实现提供环境，也促进它的快速发展。
上一页 下一页5
上一页 下一页6
数值分析输入复杂问题或运算
.,,,,,),(,)(
,,ln,,
xf
dx
ddxxf
bxAxax
b
a
x
计算机近似解上一页 下一页7
1.2 主要内容函数的插值与逼近；
数值积分与数值微分；
非线性方程的数值解法；
矩阵的特征值问题的计算；
常微分方程数值解法,
线性代数方程组的解法；
上一页 下一页8
举例,（ 1）求 的正实根；29 s inxx?
（ 2）求一阶微分方程初值问题：
(,),( 0 ) 1dy f x y ydx
的解，其中,2(,) s i n 9f x y x x
上一页 下一页9
（ 3）解线性代数方程组：
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
nn
nn
n n n n n n
a x a x a x b
a x a x a x b
a x a x a x b
（ 4）求积分,1
0
sin x dx
x?
上一页 下一页10
2.1 来源与分类 /* Source & Classification */
从实际问题中抽象出数学模型
—— 模型误差 /* Modeling Error */
通过测量得到模型中参数的值
—— 观测误差 /* Measurement Error */
求近似解 —— 方法误差 (截断误差 /* Truncation Error */ )
机器字长有限 —— 舍入误差 /* Roundoff Error */
§ 2 误差的基本概念上一页 下一页11
dxe x10 2 近似计算:例大家一起猜？
dxe 2x10
11 / e
解法之一,将 作 Taylor展开后再积分2xe?
9
1
!4
1
7
1
!3
1
5
1
!2
1
3
1
1
)
!4!3!2
1(
1
0
864
21
0
dx
xxx
xdxe
2x
S4 R4 /* Remainder */
,10 4 Sdxe 2x取则
11
1
!5
1
9
1
!4
1
4R
称为 截断误差 /* Truncation Error */
005091!414,R这里
7 4 300 2 40103 3 3014211013114,...S
0010200050,,| 舍入误差 /* Roundoff Error */ |
00600010005010 2,..dxe -x 的总体误差计算
≈ 0.743
由截去部分
/* excluded terms */
引起由留下部分
/* included terms */
引起上一页 下一页12
2.2 误差与有效数字 /* Error and Significant Digits */
绝对误差 /* absolute error */
xxe ** 其中 x为精确值,x*为 x的近似值。
|| *e *ε
10 006074302,.dxe x** εxx,例如：工程上常记为
，称为 绝对误差限 /* accuracy */，的上限记为注,e* 理论上讲是唯一确定的,可能取正,也可能取负。
e 0 不唯一,当然 e? 越小越具有参考价值。
上一页 下一页13
相对误差 /* relative error */
x
ee
r
**?
|| *
*
*
x
εε
r?
x 的 相对误差上限 /* relative accuracy */ 定义为注：从 的定义可见,实际上被 偷换 成了,而后才考察其上限。那么这样的偷换是否 合法？
严格的说法是,与 是否反映了 同一数量级 的误差？
关于此问题的详细讨论可见教材第 6-7页。
*re
*re *
*
xe
xe
*
*
*
xe
上一页 下一页14
有效数字 /* significant digits */
用科学计数法，记 （其中 ）。若
（即 的截取按四舍五入规则），则称为有 n 位有效数字，精确到 。
mnaa.ax 100 21* 01?a
nm.xx 1050|| * na
*x nm?10
1 4 1 5.3*;8 9 7 9 3 21 4 1 5 9 2 6 5 3 5.3例：
问,有几位有效数字？请证明你的结论。*?
*
10501050*a n d
10314150
413
1
,.π|| π
,.π*?
证明：
有 位有效数字，精确到小数点后第 位。4 3
注,0.2300有 4位有效数字，而 00023只有 2位有效。 12300如果写成 0.123?105，则表示只有 3位有效数字。
数字末尾的 0不可随意省去！
上一页 下一页15
有效数字与相对误差的关系
有效数字?相对误差限
1
1
121
10
2
1
02
10
100
1050
*
n
n
m
n
nm
r
a
.aaa.a
.
x*
ε*
ε
已知 x* 有 n 位 有效数字,则其 相对误差限 为
相对误差限?有效数字
nmm
n
m
n
r
.a
a
a.a
a
xεxx
105010)1(
)1(2
10
100
)1(2
10
|*|*|*|
1
1
1
1
21
1
1
1
1
10)1(2 1* nr aε已知 x* 的 相对误差限 可写为则可见 x* 至少 有 n 位 有效数字 。
上一页 下一页16
例：为使 的相对误差小于 0.001%,至少应取几位有效数字？*π
解：假设?* 取到 n 位有效数字，则其相对误差上限为
1
1
102 1* nr aε
要保证其相对误差小于 0.001%，只要保证其上限满足
%0 0 1.0102 1* 1
1
nr aε
已知 a1 = 3，则从以上不等式可解得 n > 6? log6，即
n? 6，应取?* = 3.14159。
上一页 下一页17
2.3 函数的误差估计 /*Error Estimation for Functions*/
问题,对于 y = f (x)，若用 x* 取代 x，将对 y 产生什么影响？
分析,e*(y) = f (x*)? f (x) e*(x) = x*? xMean Value Theorem
= f ’(? )(x*? x)
x* 与 x 非常接近时，可认为 f ’(? )? f ’(x*),则有：
|e*(y)|? | f ’(x*)|·|e*(x)|
即,x*产生的误差经过 f 作用后被放大 /缩小了 | f ’(x*)|
倍。故称 | f ’(x*)|为 放大因子 /* amplification factor */ 或绝对条件数 /* absolute condition number */.
上一页 下一页18
*)(
)(*|)(|
xf
yey*e
r? *
)(*|)(|
x
xex*e
r?
)(*
*)(
*)(*
*
*
*)(
*
*
)(*)(
xe
xf
xfx
x
xx
xf
x
xx
xfxf
r?
相对误差条件数
/* relative condition number*/
f 的条件数在某一点是 小 \大,则称 f 在该点是 好条件的
/* well-conditioned */ \坏条件的 /* ill-conditioned */。
注：关于多元函数 的讨论，请参阅教材第 9-11页。
)...,( 21 nx,x,xfy?
上一页 下一页19
例,计算 y = ln x。若 x? 20，则取 x 的几位有效数字可保证
y 的相对误差 < 0.1%?
*ln
|)(*||)(*|
*)(
*)(*|)(|
x
xexe
xy
xyxy*e r
rr
解：设截取 n 位有效数字后得 x*? x，则估计 x 和 y 的相对误差上限满足近似关系
)(**ln)(* yxx rr ee
%1.0*ln102 1 1
1
xa n
不知道怎么办啊？
x 可能是 20.#，也可能是 19.#，取最坏情况，
即 a1 = 1。
n? 4
例：计算,取 4 位有效，即,则相对误差
9820ln )8920ln(,
%..
.
101002
9
820ln
9
820ln8920ln
5
上一页 下一页20
几点注意事项 /* Remarks */
1,避免相近二数相减 (详细分析请参阅教材 p.9-10)
例,a1 = 0.12345,a2 = 0.12346，各有 5位有效数字。
而 a2? a1 = 0.00001，只剩下 1位有效数字。
几种经验性避免方法：;xεx εxεx ;1lnlnln xεxεx
当 | x | << 1 时：;2s i n2c o s1 2 xx
,..612111 2xxxe x
上一页 下一页21
2,避免小分母,分母小会造成浮点溢出 /* over flow */
3,避免大数 吃 小数例：用单精度计算 的根。 010)110(
992 xx
精确解为
110 291 x,x
算法 1,利用求根公式
a
acbbx
2
42
在计算机内,109存为 0.1?1010,1存为 0.1?101。 做加法时，
两加数的指数先向大指数对齐，再将浮点部分相加。即 1
的指数部分须变为 1010，则,1 = 0.0000000001? 1010，取单精度时就成为：
109+1=0.10000000?1010+0.00000000?1010=0.10000000?1010
大数 吃 小数
02 4,102 4
2
2
9
2
1?
a
acbbx
a
acbbx
上一页 下一页22
算法 2,先解出再利用
9
2
1 102
4)(
a
acbbs i g nbx
11010 9
9
1
221 xa
cx
a
cxx
注,求和时 从小到大 相加，可使和的误差减小。
例：按从小到大、以及从大到小的顺序分别计算
1 + 2 + 3 + … + 40 + 10 9
4,先化简再计算，减少步骤，避免误差积累。
一般来说，计算机处理下列运算的速度为e x p,,
上一页 下一页23
§ 3 算法的数值稳定性一个算法，如果在执行它的过程中舍入误差在一定条件下可以得到控制（或者说初始误差和舍入误差的增长不影响产生可靠的结果）,则称它是数值稳定的，否则称该算法数值不稳定,
上一页 下一页24
传播与积累 /* Spread & Accumulation */
例,蝴蝶效应 —— 纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！
NY BJ
以上是一个 病态问题 /* ill-posed problem*/
关于本身是病态的问题，我们还是留给数学家去头痛吧！
上一页 下一页25
.,,,,,2101 10,,,n,dxexeI xnn
例：计算
11 nn InI
公式一：
注意此公式 精确 成立
632120560111 100,edxeeI x
记为
*0I
8000 1050,IIE则初始误差
1
1
1
111 11
0
01
0 nI)e ( ndxexeIdxexe n
n
n
n
3 9 1 41 4 2 3151
9 5 9 4 2 494141
2 2 7 6 4 8 07131
6 3 2 8 9 6 0 00121
0 3 0 5 9 2 0 00111
0 8 8 1 2 8 0 00101
............
3 6 7 8 7 9 4 4011
1415
*
13
*
14
*
12
*
13
*
11
*
12
*
10
*
11
*
9
*
10
*
0
*
1
.II
.II
.II
.II
.II
.I
.II
!
! !
What
happened
!
上一页 下一页26
考察第 n步的误差 nE
|)1()1(||||| * 11* nnnnn nInIIIE ||! 01 En||En n
我们有责任改变。
造成这种情况的是 不稳定的算法 /* unstable algorithm */
迅速积累，误差呈递增走势。可见初始的小扰动 8
0 1050||,E
)1(11 11 nnnn InIInI 公式二：
注意此公式与公式一在理论上 等价 。
方法：先估计一个 IN,再反推要求的 In ( n << N )。
1
1
)1(
1
NINe N?
NN INNeI
1
1
)1(
1
2
1*可取
0* NNN IIEN,时当上一页 下一页27
6 3 2 1 2 0 5 60)1(
1
1
3 6 7 8 7 9 4 40)1(
2
1
0 8 3 8 7 7 1 1 50)1(
11
1
0 7 7 3 5 1 7 3 20)1(
12
1
0 7 1 7 7 9 2 1 40)1(
13
1
0 6 6 8 7 0 2 2 00)1(
14
1
0 6 3 8 1 6 9 1 80)1(
15
1
0 4 2 7 4 6 2 3 30
16
1
16
1
2
1
*
1
*
0
*
2
*
1
*
11
*
10
*
12
*
11
*
13
*
12
*
14
*
13
*
15
*
14
*
15
.II
.II
.II
.II
.II
.II
.II
.
e
I
取
We just got lucky?
上一页 下一页28
考察反推一步的误差：
||1)1(1)1(1|| *1 NNNN ENININE
以此类推，对 n < N 有：
||)1(...)1( 1|| Nn EnNNE
误差逐步递减,这样的算法称为 稳定的算法 /* stable algorithm */
在我们今后的讨论中,误差 将不可回避，
算法的 稳定性 会是一个非常重要的话题。
数值分析文立平
Lpwen@xtu.edu.cn
数学与计算科学学院 303室上一页 下一页2
第一章 引论上一页 下一页3
计算不仅仅只是作为验证理论模型的正确性的手段,大量的事实表明它已成为重大科学发现的一种重要手段 。
科学计算与实验,理论 三足鼎立,相辅相成,
成为当今科学活动的 三大方法 。
石钟慈：
,第三种科学方法 ----计算机时代的科学计算,
（ 2000）
上一页 下一页4
1.1 数值计算方法
1,数学的一个分支、数学与其它应用学科的桥梁；
2,其它学科发展迫切需要进行数值计算与仿真 ;
科学计算 已成为平行于 理论分析 和 科学实验 的第三种科学研究手段。
§ 1 数值计算方法及其主要内容
3．计算机软、硬件的发展为数值方法的实现提供环境，也促进它的快速发展。
上一页 下一页5
上一页 下一页6
数值分析输入复杂问题或运算
.,,,,,),(,)(
,,ln,,
xf
dx
ddxxf
bxAxax
b
a
x
计算机近似解上一页 下一页7
1.2 主要内容函数的插值与逼近；
数值积分与数值微分；
非线性方程的数值解法；
矩阵的特征值问题的计算；
常微分方程数值解法,
线性代数方程组的解法；
上一页 下一页8
举例,（ 1）求 的正实根；29 s inxx?
（ 2）求一阶微分方程初值问题：
(,),( 0 ) 1dy f x y ydx
的解，其中,2(,) s i n 9f x y x x
上一页 下一页9
（ 3）解线性代数方程组：
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
nn
nn
n n n n n n
a x a x a x b
a x a x a x b
a x a x a x b
（ 4）求积分,1
0
sin x dx
x?
上一页 下一页10
2.1 来源与分类 /* Source & Classification */
从实际问题中抽象出数学模型
—— 模型误差 /* Modeling Error */
通过测量得到模型中参数的值
—— 观测误差 /* Measurement Error */
求近似解 —— 方法误差 (截断误差 /* Truncation Error */ )
机器字长有限 —— 舍入误差 /* Roundoff Error */
§ 2 误差的基本概念上一页 下一页11
dxe x10 2 近似计算:例大家一起猜？
dxe 2x10
11 / e
解法之一,将 作 Taylor展开后再积分2xe?
9
1
!4
1
7
1
!3
1
5
1
!2
1
3
1
1
)
!4!3!2
1(
1
0
864
21
0
dx
xxx
xdxe
2x
S4 R4 /* Remainder */
,10 4 Sdxe 2x取则
11
1
!5
1
9
1
!4
1
4R
称为 截断误差 /* Truncation Error */
005091!414,R这里
7 4 300 2 40103 3 3014211013114,...S
0010200050,,| 舍入误差 /* Roundoff Error */ |
00600010005010 2,..dxe -x 的总体误差计算
≈ 0.743
由截去部分
/* excluded terms */
引起由留下部分
/* included terms */
引起上一页 下一页12
2.2 误差与有效数字 /* Error and Significant Digits */
绝对误差 /* absolute error */
xxe ** 其中 x为精确值,x*为 x的近似值。
|| *e *ε
10 006074302,.dxe x** εxx,例如：工程上常记为
，称为 绝对误差限 /* accuracy */，的上限记为注,e* 理论上讲是唯一确定的,可能取正,也可能取负。
e 0 不唯一,当然 e? 越小越具有参考价值。
上一页 下一页13
相对误差 /* relative error */
x
ee
r
**?
|| *
*
*
x
εε
r?
x 的 相对误差上限 /* relative accuracy */ 定义为注：从 的定义可见,实际上被 偷换 成了,而后才考察其上限。那么这样的偷换是否 合法？
严格的说法是,与 是否反映了 同一数量级 的误差？
关于此问题的详细讨论可见教材第 6-7页。
*re
*re *
*
xe
xe
*
*
*
xe
上一页 下一页14
有效数字 /* significant digits */
用科学计数法，记 （其中 ）。若
（即 的截取按四舍五入规则），则称为有 n 位有效数字，精确到 。
mnaa.ax 100 21* 01?a
nm.xx 1050|| * na
*x nm?10
1 4 1 5.3*;8 9 7 9 3 21 4 1 5 9 2 6 5 3 5.3例：
问,有几位有效数字？请证明你的结论。*?
*
10501050*a n d
10314150
413
1
,.π|| π
,.π*?
证明：
有 位有效数字，精确到小数点后第 位。4 3
注,0.2300有 4位有效数字，而 00023只有 2位有效。 12300如果写成 0.123?105，则表示只有 3位有效数字。
数字末尾的 0不可随意省去！
上一页 下一页15
有效数字与相对误差的关系
有效数字?相对误差限
1
1
121
10
2
1
02
10
100
1050
*
n
n
m
n
nm
r
a
.aaa.a
.
x*
ε*
ε
已知 x* 有 n 位 有效数字,则其 相对误差限 为
相对误差限?有效数字
nmm
n
m
n
r
.a
a
a.a
a
xεxx
105010)1(
)1(2
10
100
)1(2
10
|*|*|*|
1
1
1
1
21
1
1
1
1
10)1(2 1* nr aε已知 x* 的 相对误差限 可写为则可见 x* 至少 有 n 位 有效数字 。
上一页 下一页16
例：为使 的相对误差小于 0.001%,至少应取几位有效数字？*π
解：假设?* 取到 n 位有效数字，则其相对误差上限为
1
1
102 1* nr aε
要保证其相对误差小于 0.001%，只要保证其上限满足
%0 0 1.0102 1* 1
1
nr aε
已知 a1 = 3，则从以上不等式可解得 n > 6? log6，即
n? 6，应取?* = 3.14159。
上一页 下一页17
2.3 函数的误差估计 /*Error Estimation for Functions*/
问题,对于 y = f (x)，若用 x* 取代 x，将对 y 产生什么影响？
分析,e*(y) = f (x*)? f (x) e*(x) = x*? xMean Value Theorem
= f ’(? )(x*? x)
x* 与 x 非常接近时，可认为 f ’(? )? f ’(x*),则有：
|e*(y)|? | f ’(x*)|·|e*(x)|
即,x*产生的误差经过 f 作用后被放大 /缩小了 | f ’(x*)|
倍。故称 | f ’(x*)|为 放大因子 /* amplification factor */ 或绝对条件数 /* absolute condition number */.
上一页 下一页18
*)(
)(*|)(|
xf
yey*e
r? *
)(*|)(|
x
xex*e
r?
)(*
*)(
*)(*
*
*
*)(
*
*
)(*)(
xe
xf
xfx
x
xx
xf
x
xx
xfxf
r?
相对误差条件数
/* relative condition number*/
f 的条件数在某一点是 小 \大,则称 f 在该点是 好条件的
/* well-conditioned */ \坏条件的 /* ill-conditioned */。
注：关于多元函数 的讨论，请参阅教材第 9-11页。
)...,( 21 nx,x,xfy?
上一页 下一页19
例,计算 y = ln x。若 x? 20，则取 x 的几位有效数字可保证
y 的相对误差 < 0.1%?
*ln
|)(*||)(*|
*)(
*)(*|)(|
x
xexe
xy
xyxy*e r
rr
解：设截取 n 位有效数字后得 x*? x，则估计 x 和 y 的相对误差上限满足近似关系
)(**ln)(* yxx rr ee
%1.0*ln102 1 1
1
xa n
不知道怎么办啊？
x 可能是 20.#，也可能是 19.#，取最坏情况，
即 a1 = 1。
n? 4
例：计算,取 4 位有效，即,则相对误差
9820ln )8920ln(,
%..
.
101002
9
820ln
9
820ln8920ln
5
上一页 下一页20
几点注意事项 /* Remarks */
1,避免相近二数相减 (详细分析请参阅教材 p.9-10)
例,a1 = 0.12345,a2 = 0.12346，各有 5位有效数字。
而 a2? a1 = 0.00001，只剩下 1位有效数字。
几种经验性避免方法：;xεx εxεx ;1lnlnln xεxεx
当 | x | << 1 时：;2s i n2c o s1 2 xx
,..612111 2xxxe x
上一页 下一页21
2,避免小分母,分母小会造成浮点溢出 /* over flow */
3,避免大数 吃 小数例：用单精度计算 的根。 010)110(
992 xx
精确解为
110 291 x,x
算法 1,利用求根公式
a
acbbx
2
42
在计算机内,109存为 0.1?1010,1存为 0.1?101。 做加法时，
两加数的指数先向大指数对齐，再将浮点部分相加。即 1
的指数部分须变为 1010，则,1 = 0.0000000001? 1010，取单精度时就成为：
109+1=0.10000000?1010+0.00000000?1010=0.10000000?1010
大数 吃 小数
02 4,102 4
2
2
9
2
1?
a
acbbx
a
acbbx
上一页 下一页22
算法 2,先解出再利用
9
2
1 102
4)(
a
acbbs i g nbx
11010 9
9
1
221 xa
cx
a
cxx
注,求和时 从小到大 相加，可使和的误差减小。
例：按从小到大、以及从大到小的顺序分别计算
1 + 2 + 3 + … + 40 + 10 9
4,先化简再计算，减少步骤，避免误差积累。
一般来说，计算机处理下列运算的速度为e x p,,
上一页 下一页23
§ 3 算法的数值稳定性一个算法，如果在执行它的过程中舍入误差在一定条件下可以得到控制（或者说初始误差和舍入误差的增长不影响产生可靠的结果）,则称它是数值稳定的，否则称该算法数值不稳定,
上一页 下一页24
传播与积累 /* Spread & Accumulation */
例,蝴蝶效应 —— 纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！
NY BJ
以上是一个 病态问题 /* ill-posed problem*/
关于本身是病态的问题，我们还是留给数学家去头痛吧！
上一页 下一页25
.,,,,,2101 10,,,n,dxexeI xnn
例：计算
11 nn InI
公式一：
注意此公式 精确 成立
632120560111 100,edxeeI x
记为
*0I
8000 1050,IIE则初始误差
1
1
1
111 11
0
01
0 nI)e ( ndxexeIdxexe n
n
n
n
3 9 1 41 4 2 3151
9 5 9 4 2 494141
2 2 7 6 4 8 07131
6 3 2 8 9 6 0 00121
0 3 0 5 9 2 0 00111
0 8 8 1 2 8 0 00101
............
3 6 7 8 7 9 4 4011
1415
*
13
*
14
*
12
*
13
*
11
*
12
*
10
*
11
*
9
*
10
*
0
*
1
.II
.II
.II
.II
.II
.I
.II
!
! !
What
happened
!
上一页 下一页26
考察第 n步的误差 nE
|)1()1(||||| * 11* nnnnn nInIIIE ||! 01 En||En n
我们有责任改变。
造成这种情况的是 不稳定的算法 /* unstable algorithm */
迅速积累，误差呈递增走势。可见初始的小扰动 8
0 1050||,E
)1(11 11 nnnn InIInI 公式二：
注意此公式与公式一在理论上 等价 。
方法：先估计一个 IN,再反推要求的 In ( n << N )。
1
1
)1(
1
NINe N?
NN INNeI
1
1
)1(
1
2
1*可取
0* NNN IIEN,时当上一页 下一页27
6 3 2 1 2 0 5 60)1(
1
1
3 6 7 8 7 9 4 40)1(
2
1
0 8 3 8 7 7 1 1 50)1(
11
1
0 7 7 3 5 1 7 3 20)1(
12
1
0 7 1 7 7 9 2 1 40)1(
13
1
0 6 6 8 7 0 2 2 00)1(
14
1
0 6 3 8 1 6 9 1 80)1(
15
1
0 4 2 7 4 6 2 3 30
16
1
16
1
2
1
*
1
*
0
*
2
*
1
*
11
*
10
*
12
*
11
*
13
*
12
*
14
*
13
*
15
*
14
*
15
.II
.II
.II
.II
.II
.II
.II
.
e
I
取
We just got lucky?
上一页 下一页28
考察反推一步的误差：
||1)1(1)1(1|| *1 NNNN ENININE
以此类推，对 n < N 有：
||)1(...)1( 1|| Nn EnNNE
误差逐步递减,这样的算法称为 稳定的算法 /* stable algorithm */
在我们今后的讨论中,误差 将不可回避，
算法的 稳定性 会是一个非常重要的话题。
