为不可约矩阵(PPT课件).ppt

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