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

《线性代数方程组的迭代解法课件.ppt》由会员分享，可在线阅读，更多相关《线性代数方程组的迭代解法课件.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性代数方程组的迭代解法第1页，此课件共22页哦2 Jacobi和和Gauss-Seidel迭代法迭代法一、一、Jacobi迭代法迭代法设方程组设方程组将系数矩阵将系数矩阵分裂分裂为：为：其中其中第2页，此课件共22页哦如果如果原方程组可化为原方程组可化为其中其中相应的迭代格式相应的迭代格式上述方法称为上述方法称为Jacobi迭代法，简称迭代法，简称J法或法或简单简单迭代法迭代法分量分量形式：形式：第3页，此课件共22页哦二、二、Gauss-Seidel迭代法迭代法G-S迭代法是迭代法是J迭代法的一种迭代法的一种改进改进在在J迭代公式中，计算迭代公式中，计算 时，利用已经算出来的时，利用已经算

2、出来的新的新的值，从而得到值，从而得到G-S迭代法。迭代法。G-S迭代法的迭代法的分量分量形式：形式：第4页，此课件共22页哦例例1：利用利用Jacobi和和Gauss-Seidel迭代法求解方程组迭代法求解方程组解：解：Jacobi迭迭代代格格式式第5页，此课件共22页哦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.9999

3、981)方方 程程 组组 的的 近近 似似 解解第6页，此课件共22页哦 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页，此课件共22页哦三、三、Jacobi和和Gauss-Seidel迭代法的收敛性迭

4、代法的收敛性Jacobi迭代法收敛的迭代法收敛的充要充要条件是条件是Gauss-Seidel迭代法收敛的迭代法收敛的充要充要条件是条件是推论推论1：Jacobi迭代法收敛的迭代法收敛的充分充分条件是条件是Gauss-Seidel迭代法收敛的迭代法收敛的充分充分条件是条件是 如例如例1：利用利用J和和G-S迭代法求解方程组迭代法求解方程组第8页，此课件共22页哦Jacobi迭代矩阵迭代矩阵系数矩阵系数矩阵第9页，此课件共22页哦Gauss-Seidel迭代矩阵迭代矩阵第10页，此课件共22页哦设设满足满足称称为严格为严格对角占优对角占优矩阵矩阵如果如果且至少有一个严格且至少有一个严格不等式成立，

5、则称不等式成立，则称为为弱对角占优弱对角占优矩阵。矩阵。设设，如果能找到，如果能找到排列排列阵阵，使得，使得其中其中与与均为均为方方阵阵，称，称为为可约可约的的否则称否则称为为不可约不可约的的第11页，此课件共22页哦例如：例如：矩阵矩阵是是可约可约的的若系数矩阵是若系数矩阵是可约可约的，则可通过的，则可通过行行与与列重排列重排化为化为（*）式，从而可以将方程组简化为式，从而可以将方程组简化为低阶低阶方程组。方程组。第12页，此课件共22页哦（补充（补充:可约可约矩阵的矩阵的等价等价定义）定义）是可约矩阵，当且仅当存在一个下标的非空是可约矩阵，当且仅当存在一个下标的非空子集子集，使得，使得例如

6、：例如：矩阵矩阵矩阵矩阵不可约不可约第13页，此课件共22页哦如果如果 严格严格对角占优对角占优，则，则，且，且非奇异。非奇异。如果如果 不可约且不可约且弱弱对角占优对角占优，则，则，且，且非奇异。非奇异。自己看自己看证明：证明：首先证明首先证明设设由条件：由条件：是是弱弱对角占优对角占优，交换交换 的第的第k、n行与行与k、n列，则矩阵列，则矩阵 变为变为与与 不可约不可约矛盾！矛盾！第14页，此课件共22页哦其次证明其次证明是是非奇异非奇异的的设设则存在则存在非零非零向量向量满足满足定义定义下标下标的集合的集合且令且令对某个对某个j显然显然J非空，否则非空，否则第15页，此课件共22页哦对

7、对，有，有由此可知，当由此可知，当时，时，但对于但对于都有都有所以所以否则与否则与弱弱对角占优对角占优矛盾！矛盾！与与不可约不可约矛盾矛盾第16页，此课件共22页哦如果如果 为为严格对角占优严格对角占优或为或为不可约不可约且且弱弱对角占优对角占优矩阵，则求解方程组矩阵，则求解方程组的的J法和法和G-S法均收敛法均收敛。证明：证明：仅给出仅给出不可约不可约且且弱弱对角占优对角占优矩阵矩阵G-S法法的证明的证明只要证明只要证明，其中，其中设设有一个特征值有一个特征值，满足，满足，且有，且有 是是不可约不可约且且弱弱对角占优对角占优矩阵，由定理矩阵，由定理6.8：第17页，此课件共22页哦因此因此注

8、意到注意到和和的零元素和的零元素和非零元素的非零元素的位置位置完全一样，故完全一样，故是是不可约不可约也是也是弱弱对角占优对角占优矩阵矩阵矛盾！矛盾！如果如果 为为严格对角占优严格对角占优矩阵，易证矩阵，易证其中其中 为为J法的法的迭代迭代矩阵矩阵第18页，此课件共22页哦如果如果 是对称矩阵，且有是对称矩阵，且有正正的对角元，则的对角元，则求解方程组求解方程组的的J法收敛的充要条件是矩阵法收敛的充要条件是矩阵和和 均为正定的，其中均为正定的，其中证明：证明：记记其中其中迭代迭代矩阵矩阵矩阵矩阵 和和 相似相似，故有相同的，故有相同的特征值特征值；且；且、对称对称第19页，此课件共22页哦必要

9、性设设J法收敛，则法收敛，则记记 的特征值为的特征值为 ，则则 的特征值的特征值为为所以所以 是对称是对称正定正定的。的。对对而矩阵而矩阵 是对称是对称正定正定的的同理同理可证可证第20页，此课件共22页哦矩阵矩阵的的正正特征值均特征值均小小于于1充分性因为因为 正定正定，所以，所以 也是也是正定正定矩阵，矩阵，且其特征值且其特征值 全部大于全部大于零零。所以所以 的特征值均小于的特征值均小于1矩阵矩阵 和和 相似相似，故有相同的故有相同的特征值特征值，且特征值均小于，且特征值均小于1。第21页，此课件共22页哦如果如果 是对称是对称正定正定矩阵，则矩阵，则求解方程组求解方程组 的的G-S法收敛。法收敛。证明见定理证明见定理6.13注：注：如果如果 是对称是对称正定正定矩阵，则矩阵，则求解方程组求解方程组 的的G-S法收敛，而法收敛，而J法法不一定不一定收敛。收敛。例例2：判定用判定用J法和法和G-S法求解下列方程组的收敛性：法求解下列方程组的收敛性：第22页，此课件共22页哦