计算方法迭代法.ppt

第三章迭代法第三章迭代法§3.1 二分法二分法§3.2 迭代法原理迭代法原理§3.3 Newton迭代法和迭代加速迭代法和迭代加速§3.4 解线性方程组的迭代法解线性方程组的迭代法2021/7/11§3.1 二分法二分法 根的估计根的估计 二分法二分法2021/7/12根的估计根的估计引理引理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 , 扫描节点函数值扫描节点函数值异号区间内有根异号区间内有根2021/7/13f(x)= x3 3x 1 2021/7/14二分法二分法条件条件: 设设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, bk=bk-1; Let xk=(ak+bk)/2. 收敛性及截断误差分析收敛性及截断误差分析:2021/7/15例例3.2 x3 3x 1 = 0, [1,2], 精度精度0.5e-12021/7/16二分法二分法优点优点算法简单算法简单收敛有保证收敛有保证只要只要f(x)连续连续缺点缺点对区间两端点选取条件苛刻对区间两端点选取条件苛刻收敛速度慢收敛速度慢2021/7/17§3.2 迭代法原理迭代法原理迭代法的思想迭代法的思想 不动点原理不动点原理 局部收敛性局部收敛性收敛性的阶收敛性的阶 2021/7/18迭代法的思想迭代法的思想 条件条件: f(x)=0 在在x0附近有且仅有一个根附近有且仅有一个根 设计同解变形设计同解变形 x=g(x) 迭代式迭代式 xk=g(xk-1), k=1,2,… 如果收敛如果收敛 xk x*, 则则x*是是f(x)=0 的的根根2021/7/19不动点原理不动点原理(迭代过程收敛迭代过程收敛)定定理理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* 。

进一步，有误差估计式进一步，有误差估计式 后验估计先验估计算法设计中迭代结束条件算法设计中迭代结束条件: 近似使用近似使用|xk-xk-1|< 2021/7/110不动点原理不动点原理证明步骤证明步骤解的存在性解的存在性; 解的唯一性解的唯一性;解的收敛性解的收敛性; 误差估计式误差估计式例例3.3 2021/7/111局部收敛性局部收敛性(格式收敛格式收敛)定理定理3.2 （（局部收敛性局部收敛性）设）设g’(x)连续连续, , 则存在充分靠近则存在充分靠近x*的初值，使迭代收敛于的初值，使迭代收敛于x*证明：利用定理证明：利用定理3.1,3.1,取取L= = 具有局部收敛性的迭代计算上不一定收敛，具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当；它是否收敛还要看初值是否取的恰当；而不具有局部收敛性的迭代对任何初值都不而不具有局部收敛性的迭代对任何初值都不可能收敛可能收敛应用中应用中: 近似使用近似使用|g'(x0)|<1判断判断2021/7/112收敛性的阶收敛性的阶(局部收敛速度局部收敛速度)定定义义3.1 当当xkx*，，记记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}平方收敛平方收敛 2021/7/1133.3 Newton迭代法和迭代加速迭代法和迭代加速 牛顿牛顿(Newton)迭代法迭代法 “迭代－加速迭代－加速”技术技术2021/7/114牛顿牛顿(Newton)迭代法迭代法原理原理(1次近似次近似, 直线代替曲线直线代替曲线)牛顿格式牛顿格式2021/7/115Newton法几何意义：切线法法几何意义：切线法切线代替曲线切线代替曲线2021/7/116Newton法局部收敛性法局部收敛性•单根：平方收敛单根：平方收敛•m重重根：线性收敛根：线性收敛•例例3.5 （（P56) –Newton迭代法，计算迭代法，计算3次达到次达到4位有效数字位有效数字– 计算计算4次达到次达到4位有效数字位有效数字•越是精度要求高越是精度要求高, Newton迭代法优势越明显迭代法优势越明显2021/7/117“迭代－加速迭代－加速”技术技术加快迭代过程的收敛速度加快迭代过程的收敛速度将发散的迭代格式加工成收敛的将发散的迭代格式加工成收敛的若若g’(x)在在x*附近大约为附近大约为D, 改进改进xk = g(xk-1) 为为 例例3.6 （（P57)2021/7/118§§4 解线性方程组的迭代法解线性方程组的迭代法 1 迭代思想迭代思想2 Jacobi迭代和迭代和Gauss-Seidel迭代迭代3 迭代的收敛性迭代的收敛性4 迭代加速迭代加速——逐次超松弛（逐次超松弛（SOR）法）法2021/7/1191 迭代思想迭代思想解大型稀疏型方程组比直接法存储量小解大型稀疏型方程组比直接法存储量小 条件条件: Ax=b 解存在唯一解存在唯一 设计同解变形设计同解变形 x=Gx+f 迭代式迭代式 x(k)=Gx (k-1)+f, k=1,2,… 取初值取初值x(0) ，如果收敛，如果收敛 x(k) x*, 则则x*是是Ax=b的解的解 x(k) x*2021/7/1202 Jacobi迭代和迭代和Gauss-Seidel迭代迭代例例3.7解：变形解：变形2021/7/121Jacobi迭代迭代Jacobi迭代迭代初值取初值取 ，精度要求，精度要求  =10-3。

