第八章 线性代数方程组迭代法

1、第八章第八章迭代法基础迭代法基础在实际应用中遇到的系数矩阵多为大型稀疏在实际应用中遇到的系数矩阵多为大型稀疏矩阵，如用求解线性方程组的直接法求解，矩阵，如用求解线性方程组的直接法求解，在计算机上会耗费大量的时间和存储单元。在计算机上会耗费大量的时间和存储单元。在许多应用问题中使用迭代法。在许多应用问题中使用迭代法。思思路路将将 改写为改写为 等价形式等价形式 ，建，建立迭代立迭代 , ,从初值从初值 出发，得出发，得到序列到序列 。AxbxBxg(1)( )kkxBxg(0)x()kx研究内容：研究内容： 如何建立迭代格式？如何建立迭代格式？ 收敛速度？收敛速度？ 向量序列的收敛条件？向量序列

2、的收敛条件？ 误差估计？误差估计？一般迭代法一般迭代法定义定义1 1 对方程组对方程组 ，化为等价方程，化为等价方程组组 ，设，设 为任取的初值，将上式写为为任取的初值，将上式写为迭代过程迭代过程这种迭代过程称为这种迭代过程称为逐次逼近法逐次逼近法，B B 称为称为迭代矩阵迭代矩阵。若若 称逐次逼近法称逐次逼近法收敛，收敛， 否则，称否则，称逐次逼近法逐次逼近法不收敛或发散不收敛或发散。(1)( )(0,1,)kkxBxg k( )*lim,kkxx(0)Axb AxBxg(0)x问题：问题：按上述思想迭代产生的向量序列按上述思想迭代产生的向量序列 在什在什 么条件下收敛于方程组么条件下收敛于

3、方程组Ax=bAx=b的解？的解？( )kx引进误差向量引进误差向量： ，其中，其中 为方为方程组的解，即有程组的解，即有所以，要使所以，要使 收敛到收敛到 ，则需研究，则需研究 在什么条在什么条件下有件下有 。*( )(1)kkxBxgxBxg( )( )*(1)*(1)2(2)(0)(0)(0)*()()kkkkkkxxB xxBBBxx( )kx*x( )( )*(0,1, )kkxx k*xB( )0()0()kkkBk 迭代法的收敛条件与误差估计迭代法的收敛条件与误差估计引理引理 当当k 时，时，Bk 0 0 ( ( B ) 1 ) 1定理定理1 1 设有线性方程组设有线性方程组 ，

4、那么逐次逼近，那么逐次逼近 法对任意初始向量法对任意初始向量 收敛的充分必要条件收敛的充分必要条件 是迭代矩阵是迭代矩阵B B的谱半径的谱半径 ( (B B ) )11。xBxg(0)x注：注：要检验一个矩阵的谱半径小于要检验一个矩阵的谱半径小于1 1比较困难，比较困难， 所以我们希望用别的办法判断收敛性。所以我们希望用别的办法判断收敛性。 注注: 1.1.因为矩阵范数因为矩阵范数 都可以直接用矩阵的元素都可以直接用矩阵的元素 计算，因此用定理计算，因此用定理2 2， 很容易判别逐次逼近法的收敛性。很容易判别逐次逼近法的收敛性。 2.2.定理定理2 2是充分条件，当找不到矩阵的某一范数小于是充

5、分条件，当找不到矩阵的某一范数小于1 1时，时， 并不能判断并不能判断迭代法不收敛。迭代法不收敛。12,BBB(1)(1)()|*|1|kkkBxxxxB1(1)(1)(0)|*|1|kkBxxxxB定理定理2 2 设线性方程组设线性方程组 有惟一解有惟一解 ，若存若存 在一个矩阵范数使得在一个矩阵范数使得 | B | 1, 则则迭代收敛迭代收敛, 且有下列误差估计：且有下列误差估计：xBxg*xnnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111（8 8.1） 1 1雅克比（雅克比（JacobiJacobi）迭代法）迭代法设有设有n n阶方程

6、组阶方程组几种常用的迭代法几种常用的迭代法若系数矩阵非奇异，且若系数矩阵非奇异，且 (i = 1, 2, n)，将方程组将方程组0iia()()()11,22112323121222213132121111111nnnnnnnnnnnnnxaxaxabaxxaxaxabaxxaxaxabax（8.1）改写成改写成然后写成迭代格式然后写成迭代格式()()()(11,)(22)(11)1()(2)(323)(121122)1(2)(1)(313)(212111)1(1111knnnknknnnnknknnkkkknnkkkxaxaxabaxxaxaxabaxxaxaxabax（8.2）（8.2）式

7、也可以简单地写为式也可以简单地写为), 2, 1(1)(1)1(nixabaxkjnijjijiiiki（8.3）11()()()AxbDL U xbDxL U xbxDL U xD b记记 , ,其中其中A D L U 112233nnaaDaa2131321230000nnnaLaaaaa 1213123230000nnnaaaaaUa 则雅克比迭代法的矩阵形式为：则雅克比迭代法的矩阵形式为：(8.4)(1)1( )1( )()(0,1,)kkkJxDL U xD bB xgk称称 为雅克比迭代矩阵。为雅克比迭代矩阵。1()JBDLU1 311 21 11 11 12 322 12 22

8、22 23 13 233 33 33 31230000nnnnnnn nn nn naaaaaaaaaaaaaaaaaaaaaaaa33111112131122212321313231123()00000000JnnnnnnnnBD L Uaaaaaaaaaaaaaaaa (1)( )( )( )( )111221331441111()kkkkknnxba xa xa xa xa(1)(1)( )( )( )2221 12332442221()kkkkknnxba xa xa xa xa(1)(1)(1)( )( )3331)kkkkknnxba xa xa xa x

