为严格对角占优阵

《为严格对角占优阵》由会员分享，可在线阅读，更多相关《为严格对角占优阵（31页珍藏版）》请在装配图网上搜索。

1、1 6.3.2 关于解某些特殊方程组迭代法的收敛性关于解某些特殊方程组迭代法的收敛性 定义定义3 3 (1)如果 的元素满足 A).,2,1(1niaanijjijii称 为严格对角占优阵严格对角占优阵.A (2)如果 的元素满足 A).,2,1(1niaanijjijii且上式至少有一个不等式严格成立，称 为弱对角占优阵弱对角占优阵.A(对角占优阵).)(nnijaA设 2 定义定义4 4设 ,)2()(naAnnij如果存在置换阵 使P,0221211AAAAPPT（3.6）其中 为 阶方阵，为 阶方阵 ，11Ar22Arn)1(nr 为可约矩阵可约矩阵.A 否则，如果不存在这样置换阵 使

2、(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 7,11122211nnnnnbacba

3、cbacbA则 都是不可约矩阵.BA,.4110140110410114B),(都不为零iiicba设有矩阵 6 定理定理6 6如果 为严格对角nnijaA)(占优矩阵或 为不可约弱对角占优矩阵，A则 为非奇异矩阵.A 证明证明只就 为严格对角占优阵证明此定理.A 采用反证法，如果 ，0)det(A则 有非零解，0Ax记为 ,Tnxxxx),(21 由齐次方程组第 个方程 k,01njjkjxa则有(对角占优定理).0max1inikxx则 7,111nijjkjknijjjkjnijjjkjkkkaxxaxaxa,1nijjkjkkaa即 与假设矛盾，故.0)det(A8 定理定理7 7 设

4、 ,bAx (1)为严格对角占优阵，则解 的雅可比迭代法，高斯-塞德尔迭代法均收敛.AbAx (2)为弱对角占优阵，且 为不可约矩阵，则解 雅可比迭代法，高斯-塞德尔迭代法均收敛.AAbAx 证明证明如果：只证(1)中高斯-塞德尔迭代法收敛，其他同理.由设可知，解 的高斯-塞德尔迭代法的迭代矩阵为),1(0niaiibAx)()(1ULDAULDG9 下面考查 的特征值情况.G)(det()det(1ULDIGI由于 ,0)det(1LD于是 特征值即为G0)(det(ULD之根.ULDC)().)(det()det(1ULDLD记,212222111211nnnnnnaaaaaaaaa10

5、下面证明，当 时，即 的特征值均满足 ，10)det(CG1 事实上，当 时，1由 为严格对角占优阵，Aiiiiac 这说明，当 时，矩阵 为严格对角占优阵，1C再由对角占优定理有.0)det(C由基本定理，则有高斯-塞德尔迭代法收敛.有 nijijijijaa111nijijijijaa111nijjijc1).,2,1(ni11 证明证明有 ，1)(L设 的特征值为 ，Ln,21 定理定理8 8nL21)det(或)()det(/1LLn另一方面)1det()det()det(1UDLDL(SOR方法收敛的必要条件)bAx 设解方程组 的SOR迭代法收敛，.20则由SOR迭代法收敛，则由定

6、理4的推论中的(3)则,)(nL.1,)1(n12从而,11)det(/1nL即.20 定理8说明解 的SOR迭代法，只有在 范围内取松弛因子 ，才可能收敛.bAx)2,0(定理定理9 9设 ，bAx (1)为对称正定矩阵，A;ULDA.20)2(则解 的SOR迭代法收敛.bAx 如果：13 证明证明在上述假定下，只需证明 ，1其中 为L的任一特征值.事实上，设 为对应 的 的特征向量，yL,yyL亦即.)()1(yLDyUD即,0),(21Tnyyyy,)1()(1yyUDLD为了找出 的表达式，考虑数量积),)(),)1(yyLDyyUD14则,),(),(),(),(),(yLyyDyy

7、UyyDyyDy显然 niiiiyayDy12),(记,i),(yLy由于 ，TAA 所以 ,TLU),(),(LyyyUy（3.7）,0故),(yLy,i),(0yAy),)(yyULD（3.8）,215所以,i)(i)(从而.)()(2222222 当 时，利用(3.7)，(3.8)，有 20)2)(2()()(22 当 时，20即 的任一特征值满足 ，1L.0)(222故SOR方法收敛可以证明,016 定理定理1010设 ，bAx (1)为严格对角占优矩阵(或 为弱对角占优不可约矩阵)；AA.10)2(如果：则解 的SOR迭代法收敛.bAx 下面讨论迭代法的收敛速度.由定理3证明中可知，

8、如果 且 越小时，1)(B)(B迭代法收敛越快.17及一阶定常迭代法),1,0()()1(kfBxxkk（3.9）且设迭代法收敛，记 ，*lim)(xxkk 现设有方程组nnBfBxxR,.*fBxx则,)0()(kkB 由基本定理有 ,1)(0B*)()(xxkk且误差向量 满足 故.)0()(kkB18 设 为对称矩阵，则有 B2)0(22)(kkB欲使.10)(skB 取对数，得到所需最少迭代次数为.)(ln10lnBsk（3.10）.)(2)0(kB 这说明，所需迭代次数与 成反比.)(lnBR 越小，越大，由(3.10)式所需迭代次数越少，即迭代法收敛越快.1)(B)(lnBR19

9、对于SOR迭代法希望选择松弛因子 使迭代过程(2.10)收敛较快，定义定义5 5称 为迭代法(3.9)的渐近收敛渐近收敛)(ln)(BBR在理论上即确定 使 opt).()(min20optLL 对某些特殊类型的矩阵，已建立了SOR方法最佳松弛因子理论.例如，对所谓具有“性质 ”等条件的线性方程组建立了最佳松弛因子公式A速度速度，简称迭代法收敛速度迭代法收敛速度.20其中 为解 的雅可比迭代法的迭代矩阵的谱半径.)(JbAx 在实际应用中，对于某些椭圆型微分方程(模型问题)，可以给出 的计算方法，opt 但一般来说，计算 是有困难的，可用试算的办法来确定一个适当的 .opt 算法算法2 2设

10、，bAx 其中 为对称正定A,)(1122Jopt(SOR迭代法)矩阵或为严格对角占优阵或为弱对角占优不可约矩阵等，210.1k 本算法用SOR迭代法求解 ，bAx 数组 存放 )(nx)0(x及，)(kx用 控制迭代终止，epsxpini10max用 表示最大0N迭代次数.),2,1(0.0.2nixi1.3 kk0.0.40pni,2,1.5对于iinijjijijjijiiaxaxabxp/)(111）（22pppp00)2(则如果 也可用 来控制迭代终止，其中 epsrk)(.)()(kkAxbrpxxii)3(0.6p输出停机则输出如果,.70 xkepsp3.80则转如果Nk 及有

11、关信息输出0.9N236.4 分块迭代法分块迭代法24 上述迭代法，从 计算时，是逐个计算的分量 ，这种迭代法又称为点迭代法.)1()(kkxx)1(kx),2,1()1(nixki 分块迭代法，就是一块或一组未知数同时被改进.设 ，其中 为大型稀疏矩阵且将 分块为三部分 ，bAx nnA RAULDA,212222111211qqqqqqAAAAAAAAAA其中 ,2211qqAAAD25,0002121qqAAAL且 为 非奇异矩阵，),2,1(qiAiiiinn.1nnqii对 及 同样分块 xb,21qxxxx.0002112qqAAAU,21qbbbb其中，.R,Riininibx2

12、6 (1)块雅可比迭代法(BJ)选取分裂阵 为 的对角块部分，即选 MA.NMADM(块对角阵)于是，得到块雅可比迭代法 fBxxkk)()1(（4.1）其中迭代矩阵,)(11JULDADIB或.)()()1(bxULDxkk.1bDf27由分块矩阵乘法，得到块雅可比迭代法的具体形式),2,1(1)()1(qixAbxAqijjkjijikiii（4.1）其中.R,)()()(2)(1)(inkikqkkkxxxxx 这说明，块雅可比迭代法每迭代一步，从 ，)1()(kkxx需要求解 个低阶方程组 q28.式右边部分为其中）（12.3),2,1()(iikiiigqigxA (2)块SOR迭代

13、法(BSOR)选取分裂矩阵 为带松弛因子的 块下三角部分，MA.),(1NMALDM得到块SOR迭代法,)()1(fxLxkk（4.3）即 29其中迭代矩阵 ALDIL1)(由分块矩阵乘法得到块SOR迭代法的具体形式 为松弛因子.),1,0;,2,1()()(11)1()()1(kqixAxAbxAxAqijkjijijkjijikiiikiii（4.4）),)1()(1UDLD,)(1bLDf30 于是，当 及 已计算时，解低阶方程组(3.14)可计算小块)(kx)1,2,1()1(ijxkj.)1(kix 从 共需要解 个低阶方程组，当 为三对角阵或带状矩阵时，可用直接法求解.)1()(kkxxqiiA 定理定理1111 设 ，其中 (分块形式).bAx ULDA (1)如果 为对称正定矩阵，A则解 的BSOR迭代法收敛.bAx.20(2)若有不当之处，请指正，谢谢！若有不当之处，请指正，谢谢！