为不可约矩阵(PPT课件)

16.3.2关于解某些特殊方程组迭代法的收敛性定义3(1)如果的元素满足A).,,2,1(1niaanijjijii称为严格对角占优阵.A(2)如果的元素满足A).,,2,1(1niaanijjijii且上式至少有一个不等式严格成立，称为弱对角占优阵.A(对角占优阵).)(nnijaA设2定义4设,)2()(naAnnij如果存在置换阵使P,0221211AAAAPPT（3.6）其中为阶方阵，为阶方阵，11Ar22Arn)1(nr为可约矩阵.A否则，如果不存在这样置换阵使(3.6)式成立，则P称为不可约矩阵.A(可约与不可约矩阵)则称为可约矩阵意即可经过若干行列重排化为(3.6)或AA3可化为两个低阶方程组求解.bAx如果经过两行交换的同时进行相应两列的交换，A称对进行一次行列重排.A事实上，由可化为bAx,)(bPxPAPPTTT且记2121,ddbPyyxPyTT于是，求解化为求解bAx11,dyr其中为维向量.4.,22221212111dyAdyAyA由上式第2个方程组求出,2y显然，如果所有元素都非零，则为不可约阵.AA.1y再代入第1个方程组求出5例7,11122211nnnnnbacbacbacbA则都是不可约矩阵.BA,.4110140110410114B),,(都不为零iiicba设有矩阵6定理6如果为严格对角nnijaA)(占优矩阵或为不可约弱对角占优矩阵，A则为非奇异矩阵.A证明只就为严格对角占优阵证明此定理.A采用反证法，如果，0)det(A则有非零解，0Ax记为,Tnxxxx),,,(21由齐次方程组第个方程k,01njjkjxa则有(对角占优定理).0max1inikxx则7,111nijjkjknijjjkjnijjjkjkkkaxxaxaxa,1nijjkjkkaa即与假设矛盾，故.0)det(A8定理7设,bAx(1)为严格对角占优阵，则解的雅可比迭代法，高斯-塞德尔迭代法均收敛.AbAx(2)为弱对角占优阵，且为不可约矩阵，则解雅可比迭代法，高斯-塞德尔迭代法均收敛.AAbAx证明如果：只证(1)中高斯-塞德尔迭代法收敛，其他同理.由设可知，，解的高斯-塞德尔迭代法的迭代矩阵为),,1(0niaiibAx)()(1ULDAULDG9下面考查的特征值情况.G))(det()det(1ULDIGI由于,0))det((1LD于是特征值即为G0))(det(ULD之根.ULDC)().)(det())det((1ULDLD记,212222111211nnnnnnaaaaaaaaa10下面证明，当时，，即的特征值均满足，10)det(CG1事实上，当时，1由为严格对角占优阵，Aiiiiac这说明，当时，矩阵为严格对角占优阵，1C再由对角占优定理有.0)det(C由基本定理，则有高斯-塞德尔迭代法收敛.有nijijijijaa111nijijijijaa111nijjijc1).,,2,1(ni11证明有，1)(L设的特征值为，Ln,,,21定理8nL21)det(或)()det(/1LLn另一方面))1det((])det[()det(1UDLDL(SOR方法收敛的必要条件)bAx设解方程组的SOR迭代法收敛，.20则由SOR迭代法收敛，则由定理4的推论中的(3)则,)(nL.1,)1(n12从而,11)det(/1nL即.20定理8说明解的SOR迭代法，只有在范围内取松弛因子，才可能收敛.bAx)2,0(定理9设，bAx(1)为对称正定矩阵，A;ULDA.20)2(则解的SOR迭代法收敛.bAx如果：13证明在上述假定下，只需证明，1其中为L的任一特征值.事实上，设为对应的的特征向量，yL,yyL亦即.)())1((yLDyUD即,0),,,(21Tnyyyy,))1(()(1yyUDLD为了找出的表达式，考虑数量积),,)((),))1(((yyLDyyUD14则,),(),(),(),(),(yLyyDyyUyyDyyDy显然niiiiyayDy12),(记,i),(yLy由于TAA所以,TLU),(),(LyyyUy（3.7）,0故),(yLy,i),(0yAy),)((yyULD（3.8）,215所以,i)(i)(从而.)()(2222222当时，利用(3.7)，(3.8)，有20)2)(2()()(22当时，20即的任一特征值满足，1L.0)(222故SOR方法收敛可以证明,016定理10设，bAx(1)为严格对角占优矩阵(或为弱对角占优不可约矩阵)；AA.10)2(如果：则解的SOR迭代法收敛.bAx下面讨论迭代法的收敛速度.由定理3证明中可知，如果且越小时，1)(B)(B迭代法收敛越快.17及一阶定常迭代法),,1,0()()1(kfBxxkk（3.9）且设迭代法收敛，记，*lim)(xxkk现设有方程组nnBfBxxR,.**fBxx则,)0()(kkB由基本定理有,1)(0B*)()(xxkk且误差向量故.)0()(kkB18设为对称矩阵，则有B2)0(22)(kkB欲使.10)(skB取对数，得到所需最少迭代次数为.)(ln10lnBsk（3.10）.)(2)0(kB这说明，所需迭代次数与成反比.)(lnBR越小，越大，由(3.10)式所需迭代次数越少，即迭代法收敛越快.1)(B)(lnBR19对于SOR迭代法希望选择松弛因子使迭代过程(2.10)收敛较快，定义5称为迭代法(3.9)的渐近收敛)(ln)(BBR在理论上即确定使opt).()(min20optLL对某些特殊类型的矩阵，已建立了SOR方法最佳松弛因子理论.例如，对所谓具有“性质”等条件的线性方程组建立了最佳松弛因子公式A速度，简称迭代法收敛速度.20其中为解的雅可比迭代法的迭代矩阵的谱半径.)(JbAx在实际应用中，对于某些椭圆型微分方程(模型问题)，可以给出的计算方法，opt但一般来说，计算是有困难的，可用试算的办法来确定一个适当的.opt算法2设，bAx其中为对称正定A,))((1122Jopt(SOR迭代法)矩阵或为严格对角占优阵或为弱对角占优不可约矩阵等，210.1k本算法用SOR迭代法求解，bAx数组存放)(nx)0(x及)(kx用控制迭代终止，epsxpini10max用表示最大0N迭代次数.),,2,1(0.0.2nixi1.3kk0.0.40pni,,2,1.5对于iinijjijijjijiiaxaxabxp/)(111）（22pppp00)2(则如果也可用来控制迭代终止，其中epsrk)(.)()(kkAxbrpxxii)3(0.6p输出停机则输出如果,,,.70xkepsp3.80则转如果Nk及有关信息输出0.9N236.4分块迭代法24上述迭代法，从计算时，是逐个计算的分量，这种迭代法又称为点迭代法.)1()(kkxx)1(kx),,2,1()1(nixki分块迭代法，就是一块或一组未知数同时被改进.设，其中为大型稀疏矩阵且将分块为三部分，bAxnnARAULDA,212222111211qqqqqqAAAAAAAAAA,2211qqAAAD25,0002121qqAAAL且为非奇异矩阵，),,2,1(qiAiiiinn.1nnqii对及同样分块xb,21qxxxx.0002112qqAAAU,21qbbbb其中，.R,Riininibx26(1)块雅可比迭代法(BJ)选取分裂阵为的对角块部分，即选MA.NMADM(块对角阵)于是，得到块雅可比迭代法fBxxkk)()1(（4.1）其中迭代矩阵,)(11JULDADIB或.)()()1(bxULDxkk.1bDf27由分块矩阵乘法，得到块雅可比迭代法的具体形式),,,2,1(1)()1(qixAbxAqijjkjijikiii（4.1）其中.R,)()()(2)(1)(inkikqkkkxxxxx这说明，块雅可比迭代法每迭代一步，从，)1()(kkxx需要求解个低阶方程组q28.式右边部分为其中）（12.3),,,2,1()(iikiiigqigxA(2)块SOR迭代法(BSOR)选取分裂矩阵为带松弛因子的块下三角部分，MA.),(1NMALDM得到块SOR迭代法,)()1(fxLxkk（4.3）即29其中迭代矩阵ALDIL1)(由分块矩阵乘法得到块SOR迭代法的具体形式为松弛因子.),,1,0;,,2,1()()(11)1()()1(kqixAxAbxAxAqijkjijijkjijikiiikiii（4.4）),)1(()(1UDLD,)(1bLDf30于是，当已计算时，解低阶方程组(3.14)可计算小块)(kx)1,,2,1()1(ijxkj.)1(kix从共需要解个低阶方程组，当为三对角阵或带状矩阵时，可用直接法求解.)1()(kkxxqiiA定理11设，其中(分块形式).bAxULDA(1)如果为对称正定矩阵，A则解的BSOR迭代法收敛.bAx.20(2)