计算机科学中的重要数学思想—迭代数学与应用数学毕业论文

本科毕业论文（设计）

题目：计算机科学中的重要数学思想—迭代法

院（系）：数学科学学院专业：数学与应用数学

入学时间：二○○六年九月

导师姓名：李某某职称/学位：教授

导师所在单位：数学科学学院

毕业论文（设计）提交时间：二○一○年五月

计算机科学中的重要数学思想—迭代法

摘要

本文将探讨数学中重要的思想方法—迭代的实际应用。主要介绍几种

常见问题的迭代方法如：求解非线性方程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)一定有不动点

②则g（x）不动点唯一

证明：①如果g （a ）=a 或g （b ）=b ，则为真；否则g （a ）必须满足g （a ）,g(b)的值必须满足g （b ）。f （x ）有如下特性：()()0)()(0>-=<-=b g b b f a g a a f 且 对应用中值定理，而且由于常量L=0，可推断出存在数P 。因此，P=g （P ），且P 为不动点。

②我们可以采用反证法。设存在两个不动点P1与P2.根据均值定理，可推断出存在数d

根据假设，有，对前式子简化得。但这与题意矛盾，故得证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.在这种情况下，P 称为吸引不动点。如果对于所有，有>1,则迭代将不会收敛到P ，此时P 点称为排斥不动点。

我们可以证明定理中的吸引不动点。

证：首先要证明Pn 都位于（a ，b ）内。从P0开始，可推导出存在一个值C 满足满足0(,)1()(0)(0)(0)c a b P p g P g p g c P p '∈-=-=-因此，P1比P0更接近于P 。同上可以归纳出Pn 比Pn-1更接近于P 点。所以所有的点都在中。

接下来证明。

首先用数学归纳法证明可建立下面的不等式。因此

0lim lim 00n n n P pn K P p →∞→∞≤-≤-=，的极限压缩在左右2边的0之间，故=0，

这样就有=p,，所以得证迭代Pn=g （Pn-1）收敛到不动点P 例题：设=，且P0=4，找去函数的不动点。

解：设迭代，由P0=4得P1=3.5 P2=3.25 P3=3.125 …………

由此序列，不难得出P=3

2.2 绝对误差与相对误差

在迭代运算中，迭代结果与真实值间总存在误差，我们算误差方法分为：绝对误差和相对误差

绝对误差：

相对误差：（其中为真实的结果，为迭代计算的结果）

第三章二分法

3.1 波尔查诺二分法

先介绍连续函数的零点

定义3.1 设是连续函数。满足的任意r成为方程的一个根。也称r为函数的零点

二分法是将连续函数的区间进行对分取舍，从而逐步逼近到零点，直到一个任意小的包含零点的间隔

定理 3.1 设，且存在实数满足。如果与的符号相反，且表示二分法生成的中点序列，则其中n=0，1…

这样，序列收敛到零点即可表示为

证明：由于零点r和中点都位于区间内，与r之间的距离不会比这个区间的一半宽度范围大。这样，对于所有的n，

，观察连续的区间宽度范围，可得到

b1-a1=(b0-a0)/2 b2-a2=(b0-a0)/4,使用数学归纳法很容易得证，结

合上面的式子，我们有

综上可得证收敛到r，定理得证。

例题：利用二分法寻找函数的零点，区间为[0,2].

解：起始值=0，=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………………

3.2 试值法的收敛性

下面探讨试值法又叫试位法。试值法是对二分法的改造，使收敛速度变快。

与上述条件一样，假设和符号相反，如果找到经过点和的割线L与x轴的交点（c，0），则可得到一个更好的近似值。为了寻找值x，定义了线L的斜率m的的两种表示方法，一种为：另一种方法为：

于是我们有= 所以，这样

如果f（a）和f（c）符号相反，则在[a，c]内有一个零点

如果f（b）和f（c）符号相反，则在[c，b]内有一个零点

如果f（c）=0 ，则c是零点

结合上述过程可构造｛[]｝区间序列，其中每个序列包涵零点。在每一步中，零点r的近似值为，

而且可以证明序列将收敛到r

下面我们来用试值法求解，在区间[0，2]中，并观察它是否比二分法收敛得快

在区间中有一个根。利用试值法，可得到：

0.81859485(20)

21.09975017

0.81859485(1)

c

-

=-=

--

。

函数在区间内改变符号，因此从左边压缩，设，

下一个判定从右边压缩，设……

通过计算我们可以看到试值法比二分法收敛速度快.

第四章 牛顿-拉夫森法与割线法

4.1 求根的斜率法

如果在根p 附近连续，则可将它作为的特性，用于开发产生收敛到根p 的序列的算法。而且这种算法比二分法和试值法产生的序列的速度快，牛顿—拉夫森法是这类方法中最好的方法之一

设初始值在根P 附近。则函数y=f （x ）的图形与x 轴相交于点（p ，0），而且点位于靠近点（p ，0）的曲线上，将定义为曲线在点的切线与x 轴的交点，通过下图的显示可以看出比更靠近于p ，写出切线L 的两种表达式，则可得到与的相关方程，如下所示：

解出。重复上述过程可得到序列收敛到p

O

定理 4.1 设，且存在数，满足。如果，则存在一个数。对任意初始近似值，使得由如下迭代定义的序列收敛到p ：

1111()()()k k k k k f p p g p p f p ----==-' 其中k=1，2……

注：函数由如下公式定义 ，并称为牛顿-拉夫森迭代函数。由于，这样寻找函数的不动点，可以实现寻找方程根的牛顿-拉夫森迭代

证明：我们从1阶泰勒多项式和它的余项开始分析 2

0000()()()()()()2!f c x p f x f p f p x p '-'=+-+ 这里，位于与x 之间。用x=p

代入上式，并利用，可得 0=2

0000()()()()()2!

f c p p f p f p p p ''-'+-+ 如果足够逼近p ，上式右边的最后一项比前两项的和小。因此最后一项可以被忽略，而且可以利用如下近似表达式：0000()()()f p f p p p '≈+-，推出000()/()p p f p f p '≈-。

这可以用来定义下一个根的近似值 ，当用在上式的时候，就可以建立一般规律，即可得证！

推论 4.1 求平方根的牛顿迭代：设A 为实数，且A>0，而且令>0为的初始近似值，使用下列递推规则 ，k=1，2……

定义序列，则序列收敛到，也可表示为。

证明：从函数开始，方程-A=0的根为。现在利用牛顿-拉夫森函数中的和，可写出牛顿-拉夫森迭代公式

2()()()2f x x A g x x x f x x

-=-=-' 简化为，用此式中的来定义牛顿-拉夫森定理中的递归迭代时，结果得证。

例题：①用牛顿平方根算法求的近似值。从开始。

运用公式计算得： 2 2.25 2.25/2 2.2361111112p +=

=

②设，从开始，求

1111()

()()k k k k k f p p g p p f p ----==-'，所以=2.

都是无限接近与2。

4.2 收敛速度与缺陷

通过上面的讨论，我们可以得到一个很显著的性质：如果p 是f （x ）=0的单根，则牛顿法收敛很快，如果p 是重根，每个连续的近似值误差是前一个误差的一小部分，我们可以定义收敛阶来测量序列的收敛速度

定义4.1 设序列收敛到p ，并令，。如果两个常量存在，而且

1

1lim lim n n R R n n n n p p E A p p E ++→∞→∞-==-，则该序列称为以收敛阶R 收敛到p ，数A 称为渐进误差常数。R=1，2的情况为特殊情况

如果R=1，称序列的收敛性为线性收敛

如果R=2，称序列的收敛性为二次收敛。

如果R 很大，则序列很快收敛到p ；这意味着，关系式中对于大的值n ，有近似值。例如R=2且，则

下面我们用2个例题给出比较

（单根的二次收敛）从=-2.4开始，用牛顿-拉夫森迭代求多项式的根

p=-2.计算的迭代公式是：3

112122()33

k k k k p p g p p ----==- 解：用R=2并利用收敛阶检查二次收敛，可得到下表中的值

通过分析上面的收敛速度，可发现每个连续迭代的误差是前一个迭代误差的一小部分，即，其中，为了检查上式，利用

和而且很容易看出

（在二重根处线性收敛）从开始用牛顿-拉夫森迭代求多项式的二重根p=1.用收敛阶公式检查线性收敛，可得到下表中的值

可以看出，牛顿-拉夫森法收敛到二重根，但收敛速度很慢。的值趋近于0更快，因此当时，有定义。序列线性收敛，而且在每次迭代后，误差以1/2的比例下降。我们总结下牛顿法在单根和二重根上的性能。

定理4.2 （牛顿-拉夫森迭代的收敛速度）设牛顿-拉夫森产生的序列，收敛到函数的根p ，如果p 是单根，则是二次收敛，而且对于足够大的n 有

如果p 是M 阶多重根，则是线性收敛的，而且对于足够大的n 有

值得注意的是：有时序列并不一定收敛，因为并不可能在N 此迭代后总能找到结果，我们可以尽量的通过画图等各种方法来选择P0.

例如：设，而且，则 ， ，……

而且缓慢发散到无穷大。

4.3 割线法与加速收敛

割线法是对牛顿-拉夫森法的改进，它采用了试值法一样的思想。 我们需要2个靠近点的初始点和。定义为经过两个初始点的直线与x 轴相交的横坐标，由图可以看出P2比P0或P1更靠近于P 。p2，p1，p0相关的表示斜率方程为： 所以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 -+---==-- 单根上的割线法：从=-2.6和=-2.4开始，利用割线法求多项式函数的根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=（）/2=1.618；

当P是一个M阶根时，我们可以通过对牛顿法改进，使得其在多重根的情况下的收敛阶为2

定理4.3（牛顿-拉夫森迭代的加速收敛）设牛顿-拉夫森算法产生的序列线性收敛到根x=p，其中M>1，则牛顿-拉夫森迭代公式

将产生一个收敛序列二次收敛到p。

（二重根情况下的加速收敛）从p0=1.2开始，使用加速牛顿-拉夫森迭代求函数的二重根p=1

解：由于M=2，加速公式变为

3

111

12

11

()34

2

()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=

y= 这样我们就可以提出下列雅克比迭代过程：

z=

如果从p0=（x0，y0，z0）=（1，2，2）开始，则上式中的迭代将收敛

到解（2，4，3）

上述迭代过程将会产生序列，并收敛于原方程组的解。我们称这个过程为雅克比迭代

在求解偏微分方程时，线性方程组经常多达10000个变量。这些方程组的系数矩阵是稀疏矩阵，这时用迭代过程是求解这些大型方程组的有效方法。

定理5.1 设有维矩阵A ，如果 其中k=1，2，……，N ，

则称A 具有严格对角优势。

这表示在矩阵的每一行中，主对角线上的元素的绝对值大于其他元素的绝对值的和。

现在使雅克比迭代过程一般化。设有如下线性方程组：

111122111+j j N N a x a x a x a x b ++++=…………

211222222+j j N N a x a x a x a x b ++++=…………

① 1122+j j jj j jN N j a x a x a x a x b ++++=…………

1122+N N Nj j NN N N a x a x a x a x b ++++=…………

设第k 点为()()(

)12j (,,)k k k k k N P x x x x =…，，…，，

则下一点为(1)(1)(1)1112j

(,,)k k k k k N P x x x x +++++=…，，…，。坐标的上标（k ）可用来标识属于这一点的坐标。迭代公式根据前面的值()()(

)12j (,,)k k k k k N P x x x x =…，，…，，使

用上面的线性方程组中的第j 行求解式。

雅克比迭代： =()(

)(

)()111111k k k k j j jj j jj j jN N

jj b a x a x a x a x a --++-----……

其中j=1，2，…，N 。 ② 雅克比迭代使用所有旧坐标来生成新坐标，而我们下面介绍的高斯-赛德尔迭代尽可能使用新坐标得到更新的坐标。

定理5.2（雅克比迭代） 设矩阵A 具有严格对角优势，则AX=B 有唯一解X=P 。迭代式②可产生一个向量序列，而且对于任意初始向量，向量序列都将收敛到

5.2 高斯-塞德尔迭代与收敛性

有时通过其他方法可以使收敛速度加快。我们观察雅克比迭代。由于比更加接近于x ，所以在计算时用来替换是合理的，同理，可以用和计算，这种迭代方法就是高斯-赛德尔迭代

我们运用①式中给定的一般线性方程组有：

(1)(

1)()()111111(

1)j k k k k j j jj j jj j jN N

k jj b a x a x a x a x x a ++--+++-----=…… 其中j=1，2，…N 。

例题：利用上面给的线性方程组用高斯-赛德尔迭代过程求解

如果从P0=（x0，y0，z0）=（1，2，2）开始，用上式中的迭代可收敛到解（2，4，3） 我们把计算结果列表得：

下面我们来探讨收敛性：

比较向量之间的距离是很重要的，它可以用来判断是否收敛到P 。P=(x1,x2,…,xn)和Q

（y1,y2,……,yn ）之间的欧几里得距离为

它的缺点是需要相当大的计算量，因此引入另一种范数，： ③

下面的结论保证了上述范数具有度量的数学结构，因此适合作为一个一般化的距离公式。根据线性代数的理论可知，如果两个向量的范数接近，则它们的欧几里得范数也接近

定理5.3 设X 和Y 是N 维向量，c 是一个标量。则函数有如下性质：

； =0，当且仅当X=0 ；

； 。

上面很容易证明，我们证一下最后一个。

证明：对于每个j ，实数的三角不等式表示为。根据这些不等式可以得证上述不等式111111N N N

j j j j j j j X Y x y x y X Y ===+=+≤+=+∑∑∑。 可以用③中的定义的范数来定义两点之间的距离

定义5.1 设X 和Y 是N 维空间中的中点。可定义X 和Y 的距离为范数，表示为

例题：计算点P=（2，4，3）和Q=（1.75，3.75，2.95）的欧几里得距离和距离 解：欧几里得距离为2221/2((2 1.75)(4 3.75)(3 2.95))P Q -=-+-+-=0.3570 距离为12 1.754 3.753 2.95P Q -=-+-+-=0.55

更容易计算，常用来确定N 维空间的收敛性

第六章 非线性方程组的迭代法

6.1 理论与广义微分

定义6.1（雅克比矩阵） 设和是包含自变量x 和y 的函数，则它们的

雅克比矩阵J （x ，y ）表示为 同理如果，，是包含自变量x ，y ，z 的函数，则雅克比矩阵J （x ，y ，z ）定义为

。

例题：对下列函数求解在点（1，3，2）处的维雅克比矩阵J （x ，y ，z ） 32421(,,)f x y z x y y z z =-+-+

解：雅克比矩阵为111232

2222

33

332142(,,)1f f f x y z z x y z y z x z x y f f f J x y z x

y z y y f f f x z xz xz x y z ?????????-+-+?????????+++?????==???????--???????????

??????? 这样在点（1，3，2）处的雅克比矩阵为矩阵

3528(1,3,2)5343/21/23/4J --????=????--??

下面介绍广义微分

对于含多个变量的函数，微分用来表示自变量的变化情况如何影响因变量。设有如下表达式

， ， ①

设已知表达式①中函数在点处的值，现在希望可以预测在临近点（x ，y ，z ）处的值。设

111000000000(,,)(,,)(,,)f f f du x y z x y z x y z x y z ???=++???

222000000000(,,)(,,)(,,)f f f dv x y z x y z x y z x y z

???=++??? ② 333000000000(,,)(,,)(,,)f f f dw x y z x y z x y z x y z ???=

++???。 如果使用向量表示，则关系式②可通过雅克比矩阵进行简化。函数的变化用表示，变量的变化用表示。

000000(,,)(,,)du dx dF dv J x y z dy J x y z dX dw dz ????????===????????????

6.2 接近不动点处的收敛性

定义6.2 包含2个方程， ③的方程组的不动点是点（p ，q ），满足。在三维情况下，方程组

，，④的不动点是点（p,q,r ）满足123(,,),(,,)p g p q r q g p q r ==且r=g (p,q,r) 定义6.3 对于方程组③中的函数，不动点迭代为

， ⑤

对于方程组④中的函数，不动点迭代为

，， ⑥

其中k=0，1……

定理 6.1（不动点迭代）设方程组③④中的函数和它们的一阶偏导数分别在包含（p ，q ）或（p ，q ，r ）的区域内连续。如果初始点值足够接近不动点，则有下面2种情况

（二维）如果足够接近（p ，q ）而且

则迭代⑤收敛到不动点（p ，q ）

（三维）如果足够接近（p ，q ，r ），而且 111(,,)(,,)(,,)1g g g p q r p q r p q r x y z

???++

???++

则迭代⑥将收敛到不动点（p ，q ，r ）

如果上述条件不满足，则迭代可能发散

6.3 赛德尔迭代法与牛顿法

现在可以构造一个与高斯-赛德尔法类似的改进型不动点迭代法，设用计算（在三维情况下，用和，计算），并将这些改进融入公式⑤和⑥中时，这个方法称为赛德尔迭代

以及

下面我们把牛顿法扩展到二维空间

设有方程组

⑦

它意味着从xy 平面到w 平面的转换。这里只关心在点处的变换行为，即点。如果两个函数有连续的偏导，则在点处用微分表示下列线性近似方程组是合法的 010001000(,)()(,)()u u f x y x x f x y y y x y

??-=-+-?? 020002000(,)()(,)()v v f x y x x f x y y y x y ??-=

-+-?? ⑧ 方程组⑧是一个局部线性变换，它将自变量的微小变化联系起来。当使用雅克比矩阵时，这个关系可更容易地表示为：

1001000000200200(,)(,)(,)(,)f x y f x y x x x y u u y y v v f x y f x y x y ??????-??????-?

?=??????--???

?????????

⑨ 如果方程组⑦用向量函数V=F （X ）表示，这个雅克比矩阵是导数的二维近似，因为关系式⑨可表示为 ⑩

现在可以利用上式推导二维情况下的牛顿法。

设方程⑦中u 和v 为0： Ⅰ

设（p ，q ）为上述方程组的解，即 Ⅱ

为利用牛顿法求解Ⅰ，需要考虑函数在点的微小变化：

设方程组⑦中（x ，y ）=（p ，q ），并利用式Ⅱ，可得到（u ，v ）=（0，0）。因此因变量的变化是

本文来源：https://www.bwwdw.com/article/8cde.html