线性方程组的迭代解法

1、 第第六六章章 线性与非线性方程组线性与非线性方程组的迭代解法的迭代解法/*Iterative Method for Solving Linear and Nonlinear Algebraic Systems*/求解求解,n nAxb AR 0det( )A 迭代法迭代法从一个从一个初始向量初始向量出发出发, ,按照一定的按照一定的递推递推格式格式, ,产生逼近方程组的产生逼近方程组的近似解序列近似解序列。迭代法迭代法是一种是一种逐次逼近逐次逼近的方法的方法, ,与与直接法直接法比较比较, , 具有具有: : 程序简单程序简单, ,存储量小的存储量小的优点。优点。特别适用于求解系数特别适用于

2、求解系数矩阵为大型矩阵为大型稀疏矩阵稀疏矩阵 /* sparse matrices */ 的方程组的方程组。思思路路与解与解f (x)=0 的的不动点迭代不动点迭代相似相似 ， 将方程组将方程组等价改写成等价改写成 形式，从而建立形式，从而建立迭代格式迭代格式A xb xM xg 1()( )kkxMxg ，从，从 出发，生成迭代序列出发，生成迭代序列0( )x( )kx6.1 Jacobi和和Gauss-Seidel迭代法迭代法一、一、 Jacobi迭代法迭代法设方程组设方程组10;(),();det()ijn ninAxb AabbA 将系数矩阵将系数矩阵分裂分裂为：为：ADLU 其中其中

3、1122(,)nnDdiag aaa 0L 21a31a1na0032a2na1,n na 000U 12a13a1na0023a2na1,nna 00如果如果01 2(, , )iiain原方程组可化为原方程组可化为11()xDLU xD bMxg其中其中111()();MDLUID AgD b 相应的迭代格式相应的迭代格式10 1 2()( );, , ,kkxMxg k 上述方法称为上述方法称为Jacobi迭代法，简称迭代法，简称J法或法或简单简单迭代法迭代法分量分量形式：形式：11111 2( )( )();, ,inkkiijjijjjj ikiiiba xa xxina 二、二、

4、Gauss-Seidel迭代法迭代法G-S迭代法是迭代法是J迭代法的一种迭代法的一种改进改进在在J迭代公式中，计算迭代公式中，计算 时，利用已经算出来的新的时，利用已经算出来的新的1()kix 111121()()(),kkkixxx 值，从而得到值，从而得到G-S迭代法。迭代法。 G-S迭代法的迭代法的分量分量形式：形式：111111 2()( )();, ,inkkiijjijjjj ikiiiba xa xxina 例例1 1：利用利用Jacobi和和Gauss-Seidel迭代法求解方程组迭代法求解方程组10311010 21331x2x3x 145 14解：解：123114310(

5、)( )()()kkkxxx 113252310( )( )()()()kkkxxx 112314310( )( )()()kkkxxx Jacobi迭代格式迭代格式123114310( )( )()()kkkxxx 1113252310()( )()()()kkkxxx 11112314310()()()()kkkxxx G-S迭代格式迭代格式计算结果计算结果000()Tx 取初值取初值Jacobi迭代法迭代法 要求要求 精度精度迭代迭代次数次数 0.001 9( (1.0002507 1.0000694 1.0002507) ) 0.0001 10( (0.9999541 1.000125

6、3 0.9999541) )0.00001 14( (0.9999981 1.0000020 0.9999981) )方方 程程 组组 的的 近近 似似 解解 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) )方方 程程 组组 的的 近近 似似 解解000(

7、)Tx 取初值取初值1111()()( )kkkxD LxD Uxg由迭代公式由迭代公式111111()( )()()kkxID LD UxID Lg迭代矩阵迭代矩阵1111()()MID LD UDLU 6 6.2.2 Jacobi和和Gauss-Seidel迭代法的收敛性分析迭代法的收敛性分析 收敛的充要条件与误差估计收敛的充要条件与误差估计上述两种方法都可以写成如下迭代形式：上述两种方法都可以写成如下迭代形式：10 1 2()( ), , ,kkxM xg k 称为称为单步定常单步定常线性迭代法，线性迭代法， 为为迭代矩阵迭代矩阵， 为常数项。为常数项。Mg 当迭代公式产生的序列当迭代公

