线性代数方程组的迭代解法.ppt

关于线性代数方程组的迭代解法现在学习的是第1页，共25页2 Jacobi和和Gauss-Seidel迭代法迭代法一、一、Jacobi迭代法迭代法设方程组设方程组将系数矩阵将系数矩阵分裂分裂为：为：其中其中现在学习的是第2页，共25页如果如果原方程组可化为原方程组可化为其中其中相应的迭代格式相应的迭代格式上述方法称为上述方法称为Jacobi迭代法，简称迭代法，简称J法或法或简单简单迭代法迭代法分量分量形式：形式：现在学习的是第3页，共25页二、二、Gauss-Seidel迭代法迭代法G-S迭代法是迭代法是J迭代法的一种迭代法的一种改进改进在在J迭代公式中，计算迭代公式中，计算 时，利用已经算出来的时，利用已经算出来的新的新的值，从而得到值，从而得到G-S迭代法。迭代法。G-S迭代法的迭代法的分量分量形式：形式：现在学习的是第4页，共25页例例1 1：利用利用Jacobi和和Gauss-Seidel迭代法求解方程组迭代法求解方程组解：解：Jacobi迭迭代代格格式式现在学习的是第5页，共25页G-S迭迭代代格格式式计计算算结结果果取初值取初值Jacobi迭代法迭代法 要求 精度迭代次数 0.001 9(1.0002507 1.0000694 1.0002507)0.0001 10(0.9999541 1.0001253 0.9999541)0.00001 14(0.9999981 1.0000020 0.9999981)方方 程程 组组 的的 近近 似似 解解现在学习的是第6页，共25页 G-S迭代法的迭代矩阵：迭代法的迭代矩阵：计计算算结结果果Gauss-Seidel迭代法迭代法 要求 精度迭代次数 0.001 5(0.9997916 0.9998479 1.0000664)0.0001 7(0.9999929 0.9999949 1.0000022)0.00001 8(1.0000013 1.0000009 0.9999996)方方 程程 组组 的的 近近 似似 解解取初值取初值由迭代公式由迭代公式迭代矩阵迭代矩阵现在学习的是第7页，共25页三、三、Jacobi和和Gauss-Seidel迭代法的收敛性迭代法的收敛性Jacobi迭代法收敛的迭代法收敛的充要充要条件是条件是Gauss-Seidel迭代法收敛的迭代法收敛的充要充要条件是条件是推论推论1：Jacobi迭代法收敛的迭代法收敛的充分充分条件是条件是Gauss-Seidel迭代法收敛的迭代法收敛的充分充分条件是条件是 如例如例1 1：利用利用J和和G-S迭代法求解方程组迭代法求解方程组现在学习的是第8页，共25页Jacobi迭代矩阵迭代矩阵系数矩阵系数矩阵现在学习的是第9页，共25页Gauss-Seidel迭代矩阵迭代矩阵现在学习的是第10页，共25页设设 满足满足称称 为严格为严格对角占优对角占优矩阵矩阵如果如果 且至少有一个严格且至少有一个严格不等式成立，则称不等式成立，则称 为为弱对角占优弱对角占优矩阵。矩阵。设设 ，如果能找到，如果能找到排列排列阵阵 ，使得，使得其中其中 与与 均为均为方方阵阵，称，称 为为可约可约的的否则称否则称 为为不可约不可约的的现在学习的是第11页，共25页例如：例如：矩阵矩阵是是可约可约的的若系数矩阵是若系数矩阵是可约可约的，则可通过的，则可通过行行与与列重排列重排化为化为（*）式，从而可以将方程组简化为式，从而可以将方程组简化为低阶低阶方程组。方程组。现在学习的是第12页，共25页（补充（补充:可约可约矩阵的矩阵的等价等价定义）定义）是可约矩阵，当且仅当存在一个下标的非空是可约矩阵，当且仅当存在一个下标的非空子集子集 ，使得，使得例如：例如：矩阵矩阵矩阵矩阵不可约不可约现在学习的是第13页，共25页如果如果 严格严格对角占优对角占优，则，则，且，且 非奇异。非奇异。如果如果 不可约且不可约且弱弱对角占优对角占优，则，则，且，且 非奇异。非奇异。自己看自己看证明：证明：首先证明首先证明设设由条件：由条件：是是弱弱对角占优对角占优，交换交换 的第的第k、n行与行与k、n列，则矩阵列，则矩阵 变为变为与与 不可约不可约矛盾！矛盾！现在学习的是第14页，共25页其次证明其次证明 是是非奇异非奇异的的设设则存在则存在非零非零向量向量 满足满足定义定义下标下标的集合的集合且令且令对某个对某个j显然显然J非空，否则非空，否则现在学习的是第15页，共25页对对 ，有，有由此可知，当由此可知，当 时，时，但对于但对于都有都有所以所以否则与否则与弱弱对角占优对角占优矛盾！矛盾！与与不可约不可约矛盾矛盾现在学习的是第16页，共25页如果如果 为为严格对角占优严格对角占优或为或为不可约不可约且且弱弱对角占优对角占优矩阵，则求解方程组矩阵，则求解方程组 的的J法和法和G-S法均收敛法均收敛。证明：证明：仅给出仅给出不可约不可约且且弱弱对角占优对角占优矩阵矩阵G-S法法的证明的证明只要证明只要证明 ，其中，其中设设 有一个特征值有一个特征值 ，满足，满足 ，且有，且有 是是不可约不可约且且弱弱对角占优对角占优矩阵，由定理矩阵，由定理6.86.8：现在学习的是第17页，共25页因此因此注意到注意到 和和 的零元素和的零元素和非零元素的非零元素的位置位置完全一样，故完全一样，故 是是不可约不可约也是也是弱弱对角占优对角占优矩阵矩阵矛盾！矛盾！如果如果 为为严格对角占优严格对角占优矩阵，易证矩阵，易证其中其中 为为J法的法的迭代迭代矩阵矩阵现在学习的是第18页，共25页如果如果 是对称矩阵，且有是对称矩阵，且有正正的对角元，则的对角元，则求解方程组求解方程组 的的J法收敛的充要条件是矩阵法收敛的充要条件是矩阵和和 均为正定的，其中均为正定的，其中证明：证明：记记其中其中迭代迭代矩阵矩阵矩阵矩阵 和和 相似相似，故有相同的，故有相同的特征值特征值；且；且、对称对称现在学习的是第19页，共25页必要性设设J法收敛，则法收敛，则记记 的特征值为的特征值为 ，则则 的特征值的特征值为为所以所以 是对称是对称正定正定的。的。对对而矩阵而矩阵 是对称是对称正定正定的的同理同理可证可证现在学习的是第20页，共25页矩阵矩阵 的的正正特征值均特征值均小小于于1 1充分性因为因为 正定正定，所以，所以 也是也是正定正定矩阵，矩阵，且其特征值且其特征值 全部大于全部大于零零。所以所以 的特征值均小于的特征值均小于1矩阵矩阵 和和 相似相似，故有相同的故有相同的特征值特征值，且特征值均小于，且特征值均小于1。现在学习的是第21页，共25页如果如果 是对称是对称正定正定矩阵，则矩阵，则求解方程组求解方程组 的的G-S法收敛。法收敛。证明见定理证明见定理6.13注：注：如果如果 是对称是对称正定正定矩阵，则矩阵，则求解方程组求解方程组 的的G-S法收敛，而法收敛，而J法法不一定不一定收敛。收敛。例例2 2：判定用判定用J法和法和G-S法求解下列方程组的收敛性：法求解下列方程组的收敛性：现在学习的是第22页，共25页解：解：是是正定正定矩阵矩阵所以所以G-S法收敛；法收敛；J法的法的迭代迭代矩阵为矩阵为计算计算特征值特征值：J法法不不收敛。收敛。现在学习的是第23页，共25页例例3 3：判定用判定用J法和法和G-S法求解下列方程组的收敛性：法求解下列方程组的收敛性：解：解：计算计算特征值特征值：J法收敛法收敛现在学习的是第24页，共25页感谢大家观看现在学习的是第25页，共25页