9、a(1)(1)(1)(1)(1)1 12233111()kkkkknnnnnnnnnnxba xa xa xaxa 写成矩阵形式：写成矩阵形式：(1)1(1)( )1(1)( )(1)1( )1( )()()()()kkkkkkkkG SxDLxUxD bDL xUxbxDLUxDLbBxg2 2高斯高斯赛得尔赛得尔(Gauss-Seidel)(Gauss-Seidel)迭代法迭代法(8.5)(8.6)其中其中 称为称为高斯高斯赛得尔赛得尔迭代矩阵。迭代矩阵。11(),()G SgD Lb BD L U定理定理4 4 n n阶矩阵阶矩阵A A是严格对角占优矩阵的充分必要条件是是严格对角占优矩阵

10、的充分必要条件是 JacobiJacobi迭代法的迭代矩阵满足迭代法的迭代矩阵满足 BBJ J11。3 3JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法的收敛性迭代法的收敛性定理定理5 5 如果如果A A是严格对角占优矩阵，那么是严格对角占优矩阵，那么JacobiJacobi和和G GS S 迭代法都收敛。迭代法都收敛。定理定理6 6 若若A A是是n n阶正定矩阵，那么阶正定矩阵，那么G-SG-S迭代法收敛。迭代法收敛。定理定理3 3 n n阶矩阵阶矩阵A A是严格对角占优矩阵，则是严格对角占优矩阵，则A A非奇异，且非奇异，且 所有对角元所有

11、对角元 。0 (1,2, )iiain注意的问题注意的问题（1 1）JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法的迭代矩阵不同：迭代法的迭代矩阵不同：BJ =D-1(L+U), B G-S = (D-L)-1U（2 2）JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法收敛性没有必然的迭代法收敛性没有必然的 联系。即当联系。即当Gauss-SeidelGauss-Seidel法收敛时，法收敛时，JacobiJacobi法可能不收法可能不收 敛；而敛；而JacobiJacobi法收敛时，法收敛时，Gau

12、ss-SeidelGauss-Seidel法也可能不收敛法也可能不收敛（3 3）JacobiJacobi迭代和迭代和Gauss-SeidelGauss-Seidel迭代的特征方程：迭代的特征方程：()ijnnAaDLU10(L+U)0(L+U)0JIBIDDJacobiJacobi迭代：迭代：1112121222120nnnnnnaaaaaaaaaGauss-SeidelGauss-Seidel迭代：迭代：10() U0(L)U)0G SIBIDLD1112121222120nnnnnnaaaaaaaaa12312312321).121xxxaxxxxxx123123123221).2223x

13、xxbxxxxxx用用JacobiJacobi迭代法求解收敛，迭代法求解收敛，但用但用 Gauss-SeidelGauss-Seidel法不收敛。法不收敛。（4 4）举例）举例：用用JacobiJacobi迭代法求解不收敛，迭代法求解不收敛，但用但用 Gauss-SeidelGauss-Seidel法收敛。法收敛。12123231).221251xxcxxxxx系数矩阵系数矩阵A A是正定矩阵，因此用是正定矩阵，因此用 Gauss-SeidelGauss-Seidel法收敛。法收敛。1341231234123410 5783 11).3282322717xxxxxxdxxxxxxxx 线性方程

14、组的系数矩阵为线性方程组的系数矩阵为10015183032811227A是严格对角占优的，所以是严格对角占优的，所以Jacobi和和Gauss-Seidel迭代格式迭代格式均收敛。均收敛。)(1)1(11)1(1kjnijijkjijijiiikixaxabax(1)()1(1)(1, 2, )kkkiiixxxin)(1)1(11)()1()1 (kjnijijkjijijiiikikixaxabaxx（1）迭代）迭代（2）加速）加速（8.7）()(1)( )1(1)( )(1)kkkkxxDbLxUx(1)( )()(1)kkDL xDU xb(1)1( )1()(1)()kkxDLDU

15、xDLb即即超松驰超松驰迭代法（迭代法（SOR法）法） （Sequential Over-Relaxation)Sequential Over-Relaxation)矩阵形式：矩阵形式：注：注：1.1.称称 为为超松弛超松弛迭代矩阵。迭代矩阵。 2.2.称称 为为松弛因子。松弛因子。 3.3.当当 时，就是时，就是G-SG-S迭代法；当迭代法；当 时，称为低时，称为低 松弛松弛迭代法；当迭代法；当 时，称为时，称为超松弛超松弛迭代法。迭代法。 4.SOR4.SOR法也称为法也称为G-SG-S迭代法的一种加速方法。迭代法的一种加速方法。 5.5.研究研究SORSOR法就是需要找到最佳法就是需要找到最佳松弛因子，使得松弛因子，使得迭代迭代 过程的收敛速度最快，即过程的收敛速度最快，即 。 6.6.在找最佳在找最佳松弛因子之前，先要