本科毕业论文（设计）
题目：计算机科学中的重要数学思想—迭代法
计算机科学中的重要数学思想—迭代法
摘要
本文将探讨数学中重要的思想方法—迭代的实际应用。主要介绍几种常见问题的迭代方法如：求解非线性方程f(x)=0的不动点迭代、二分法、牛顿迭代法，还有求解线性方程组及非线性方程组的各种迭代法。并对各种迭代法的收敛性进行讨论和比较，讨论各种迭代法的优缺点。在分析结果的基础上我们可以看出迭代法的实际应用性很强，对于计算机上的应用尤为突出。研究结果告诉我们：在具体的应用中要根据实际情况来选择不一样的迭代法，也可以将几种方法结合来运用。
关键词
迭代；收敛性；牛顿法；雅克比迭代；塞德尔迭代；非线性方程；（非）线性方程组。
An important Mathematics thought from the computer
science---- Iteration Method
Abstract
In this paper, we will discuss an important mathematics thought of iteration method and discuss its realistic application First, I will introduce a lot of iteration method from some natural question ，for example ：the Fixed-point iteration ，the Bisection Method ，Newton method ，and some iteration method of solving linear equation set or not linear equation set。Second ，we will discuss and compare the astringency of those methods 。We will find out the advantages and disadvantages of several methods for iteration。From analysis the result of iteration method ，we can find it has lots of action in reality，particularly in computer science。According to the analysis result，we get that we use iteration method must base on reality，and also we can combine different method to deal with some problem around us。
Keywords：astringency；Newton Method；Jacobi iteration；Gauss-Seidel iteration；nonlinear equation；linear or nonlinear equation set。
目录
第一章迭代法 (4)
1.1 迭代法简介 (4)
1.2 运用迭代法的前提准备 (4)
第二章不动点迭代法 (5)
2.1 不动点的寻找 (5)
2.2 绝对误差与相对误差 (6)
第三章二分法 (8)
3.1 波尔查诺二分法 (8)
3.2 试值法的收敛性 (9)
第四章牛顿-拉夫森法与割线法 (11)
4.1 求根的斜率法 (11)
4.2 收敛速度与缺陷 (13)
4.3 割线法与加速收敛 (16)
第五章求线性方程组的迭代法 (19)
5.1 雅克比迭代 (19)
5.2 高斯-塞德尔迭代与收敛性 (20)
第六章非线性方程组的迭代法 (24)
6.1 理论与广义微分 (24)
6.2 接近不动点处的收敛性 (25)
6.3 赛德尔迭代法与牛顿法 (26)
结束语 (29)
主要参考文献 (30)
致谢 (31)
计算机科学中的重要数学思想—迭代法
第一章迭代法
1.1 迭代法简介
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代法常用于求方程或方程组的近似根。
1.2 运用迭代法的前提准备
一、确定迭代变量。在可以用迭代算法解决的问题中，至少存
在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是
迭代变量。
二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一
个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决
迭代问题的关键，通常可以使用递推或倒推的方法来完成。
三、迭代过程进行控制。在什么时候结束迭代过程？这是编写
迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。
迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个
确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对
于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的
控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条
件
第二章 不动点迭代法
2.1 不动点的寻找
我们先探讨不动点的存在性和介绍不动点迭代的方法。
定义2.1 函数g （x ）的一个不动点是指一个实数P ，满足P=g （P ）。 定义2.2 迭代Pn+1=g(Pn),其中n=0，1，…称为不动点迭代 定理 2.1 g （x ）为连续函数且∈[a,b] 我们有
①g （x ）∈[a,b] 任意x ∈[a,b] 则g(x)一定有不动点 ②1)(<'x g 则g （x ）不动点唯一
证明：①如果g （a ）=a 或g （b ）=b ，则为真；否则g （a ）必须满足g （a ）∈ (]b a ,,g(b)的值必须满足g （b ）[)b a ,∈。f （x ）()x g x -≡有如下特性：()()0)()(0>-=<-=b g b b f a g a a f 且 对)(x f 应用中值定理，而且由于常量L=0，可推断出存在数P 0p f ),(=∈）（满足b a 。因此，P=g （P ），且P 为不动点。
②我们可以采用反证法。设存在两个不动点P1与P2.根据均值定理，可推断出存在数d 满足),,(b a ∈ 1
2)
1()2()(p p p g p g d g --='根据假设，有2)2(1)1(p p g p p g ==且，对前式子简化
得11
21
2)(=--=
'p p p p d g 。但这与题意矛盾，故得证P 点唯一。 下面我们给定一个定理来判断，迭代所产生的序列是收敛的还是发散的。
定理 2.2 设有
[],[.],,,g(x)[a,b]
g g C ab K a b '∈∈∈∈①②是一个正常数，③p0(a,b),④对于所有x 有如果对于所有[,],g ()1,x a b x K '∈≤<有则迭代Pn=g(Pn-1)将收敛到唯一的不动点P [,]a b ∈.在这种情况下，P 称为吸引不动点。如果对于所有
[,]x a b ∈，有g ()x '>1,则迭代将不会收敛到P ，此时P 点称为排斥不动
点。
我们可以证明定理中的吸引不动点。
证：首先要证明Pn 都位于（a ，b ）内。从P0开始，可推导出存在
一个值C 满足0(,)c a b ∈满足
0(,)1()(0)(0)(0)c a b P p g P g p g c P p '∈-=-=-(0)(0)g c P p '=-00
K P p P p ≤-<-因此，P1比P0更接近于P 。同上可以归纳出Pn 比
Pn-1更接近于P 点。所以所有的点都在(,)a b 中。
接下来证明。lim 0n P pn →∞
-=
首先用数学归纳法证明可建立下面的不等式lim 0n n P pn K P p →∞-≤-。因此
0lim lim 00n n n P pn K P p →∞
→∞
≤-≤-=，P pn
-的极限压缩在左右2边的0之间，
故lim
n P pn →∞
-=0，这样就有lim n pn →∞=p,，所以得证迭代Pn=g （Pn-1）收敛到不动点P
例题：设()g x =0.5 1.5x +，且P0=4，找去函数的不动点。
解：设迭代1()n n P g P +=，由P0=4得 P1=3.5 P2=3.25 P3=3.125 …………
由此序列，不难得出P=3
2.2 绝对误差与相对误差
在迭代运算中，迭代结果与真实值间总存在误差，我们算误差方法分为：绝对误差
和相对误差 绝对误差：*e
x x
=-
相对误差：**
x x e x
-= （其中
*
x
为真实的结果，
x
为迭代计算的结果）
第三章 二分法
3.1 波尔查诺二分法 先介绍连续函数的零点
定义3.1 设()f x 是连续函数。满足()0f r =的任意
r 成为方程()0f x =的
一个根。也称r 为函数()f x 的零点
二分法是将连续函数的区间进行对分取舍，从而逐步逼近到零点，直到一个任意小
的包含零点的间隔 定理3.1 设()(,)f x C a b ∈，且存在实数[,]r a b ∈满足()0f r =。如果()f a 与
()f b 的符号相反，且{}0n n c ∞
=表示二分法生成的中点序列，则
1
2n n b a
r c +--≤
其中n=0，1… 这样，序列{}0n n c ∞
=收敛到零点x r =即可表示为lim n n c r →∞
= 证明：由于零点r 和中点n c 都位于区间[],n n a b 内，n c 与r 之间的距离不
会比这个区间的一半宽度范围大。这样，对于所有的n ，
2
n n
n b a r c --≤
，观察连续的区间宽度范围，可得到
b1-a1=(b0-a0)/2 b2-a2=(b0-a0)/4,使用数学归纳法很容易得证
00
2n n n
b a b a --=
，结合上面的式子，我们有1
2n n n n b a r c +--≤
综上可得证
{}0n n c ∞
=收敛到r ，定理得证。
例题：利用二分法寻找函数
()sin 1f x x x =-的零点，区间为[0,2].
解：起始值0a =0，0b =2.计算f （0）=-1 f （2）=0.818595 所以f （x ）的一个根位于[0,2]内在中点C0=1，可发现f （1）
=-0.158529，因此区间改变为[C0,b0]=[1,2], 接下来从左边压缩，使得a1=c0 b1=b0. 中点为c1=1.5………………
按照这种方法，可得到序列{}k c ，他收敛于r ≈1.11415714
3.2 试值法的收敛性
下面探讨试值法又叫试位法。试值法是对二分法的改造，使收敛速度变快。
与上述条件一样，假设()f a 和()f b 符号相反，如果找到经过点(,())a f a 和(,())b f b 的割线L 与x 轴的交点（c ，0）
，则可得到一个更好的近似值。为了寻找值x ，定义了线L 的斜率m 的的两种表示方法，一种为：()()
f b f a m b a
-=-
另一种方法为：0()
f b m c b
-=- 于是我们有
()()f b f a b a --=0()f b c b -- 所以()()
()()
f b b a c b f b f a -=--，这样
如果f （a ）和f （c ）符号相反，则在[a ，c]内有一个零点 如果f （b ）和f （c ）符号相反，则在[c ，b]内有一个零点 如果f （c ）=0 ，则c 是零点
结合上述过程可构造｛[,n n a b ]｝区间序列，其中每个序列包涵零点。在每一
步中，零点r 的近似值为
()()
()()n n n n n n n f b b a c b f b f a -=-
-，
而且可以证明序列{}n c 将收敛到r
下面我们来用试值法求解sin 10x x -=，在区间[0，2]中，并观察它是否比二分法收敛得快
解：根据初始值000b 2a ==和，可得到f （0）=-1 f （2）=0.81859485，因此在区间中有一个根。利用试值法，可得到：00.81859485(20)
2 1.099750170.81859485(1)
c -=-=--
0()0.020019
21f c =-。
函数在区间[]00,[1.09975017,2]c b =内改变符号，因此从左边压缩，设
1010,a c b b ==，根据上面结论可得到下一个近似值1c =1.12124074和1()0.00983461f c =，
下一个判定从右边压缩，设2121,a a b c ==……
我们可以得到通过4次运算，就能算出r ≈1.11415714 通过计算我们可以看到试值法比二分法收敛速度快.
第四章 牛顿-拉夫森法与割线法
4.1 求根的斜率法
如果(),(),()f x f x f x '''在根p 附近连续，则可将它作为()f x 的特性，用于开发产生收敛到根p 的序列{}k p 的算法。而且这种算法比二分法和试值法产生的序列的速度快，牛顿—拉夫森法是这类方法中最好的方法之一
设初始值0p 在根P 附近。则函数y=f （x ）的图形与x 轴相交于点（p ，0），而且点()00,()p f p 位于靠近点（p ，0）的曲线上，将1p 定义为曲线在点()00,()p f p 的切线与x 轴的交点，通过下图的显示可以看出1p 比0p 更靠近于p ，写出切线L 的两种表达式，则可得到0p 与1p 的相关方程，如下所示：
0010
0()()f p m f p p p -'=
=- 解出0100()
()f p p p f p =-
'。重复上述过程可得到序列{}k p 收敛到p
定理 4.1 设2[,]f C a b ∈，且存在数[,]p a b ∈，满足()0f p =。如果()0f p '≠，则存在一个数0δ>。对任意初始近似值0[,]p p p δδ∈-+，使得由如下迭代定义
的序列0{}k k p ∞
=收敛到p ：
1111()
()()k k k k k f p p g p p f p ----==-
' 其中k=1，2……
注：函数()g x 由如下公式定义 ()
()()f x g x x f x =-'，并称为牛顿-拉夫森迭代
函数。由于()g p p =，这样寻找函数()g x 的不动点，可以实现寻找方程()0f x =根的牛顿-拉夫森迭代
证明：我们从1阶泰勒多项式和它的余项开始分析
20000()()()()()()2!
f c x p f x f p f p x p '-'=+-+ 这里，c 位于0
p
与x 之间。用x=p
代入上式，并利用0()0f p =，可得 0=2
0000()()()()()2!f c p p f p f p p p ''-'+-+
如果0p 足够逼近p ，上式右边的最后一项比前两项的和小。因此最后一项可以被忽略，而且可以利用如下近似表达式：0000()()()f p f p p p '≈
+-，推出
000()/()p p f p f p '≈-。
这可以用来定义下一个根的近似值1p 1
00
0()/()p p f p f p '=-，当1
k p -用在
上式的时候，就可以建立一般规律，即可得证！
推论 4.1 求平方根的牛顿迭代：设A 为实数，且A>0，而且令0p >0
的初始近似值，使用下列递推规则 11
2
k k k A
p p p --+
=，k=1，2……
定义序列0{}
k k p
∞
=，则序列
0{}
k k p ∞
=
，也可表示为lim k
n p →∞
=
证明：从函数2()f x x A =-开始，方程2x -A=0
的根为-拉夫森函数中的()f x 和()f x '，可写出牛顿-拉夫森迭代公式
2()()()2f x x A g x x x f x x -=-=-' 简化为()2
A x x g x +=，用此式中的()g x 来定义牛
顿-拉夫森定理中的递归迭代时，结果得证。
例题：①
02p =开始。
运用公式计算得：125/2 2.252p +=
= 2 2.25 2.25/2
2.2361111112
p +== 3 2.23067978p = 4 2.236067978
p =
②设3()32f x x x =--，从0 2.1p =开始，求1234,,p p p p 和
1111()()()k k k k k f p p g p p f p ----==-'，所以1p =32.1 6.322.13*4.23
---≈- 2. 234,p p p 和都是无限接近与2。
4.2 收敛速度与缺陷
通过上面的讨论，我们可以得到一个很显著的性质：如果p 是f （x ）
=0的单根，则牛顿法收敛很快，如果p 是重根，每个连续的近似值误差是前一个误差的一小部分，我们可以定义收敛阶来测量序列的收敛速度
定义 4.1 设序列0{}n n p ∞=收敛到p ，并令n n E p p =-，
0n ≥。如果两个常量00A R ≠>和存在，而且
11lim
lim
n n R
R
n n n
n
p p E A p p E ++→∞
→∞
-==-，则该序列称为以收敛阶R 收敛到p ，数A 称为
渐进误差常数。R=1，2的情况为特殊情况
如果R=1，称序列0{}n n p ∞
=的收敛性为线性收敛
如果R=2，称序列0{}n n p ∞
=的收敛性为二次收敛。
如果R 很大，则序列{}n p 很快收敛到p ；这意味着，关系式中对于大的值n ，有近似值1R
n n E A E +≈。例如R=2且2
10
n E -≈，则4
110n E A -+≈?
下面我们用2个例题给出比较
（单根的二次收敛）从0p =-2.4开始，用牛顿-拉夫森迭代求多项式
3()32f x x x =-+的根p=-2.计算{}k p 的迭代公式是：
3112122
()33
k k k k p p g p p ----==-
解：用R=2并利用收敛阶检查二次收敛，可得到下表中的值
通过分析上面的收敛速度，可发现每个连续迭代的误差是前一个迭代误差的一小部分，即2
1k k p p A p p +-≈-，其中2/3A ≈，为了检查上式，利用
30.000008589p p -= 和 2
20.000012935p p -= 而且很容易看出
2
322/3p p p p -≈-
（在二重根处线性收敛）从0 1.2p =开始用牛顿-拉夫森迭代求多项式
3()32f x x x =-+的二重根p=1.用收敛阶公式检查线性收敛，可得到下表中的值
可以看出，牛顿-拉夫森法收敛到二重根，但收敛速度很慢。()()k k f p f p '的值比的值趋近于0更快，因此当k p p ≠时，
()
()
k k f p f p '有定义。序列线性收敛，而且在每次迭代后，误差以1/2的比例下降。我们总结下牛顿法在单根和二重根上的性能。
定理4.2 （牛顿-拉夫森迭代的收敛速度）设牛顿-拉夫森产生的序列0{}n n p ∞=，收敛到函数()f x 的根p ，如果p 是单根，则是二次收敛，而且对于足够大的n 有
2
1()2()
n n f p E E f p +''≈
'
如果p 是M 阶多重根，则是线性收敛的，而且对于足够大的n 有11
n n M E E M
+-≈
值得注意的是：有时序列并不一定收敛，因为并不可能在N 此迭代后总能找到结果，我们可以尽量的通过画图等各种方法来选择P0. 例如：设()x
f x x
-=，而且0 2.0p =，则14p = ， 25.3333333
p = ，…… 1519.723549434p = 而且{}k p 缓慢发散到无穷大。
4.3 割线法与加速收敛
割线法是对牛顿-拉夫森法的改进，它采用了试值法一样的思想。
我们需要2个靠近点(,0)p 的初始点00(,())p f p 和11(,())p f p 。定义2p 为经过两个初始点的直线与x 轴相交的横坐标，由图可以看出P2比P0或P1更靠近于P 。p2，p1，p0相关的表示斜率方程为：1010()()f p f p m p p -=- 121
0()
f p m p p -=-
所以110210110()()
(,)()()f p p p p g p p p f p f p -==--，根据两点迭代公式可得到一般项为
1111()()
(,)()()
k k k k k k k k k f p p p p g p p p f p f p -+---==-
-
单根上的割线法：从0p =-2.6和1p =-2.4开始，利用割线法求多项式函数
3()32f x x x =-+的根p=-2.
解：根据迭代公式我们得2211113311
2
(,)33k k k k k k k k k k k p p p p p g p p p p p p --+---+-==--+
我们得如下的迭代序列
其中收敛阶为R=
（1/2=1.618；
当P 是一个M 阶根时，我们可以通过对牛顿法改进，使得其在多重根的情况下的收敛阶为2
定理4.3（牛顿-拉夫森迭代的加速收敛）设牛顿-拉夫森算法产生的序列线性收敛到根x=p ，其中M>1，则牛顿-拉夫森迭代公式
111()
()
k k k k Mf p p p f p ---=-
' 将产生一个收敛序列0{}k k p ∞=二次收敛到p 。 （二重根情况下的加速收敛）从p0=1.2开始，使用加速牛顿-拉夫森迭代求函数3()32f x x x =-+的二重根p=1
解：由于M=2，加速公式变为 31111211()342()33
k k k k k k k f p p p p p f p p ------+-=-='- 可得
到下表中的值
很容易看出收敛速度变快。
第五章 求线性方程组的迭代法
下面来探讨将解非线性方程的迭代扩展到更高维数中，有什么规律与方法？ 5.1 雅克比迭代
首先我们考虑线性方程组的不动点迭代的扩展 考虑如下方程组：4x- y+z= 7 4x-8y+z=-21
-2x+ y+5z=15 上述方程可表示成如下形式：
x=
74
y z
+- y=2148x z ++ 这样我们就可以提出下列雅克比迭代过程：
z=1525
x y +-
174
k k
k y z x ++-=
12148
k k
k x z y +++= 如果从p0=（x0，y0，z0）=（1，2，2）开始，则上式中的迭代将收敛
11525
k k
k x y z ++-= 到解（2，4，3）
上述迭代过程将会产生序列{}k p ，并收敛于原方程组的解。我们称这个过程为雅克比迭代
在求解偏微分方程时，线性方程组经常多达10000个变量。这些方程组的系数矩阵是稀疏矩阵，这时用迭代过程是求解这些大型方程组的有效方法。 定理5.1 设有N N ?维矩阵A ，如果1N
kk kj j j k a a =≠>∑ 其中k=1，2，……，N ，
则称A 具有严格对角优势。
这表示在矩阵的每一行中，主对角线上的元素的绝对值大于其他元素的绝对值的和。