计算方法迭代法.ppt

《计算方法迭代法.ppt》由会员分享，可在线阅读，更多相关《计算方法迭代法.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章迭代法第三章迭代法3.1 二分法二分法3.2 迭代法原理迭代法原理3.3 Newton迭代法和迭代加速迭代法和迭代加速3.4 解线性方程组的迭代法解线性方程组的迭代法3.1 二分法二分法 根的估计根的估计 二分法二分法根的估计根的估计引理引理3.1（连续函数的介值定理连续函数的介值定理）设设f(x)在在a,b上连续，且上连续，且f(a)f(b)0，则存在，则存在x*(a,b)使使f(x*)=0。例例3.1 证明证明x3 3x 1=0 有且仅有有且仅有3个实根，并个实根，并确定根的大致位置使误差不超过确定根的大致位置使误差不超过 =0.5。解解:单调性分析和解的位置单调性分析和解的位置选步

2、长选步长h=2,扫描节点函数值扫描节点函数值异号区间内有根异号区间内有根f(x)=x3 3x 1 二分法二分法条件条件:设设f(x)在在a,b上连续，上连续，f(x)=0在在a,b上存在唯一解，且上存在唯一解，且f(a)f(b)0。记。记Step 1:If f(a0)f(x0)0,then x*(a0,x0)let a1=a0,b1=x0;Else x*(x0,b0)let a1=x0,b1=b0;Let x1=(a1+b1)/2.Step k:If f(ak-1)f(xk-1)0,then x*(ak-1,xk-1)let ak=ak-1,bk=xk-1;Else x*(xk-1,bk-1)

3、let ak=xk-1,bk=bk-1;Let xk=(ak+bk)/2.收敛性及截断误差分析收敛性及截断误差分析:例例3.2 x3 3x 1=0,1,2,精度精度0.5e-1二分法二分法优点优点算法简单算法简单收敛有保证收敛有保证只要只要f(x)连续连续缺点缺点对区间两端点选取条件苛刻对区间两端点选取条件苛刻收敛速度慢收敛速度慢3.2 迭代法原理迭代法原理迭代法的思想迭代法的思想 不动点原理不动点原理 局部收敛性局部收敛性收敛性的阶收敛性的阶 迭代法的思想迭代法的思想 条件条件:f(x)=0 在在x0附近有且仅有一个根附近有且仅有一个根 设计同解变形设计同解变形 x=g(x)迭代式迭代式 x

4、k=g(xk-1),k=1,2,如果收敛如果收敛 xk x*,则则x*是是f(x)=0 的的根根不动点原理不动点原理(迭代过程收敛迭代过程收敛)定定理理3.1(不不动动点点原原理理)设设映映射射g(x)在在a,b上上有有连连续续的的一阶导数且满足一阶导数且满足1o 封闭性封闭性：x a,b,g(x)a,b,2o 压缩性压缩性：L (0,1)使对使对 x a,b,|g(x)|L,则则在在a,b上上存存在在唯唯一一的的不不动动点点x*，且且对对 x0 a,b,xk=g(xk-1)收敛于收敛于x*。进一步，有误差估计式。进一步，有误差估计式 后验估计先验估计算法设计中迭代结束条件算法设计中迭代结束条

5、件:近似使用近似使用|xk-xk-1|不动点原理不动点原理证明步骤证明步骤解的存在性解的存在性;解的唯一性解的唯一性;解的收敛性解的收敛性;误差估计式。误差估计式。例例3.3 局部收敛性局部收敛性(格式收敛格式收敛)定理定理3.2（局部收敛性局部收敛性）设）设g(x)连续连续,则存在充分靠近则存在充分靠近x*的初值，使迭代收敛于的初值，使迭代收敛于x*。证明：利用定理证明：利用定理3.1,3.1,取取L=具有局部收敛性的迭代计算上不一定收敛，具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当；它是否收敛还要看初值是否取的恰当；而不具有局部收敛性的迭代对任何初值都不而不具有局

6、部收敛性的迭代对任何初值都不可能收敛。可能收敛。应用中应用中:近似使用近似使用|g(x0)|1判断判断收敛性的阶收敛性的阶(局部收敛速度局部收敛速度)定定义义3.1 当当xkx*，记记ek=x*-xk，若若存存在在实数实数p，使，使ek+1/epk c 0，则称则称xk有有p p阶收敛速度阶收敛速度。线性收敛线性收敛 p=1平方收敛平方收敛 p=2 定理定理3.3 设设xk=g(xk-1)x*，则，则(1)当当g(x*)0时，时，xk线性收敛；线性收敛；(2)当当g(x*)=0,而而g(x*)0时，时，xk平方收敛。平方收敛。3.3 Newton迭代法和迭代加速迭代法和迭代加速 牛顿牛顿(Ne

7、wton)迭代法迭代法“迭代加速迭代加速”技术技术牛顿牛顿(Newton)迭代法迭代法原理原理(1次近似次近似,直线代替曲线直线代替曲线)牛顿格式牛顿格式Newton法几何意义：切线法法几何意义：切线法切线代替曲线切线代替曲线Newton法局部收敛性法局部收敛性单根：平方收敛单根：平方收敛m重重根：线性收敛根：线性收敛例例3.5（P56)Newton迭代法，计算迭代法，计算3次达到次达到4位有效数字位有效数字 计算计算4次达到次达到4位有效数字位有效数字越是精度要求高越是精度要求高,Newton迭代法优势越明显迭代法优势越明显“迭代加速迭代加速”技术技术加快迭代过程的收敛速度加快迭代过程的收敛