8、式产生的序列 收敛到向量收敛到向量 ， 0( )kkx x 即即 ，则称该迭代法，则称该迭代法收敛收敛，否则为，否则为发散发散。( )limkkxx ( )limkkxx xMxg Axb ？6 2 1. .kMO引理引理迭代法迭代法 收敛的充要条件是收敛的充要条件是1()( )kkxMxg 证明：证明： 1( )()()kkxxM xx 为方程组为方程组 的解，的解，x Axb 设迭代法设迭代法 收敛，则有收敛，则有1()( )kkxMxg ( )limkkxx xMxg 由相容性知，由相容性知，xMxgAxb 0( )()kM xx ( )limkkxx kMO0(x 任 意 )6 2 1

9、. .Th1()M 求解方程组求解方程组 的单步线性定常迭代法的单步线性定常迭代法收敛的充要条件是收敛的充要条件是 。Axb 10 1 2()( ), , ,kkxM xg k （1）迭代法是否收敛取决于迭代矩阵的迭代法是否收敛取决于迭代矩阵的谱半径谱半径，与初，与初 始向量和常数项无关始向量和常数项无关。（2）而对于同一个方程组，不同的迭代法对应的迭代而对于同一个方程组，不同的迭代法对应的迭代 矩阵的矩阵的谱半径谱半径一般不会相同，因而收敛性也不同。一般不会相同，因而收敛性也不同。上述定理说明：上述定理说明：例例2 2：说明用说明用J法和法和G-S法求解下列方程组的收敛性：法求解下列方程组的

10、收敛性：212 11x2x3x 31 111163 解：解：212 11 1111A 计算计算特征值特征值：12 3502,i 1()M 12 120001 1 1MID A 1212J法不收敛法不收敛后面两个特征值算错了，应该是是复数G-S法的法的迭代迭代矩阵为矩阵为1()GD LU 202 1110101 0100001 01 12012 112 001200100001 01 112( )G G-S法收敛法收敛12 000012 12 12 12 6 2 2. .Th( )kx若迭代矩阵若迭代矩阵 的范数的范数 ，并假定，并假定的第的第k次迭代向量次迭代向量 与精确解与精确解 的误差满足

11、：的误差满足：M1()( )kkxM xg 范数满足范数满足 ，则迭代法，则迭代法1Mq1I x 101( )( )( )kkqxxxxq 证明：证明： 0( )( )()kkxxMxx 00( )( )( )()kkkxxM xxqxx 111111()MqIMMq 001( )( )()xxxIMg 10( )()()IMIM xg 100( )( )()IMxMxg 100( )( )()IMxMxg 101( )( )()IMxx 代入前述不等式即得。代入前述不等式即得。利用利用矩阵的范数判定迭代收敛只是一个充分条矩阵的范数判定迭代收敛只是一个充分条件，通常采用矩阵的件，通常采用矩阵的

12、1- -范数、范数、 - -范数来判定。范数来判定。 6 2 3. .Th( )kx若迭代矩阵若迭代矩阵 的范数的范数 ，并假定，并假定的第的第k次迭代向量次迭代向量 与与精确解精确解 的误差满足：的误差满足：M1()( )kkxM xg 范数满足范数满足 ，则迭代法，则迭代法1Mq 1I x 11( )()( )kkkqxxxxq 证明证明：与前面类似。：与前面类似。 6 2 4. .Th设设 为为Jacobi法的迭代矩阵，若法的迭代矩阵，若B则则Gauss-Seidel迭代收敛，而且有估计式迭代收敛，而且有估计式1B 1111maxniijijij ijbb 101( )( )( )kkx

