《计算方法迭代法》PPT课件.ppt
第三章迭代法,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 证明x33x1=0 有且仅有3个实根，并确定根的大致位置使误差不超过=0.5。解:单调性分析和解的位置选步长h=2,扫描节点函数值异号区间内有根,f(x)=x33x1,二分法,条件:设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.,收敛性及截断误差分析:,例3.2 x33x1=0,1,2,精度0.5e-1,二分法,优点算法简单收敛有保证只要f(x)连续缺点对区间两端点选取条件苛刻收敛速度慢,3.2 迭代法原理,迭代法的思想 不动点原理 局部收敛性收敛性的阶,迭代法的思想,条件:f(x)=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(xk-1)收敛于x*。进一步，有误差估计式,算法设计中迭代结束条件:近似使用|xk-xk-1|,不动点原理,证明步骤解的存在性;解的唯一性;解的收敛性;误差估计式。例3.3,局部收敛性(格式收敛),定理3.2（局部收敛性）设g(x)连续,则存在充分靠近x*的初值，使迭代收敛于x*。证明：利用定理3.1,取L=具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当；而不具有局部收敛性的迭代对任何初值都不可能收敛。,应用中:近似使用|g(x0)|1判断,收敛性的阶(局部收敛速度),定义3.1 当xkx*，记ek=x*-xk，若存在实数p，使ek+1/epk c0，则称xk有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迭代法和迭代加速,牛顿(Newton)迭代法“迭代加速”技术,牛顿(Newton)迭代法,原理(1次近似,直线代替曲线)牛顿格式,Newton法几何意义：切线法,切线代替曲线,Newton法局部收敛性,单根：平方收敛m重根：线性收敛例3.5（P56)Newton迭代法，计算3次达到4位有效数字 计算4次达到4位有效数字越是精度要求高,Newton迭代法优势越明显,“迭代加速”技术,加快迭代过程的收敛速度将发散的迭代格式加工成收敛的若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,取初值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)|问题(1)收敛性条件?(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 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迭代均收敛。证明思路：用定理3.4.A严格对角占优，则无穷大范数|G|1Jacobi迭代(直接证|G|1)Gauss-Seidel迭代,令y=Gx，则y=-D-1(Ly+Ux)先证存在某x,|x|=1,使|G|=|y|再证当|x|=1,有|y|1,Gauss-Seidel迭代收敛性证明,记迭代矩阵存在m,令那么 且,Gauss-Seidel迭代收敛性证明,记，其中迭代矩阵那么存在k使得所以,充分必要条件,谱半径(G)：G的特征值模的最大值定理3.5 迭代x(k)=Gx(k-1)+f对任意初值收敛(G)1.（证明较深，略）,三种方法比较,方法一(推论):从A判断,A严格对角占优，则Jacobi迭代和Gauss-Seidel迭代收敛,充分条件,最方便方法二(定理3.4):从G判断,有一种范数|G|1,充分条件方法三(定理3.5):从G判断,谱半径(G)1,充要条件,最宽P63,例3.8（特征值的性质：特征值之和等于对角线元素的和）,4 逐次超松弛（SOR）法,Gauss-Seidel迭代格式的加速收敛的必要条件02低松弛法 01=1,Gauss-Seidel迭代超松弛法 12P66 例3.9,P70习题,ex1ex2,ex3ex5,ex6ex9,ex10,ex11(2)ex13,
