计算机科学中的重要数学思想迭代数学与应用数学毕业设计论文.docx
《计算机科学中的重要数学思想迭代数学与应用数学毕业设计论文.docx》由会员分享，可在线阅读，更多相关《计算机科学中的重要数学思想迭代数学与应用数学毕业设计论文.docx（22页珍藏版）》请在冰点文库上搜索。
计算机科学中的重要数学思想迭代数学与应用数学毕业设计论文
本科毕业论文（设计）
题 目：
计算机科学中的重要数学思想—迭代法
院（系）：
数学科学学院 专业：
数学与应用数学
入学时间：
二○○六年 九 月
导师：
李某某 职称学位：
教授
导师所在单位：
数学科学学院
毕业论文（设计）提交时间：
二○一○年 五 月
计算机科学中的重要数学思想—迭代法
摘要
本文将探讨数学中重要的思想方法—迭代的实际应用。
主要介绍几种常见问题的迭代方法如：
求解非线性方程f（x）=0的不动点迭代、二分法、牛顿迭代法，还有求解线性方程组及非线性方程组的各种迭代法。
并对各种迭代法的收敛性进行讨论和比较，讨论各种迭代法的优缺点。
在分析结果的基础上我们可以看出迭代法的实际应用性很强，对于计算机上的应用尤为突出。
研究结果告诉我们：
在具体的应用中要根据实际情况来选择不一样的迭代法，也可以将几种方法结合来运用。
关键词
迭代；收敛性；牛顿法；雅克比迭代；塞德尔迭代；非线性方程；（非）线性方程组。
AnimportantMathematicsthoughtfromthecomputerscience----IterationMethod
Abstract
Inthispaper,wewilldiscussanimportantmathematicsthoughtofiterationmethodanddiscussitsrealisticapplicationFirst,Iwillintroducealotofiterationmethodfromsomenaturalquestion，forexample：
theFixed-pointiteration，theBisectionMethod，Newtonmethod，andsomeiterationmethodofsolvinglinearequationsetornotlinearequationset。
Second，wewilldiscussandcomparetheastringencyofthosemethods。
Wewillfindouttheadvantagesanddisadvantagesofseveralmethodsforiteration。
Fromanalysistheresultofiterationmethod，wecanfinditinreality，particularlyincomputerscience。
Accordingtotheanalysisresult，wegetthatweuseiterationmethodmustbaseonreality，andalsowecancombinedifferentmethodtodealwithsomeproblemaroundus。
Keywords：
astringency；NewtonMethod；Jacobiiteration；Gauss-Seideliteration；nonlinearequation；linearornonlinearequationset。
目 录
第一章迭代法·····································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.1g（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）有如下特性：
对应用中值定理，而且由于常量L=0，可推断出存在数P。
因此，P=g（P），且P为不动点。
②我们可以采用反证法。
设存在两个不动点P1与P2.根据均值定理，可推断出存在数d
根据假设，有，对前式子简化得。
但这与题意矛盾，故得证P点唯一。
下面我们给定一个定理来判断，迭代所产生的序列是收敛的还是发散的。
定理2.2设有
如果对于所有
将收敛到唯一的不动点P.在这种情况下，P称为吸引不动点。
如果对于所有，有>1,则迭代将不会收敛到P，此时P点称为排斥不动点。
我们可以证明定理中的吸引不动点。
证：
首先要证明Pn都位于（a，b）内。
从P0开始，可推导出存在一个值C满足满足
因此，P1比P0更接近于P。
同上可以归纳出Pn比Pn-1更接近于P点。
所以所有的点都在中。
接下来证明。
首先用数学归纳法证明可建立下面的不等式。
因此
，的极限压缩在左右2边的0之间，故=0，这样就有=p,，所以得证迭代Pn=g（Pn-1）收敛到不动点P
例题：
设=，且P0=4，找去函数的不动点。
解：
设迭代，由P0=4得P1=3.5P2=3.25P3=3.125…………
由此序列，不难得出P=3
2.2绝对误差与相对误差
在迭代运算中，迭代结果与真实值间总存在误差，我们算误差方法分为：
绝对误差和相对误差
绝对误差：
相对误差：
（其中为真实的结果，为迭代计算的结果）
第三章二分法
3.1波尔查诺二分法
先介绍连续函数的零点
定义3.1设是连续函数。
满足的任意r成为方程的一个根。
也称r为函数的零点
二分法是将连续函数的区间进行对分取舍，从而逐步逼近到零点，直到一个任意小的包含零点的间隔
定理3.1设，且存在实数满足。
如果与的符号相反，且表示二分法生成的中点序列，则其中n=0，1…
这样，序列收敛到零点即可表示为
证明：
由于零点r和中点都位于区间内，与r之间的距离不会比这个区间的一半宽度范围大。
这样，对于所有的n，
，观察连续的区间宽度范围，可得到
b1-a1=（b0-a0）2b2-a2=（b0-a0）4,使用数学归纳法很容易得证，结合上面的式子，我们有
综上可得证收敛到r，定理得证。
例题：
利用二分法寻找函数的零点，区间为[0,2].
解：
起始值=0，=2.计算f（0）=-1f
（2）=0.818595
所以f（x）的一个根位于[0,2]内在中点C0=1，可发现f
（1）=-0.158529，因此区间改变为[C0,b0]=[1,2],接下来从左边压缩，使得a1=c0b1=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]中，并观察它是否比二分法收敛得快
在区间中有一个根。
利用试值法，可得到：
。
函数在区间内改变符号，因此从左边压缩，设，
下一个判定从右边压缩，设……
通过计算我们可以看到试值法比二分法收敛速度快.
第四章牛顿-拉夫森法与割线法
4.1求根的斜率法
如果在根p附近连续，则可将它作为的特性，用于开发产生收敛到根p的序列的算法。
而且这种算法比二分法和试值法产生的序列的速度快，牛顿—拉夫森法是这类方法中最好的方法之一
设初始值在根P附近。
则函数y=f（x）的图形与x轴相交于点（p，0），而且点位于靠近点（p，0）的曲线上，将定义为曲线在点的切线与x轴的交点，通过下图的显示可以看出比更靠近于p，写出切线L的两种表达式，则可得到与的相关方程，如下所示：
解出。
重复上述过程可得到序列收敛到p
O
定理4.1设，且存在数，满足。
如果，则存在一个数。
对任意初始近似值，使得由如下迭代定义的序列收敛到p：
其中k=1，2……
注：
函数由如下公式定义，并称为牛顿-拉夫森迭代函数。
由于，这样寻找函数的不动点，可以实现寻找方程根的牛顿-拉夫森迭代
证明：
我们从1阶泰勒多项式和它的余项开始分析
这里，位于与x之间。
用x=p代入上式，并利用，可得0=
如果足够逼近p，上式右边的最后一项比前两项的和小。
因此最后一项可以被忽略，而且可以利用如下近似表达式：
，推出
。
这可以用来定义下一个根的近似值，当用在上式的时候，就可以建立一般规律，即可得证！
推论4.1求平方根的牛顿迭代：
设A为实数，且A>0，而且令>0为的初始近似值，使用下列递推规则，k=1，2……
定义序列，则序列收敛到，也可表示为。
证明：
从函数开始，方程-A=0的根为。
现在利用牛顿-拉夫森函数中的和，可写出牛顿-拉夫森迭代公式
简化为，用此式中的来定义牛顿-拉夫森定理中的递归迭代时，结果得证。
例题：
①用牛顿平方根算法求的近似值。
从开始。
运用公式计算得：
②设，从开始，求
，所以=2.
都是无限接近与2。
4.2收敛速度与缺陷
通过上面的讨论，我们可以得到一个很显著的性质：
如果p是f（x）=0的单根，则牛顿法收敛很快，如果p是重根，每个连续的近似值误差是前一个误差的一小部分，我们可以定义收敛阶来测量序列的收敛速度
定义4.1设序列收敛到p，并令，。
如果两个常量存在，而且
，则该序列称为以收敛阶R收敛到p，数A称为渐进误差常数。
R=1，2的情况为特殊情况
如果R=1，称序列的收敛性为线性收敛
如果R=2，称序列的收敛性为二次收敛。
如果R很大，则序列很快收敛到p；这意味着，关系式中对于大的值n，有近似值。
例如R=2且，则
下面我们用2个例题给出比较
（单根的二次收敛）从=-2.4开始，用牛顿-拉夫森迭代求多项式的根p=-2.计算的迭代公式是：
解：
用R=2并利用收敛阶检查二次收敛，可得到下表中的值
0
-2.4
0.4
1
2
3
4
-2
0
0
通过分析上面的收敛速度，可发现每个连续迭代的误差是前一个迭代误差的一小部分，即，其中，为了检查上式，利用
和而且很容易看出
（在二重根处线性收敛）从开始用牛顿-拉夫森迭代求多项式的二重根p=1.用收敛阶公式检查线性收敛，可得到下表中的值
0
1.2
-0.2
1
2
3
4
5
…
……
……
……
……
可以看出，牛顿-拉夫森法收敛到二重根，但收敛速度很慢。
的值趋近于0更快，因此当时，有定义。
序列线性收敛，而且在每次迭代后，误差以12的比例下降。
我们总结下牛顿法在单根和二重根上的性能。
定理4.2（牛顿-拉夫森迭代的收敛速度）设牛顿-拉夫森产生的序列，收敛到函数的根p，如果p是单根，则是二次收敛，而且对于足够大的n有
如果p是M阶多重根，则是线性收敛的，而且对于足够大的n有
值得注意的是：
有时序列并不一定收敛，因为并不可能在N此迭代后总能找到结果，我们可以尽量的通过画图等各种方法来选择P0.
例如：
设，而且，则，，……
而且缓慢发散到无穷大。
4.3割线法与加速收敛
割线法是对牛顿-拉夫森法的改进，它采用了试值法一样的思想。
我们需要2个靠近点的初始点和。
定义为经过两个初始点的直线与x轴相交的横坐标，由图可以看出P2比P0或P1更靠近于P。
p2，p1，p0相关的表示斜率方程为：
所以
，根据两点迭代公式可得到一般项为
单根上的割线法：
从=-2.6和=-2.4开始，利用割线法求多项式函数的根p=-2.
解：
根据迭代公式我们得
我们得如下的迭代序列
0
-2.6
0.2
0.6
1
-2.4
0.4
2
3
4
5
6
7
-2
0
0
其中收敛阶为R=（）2=1.618；
当P是一个M阶根时，我们可以通过对牛顿法改进，使得其在多重根的情况下的收敛阶为2
定理4.3（牛顿-拉夫森迭代的加速收敛）设牛顿-拉夫森算法产生的序列线性收敛到根x=p，其中M>1，则牛顿-拉夫森迭代公式
将产生一个收敛序列二次收敛到p。
（二重根情况下的加速收敛）从p0=1.2开始，使用加速牛顿-拉夫森迭代求函数的二重根p=1
解：
由于M=2，加速公式变为
可得到下表中的值
K
0
1.2
-0.2
1
2
3
很容易看出收敛速度变快。
第五章求线性方程组的迭代法
下面来探讨将解非线性方程的迭代扩展到更高维数中，有什么规律与方法？
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具有严格对角优势。
这表示在矩阵的每一行中，主对角线上的元素的绝对值大于其他元素的绝对值的和。
现在使雅克比迭代过程一般化。
设有如下线性方程组：
①
设第k点为
，
则下一点为
。
坐标的上标（k）可用来标识属于这一点的坐标。
迭代公式根据前面的值
，使用上面的线性方程组中的第j行求解式。
雅克比迭代：
=
其中j=1，2，…，N。
②
雅克比迭代使用所有旧坐标来生成新坐标，而我们下面介绍的高斯-赛德尔迭代尽可能使用新坐标得到更新的坐标。
定理5.2（雅克比迭代）设矩阵A具有严格对角优势，则AX=B有唯一解X=P。
迭代式②可产生一个向量序列，而且对于任意初始向量，向量序列都将收敛到
5.2高斯-塞德尔迭代与收敛性
有时通过其他方法可以使收敛速度加快。
我们观察雅克比迭代。
由于比更加接近于x，所以在计算时用来替换是合理的，同理，可以用和计算，这种迭代方法就是高斯-赛德尔迭代
我们运用①式中给定的一般线性方程组有：
其中j=1，2，…N。
例题：
利用上面给的线性方程组用高斯-赛德尔迭代过程求解
如果从P0=（x0，y0，z0）=（1，2，2）开始，用上式中的迭代可收敛到解（2，4，3）
我们把计算结果列表得：
K
Xk
Yk
Zk
0
1.0
2.0
2.0
1
1.75
3.75
2.95
2
1.95
3.96875
2.98625
3
1.995625
8
9
10
下面我们来探讨收敛性：
比较向量之间的距离是很重要的，它可以用来判断是否收敛到P。
P=（x1,x2,…,xn）和Q（y1,y2,……,yn）之间的欧几里得距离为
它的缺点是需要相当大的计算量，因此引入另一种范数，：
③
下面的结论保证了上述范数具有度量的数学结构，因此适合作为一个一般化的距离公式。
根据线性代数的理论可知，如果两个向量的范数接近，则它们的欧几里得范数也接近
定理5.3设X和Y是N维向量，c是一个标量。
则函数有如下性质：
；=0，当且仅当X=0；
；。
上面很容易证明，我们证一下最后一个。
证明：
对于每个j，实数的三角不等式表示为。
根据这些不等式可以得证上述不等式
。
可以用③中的定义的范数来定义两点之间的距离
定义5.1设X和Y是N维空间中的中点。
可定义X和Y的距离为范数，表示为
例题：
计算点P=（2，4，3）和Q=（1.75，3.75，2.95）的欧几里得距离和距离
解：
欧几里得距离为
=0.3570
距离为
=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）
解：
雅克比矩阵为
这样在点（1，3，2）处的雅克比矩阵为矩阵
下面介绍广义微分
对于含多个变量的函数，微分用来表示自变量的变化情况如何影响因变量。
设有如下表达式
，，①
设已知表达式①中函数在点处的值，现在希望可以预测在临近点（x，y，z）处的值。
设
②
。
如果使用向量表示，则关系式②可通过雅克比矩阵进行简化。
函数的变化用表示，变量的变化用表示。
6.2接近不动点处的收敛性
定义6.2包含2个方程，③的方程组的不动点是点（p，q），满足。
在三维情况下，方程组
，，④的不动点是点（p,q,r）满足
定义6.3对于方程组③中的函数，不动点迭代为
，⑤
对于方程组④中的函数，不动点迭代为
，，⑥
其中k=0，1……
定理6.1（不动点迭代）设方程组③④中的函数和它们的一阶偏导数分别在包含（p，q）或（p，q，r）的区域内连续。
如果初始点值足够接近不动点，则有下面2种情况
（二维）如果足够接近（p，q）而且
则迭代⑤收敛到不动点（p，q）
（三维）如果足够接近（p，q，r），而且
则迭代⑥将收敛到不动点（p，q，r）
如果上述条件不满足，则迭代可能发散
6.3赛德尔迭代法与牛顿法
现在可以构造一个与高斯-赛德尔法类似的改进型不动点迭代法，设用计算（在三维情况下，用和，计算），并将这些改进融入公式⑤和⑥中时，这个方法称为赛德尔迭代
以及
下面我们把牛顿法扩展到二维空间
设有方程组
⑦
它意味着从xy平面到w平面的转换。
这里只关心在点处的变换行为，即点。
如果两个函数有连续的偏导，则在点处用微分表示下列线性近似方程组是合法的
⑧
方程组⑧是一个局部线性变换，它将自变量的微小变化联系起来。
当使用雅克比矩阵时，这个关系可更容易地表示为：
⑨
如果方程组⑦用向量函数V=F（X）表示，这个雅克比矩阵是导数的二维近似，因为关系式⑨可表示为⑩
现在可以利用上式推导二维情况下的牛顿法。
设方程⑦中u和v为0：
Ⅰ
设（p，q）为上述方程组的解，即Ⅱ
为利用牛顿法求解Ⅰ，需要考虑函数在点的微小变化：
设方程组⑦中（x，
升级会员 