13、xxx 其中其中且有且有 ，这里，这里 是矩阵是矩阵 的元素。的元素。1B Bijb6 2 5. .Th设设 为为Jacobi法的迭代矩阵，若法的迭代矩阵，若B则则Gauss-Seidel迭代收敛，而且有估计式迭代收敛，而且有估计式11B 1111111max,maxnijjijjnijijjiijsbbbB 101111( )( )( )()()kkxxxxs 其中其中6 2 6. .ThA如果如果 是对称矩阵，且有是对称矩阵，且有正正的对角元，则的对角元，则求解方程组求解方程组 的的J法收敛的充要条件是矩阵法收敛的充要条件是矩阵Axb 和和 均为正定的，其中均为正定的，其中A2DA 11(

14、,)nnDdiag aa 6 2 7. .ThA如果如果 是对称是对称正定正定矩阵，则矩阵，则求解方程组求解方程组 的的G-S法收敛。法收敛。Axb 2Def设设 满足满足()n nijAaR 11 2, ,niiijjj iaain 称称 为严格为严格对角占优对角占优矩阵矩阵A如果如果 且至少有一个严格且至少有一个严格不等式成立，则称不等式成立，则称 为为弱对角占优弱对角占优矩阵。矩阵。11 2, ,niiijjj iaain A3Def设设 ，如果能找到，如果能找到排列排列阵阵 ，使得，使得n nAR 111222TAOPAPAA P其中其中 与与 均为均为方方阵阵，称，称 为为可约可约的

15、的A11A22A( ) 否则称否则称 为为不可约不可约的的A例如：例如：矩阵矩阵1 1100011 A 2是是可约可约的的1 1100011 213rr13cc1 1100011 2若系数矩阵是若系数矩阵是可约可约的，则可通过的，则可通过行行与与列重排列重排化为化为上面上面( (* *) )式，从而可将方程组简化为式，从而可将方程组简化为低阶低阶方程组。方程组。3Def（可约可约矩阵的矩阵的等价等价定义）定义）2()n nARn 设矩阵设矩阵 ， ，如果，如果存在存在 的两个非空子集的两个非空子集 和和 ，满足，满足T 1 2, ,n , 使得使得 0,ijaij则称矩阵则称矩阵 可约，否则称

16、可约，否则称 不可约。不可约。AA210a 220a 310a 例如：例如：矩阵矩阵1 1100011 A 2 2,31 矩阵矩阵11 1 01201B 0130a 320a 330a 不可约不可约6 2 8. .Th()ijn nAa 01 2, ,iiain 设设 为为 严格严格对角占优或对角占优或不可不可约弱约弱对角对角占优，则占优，则 ，且，且 非奇异。非奇异。A6 2 1. .A设设 为为 严格严格对角占优或对角占优或不可不可约弱约弱对角对角占优的占优的对称对称矩阵，矩阵，且对角元素皆为且对角元素皆为正正，则，则 正定。正定。推论推论A6 2 9. .ThA若若 为为 严格严格对角占

17、优或对角占优或不可不可约弱约弱对角对角占优的，占优的，则则Jacobi迭代和迭代和Gauss-Seidel迭代收敛迭代收敛。 迭代法的迭代法的收敛速度收敛速度：1()( )kkxMxg 设迭代法设迭代法 收敛收敛，即，即1()M 1()( )kkxMxg 4Def（/* Rate of Average Convergence */）1()lnkkkRMM 称之为迭代法称之为迭代法 的的平均收敛率平均收敛率。上式说明：上式说明： 可看作第可看作第k次迭代误差范数的次迭代误差范数的压缩率压缩率kM10( )()( )()()kkkxxM xxMxx 平均平均压压缩率缩率0( )( )()kkxxMxx 1lnlnkkMkMk 1lnlnkkM 上式说明：上式说明：最小最