第5节_迭代法的收敛性

1、课程回顾 迭代法的原理； 迭代法的构造； 迭代法的关键问题； 分形 迭代法解线性方程组： 最简单方法 最有效方法 Jacobi方法 Gauss-Seidel方法 SOR方法 问题：如何评价不同迭代方法的优劣？如何评价不同迭代方法的优劣？第三章第三章 线性方程组求解的数值方法线性方程组求解的数值方法第五节第五节 迭代法的收敛性迭代法的收敛性迭代法收敛性 收缩映射原理（Contraction Principle）：(1)( )121212, 01, ( ) ()()()kkx xLxxxL xxxf x：，满足则收敛fff( ) kx序列收敛证明：(1)( )( )(1)( )(1)(1)(2)2

2、(1)(2)1(1)(0)(1)(0)()() ()() . ()()kkkkkkkkkkkkxxf xf xL xxL f xf xL xxLf xf xLxx10(1)( )0, log () , LkkKkKxxxx 满足：收缩映射xx 表示取大于 的整数线性方程组迭代法收敛性lim0( )1kkAnAA引理：设 为 阶方阵，则的充要条件为。lim0lim0 (A)A 0()lim ()=0() ( ) lim ( ) =0( )1kkkkkkkkkkkkAAAAAAAAA：证：必要性 若 由矩阵收敛的定义知 又因 由夹逼定理，有 。又由于： 则： 谱半径谱半径-1=.= ( )kkkk

3、kkkuAA uA uuAAA证：设 为 特征值 对应的特征向量，则：即：为矩阵的特征值。所以：（）线性方程组迭代法收敛性-11-( )( )1021( )( )12lim00.,lim0.kkkkkkkAAAAAAAAAAA：证： 充分性若，取，存在矩阵范数，使得 则有： 由算子范数相容性，可得： 由夹逼定理，可得： ,( )AnAA：定理：设 为任意 阶方阵，则对任意正数存在矩阵范数，使得线性方程组迭代法收敛性*( )*( -1)*( -1)*2( -2)( )*(0)*() -() () = . . kkkkkkxxxMxgxxMxgMxxgM xxMxxxMxx性质：证明：如果 存在，

4、则 满足： (0)* . (-)kMxx 第第1步迭代与第步迭代与第k步迭代关系。步迭代关系。线性方程组迭代法收敛性(0)(1)( )( ) ()1kkkxgxMxgxM定理：对任意初始向量和右端项 ，由迭代式产生的向量序列收敛是充要条件的.*( )*( )*(0)*(0)( )*(0)*limli-(-m(-)0lim(-)0lim()0). 1kkkkkkkkkknxxxxxMxgxxMxxxnMxxMxMx证:必要性: 设存在 维向量,使得 则 满足 由迭代公式有: 于是有 因为为任意 维向量,因此上式成立必须 由上一定理 线性方程组迭代法收敛性( )*( -1)*(0)0)*()11-

