《为不可约矩阵ppt课件.ppt》由会员分享，可在线阅读，更多相关《为不可约矩阵ppt课件.ppt（30页珍藏版）》请在三一办公上搜索。
1、1,6.3.2 关于解某些特殊方程组迭代法的收敛性,定义3,(1) 如果 的元素满足,称 为严格对角占优阵.,(2) 如果 的元素满足,且上式至少有一个不等式严格成立，,称 为弱对角占优阵.,(对角占优阵),设,2,定义4,设 ,如果存在置换阵 使,（3.6）,其中 为 阶方阵， 为 阶方阵 ，,为可约矩阵.,否则，如果不存在这样置换阵 使(3.6)式成立，则,称 为不可约矩阵.,(可约与不可约矩阵),则称,为可约矩阵意即 可经过若干行列重排化为(3.6)或,3,可化为两个低阶方程组求解.,如果 经过两行交换的同时进行相应两列的交换，,称对 进行一次行列重排.,事实上，由 可化为,且记,于是，
2、求解 化为求解,其中 为 维向量.,4,由上式第2个方程组求出 ,显然，如果 所有元素都非零，则 为不可约阵.,再代入第1个方程组求出,5,例7,则 都是不可约矩阵.,设有矩阵,6,定理6,如果 为严格对角,占优矩阵或 为不可约弱对角占优矩阵，,则 为非奇异矩阵.,证明,只就 为严格对角占优阵证明此定理.,采用反证法，,如果 ，,则 有非零解，,记为 ,由齐次方程组第 个方程,则有,(对角占优定理),则,7,即,与假设矛盾，故,8,定理7,设 ,(1) 为严格对角占优阵，则解 的雅可比迭代法，高斯-塞德尔迭代法均收敛.,(2) 为弱对角占优阵，且 为不可约矩阵，则解 雅可比迭代法，高斯-塞德尔
3、迭代法均收敛.,证明,如果：,只证(1)中高斯-塞德尔迭代法收敛，其他同理.,由设可知， ，解 的高斯-塞德尔迭代法的迭代矩阵为,9,下面考查 的特征值情况.,由于 ,于是 特征值即为,之根.,记,10,下面证明，当 时， ，即 的特征值均满足 ，,事实上，当 时，,由 为严格对角占优阵，,这说明，当 时，矩阵 为严格对角占优阵，,再由对角占优定理有,由基本定理，则有高斯-塞德尔迭代法收敛. ,有,11,证明,有 ，,设 的特征值为 ，,定理8,或,另一方面,(SOR方法收敛的必要条件),设解方程组,的SOR迭代法收敛，,则,由SOR迭代法收敛，则由定理4的推论中的(3),则,12,从而,即,
4、定理8说明解 的SOR迭代法，只有在 范围内取松弛因子 ，才可能收敛.,定理9,设 ，,(1) 为对称正定矩阵，,则解 的SOR迭代法收敛.,如果：,13,证明,在上述假定下，只需证明 ，,其中 为,的任一特征值.,事实上，设 为对应 的 的特征向量，,亦即,即,为了找出 的表达式，考虑数量积,14,则,显然,记,由于 ，,所以 ,（3.7）,故,（3.8）,15,所以,从而,当 时，利用(3.7)，(3.8)，有,当 时，,即 的任一特征值满足 ，,故SOR方法收敛,可以证明,16,定理10,设 ，,(1) 为严格对角占优矩阵(或 为弱对角占优不可约矩阵)；,如果：,则解 的SOR迭代法收敛
5、.,下面讨论迭代法的收敛速度.,由定理3证明中可知，如果 且 越小时，,迭代法收敛越快.,17,及一阶定常迭代法,（3.9）,且设迭代法收敛，,记 ，,现设有方程组,则,由基本定理有 ,且误差向量,满足,故,18,设 为对称矩阵，则有,欲使,取对数，得到所需最少迭代次数为,（3.10）,这说明，所需迭代次数与 成反比.,越小， 越大，由(3.10)式所需迭代次数越少，即迭代法收敛越快.,19,对于SOR迭代法希望选择松弛因子 使迭代过程(2.10)收敛较快，,定义5,称 为迭代法(3.9)的渐近收敛,在理论上即确定 使,对某些特殊类型的矩阵，已建立了SOR方法最佳松弛因子理论.,例如，对所谓具
6、有“性质 ” 等条件的线性方程组建立了最佳松弛因子公式,速度，简称迭代法收敛速度. ,20,其中 为解 的雅可比迭代法的迭代矩阵的谱半径.,在实际应用中，对于某些椭圆型微分方程(模型问题)，,可以给出 的计算方法，,但一般来说，计算 是有困难的，可用试算的办法来确定一个适当的 .,算法2,设 ，,其中 为对称正定,(SOR迭代法),矩阵或为严格对角占优阵或为弱对角占优不可约矩阵等，,21,本算法用SOR迭代法求解 ，,数组 存放,及 ，,用 控制迭代终止，,用 表示最大,迭代次数.,22,也可用 来控制迭代终止，其中,23,6.4 分块迭代法,24,上述迭代法，从 计算时，是逐个计算的分量 ，
7、这种迭代法又称为点迭代法.,分块迭代法，就是一块或一组未知数同时被改进., 设 ，其中 为大型稀疏矩阵且将 分块为三部分 ，,其中,25,且 为 非奇异矩阵，,对 及 同样分块,其中，,26,(1) 块雅可比迭代法(BJ),选取分裂阵 为 的对角块部分，即选,于是，得到块雅可比迭代法,（4.1）,其中迭代矩阵,或,27,由分块矩阵乘法，得到块雅可比迭代法的具体形式,（4.1）,其中,这说明，块雅可比迭代法每迭代一步，,从 ，,需要求解 个低阶方程组,28,(2) 块SOR迭代法(BSOR),选取分裂矩阵 为带松弛因子的 块下三角部分，,得到块SOR迭代法,（4.3）,即,29,其中迭代矩阵,由分块矩阵乘法得到块SOR迭代法的具体形式,（4.4）,30,于是，当 及 已计算时，解低阶方程组(3.14)可计算小块,从 共需要解 个低阶方程组，当 为三对角阵或带状矩阵时，可用直接法求解.,定理11,设 ，其中 (分块形式).,(1) 如果 为对称正定矩阵，,则解 的BSOR迭代法收敛.,(2),
