计算机科学中的重要数学思想迭代数学与应用数学毕业设计论文Word文档下载推荐.docx

1、Keywords：astringency；Newton Method；Jacobi iteration；Gauss-Seidel iteration；nonlinear equation；linear or nonlinear equation set。目录第一章 迭代法4 1.1 迭代法简介 1.2 运用迭代法的前提准备第二章 不动点迭代法5 2.1 不动点的寻找 2.2 绝对误差与相对误差6第三章 二分法8 3.1 波尔查诺二分法 3.2 试值法的收敛性9第四章 牛顿-拉夫森法与割线法11 4.1 求根的斜率法 4.2 收敛速度与缺陷13 4.3 割线法与加速收敛16第五章 求线性方程组的

2、迭代法19 5.1 雅克比迭代 5.2 高斯-塞德尔迭代与收敛性20第六章 非线性方程组的迭代法24 6.1 理论与广义微分 6.2 接近不动点处的收敛性25 6.3 赛德尔迭代法与牛顿法26结束语29主要参考文献30致谢31第一章 迭代法1.1 迭代法简介迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代法常用于求方程或方程组的近似根。1.2 运用迭代法的前提准备一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递

3、推出新值的变量，这个变量就是迭代变量。二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 三、迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件第二章 不动点迭代法2.1 不动点的寻找 我们先

4、探讨不动点的存在性和介绍不动点迭代的方法。定义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）有如下特性： 对应用中值定理，而且由于常量L=0，可推断出存在数P。因此，P=g（P），且P为不动点。 我们可以采用反证法。设存在两个不动点P1与P2.根据均值定理，可推断出存

5、在数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,，所

6、以得证迭代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为函数的零点 二分法是将连续函数的区间进行对分取舍，从而逐步逼近到零点，直到一个任意小的包含零点的间隔 定理3.1 设

7、，且存在实数满足。如果与的符号相反，且表示二分法生成的中点序列，则其中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，因

8、此区间改变为C0,b0=1,2, 接下来从左边压缩，使得a1=c0 b1=b0. 中点为c1=1.53.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的

9、近似值为 ，而且可以证明序列将收敛到r下面我们来用试值法求解，在区间0，2中，并观察它是否比二分法收敛得快在区间中有一个根。利用试值法，可得到： 。函数在区间内改变符号，因此从左边压缩，设，下一个判定从右边压缩，设通过计算我们可以看到试值法比二分法收敛速度快. 第四章 牛顿-拉夫森法与割线法4.1 求根的斜率法如果在根p附近连续，则可将它作为的特性，用于开发产生收敛到根p的序列的算法。而且这种算法比二分法和试值法产生的序列的速度快，牛顿拉夫森法是这类方法中最好的方法之一设初始值在根P附近。则函数y=f（x）的图形与x轴相交于点（p，0），而且点位于靠近点（p，0）的曲线上，将定义为曲线在点的切

10、线与x轴的交点，通过下图的显示可以看出比更靠近于p，写出切线L的两种表达式，则可得到与的相关方程，如下所示： 解出。重复上述过程可得到序列收敛到p O定理 4.1 设，且存在数，满足。如果，则存在一个数。对任意初始近似值，使得由如下迭代定义的序列收敛到p： 其中k=1，2注：函数由如下公式定义 ，并称为牛顿-拉夫森迭代函数。由于，这样寻找函数的不动点，可以实现寻找方程根的牛顿-拉夫森迭代我们从1阶泰勒多项式和它的余项开始分析 这里，位于与x之间。用x=p代入上式，并利用，可得 0=如果足够逼近p，上式右边的最后一项比前两项的和小。因此最后一项可以被忽略，而且可以利用如下近似表达式：，推出。这可

11、以用来定义下一个根的近似值 ，当用在上式的时候，就可以建立一般规律，即可得证！推论 4.1 求平方根的牛顿迭代：设A为实数，且A0，而且令0为的初始近似值，使用下列递推规则 ，k=1，2定义序列，则序列收敛到，也可表示为。从函数开始，方程-A=0的根为。现在利用牛顿-拉夫森函数中的和，可写出牛顿-拉夫森迭代公式简化为，用此式中的来定义牛顿-拉夫森定理中的递归迭代时，结果得证。用牛顿平方根算法求的近似值。从开始。运用公式计算得： 设，从开始，求，所以=2. 都是无限接近与2。4.2 收敛速度与缺陷 通过上面的讨论，我们可以得到一个很显著的性质：如果p是f（x）=0的单根，则牛顿法收敛很快，如果p

12、是重根，每个连续的近似值误差是前一个误差的一小部分，我们可以定义收敛阶来测量序列的收敛速度定义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并利用收敛阶检查二次收敛，可得到下表中的值-2.40.4123-2通过分析上面

13、的收敛速度，可发现每个连续迭代的误差是前一个迭代误差的一小部分，即，其中，为了检查上式，利用 和 而且很容易看出（在二重根处线性收敛）从开始用牛顿-拉夫森迭代求多项式的二重根p=1.用收敛阶公式检查线性收敛，可得到下表中的值1.2-0.2 可以看出，牛顿-拉夫森法收敛到二重根，但收敛速度很慢。的值趋近于0更快，因此当时，有定义。序列线性收敛，而且在每次迭代后，误差以12的比例下降。我们总结下牛顿法在单根和二重根上的性能。定理4.2 （牛顿-拉夫森迭代的收敛速度）设牛顿-拉夫森产生的序列，收敛到函数的根p，如果p是单根，则是二次收敛，而且对于足够大的n有如果p是M阶多重根，则是线性收敛的，而且对