5、0-l im0l-(-)(-)im(-)limkkkkkkkkMMI MngI MxgxxMxxM xxMxxxgMxxx 充分性：若,则不是的特征值,因而有,于是对任意 维向量 ,方程组（）有唯一解,记为,即 并且 又因为 所以,对任意初始向量,都有 (0)*(1)( )( ).(-0kkkkMxxxMxgx即由迭代公式产生的向量序列收敛11111011,)00,()0,max1,xBBIBIB xxIB xBxxBxBxBxx性质：若矩阵 的某个算子范数则必有可逆证明：反证法：设(有非零解，即： 使得即： 与已知矛盾！线性方程组迭代法收敛性线性方程组迭代法收敛性(0)(1)( )( )1k

6、kkxgMxMxgx推论1： 对任意初始向量和右端项 ，若, 由迭代式 产生的向量序列收敛.( )|AA证明：矩阵范数性质3： 迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向量及右端项无关。 对同一方程组，由于不同的迭代法迭代矩阵不同，可能出现有的方法收敛，有的方法发散的情形。迭代法收敛性：1231231232-212223-112-2100111010221001000-100-2-20 xxxxxxxxxJacobiGauss SeidelADL 例：对方程组讨论迭代法与迭代法的收敛性。 解：求迭代矩阵判别其谱半径是否小于。 0-2200-1000U 迭代法收敛性：-131230-22-

7、10-1-2-202-2-110220,( )01,JacobiBI D AI BBJacobi 迭代法的迭代矩阵为 其特征方程为 因此有于是所以迭代法收敛。迭代法收敛性：-1-121-100100-110(- )-1102210-211000-220-22(- )-11000-102-30-210000022-2-0-23( -2)000-20,Gauss SeidelD LD LMD LUI M 迭代，由 特征方程 特征值为232,()21,M故所以迭代发散。SOR迭代收敛性：1212-1-11122202,.,det(). ()det()1det()(-)(1-)1(-).(1-)nnn

8、nnMMMMMDLDUDLa aaD 推论 ： 松弛法收敛的必要条件是。证明：设松弛法的迭代矩阵有特征值。因为 由定理，松弛法收敛必有 又因为 1122(1-).det()(1-)102nnnnUa aaM 。特殊矩阵收敛性的判定：1()(1,2, , )nijiiijjj inAaaaiL niAiA定义：若 阶方阵满足且至少有一个 值，使上式中不等号严格成立，则称 为。若对所有，上式不等号均严格成立，则称 弱对角占优阵严为格角占优阵。1112112222,0AAAAAAAA定义：如果矩阵 不能通过行的互换和相应的列互换成为形式 其中，为方阵，则称 为不可约。1311021011001101

9、2011P ITAP AP 例： Gauss-Seidel迭代收敛性：,1.-2.01,3.02AxbAJacobiGauss SeidelAA（）设有线性方程组下列结论成立：若 为严格对角占优阵或不可约弱对角占优阵，则迭代法和迭代法均收敛。若 为严格对角占优阵，则松弛法收敛。若 为对称正定阵，则松弛法收敛的充要条件为教材定理3.3。注：注：Gauss-Seidel法为法为SOR法的特例。法的特例。Gauss-Seidel迭代收敛性：-11112211,122111223-(02)1110-2211-0-2211-022Axb AAAGauss SeidelAJacobiBI D A例：讨论用

10、三种迭代法求解的收敛性。解：因 为对称且其各阶主子式皆大于零，故 为对称正定矩阵。由判别条件 ，迭代法与松弛法均收敛。不是严格对角占优阵，故不能用条件 判断。 迭代法的迭代矩阵为Gauss-Seidel迭代收敛性：3212311221131-224411221( -) (1)021,-1,( )12I BBJacobi其特征方程 得 因而 迭代法不收敛。三种算法收敛性各有优劣。三种算法收敛性各有优劣。Gauss-Seidel迭代收敛性：3-10,9-4-10100-033,915-00423015( ), ()22Axb AJacobiGauss SeidelBMBM， 例： 与迭代的迭代矩注

11、意：改变方程组中方程的次序，即将系数矩阵作行交换，会改变迭代法的收敛阵分别为 谱半径分别是性。均不收敛。Gauss-Seidel迭代收敛性：,3-109-49-43-10- AxbAxbAAAAxbJacobiGauss Seidel 若交换方程的次序，得的同解方程组 为严格对角占优阵，因而对方程组用与迭代求解均收敛。线性方程组迭代法收敛速度*( )*(0( )*-1(0)*(0)-1-1(0)(1)*-1)-()()() () () ()( -) kkkkkkxxxxMxxMxIMgMIMIM xxxMIMxxI Mgxg性质：证明：如果 存在，则 满足： -1(0)1 () kMIMxx（

12、 ）线性方程组迭代法收敛速度(1)( )( )*( )*(1)(0)1 -1-kkkkkxMxgMxxMxxxxM 定理：设有迭代公式,若,收敛于,则有误差估计式： -1*( )*-1(0)1-1( )*(1( )*-1(01)( )0()10()()1)1.15()kkkkkkMMIMIMxMxgxxxMIMxxIMMMxxxxxxMIMxMx（ ）（ ）证：因,故,于是存在，方程组有唯一解 ，取范数 又因为 （）代入得 性 矩阵范数质(1)(0)(1)ln lnMxxkkM根据事先给定的精度 ，可估计出迭代的次数 :线性方程组迭代法收敛速度(0)(1)4(1)(0)00.10.207.20

13、.100.20 ,8.3 100.20.2008.40.4,-8.412.932,13MxxMxxk 例：若,则有 即需迭代 次才能满足精度。线性方程组迭代法收敛速度*-1( )*(1)*(1)-1-1( )*-1(1)()1( -)-()()() () () () kkkkkkkxxxI MgxxM xxM xIMgM IMIM xxxMMxxgI性质：证明：如果 存在，则 满足： -1(1) () kkM IMxx（ ）迭代法收敛速度(1)( )( )*( )*( )(1)1 1kkkkkkxMxgMxxMxxxxM 定理：设有迭代公式,若,收敛于,则有误差估计式：( )*-1( -1)(

14、 )( )*-1( -1)( )( )( -1)-( -) (-)-( -)-.1-kkkkkkkkxxM I MxxxxMI MxxMxxM证：因 ( )( -1)11-kkMMxxM当不太接近 时，可用（）作为停机准则。迭代法算法结构-Matlab(1)( )i;.1 ,f ,JGMSkMkMxMMgMxggM/-迭代方程 / 初始化：/ 初始化迭代矩阵/ ; 初始化/ 计算迭代方程谱半径 / 谱半径大于等于1，迭代 ; 法不收敛。0 ;.;retu.rnend;while;xxeee / 终止迭代。/ 初始化变量x/ 定义迭代误差容限/ 初始化迭代误差:/ 迭代 ; ： (1) ;-;

15、1-ktmpxxMxgMex tmpxM （/ 如果迭代误差大于门限，继续执行/计算/计算迭代） 误差 111111 : (), (), () () (1) : :()JGSSORMID AgD bMDJacobiGaussLU gDLbMDLDUgSeideDSORLb11121112122212313231121.nnnnnnnnnnnaaaaaaaaAaaaaaaaDLU注意：注意：L L、U U 前有负号前有负号迭代法算法结构-Matlab1 AIIA 矩阵求逆： :aussSeidel:JacobiG对角矩阵求逆三角矩阵求逆 上述两种算法计算上述两种算法计算M矩阵过程运算量小矩阵过程

16、运算量小于矩阵于矩阵A求逆。求逆。迭代法算法低级语言实现(0)(0)(0)(0)1(012(0)(0)11.(),( ,.,),(,.,),.2.1.3.1,2,.,4.-,55.,1(,(1,2,., ),)/3-ijnniniiijjiiijj ixba xAabbbn xxxxNkinx xxkaNkk xxin 输入维数最大容许迭代次数置对 若输出 停机；否则转 。若置转 ；否则，输出失败 信息，停机。JacobiJacobi算法：算法：( )(1,kkMxx ）评价：公式简单，每迭代一次只需计算一次矩阵和向量的乘法，不改变的稀疏性，需两组工作单元，存。迭代法算法低级语言实现(0)(0

17、)(0)(0)(0)112111112-1(0)111.(),( ,.,),(,.,(-)/(-)/(2,)., ,., -.2.11.3.)njjjinijnniiijjijjiijj inAabbbn xxxxNkxba xaxba xa xainx 输入维数最大容许迭代次数置计算 -11(0)(0)4.-,55.,1,(1,2,.(-)/., ),3nnnjjnnjiix xxkNkk xxinba xa 若输出 停机；否则转 。若置转 ；否则，输出失败信息，停机。Gauss-SeidelGauss-Seidel算法：算法：迭代法算法低级语言实现(0)(0)1111112-1(0)(0)

18、11(0)(0)(0)(0)1121.(),(1-)(-),.,),(,.,),./(1-)(-2.1.3.-)/(ijnnjjjiniiiijjijjiijinjAabbbn xxxxba xaxxba xkxNaxax 输入维数最大容许迭代次数 ，参数置计算 (0)(0)-1(0)12,., -1)(1-)(4.-,55.,1,(1,2,.-)/., ),3nnnnnjjjiinnix xxkNkk xxinnxxba xa 若输出 停机；否则转 。若置转 ；否则，输出失败 信息，停机。SORSOR算法：算法：Matlab语言实现和低级语言实现比较 高级语言中需要进行求逆运算、计算谱半径，

19、实际工程中可能找不到相关库函数。 低级语言实现无需计算矩阵求逆，但是无法事先判断迭代是否成功，另外迭代终止条件存在误差,迭代过程中计算量较大。习题例：教材习题5121-2-1-2-1;-31-1-31()-311-1-31()-11MMaaaaMaaaMa解：步骤一、写出矩阵：步骤二、计算特征值： 步骤三、讨论： 2222131131 113111 1aaaaaa （） （）（） （） 0.5,2/3)(0,0.5)aa 单调递增单调递增单调递减单调递减习题例：教材习题5-0.500.511.50.511.522.533.5A = 2, 1; 1, 2B = eye(2) for iii = 1 : 1000 a = iii / 500; a = a - 0.5; M =