《计算机科学中的重要数学思想—迭代数学与应用数学毕业论文设计1.doc》由会员分享，可在线阅读，更多相关《计算机科学中的重要数学思想—迭代数学与应用数学毕业论文设计1.doc（34页珍藏版）》请在三一办公上搜索。
1、本科毕业论文（设计）题目： 计算机科学中的重要数学思想迭代法 计算机科学中的重要数学思想迭代法摘要 本文将探讨数学中重要的思想方法迭代的实际应用。主要介绍几种常见问题的迭代方法如：求解非线性方程f(x)=0的不动点迭代、二分法、牛顿迭代法，还有求解线性方程组及非线性方程组的各种迭代法。并对各种迭代法的收敛性进行讨论和比较，讨论各种迭代法的优缺点。在分析结果的基础上我们可以看出迭代法的实际应用性很强，对于计算机上的应用尤为突出。研究结果告诉我们：在具体的应用中要根据实际情况来选择不一样的迭代法，也可以将几种方法结合来运用。关键词迭代；收敛性；牛顿法；雅克比迭代；塞德尔迭代；非线性方程；（非）线性
2、方程组。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 exampl
3、e ：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 itera
4、tion。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。Keyw
5、ords：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第五章 求线性方程
6、组的迭代法19 5.1 雅克比迭代19 5.2 高斯-塞德尔迭代与收敛性20第六章 非线性方程组的迭代法24 6.1 理论与广义微分24 6.2 接近不动点处的收敛性25 6.3 赛德尔迭代法与牛顿法26结束语29主要参考文献30致谢31 计算机科学中的重要数学思想迭代法第一章 迭代法1.1 迭代法简介迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代法常用于求方程或方程组的近似根。1.2 运用迭代法的前提准备一、确定迭代变量。在可以用迭代算法解决
7、的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 三、迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件
8、第二章 不动点迭代法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 任意xa,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为不动点。 我们可以采用反证法。设存在两
9、个不动点P1与P2.根据均值定理，可推断出存在数d 根据假设，有，对前式子简化得。但这与题意矛盾，故得证P点唯一。下面我们给定一个定理来判断，迭代所产生的序列是收敛的还是发散的。定理 2.2 设有如果对于所有将收敛到唯一的不动点P .在这种情况下，P称为吸引不动点。如果对于所有，有1,则迭代将不会收敛到P，此时P点称为排斥不动点。我们可以证明定理中的吸引不动点。证：首先要证明Pn都位于（a，b）内。从P0开始，可推导出存在一个值C满足满足因此，P1比P0更接近于P。同上可以归纳出Pn比Pn-1更接近于P点。所以所有的点都在中。接下来证明。首先用数学归纳法证明可建立下面的不等式。因此，的极限压缩
10、在左右2边的0之间，故=0，这样就有=p,，所以得证迭代Pn=g（Pn-1）收敛到不动点P例题：设=，且P0=4，找去函数的不动点。解：设迭代，由P0=4得 P1=3.5 P2=3.25 P3=3.125 由此序列，不难得出P=32.2 绝对误差与相对误差 在迭代运算中，迭代结果与真实值间总存在误差，我们算误差方法分为：绝对误差和相对误差 绝对误差： 相对误差： （其中为真实的结果，为迭代计算的结果）第三章 二分法3.1 波尔查诺二分法 先介绍连续函数的零点 定义3.1 设是连续函数。满足的任意r成为方程的一个根。也称r为函数的零点 二分法是将连续函数的区间进行对分取舍，从而逐步逼近到零点，直
11、到一个任意小的包含零点的间隔 定理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内在中点
12、C0=1，可发现f（1）=-0.158529，因此区间改变为C0,b0=1,2, 接下来从左边压缩，使得a1=c0 b1=b0. 中点为c1=1.5按照这种方法，可得到序列，他收敛于1.114157143.2 试值法的收敛性下面探讨试值法又叫试位法。试值法是对二分法的改造，使收敛速度变快。与上述条件一样，假设和符号相反，如果找到经过点和的割线L与x轴的交点（c，0），则可得到一个更好的近似值。为了寻找值x，定义了线L的斜率m的的两种表示方法，一种为： 另一种方法为：于是我们有= 所以，这样如果f（a）和f（c）符号相反，则在a，c内有一个零点如果f（b）和f（c）符号相反，则在c，b内有一个零
13、点如果f（c）=0 ，则c是零点结合上述过程可构造区间序列，其中每个序列包涵零点。在每一步中，零点r的近似值为 ，而且可以证明序列将收敛到r下面我们来用试值法求解，在区间0，2中，并观察它是否比二分法收敛得快解：根据初始值，可得到f（0）=-1 f（2）=0.81859485，因此在区间中有一个根。利用试值法，可得到： 。函数在区间内改变符号，因此从左边压缩，设，根据上面结论可得到下一个近似值=1.12124074和，下一个判定从右边压缩，设我们可以得到通过4次运算，就能算出r1.11415714通过计算我们可以看到试值法比二分法收敛速度快.第四章 牛顿-拉夫森法与割线法4.1 求根的斜率法如
14、果在根p附近连续，则可将它作为的特性，用于开发产生收敛到根p的序列的算法。而且这种算法比二分法和试值法产生的序列的速度快，牛顿拉夫森法是这类方法中最好的方法之一设初始值在根P附近。则函数y=f（x）的图形与x轴相交于点（p，0），而且点位于靠近点（p，0）的曲线上，将定义为曲线在点的切线与x轴的交点，通过下图的显示可以看出比更靠近于p，写出切线L的两种表达式，则可得到与的相关方程，如下所示： 解出。重复上述过程可得到序列收敛到p O 定理 4.1 设，且存在数，满足。如果，则存在一个数。对任意初始近似值，使得由如下迭代定义的序列收敛到p： 其中k=1，2注：函数由如下公式定义 ，并称为牛顿-拉
15、夫森迭代函数。由于，这样寻找函数的不动点，可以实现寻找方程根的牛顿-拉夫森迭代证明：我们从1阶泰勒多项式和它的余项开始分析 这里，位于与x之间。用x=p代入上式，并利用，可得 0=如果足够逼近p，上式右边的最后一项比前两项的和小。因此最后一项可以被忽略，而且可以利用如下近似表达式：，推出。这可以用来定义下一个根的近似值 ，当用在上式的时候，就可以建立一般规律，即可得证！推论 4.1 求平方根的牛顿迭代：设A为实数，且A0，而且令0为的初始近似值，使用下列递推规则 ，k=1，2定义序列，则序列收敛到，也可表示为。证明：从函数开始，方程-A=0的根为。现在利用牛顿-拉夫森函数中的和，可写出牛顿-拉
16、夫森迭代公式 简化为，用此式中的来定义牛顿-拉夫森定理中的递归迭代时，结果得证。例题：用牛顿平方根算法求的近似值。从开始。运用公式计算得： 设，从开始，求 ，所以=2. 都是无限接近与2。4.2 收敛速度与缺陷 通过上面的讨论，我们可以得到一个很显著的性质：如果p是f（x）=0的单根，则牛顿法收敛很快，如果p是重根，每个连续的近似值误差是前一个误差的一小部分，我们可以定义收敛阶来测量序列的收敛速度定义4.1 设序列收敛到p，并令，。如果两个常量存在，而且，则该序列称为以收敛阶R收敛到p，数A称为渐进误差常数。R=1，2的情况为特殊情况如果R=1，称序列的收敛性为线性收敛如果R=2，称序列的收敛
17、性为二次收敛。如果R很大，则序列很快收敛到p；这意味着，关系式中对于大的值n，有近似值。例如R=2且，则下面我们用2个例题给出比较（单根的二次收敛）从=-2.4开始，用牛顿-拉夫森迭代求多项式的根p=-2.计算的迭代公式是：解：用R=2并利用收敛阶检查二次收敛，可得到下表中的值0-2.40.3238095240.40.4761904751-2.0761904760.0725944650.0761904760.6194690862-2.0035960110.0035874220.0035960110.6642026133-2.0000085890.0000085890.0000085894-20
18、0通过分析上面的收敛速度，可发现每个连续迭代的误差是前一个迭代误差的一小部分，即，其中，为了检查上式，利用 和 而且很容易看出（在二重根处线性收敛）从开始用牛顿-拉夫森迭代求多项式的二重根p=1.用收敛阶公式检查线性收敛，可得到下表中的值01.2-0.096969697-0.20.51515151511.103030303-0.050673883-0.1030303030.50816525321.052356420-0.025955609-0.0523564200.49675111531.026400811-0.013143081-0.0264008110.50976368841.013257
19、730-0.006614311-0.0132577300.50109777551.006643419-0.003318055-0.0066434190.500550093 可以看出，牛顿-拉夫森法收敛到二重根，但收敛速度很慢。的值趋近于0更快，因此当时，有定义。序列线性收敛，而且在每次迭代后，误差以1/2的比例下降。我们总结下牛顿法在单根和二重根上的性能。定理4.2 （牛顿-拉夫森迭代的收敛速度）设牛顿-拉夫森产生的序列，收敛到函数的根p，如果p是单根，则是二次收敛，而且对于足够大的n有如果p是M阶多重根，则是线性收敛的，而且对于足够大的n有值得注意的是：有时序列并不一定收敛，因为并不可能在N
20、此迭代后总能找到结果，我们可以尽量的通过画图等各种方法来选择P0.例如：设，而且，则 ， ， 而且缓慢发散到无穷大。4.3 割线法与加速收敛割线法是对牛顿-拉夫森法的改进，它采用了试值法一样的思想。我们需要2个靠近点的初始点和。定义为经过两个初始点的直线与x轴相交的横坐标，由图可以看出P2比P0或P1更靠近于P。p2，p1，p0相关的表示斜率方程为： 所以，根据两点迭代公式可得到一般项为单根上的割线法：从=-2.6和=-2.4开始，利用割线法求多项式函数的根p=-2.解：根据迭代公式我们得我们得如下的迭代序列0-2.60.20.60.9141528311-2.40.2934010150.40.
21、4694977652-2.1065989850.0839575730.1065989850.8472900123-2.0226414120.0211303140.0226414120.6936089224-2.0015110980.0014885610.0015110980.8258411165-2.0000225150.0000225150.0000225370.7271009876-2.0000000220.0000000220.0000000227-200其中收敛阶为R=（）/2=1.618；当P是一个M阶根时，我们可以通过对牛顿法改进，使得其在多重根的情况下的收敛阶为2定理4.3（牛顿
22、-拉夫森迭代的加速收敛）设牛顿-拉夫森算法产生的序列线性收敛到根x=p，其中M1，则牛顿-拉夫森迭代公式 将产生一个收敛序列二次收敛到p。（二重根情况下的加速收敛）从p0=1.2开始，使用加速牛顿-拉夫森迭代求函数的二重根p=1 解：由于M=2，加速公式变为 可得到下表中的值K01.2-0.193939394-0.20.15151515011.006060606-0.006054519-0.0060606060.16571857821.000006087-0.000006087-0.00000608731.0000000000.0000000000.000000000很容易看出收敛速度变快。第
23、五章 求线性方程组的迭代法下面来探讨将解非线性方程的迭代扩展到更高维数中，有什么规律与方法？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个变量。这些方程组的系数矩阵是稀疏矩阵，这时用迭代过程是求解这些大
24、型方程组的有效方法。定理5.1 设有维矩阵A，如果 其中k=1，2，N，则称A具有严格对角优势。 这表示在矩阵的每一行中，主对角线上的元素的绝对值大于其他元素的绝对值的和。现在使雅克比迭代过程一般化。设有如下线性方程组： 设第k点为，则下一点为。坐标的上标（k）可用来标识属于这一点的坐标。迭代公式根据前面的值，使用上面的线性方程组中的第j行求解式。雅克比迭代：=其中j=1，2，N。 雅克比迭代使用所有旧坐标来生成新坐标，而我们下面介绍的高斯-赛德尔迭代尽可能使用新坐标得到更新的坐标。定理5.2（雅克比迭代） 设矩阵A具有严格对角优势，则AX=B有唯一解X=P。迭代式可产生一个向量序列，而且对于
25、任意初始向量，向量序列都将收敛到5.2 高斯-塞德尔迭代与收敛性有时通过其他方法可以使收敛速度加快。我们观察雅克比迭代。由于比更加接近于x，所以在计算时用来替换是合理的，同理，可以用和计算，这种迭代方法就是高斯-赛德尔迭代我们运用式中给定的一般线性方程组有： 其中j=1，2，N。例题：利用上面给的线性方程组用高斯-赛德尔迭代过程求解 如果从P0=（x0，y0，z0）=（1，2，2）开始，用上式中的迭代可收敛到解（2，4，3）我们把计算结果列表得：KXkYkZk 0 1.0 2.0 2.0 1 1.75 3.75 2.95 2 1.95 3.96875 2.98625 3 1.995625 3.
26、99609375 2.99903125 8 1.99999983 3.99999988 2.99999996 9 1.99999998 3.99999999 3.00000000 10 2.00000000 4.00000000 3.00000000 下面我们来探讨收敛性：比较向量之间的距离是很重要的，它可以用来判断是否收敛到P。P=(x1,x2,xn)和Q（y1,y2,yn）之间的欧几里得距离为它的缺点是需要相当大的计算量，因此引入另一种范数，： 下面的结论保证了上述范数具有度量的数学结构，因此适合作为一个一般化的距离公式。根据线性代数的理论可知，如果两个向量的范数接近，则它们的欧几里得范数
27、也接近定理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（雅克比矩阵） 设和是包含自变量
28、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个方程， 的方程
29、组的不动点是点（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 赛德尔迭代法与牛顿法现在可以构造一个与高斯-赛德尔法类似的改进型不动点迭代法，设
30、用计算（在三维情况下，用和，计算），并将这些改进融入公式和中时，这个方法称为赛德尔迭代 以及 下面我们把牛顿法扩展到二维空间设有方程组 它意味着从xy平面到w平面的转换。这里只关心在点处的变换行为，即点。如果两个函数有连续的偏导，则在点处用微分表示下列线性近似方程组是合法的 方程组是一个局部线性变换，它将自变量的微小变化联系起来。当使用雅克比矩阵时，这个关系可更容易地表示为： 如果方程组用向量函数V=F（X）表示，这个雅克比矩阵是导数的二维近似，因为关系式可表示为 现在可以利用上式推导二维情况下的牛顿法。设方程中u和v为0： 设（p，q）为上述方程组的解，即 为利用牛顿法求解，需要考虑函数在点
31、的微小变化： 设方程组中（x，y）=（p，q），并利用式，可得到（u，v）=（0，0）。因此因变量的变化是 将中的结果代入式可得线性变换表达式 式中的雅克比矩阵非奇异，则可解出为： 然后，解的下一个近似值为 注意上式可是用于一个变量的牛顿法的一般化，结束语迭代在计算机科学上的应用十分的广，通过重复循环的运算，将序列的值逼近于真实值。本文探讨的就是大家都比较熟悉的迭代法，比喻：不动点迭代，二分法，高斯-拉夫森法，牛顿法等。其实通过探讨，我们会发现各种迭代法之间存在着联系，并在一定条件下可以转换。甚至我们在出来问题的时候，有时要结合不同的迭代法进行处理。迭代法的实用性越来越强。我想随着计算科学的深
32、入研究探讨，迭代法将会更加完善与功能性强，将会处理更多复杂而又繁琐的问题。主要参考文献 1 姚传义 数值分析 M. 中国轻工业出版社 2009.09 2 （美）索尔 著 吴兆金，范红军 译 数值分析 M.中国邮电出版社 2010.1.1 3 （美）John H.Mathews Kurtis D.Fink 著 陈渝 钱方 译 数值方法（MATLAB版） M.电子工业出版社 2006.5 4 曹志浩 变分迭代法 M科学出版社 2005.2.1 5 （英）瓦尔加 矩阵迭代分析（第二版）M高等出版社 2002.10致 谢 本文的写作过程中一直以来得到我的导师李某某老师的悉心指导和热心帮助。李老师很平易近人，为人热情，在学术上又高度严谨，本文的完成离不开李老师的支持。再次我还要感谢以前的授课讲师章某老师，感谢老师们对我的培养。至此，我谨向导师以及老师们致以崇高的敬意和诚挚的谢意。还有我还要感谢一直以来对我支持和帮助的同学们。他们不仅生活上给我大学带来了乐趣，并且在学习上帮我找资料，找素材。再次感谢他们。最后我要特别感谢我的父母，在我漫长的求学生涯中他们的无私关爱、鼓励和支持是我不断前进的力量源泉。致此十几年的寒窗苦读即将结束之时谨向他们致以衷心的感谢。
