第1章引论
[教学目的与要求]
1．了解什么是数值计算及数值计算的主要研究内容，理解科学计算解题过程；
2．理解误差的来源，掌握误差、绝对误差、绝对误差限、相对误差、相对误差限、有效数字的定义；
3．掌握有效数字的判定方法，有效数字与绝对误差限和相对误差限的关系；
4．掌握运算中误差分析。
5．理解算法的基本概念，数值型算法的特点，理解算法设计的基本方法，掌握数值型算法的稳定性。
[重点与难点]
重点：误差、绝对误差、绝对误差限、有效数字、相对误差、相对误差限的定义。
难点：有效数字的判定方法，有效数字与绝对误差限和相对误差限的关系。
[教学安排]
[授课内容]
1.1计算机数值方法的研究对象与特点
一、科学计算解题过程
二、计算机数值方法的研究对象
数值计算是研究解决数学问题的数值近似解方法，是在计算机上使用的解数学问题的方法之一。
三、计算机数值方法的特点
1、面向计算机，要根据计算机特点提供实际有效的算法。即算法只能包括加、减、乘、除运算和逻辑运算，是计算机能直接处理的。
2、可靠的理论分析，能任意逼近并达到精度要求，对近似算法要保证收敛性和数值稳
定性，还要对误差进行分析。
3、好的算法复杂度。
1.2课程的基本内容
1、误差分析
2、解线性方程组与非线性方程
3、插值法
4、数值积分
5、常微分方程的数值解
1.3数值算法及其设计
一、算法的基本概念
算法：解题方案和步骤的准确而完整的描述
特征：
1、能行性：每一步骤能够有效的执行并达到预期目的；
2、确定性：每一步骤必须是明确定义，不允许摸棱两可；
3、有穷性：有限个操作步骤；
4、拥有足够的情报：执行算法所必须的信息。
二、算法的描述
1、自然语言
2、流程图
3、伪语言
4、程序
例：方程求根f(x)=0
定理：设函数f (x)在区间[a, b]上连续，如果f (a) f (b) < 0，则方程f (x) = 0在[a, b]内至少有一实根x*。
二分法：
基本思想：将方程根所在的区间平分为两个小区间，再判断根属于哪个小区间；把有根的小区间再平分为二，再判断根所在的更小的区间，对分；重复这一过程，最后求出所要的近似值。
注意问题：如何确定近似根是否满足精度要求。
算法：
三、算法设计的基本方法
1、列举法
基本思想：根据问题，列出所有可能情况，并用问题中给定的条件检验那些是需要的，那些是不需要的。常用于解决“是否存在”或“有多少种可能”的问题。
例：百钱买百鸡问题
2、递推法
基本思想：从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已给定，或是通过问题的分析与化简而得到确定。
例：兔子繁殖问题（Fibonacci数列）
3、递归
基本思想：将问题逐层分解，转化为一个与原问题相似的规模较小的问题来求解，再沿原分解的逆过程逐步进行综合，最终获得原问题的解。
例：汉诺塔问题
4、减半递推技术
基本思想：所谓“减半”，是指将问题的规模减半，而问题的性质不变。所谓“递推”，是指重复“减半”的过程。
例：二分法求方程根的问题
5、回溯法
基本思想：通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。
例：八皇后问题
1.4 误差分析简介
一、误差的来源
1、模型误差：数学模型与实际问题之间的误差。
例：h=1/2gt2
2、 观测误差：由使用观测工具和人引起的误差。
例：“横看岭侧成峰，远近高低各不同”
3、截断误差：计算中通过用有限过程的计算结果代替无限过程的结果造成的误差
例：e x 的展开幂级数形式：...!...!212+++++=n x x x e n
x 计算机有限求和形式：!
...!21)(2n x x x x S n
n ++++= 截断误差：10,)!1(1)(<<++=-θθx n x
e n x x S e n 4、舍入误差：计算机字长有限，一般实数不能精确存储，于是产生舍入误差。
例： π = 3.1415926…，1/3=0.3333333…
例：用毫米刻度的直尺测量一长度为x 的物体，测得的长度近似值为x* =25mm ，直尺以毫米为刻度，其误差不超过0.5mm ，求其绝对误差限及x 的准确值范围。
解：绝对误差限：|x - x*|= |x - 25| ≤0.5mm
准确值x 的范围： 24.5≤ x ≤ 25.5 或 x= 25± 0.5mm
三、相对误差与相对误差限
例：设s cm c s cm c /10997925.2*,/10)000001.0997925.2(1010?=?±=，求c*的相对误差限。
解：相对误差限：000003.0997925
.2000001.0≈=r ε
四、有效数字
例：x=3.1415926…，试判断近似值1415.3,1416.3,14.3,3*4*3*2*1====x x x x 的有效
数字位数。
解：
01*1105.0...1415.0,3?≤==εx 有效数字1位
22*2105.0...00159.0,14.3-?≤==εx 有效数字3位
43*3105.0...00000734.0,1416.3-?≤==εx 有效数字5位
34*4105.0...0000926.0,1415.3-?≤==εx 有效数字4位
例：写出下列各数具有5位有效数字的近似值： 4565.3445， 0.00422345， 9.0000234， 9.0000234*103
解：由有效数字的定义，上述各数具有5位有效数字的近似值分别是： 4565.3，0.0042235，9.0000，9.0000*103
解：绝对误差限：264102
11021|*|--?=?≤-x x 例：x*=0.0023156是x 的具有五位有效数字的近似值，求其绝对误差限。 解：绝对误差限：752101101|*|---?=?≤
-x x
例：x*=2.72是表示e 的具有三位有效数字的近似值，求其相对误差限。
解：
22311104
1102211021---?=??=?≤a r ε 例：要使20的相对误差限小于0.1%，要取几位有效数字。
解：
4.420=，则x 1=4
%1.0108
11021111≤?=?≤+-+-n n r x ε 解之得: n =4
五、运算误差分析 有运算就会产生误差，不同的运算步骤所产生的误差不一样。
例：设函数)cos 1(10)(3x x g -=，用四位数学用表计算)2( g 的近似值
解：
法1：
6.0)9994.01(10)2cos 1(10)2(33≈-≈-= g
相对误差：
()[]%3.89994
.011021*
1**)
1(10*)1(10)1(10)
2(*)2(*)2(24
333=-?≤--=----=-=-A A A A A A g g g g E r
法2： 6125.0)0175.0(102)2
(sin 102)2cos 1(10)2(23233≈??≈?=-=x g 相对误差：
()[]%57.00175
.010212*
*
2*)(*2**)(***)(*)(*)(102*)(102102)
2(*)2(*)2(24
222
2
22
32
323=??≤-=?-=
+?-=
-=????-??=-=-B B B B B B B B B B B B B B B B B B g g g g E r 运算中应注意的问题
1、避免两个相近的数相减
分析：
设y=x-A ，x 在运算时存在误差，其近似值为x*，则实际运算为y*=x*-A 。
相对误差：
A x x E A x x x A x A x A x y y E y E r -=--=
----=
=
*)
(***)*()(*)()(
由上式可知，x*越接近A ，则y 的相对误差越大
解决方法：利用数学中的恒等式或等价关系，尽量消去计算过程中的减运算
例：
（1）当x 1很接近x 2时
21
212
1
21ln
ln ln lg lg lg lg x x x x x x x x =-=- （2）当x 接近0时
x
x x x cos 1sin sin cos 1+=- （3）当x 很大时
)
1(111111
1+=+-++=-+x x x x x
x x x （4）当f(x 1)很接近f(x 2)时
+''-+'-=-+''-+
'-+=-)()(2
1)()()(])()(21)()()([)
()(2212212221221221x f x x x f x x x f x f x x x f x x x f x f x f 2、 |y|<<|x|时，应尽量避免x/y
分析：设y x z =，x 和y 的近似值为x*和y*，则*
**y x z = 其绝对误差为：
2*)()(*)(**)(*)(***)(**)(******|*||)(|y y E x x E y yy y E x x E y yy y y x x x y yy yx xy y x y x z z z E -≈-=---=-=-=
-=
由上式可知，若|y*|<<|x*|，则商的绝对误差很大。
例：
1.24710011.0718
2.22.2718001
.07182.2==
3、防止大数吃掉小数
例：在具有五位有效数字的计算工具上，计算
)9.01.0(,...87654100021≤≤++++i a a a a
解：
法一：
5
55551000211087654.01000000.01000000.01000000.01087654.0)
9.01.0(,...87654?=?++?+?+?=≤≤++++ i a a a a
法二：
)
...(87654 (876541000211000)
21a a a a a a ++++=++++
4、尽可能减少运算次数
例： x x x x x ????= 1615次运算
222216)))(((x x =4次运算
六、数值型算法的特点
1、 理论上的精确运算与实际运算之间存在着严重的差异
例：设函数x x x f -+=
1)(，在具有四位有效数字的计算工具上，计算x=1000时
的函数值。
解：
法一： 02.062.3164.3110001001100011000)1000(=-=-=-+=f
法二：
x x x x x f ++=
-+=111)( 01581.062
.3164.3111000100011
1000110001)1000(=+=+=++=f 2、 理论上的解题方案与实际能用性之间存在着严大的差异
例：求方程010)110(12
122=++-x x 的根
解：
法一：
2
10102
104101021014)110()110(2412
1212241212
2121222,1±≈?-±≈??-+±+=-±-=a
ac b b x
0,102121≈≈x x
法二：
1212
1212
241212
2121221102
10102
10410102
1014)110()110(24)sgn(=+≈?-+≈??-+++=---=a
ac b b b x
?
??<-≥+=0,10,1)sgn(b b b 1
10
1101212
1
2=?==ax c
x 3、 精确解法与近似解法一般没有本质差别
（1）精确解法：公式解法或直接解法。
理论上：精确解
实际上：运算数是近似的、运算存在误差，结果是近似解甚至错误解
（2）近似解法：迭代解法或数值解法。
运算中有精度要求，算法收敛，能够满足规定的精度要求
结论：精确解法所得结果未必准确，近似解法所得结果未必不准确，两者没有本质差别。
七、数值型算法的稳定性
数值型算法的稳定性：指初始数据的误差在算法执行过程中能否得到控制
例：求?+=
10dx 5x x I n n （n = 0, 1, 2, …, 8）的值。
解：由于 n
x x x x I I n n n n n 1dx dx 5551011
011==++=+??--- 法一：
建立递推公式
???????=-=≈=-=+=-?)8,,2,1(,51182.0)2.1ln(5ln 6ln dx 511100 n I n I x I n n
可以逐步算得
09.05101≈-=I I 05.052
112≈-=
I I 083.053
123≈-=I I 165.054134-≈-=I I 因为在[0, 1]上被积函数05≥+x x n （仅当x = 0时为零），且当m>n 时，5
5+≥+x x x x m
n （仅当x = 0时，等号成立），所以I n (n = 0, 1, 2, …, 8)是恒正的，并有08210>>>>>I I I I 。在上述计算结果中，I 4的近似值 是负的，这个结果显然是错的。为什么会这样呢？这就是误差传播所引起的危害。由递推公式可看出，I n -1的误差扩大了5倍后传给I n ，因而初值I 0的误差对以后各步计算结果的影响，随着n 的增大愈来愈严重。这就造成I 4的计算结果严重失真。
法二：
取一个I n 的近似值，用下面的公式倒过来计算I n -1，I n -2，…，即：
)1,,1,(5
1511 -=-=
-n n K I K I K k 则k I 的误差减小到51后传给1-k I ，因而初值的误差对以后各步的计算结果的影响是随着n 的增大而愈来愈小。
由于误差是逐步衰减的，初值I n 可以这样确定，不妨设I 9 ≈ I 10，于是由
1095
1501I I -= 可求得I 9 ≈ 0.017，按公式可逐次求得
I 8 ≈ 0.019 I 7 ≈ 0.021
I 6 ≈ 0.024 I 8 ≈ 0.028
I 4 ≈ 0.034 I 3 ≈ 0.043
I 2 ≈ 0.058 I 1 ≈ 0.088
I 0 ≈ 0.182
显然，这样算出的I 0与ln(1.2)的值比较符合。虽然初值I 9很粗糙，但因为用公式计算时，误差是逐步衰减的，所以计算结果相当可靠。
比较以上两个计算方案，显然，前者是一个不稳定的算法，后者是一个稳定算法。对于一个稳定的计算过程，由于舍入误差不增大，因而不具体估计舍入误差也是可用的。而对于一个不稳定的计算过程，如计算步骤太多，就可能出现错误结果。因此，在实际应用中应选用数值稳定的算法，尽量避免使用数值不稳定的算法。
[小结]
通过本章的学习，应掌握
1、数值计算的主要研究内容；
2、5个定义：有效数字、绝对误差、绝对误差限、相对误差、相对误差限；
3、2个关系：有效数字与绝对误差，有效数字与相对误差的关系；
4、减少运算误差的基本原则；
5、 数值型算法的基本特点及稳定性。