14、于足够大的n有值得注意的是：有时序列并不一定收敛，因为并不可能在N此迭代后总能找到结果，我们可以尽量的通过画图等各种方法来选择P0.例如：设，而且，则 ， ， 而且缓慢发散到无穷大。4.3 割线法与加速收敛割线法是对牛顿-拉夫森法的改进，它采用了试值法一样的思想。我们需要2个靠近点的初始点和。定义为经过两个初始点的直线与x轴相交的横坐标，由图可以看出P2比P0或P1更靠近于P。p2，p1，p0相关的表示斜率方程为：所以，根据两点迭代公式可得到一般项为单根上的割线法：从=-2.6和=-2.4开始，利用割线法求多项式函数的根p=-2.根据迭代公式我们得我们得如下的迭代序列-2.60.20.67其中

15、收敛阶为R=（）2=1.618；当P是一个M阶根时，我们可以通过对牛顿法改进，使得其在多重根的情况下的收敛阶为2定理4.3（牛顿-拉夫森迭代的加速收敛）设牛顿-拉夫森算法产生的序列线性收敛到根x=p，其中M1，则牛顿-拉夫森迭代公式将产生一个收敛序列二次收敛到p。（二重根情况下的加速收敛）从p0=1.2开始，使用加速牛顿-拉夫森迭代求函数的二重根p=1由于M=2，加速公式变为 可得到下表中的值K很容易看出收敛速度变快。第五章 求线性方程组的迭代法下面来探讨将解非线性方程的迭代扩展到更高维数中，有什么规律与方法？5.1 雅克比迭代首先我们考虑线性方程组的不动点迭代的扩展考虑如下方程组：4x- y

16、+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具有严格对角优势。 这表示在矩阵的每一行中，主对角线上的元素的绝对值大于其他元素的绝对值的和。现在

17、使雅克比迭代过程一般化。设有如下线性方程组： 设第k点为，则下一点为坐标的上标（k）可用来标识属于这一点的坐标。迭代公式根据前面的值，使用上面的线性方程组中的第j行求解式。雅克比迭代： =其中j=1，2，N。 雅克比迭代使用所有旧坐标来生成新坐标，而我们下面介绍的高斯-赛德尔迭代尽可能使用新坐标得到更新的坐标。定理5.2（雅克比迭代） 设矩阵A具有严格对角优势，则AX=B有唯一解X=P。迭代式可产生一个向量序列，而且对于任意初始向量，向量序列都将收敛到5.2 高斯-塞德尔迭代与收敛性有时通过其他方法可以使收敛速度加快。我们观察雅克比迭代。由于比更加接近于x，所以在计算时用来替换是合理的，同理，

18、可以用和计算，这种迭代方法就是高斯-赛德尔迭代我们运用式中给定的一般线性方程组有：其中j=1，2，N。利用上面给的线性方程组用高斯-赛德尔迭代过程求解 如果从P0=（x0，y0，z0）=（1，2，2）开始，用上式中的迭代可收敛到解（2，4，3）我们把计算结果列表得：XkYkZk 0 1.0 2.0 2.0 1 1.75 3.75 2.95 2 1.95 3.96875 2.98625 3 1.995625 9 10 下面我们来探讨收敛性：比较向量之间的距离是很重要的，它可以用来判断是否收敛到P。P=（x1,x2,xn）和Q（y1,y2,yn）之间的欧几里得距离为它的缺点是需要相当大的计算量，因

19、此引入另一种范数，： 下面的结论保证了上述范数具有度量的数学结构，因此适合作为一个一般化的距离公式。根据线性代数的理论可知，如果两个向量的范数接近，则它们的欧几里得范数也接近定理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 距

20、离为=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）处的值。设如果使用向量表示，则关系式

21、可通过雅克比矩阵进行简化。函数的变化用表示，变量的变化用表示。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）

22、如果上述条件不满足，则迭代可能发散6.3 赛德尔迭代法与牛顿法现在可以构造一个与高斯-赛德尔法类似的改进型不动点迭代法，设用计算（在三维情况下，用和，计算），并将这些改进融入公式和中时，这个方法称为赛德尔迭代以及 下面我们把牛顿法扩展到二维空间设有方程组 它意味着从xy平面到w平面的转换。这里只关心在点处的变换行为，即点。如果两个函数有连续的偏导，则在点处用微分表示下列线性近似方程组是合法的 方程组是一个局部线性变换，它将自变量的微小变化联系起来。当使用雅克比矩阵时，这个关系可更容易地表示为： 如果方程组用向量函数V=F（X）表示，这个雅克比矩阵是导数的二维近似，因为关系式可表示为 现在可以利用上式推导二维情况下的牛顿法。设方程中u和v为0： 设（p，q）为上述方程组的解，即 为利用牛顿法求解，需要考虑函数在点的微小变化：设方程组中（x，