8、速度将发散的迭代格式加工成收敛的将发散的迭代格式加工成收敛的若若g(x)在在x*附近大约为附近大约为D,改进改进xk=g(xk-1)为为 例例3.6（P57)4 解线性方程组的迭代法解线性方程组的迭代法 1 迭代思想迭代思想2 Jacobi迭代和迭代和Gauss-Seidel迭代迭代3 迭代的收敛性迭代的收敛性4 迭代加速迭代加速逐次超松弛（逐次超松弛（SOR）法）法1 迭代思想迭代思想解大型稀疏型方程组比直接法存储量小解大型稀疏型方程组比直接法存储量小 条件条件:Ax=b 解存在唯一解存在唯一 设计同解变形设计同解变形 x=Gx+f 迭代式迭代式 x(k)=Gx(k-1)+f,k=1,2,取

9、初值取初值x(0)，如果收敛，如果收敛 x(k)x*,则则x*是是Ax=b的解的解 x(k)x*2 Jacobi迭代和迭代和Gauss-Seidel迭代迭代例例3.7解：变形解：变形Jacobi迭代迭代Jacobi迭代迭代初值取初值取 ，精度要求，精度要求 =10-3。计算得计算得|x(6)x(5)|10-3.Gauss-Seidel迭代迭代Gauss-Seidel迭代迭代初值取初值取 ，精度要求，精度要求 =10-3。计算得计算得|x(5)x(4)|10-3.编程计算公式编程计算公式Jacobi迭代迭代Gauss-Seidel迭代迭代迭代结束条件一般用迭代结束条件一般用|x(k)x(k-1)

10、|问题问题(1)(1)收敛性条件收敛性条件?(2)?(2)|x(k)x(k-1)|作为结作为结束条件是否可靠束条件是否可靠?计算公式矩阵形式计算公式矩阵形式和分解：和分解：A=L(下三角下三角)+D(对角对角)+U(上三角上三角)迭代迭代 x(k)=Gx(k-1)+f,k=1,2,Jacobi迭代迭代 G=-D-1(L+U)=I-D-1A f=D-1 bGauss-Seidel迭代迭代 G=-(L+D)-1 U f=(L+D)-1 b3 迭代的收敛性迭代的收敛性定理定理3.4 设设G的某种范数的某种范数|G|1，则，则x=Gx+f存存在唯一解，且对任意初值，迭代序列在唯一解，且对任意初值，迭代

11、序列x(k)=Gx(k-1)+f 收敛于收敛于x*，进一步有误差估计式，进一步有误差估计式证明思路证明思路：(1)解的存在唯一性解的存在唯一性;(2)解的收敛解的收敛性性;(3)误差估计式误差估计式(习题习题)。直接从直接从Ax=b判断判断推论推论 若若A按行严格对角占优（按行严格对角占优（），），则解则解Ax=b的的Jacobi迭代和迭代和Gauss-Seidel迭代迭代均收敛。均收敛。证明思路：用定理证明思路：用定理3.4.A严格对角占优，严格对角占优，则则无穷大范数无穷大范数|G|1Jacobi迭代迭代(直接证直接证|G|1)Gauss-Seidel迭代迭代,令令y=Gx，则，则y=-D

12、-1(Ly+Ux)先证存在某先证存在某x,|x|=1,使使|G|=|y|再证当再证当|x|=1,有有|y|1Gauss-Seidel迭代收敛性证明迭代收敛性证明记迭代矩阵记迭代矩阵存在存在m,令令那么那么 且且 Gauss-Seidel迭代收敛性证明迭代收敛性证明记记 ，其中迭代矩阵，其中迭代矩阵那么那么存在存在k使得使得所以所以充分必要条件充分必要条件谱半径谱半径(G)：G的特征值模的最大值的特征值模的最大值定定理理3.5 迭迭代代x(k)=Gx(k-1)+f对对任任意意初初值值收收敛敛(G)1.（证明较深，略）（证明较深，略）三种方法比较三种方法比较方法一方法一(推论推论):从从A判断判断

13、,A严格对角占优，则严格对角占优，则Jacobi迭代和迭代和Gauss-Seidel迭代收敛迭代收敛,充分条充分条件件,最方便最方便方法二方法二(定理定理3.4):从从G判断判断,有一种范数有一种范数|G|1,充分条件充分条件方法三方法三(定理定理3.5):从从G判断判断,谱半径谱半径(G)1,充充要条件要条件,最宽最宽P63,例例3.8（特征值的性质：特征值之和等于对角线（特征值的性质：特征值之和等于对角线元素的和）元素的和）4 逐次超松弛（逐次超松弛（SOR）法）法Gauss-Seidel迭代格式的加速迭代格式的加速收敛的必要条件收敛的必要条件0 2低松弛法低松弛法 0 1=1,Gauss-Seidel迭代迭代超超松弛法松弛法 1 2P66 例例3.9P70习题习题ex1ex2,ex3ex5,ex6ex9,ex10,ex11(2)ex13