《第三章迭代法精选文档.ppt》由会员分享，可在线阅读，更多相关《第三章迭代法精选文档.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章迭代法第三章迭代法本讲稿第一页，共三十六页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。解解:单调性分析和解的位置单调性分析和解的位置选步长选步长h=2,扫描节点函数值扫描节点函数值异号区间内有根异号区间内有根本讲稿第三页，共三十六页f(
2、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)let ak=xk-1,
3、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
4、)=0 在在x0附近有且仅有一个根附近有且仅有一个根 设计同解变形设计同解变形 x=g(x)迭代式迭代式 xk=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
5、(xk-1)收敛于收敛于x*。进一步，有误差估计式。进一步，有误差估计式 后验估计先验估计算法设计中迭代结束条件算法设计中迭代结束条件:近似使用近似使用|xk-xk-1|本讲稿第十页，共三十六页不动点原理不动点原理例例3.3 x3 x 1=0，1,2,x0=1.5,本讲稿第十一页，共三十六页不动点原理不动点原理证明步骤证明步骤解的存在性解的存在性;解的唯一性解的唯一性;解的收敛性解的收敛性;误差估计式。误差估计式。本讲稿第十二页，共三十六页局部收敛性局部收敛性(格式收敛格式收敛)定理定理3.2（局部收敛性局部收敛性）设）设g(x)连续连续,则存在充分靠近则存在充分靠近x*的初值，使迭代收敛于的
6、初值，使迭代收敛于x*。证明：利用定理证明：利用定理3.1,3.1,取取L=具有局部收敛性的迭代计算上不一定收敛，具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当；它是否收敛还要看初值是否取的恰当；而不具有局部收敛性的迭代对任何初值都不而不具有局部收敛性的迭代对任何初值都不可能收敛。可能收敛。应用中应用中:近似使用近似使用|g(x0)|1判断判断本讲稿第十三页，共三十六页收敛性的阶收敛性的阶(局部收敛速度局部收敛速度)定定义义3.1 当当xkx*，记记ek=x*-xk，若若存存在在实实数数p，使，使ek+1/epk c 0，则称则称xk有有p p阶收敛速度阶收敛速度。线性
7、收敛线性收敛 p=1平方收敛平方收敛 p=2 本讲稿第十四页，共三十六页收敛性的阶收敛性的阶(局部收敛速度局部收敛速度)定理定理3.3 设设xk=g(xk-1)x*，则，则(1)当当g(x*)0时，时，xk线性收敛；线性收敛；(2)当当g(x*)=0,而而g(x*)0时，时，xk平方收敛。平方收敛。证明证明(2)本讲稿第十五页，共三十六页3.3 Newton迭代法和迭代加速迭代法和迭代加速 牛顿牛顿(Newton)迭代法迭代法“迭代加速迭代加速”技术（略）技术（略）本讲稿第十六页，共三十六页牛顿牛顿(Newton)迭代法迭代法原理原理(1次近似次近似,直线代替曲线直线代替曲线)牛顿格式牛顿格式
8、本讲稿第十七页，共三十六页Newton法几何意义：切线法法几何意义：切线法切线代替曲线切线代替曲线本讲稿第十八页，共三十六页Newton法局部收敛性法局部收敛性单根：平方收敛单根：平方收敛m重根：线性收敛重根：线性收敛,f(x)=(x-x*)mq(x),q(x*)0,例例3.5（P56)Newton迭代法，计算迭代法，计算3次达到次达到4位有效数字位有效数字 计算计算4次达到次达到4位有效数字位有效数字越是精度要求高越是精度要求高,Newton迭代法优势越明显迭代法优势越明显本讲稿第十九页，共三十六页“迭代加速迭代加速”技术技术(略略)加快迭代过程的收敛速度加快迭代过程的收敛速度将发散的迭代格
9、式加工成收敛的将发散的迭代格式加工成收敛的若若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)
10、=Gx(k-1)+f,k=1,2,取初值取初值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.本讲稿第二十五
11、页，共三十六页编程计算公式编程计算公式Jacobi迭代迭代Gauss-Seidel迭代迭代迭代结束条件一般用迭代结束条件一般用|x(k)x(k-1)|问题问题(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
12、+D)-1 b本讲稿第二十七页，共三十六页3 迭代的收敛性迭代的收敛性定理定理3.4 设设G的某种范数的某种范数|G|1，则，则x=Gx+f存存在唯一解，且对任意初值，迭代序列在唯一解，且对任意初值，迭代序列x(k)=Gx(k-1)+f 收敛于收敛于x*，进一步有误差估计式，进一步有误差估计式证明思路证明思路：(1)解的存在唯一性解的存在唯一性;(2)解的收敛解的收敛性性;(3)误差估计式误差估计式(习题习题)。本讲稿第二十八页，共三十六页直接从直接从Ax=b判断判断推论推论 若若A按行严格对角占优（按行严格对角占优（），），则解则解Ax=b的的Jacobi迭代和迭代和Gauss-Seidel
13、迭代均迭代均收敛。收敛。证明思路：用定理证明思路：用定理3.4.A严格对角占优，严格对角占优，则则无穷大范数无穷大范数|G|1Jacobi迭代迭代G=-D-1(L+U)(直接证直接证|G|1)Gauss-Seidel迭代迭代,令令 ，先证存在某先证存在某x,|x|=1,使使|=|y|再证当再证当|x|=1,有有|y|1本讲稿第二十九页，共三十六页Jacobi迭代迭代(直接证直接证|G|1)G=-D-1(L+U)本讲稿第三十页，共三十六页Gauss-Seidel迭代收敛性证明迭代收敛性证明记迭代矩阵记迭代矩阵存在存在m,令令那么那么 且且 本讲稿第三十一页，共三十六页Gauss-Seidel迭代
14、收敛性证明迭代收敛性证明记记 ，其中迭代矩阵，其中迭代矩阵那么那么存在存在k使得使得所以所以本讲稿第三十二页，共三十六页充分必要条件充分必要条件谱半径谱半径(G)：G的特征值模的最大值的特征值模的最大值定定理理3.5 迭迭代代x(k)=Gx(k-1)+f对对任任意意初初值值收收敛敛(G)1.（证明较深，略）（证明较深，略）本讲稿第三十三页，共三十六页三种方法比较三种方法比较方法一方法一(推论推论):从从A判断判断,A严格对角占优，则严格对角占优，则Jacobi迭代和迭代和Gauss-Seidel迭代收敛迭代收敛,充分条充分条件件,最方便最方便方法二方法二(定理定理3.4):从从G判断判断,有一
15、种范数有一种范数|G|1,充分条件充分条件方法三方法三(定理定理3.5):从从G判断判断,谱半径谱半径(G)1,充充要条件要条件,最宽最宽P63,例例3.8（特征值的性质：特征值之和等于对角线元素（特征值的性质：特征值之和等于对角线元素的和）的和）本讲稿第三十四页，共三十六页4 逐次超松弛（逐次超松弛（SOR）法）法Gauss-Seidel迭代格式的加速迭代格式的加速收敛的必要条件收敛的必要条件0 2低松弛法低松弛法 0 1=1,Gauss-Seidel迭代迭代超超松弛法松弛法 1 2P66 例例3.9本讲稿第三十五页，共三十六页P70习题习题ex1ex2,ex3ex5,ex6ex9,ex10,ex11(2)ex13本讲稿第三十六页，共三十六页