计算得计算得 ||x(6)  x(5)||  10-3. 2021/7/122Gauss-Seidel迭代迭代Gauss-Seidel迭代迭代初值取初值取 ，精度要求，精度要求  =10-3计算得计算得 ||x(5)  x(4)||  10-3. 2021/7/123编程计算公式编程计算公式Jacobi迭代迭代Gauss-Seidel迭代迭代迭代结束条件一般用迭代结束条件一般用 ||x(k)  x(k-1)|| 问题问题(1)(1)收敛性条件收敛性条件? (2) ? (2) ||x(k)  x(k-1)|| 作为结作为结束条件是否可靠束条件是否可靠? ?2021/7/124计算公式矩阵形式计算公式矩阵形式和分解：和分解： 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 b2021/7/1253 迭代的收敛性迭代的收敛性定理定理3.4 设设G的某种范数的某种范数||G||<1，则，则x=Gx+f存存在唯一解，且对任意初值，迭代序列在唯一解，且对任意初值，迭代序列x(k)= Gx (k-1) + f 收敛于收敛于x*，进一步有误差估计式，进一步有误差估计式证明思路证明思路：：(1)解的存在唯一性解的存在唯一性; (2)解的收敛解的收敛性性;(3)误差估计式误差估计式( (习题习题) )。

2021/7/126直接从直接从Ax=b判断判断推论推论 若若A按行严格对角占优（按行严格对角占优（ ），），则解则解Ax=b的的Jacobi迭代和迭代和Gauss-Seidel迭代迭代均收敛证明思路：用定理证明思路：用定理3.4. A严格对角占优，严格对角占优， 则则无穷大范数无穷大范数 ||G||<1Jacobi迭代迭代(直接证直接证||G|| <1)Gauss-Seidel迭代迭代, 令令y=Gx，则，则y= -D-1(Ly+Ux)先证存在某先证存在某x, ||x||  =1, 使使||G||  =||y||  再证当再证当||x||  =1, 有有||y||  <12021/7/127Gauss-Seidel迭代收敛性证明迭代收敛性证明记迭代矩阵记迭代矩阵存在存在m,令令那么那么 且且 2021/7/128Gauss-Seidel迭代收敛性证明迭代收敛性证明记记 ，其中迭代矩阵，其中迭代矩阵那么那么存在存在k使得使得所以所以2021/7/129充分必要条件充分必要条件谱半径谱半径 (G)：：G的特征值模的最大值的特征值模的最大值定定理理3. 5 迭迭代代x(k)= Gx (k-1) + f对对任任意意初初值值收收敛敛 (G)<1. （证明较深，略）（证明较深，略）2021/7/130三种方法比较三种方法比较方法一方法一(推论推论): 从从A判断判断, A严格对角占优，则严格对角占优，则Jacobi迭代和迭代和Gauss-Seidel迭代收敛迭代收敛, 充分条充分条件件, 最方便最方便方法二方法二(定理定理3.4): 从从G判断判断, 有一种范数有一种范数||G||<1, 充分条件充分条件方法三方法三(定理定理3.5): 从从G判断判断,谱半径谱半径 (G) <1, 充充要条件要条件, 最宽最宽P63, 例例3.8（特征值的性质：特征值之和等于对角线（特征值的性质：特征值之和等于对角线元素的和）元素的和）2021/7/1314 逐次超松弛（逐次超松弛（SOR）法）法Gauss-Seidel迭代格式的加速迭代格式的加速收敛的必要条件收敛的必要条件0< <2低松弛法低松弛法 0< <1 =1, Gauss-Seidel迭代迭代超超松弛法松弛法 1< <2P66 例例3.92021/7/132P70习题习题ex1ex2,ex3ex5,ex6ex9,ex10,ex11(2)ex132021/7/133 结束语结束语若有不当之处，请指正，谢谢！若有不当之处，请指正，谢谢！。