解线性方程组的迭代法

1、解线性方程组的迭代法 考虑 Ax=b，其中detA 0。当A为低阶稠密矩阵时，上一章讨论的选主元素消去法是有效方法。但对于工程实践中的大型稀疏矩阵方程组（A的阶数n很大，但零元素较多，如：n )，则利用迭代法解此线性方程组是合适的。迭代法在计算机内存和运算两方面，通常都可利用A中有大量零元素的特点。下面先举例说明迭代法的基本思想。 4101 引言1231234123423410261125210113815xxxxxxxAxbxxxxxxx 简记：例：例：解线性方程组的迭代法 Tx)1 , 1,2, 1(*解：其精确解为：fBxxxxxxxxxxxxxxxx或)315(81)211(101)3

2、25(111)26(10132442134312321先将Ax=b转化为等价方程组Tx)0 , 0 , 0 , 0()0(迭代公式：选取初始向量解线性方程组的迭代法经10次迭代解：0002.0:)9998.0 ,9998.0,9998.1 ,0001.1 ()10(*)10(xxxT误差为)2, 1 ,0()315(81)211(101)325(111)26(101)(3)(2)1(4)(4)(2)(1)1(3)(4)(3)(1)1(2)(3)(2)1(1kxxxxxxxxxxxxxxkkkkkkkkkkkkkk解线性方程组的迭代法53521221xxxx精确解为若取Tx4, 3 .0 , 0

3、0Tx .,Tkx则 一般地，对于线性方程组 Ax=b .转化为等价方程组 x=Bx+f,设有唯一解 ，则 （1）又设 为任取初值向量。按下列方式产生迭代向量序列： xfBxx 0 x 可见由迭代法产生的向量序列 逐次逼近方程组的精确解。但是，并不是对任何一个方程组，由迭代法产生的向量序列 均收敛到精确解的。如用迭代法解下面的线性方程组： kx kx fBxxfBxxfBxxkk11201k为迭代次数。（2）解线性方程组的迭代法由（1），（2）得： ，从而递推得：为讨论 收敛性，引进误差向量：.11xxkk 1kkB 01kkkBB kx定义定义1：对x=Bx+f.用（2）逐步求近似解的方法称

4、为迭代 法（又称为一阶定常迭代法，这里B与k无关）。 若 存在（记为 ）。称此迭代法收敛迭代法收敛。 显然 就是方程组的解。若极限不存在，则称迭代法发散迭代法发散。 kkxlimxx亦即B满足什么条件使 （零矩阵） 。 要 收敛于 。则须考察B在什么条件下 ，x kx 0k0kBk解线性方程组的迭代法2 Jacobi迭代法与Gauss-Seidel迭代法一 Jacobi迭代法又将A分裂为：A=M-N。则（1）等价于 Mx=Nx+b (3)其中M应选择为一个非奇异阵。并使 Mz=f 容易求解。对Ax=b. 设detA 0. 0. (i=1n) (1)将A改写为:iiannaaa221100001

5、,21323121nnnnaaaaaa000, 122311312nnnnaaaaaaA= - -=D-L-U (2)解线性方程组的迭代法 （初始向量）， 其中： .1fJxxkkbDfULDJ11),(（5）J称为称为Jacobi迭代法的迭代矩阵迭代法的迭代矩阵。 0 x可得:Jacobi迭代公式：特别地，若选取 M=D 则N=M-A=L+U 从而（1）化为： Dx=(L+U)x+b对应于（3）可构造一个迭代过程：初始向量 ， ), 1 , 0.(111kbMNxMxkk 0 x（4）Jacobi迭代法的分量形式： 引进记号： 为第k次近似， Tknkkkxxxx,21由（5）有:解线性方程

6、组的迭代法 Jacobi迭代公式简单，由公式（5），（6）可知，每迭代一次只需计算一次矩阵与向量乘法，计算机中只需要两组工作单元用来保存 及 且可用 来控制迭代终止。由迭代计算公式可知，迭代法一个重要特征是计算过程中原来矩阵A数据始终不变。 前一个例子即为Jacobi法求解，在此不再举例。 1kx kx kkxx1 Tnxxxx002010, , 1 , 0,1,111knixabaxnijjkjijiiiki（6）解线性方程组的迭代法 在（3）中选取M=D-L（下三角阵），则N=M-A=U。 从而（1）化为等价的：（D-L）x=Ux + b (7)可得Gauss-Seidel迭代公式： 初始

7、向量 x(0) ， ，其中 ， fGxxkk1ULDG1bLDf1 （8） Tknkkkxxxx,21,2,1 ,0,11,11111002010knixaxabaxxxxxijnijkjijkjijiiikiTn (9) ，有迭代公式（9）G称为称为Gauss-Seidel迭代矩阵迭代矩阵。G-S迭代法的分量形式为：记二 Gauss-Seidel迭代法解线性方程组的迭代法 Gauss-Seidel迭代法每迭代一次只需计算一次矩阵与向量的乘法，但G-S迭代法比Jacobi迭代法有一个明显的优点，那就是计算机上仅需一组工作单元用来保存 分量（或 分量）当计算出 就冲掉旧的分量 。由G-S迭代公式

8、（9）可看出在的一步迭代中，计算分量 时利用了已计算出来的新分量 因此，G-S迭代法可以看作是Jacobi迭代法的一个修正。1kjx 1kkxx1kjx1kx kjx kx1kix.11ij15831110225311621043243214321321xxxxxxxxxxxxxx.1 , 1, 2 , 1Tx例：用G-S方法解下面方程组，其精确解为：解线性方程组的迭代法解解：由（9）可得本题G-S迭代公式为： 131214412111343111232113158121110132511126101kkkkkkkkkkkkkkxxxxxxxxxxxxxx, 2 , 1 , 0k 055(0,

9、0,0,0)1.0001,2.0000,1.0000,1.0000 .0.0001TTxxxx经5次迭代得:解线性方程组的迭代法 从此例可见，G-S迭代法比Jacobi迭代法收敛快（初始向量相同，达到同样精度，所须迭代步数较少），但这个结论对Ax=b的矩阵A满足某些条件才是对的，甚至有这样的线性方程组，用Jacobi方法是收敛的，而用G-S迭代法却是发散的。此例用Jacobi迭代法收敛而G-S迭代法却发散。 简要分析如下：（需要下一节的知识需要下一节的知识）1221132321321321xxxxxxxxx如线性方程组：解线性方程组的迭代法100023023110001024021000002

10、()21GG00010032012111111ULDGG特征方程0221013201111ULDGJ30.0 1JG 解线性方程组的迭代法 1,2,lim,1lim.kkijijn nkijijkkkkAakAaaai jnAAAA定义：设有矩阵序列，及如果，成立，则称收敛于 。记为212212,00000100kkkkkkAAAAk例如，矩阵序列当时，当时矩阵序列收敛的概念可以用任何矩阵范数来描述。3 迭代法的收敛性解线性方程组的迭代法 0:lim0.0.kkkkkkAAAAkBxxBk 充要条件是我们要考虑迭代法收敛性，即要研究 在什么条件下使误差向量趋于零向量。即定理 ,0,1kijn

11、nBbBkB定理：设则零矩阵的充要条件是:。证明见相关教材。 01.1)1.kkxBxfxfxBxfB定理： 迭代法基本定理 设有方程组对于任意初始向量及任意 ，解此方程组的迭代法（即收敛的充要条件是：此定理应用时要计算谱半径，不太方便。形式。此定理可以修改为下面解线性方程组的迭代法 10.,.1.kkkxBxfxxBxfxBBq定理：（迭代法收敛的充分条件） 设有方程组且为由迭代法产生的序列为初始任意向量。若迭代矩阵 的某种范数满足则：证明：（1） 1011,.0,1,kkkkkkBqIBxxBxfexxeeBeBek由于则可逆，有唯一解。设为引进误差向量即得误差的递推公式：.11).2(1

12、kkkxxqxx .1).3(01xxqqxxkk误差估计： .1xfxBIxk的唯一解收敛于方程组）（解线性方程组的迭代法 .,00000 xxekeqeBekkk时于是（2） kkkkkkkkkkkkkkkkxxqxxxxqxxxxxxxxxxeBexxBxx111111111.1即则又由迭代公式有 11kkxxqq利用此递推式即可得误差估计。解线性方程组的迭代法例例：考察用Jacobi方法求解前例1中线性方程组的收敛性. 解解：0103100210013001201081011108130110123111102110AULD则Jacobi迭代矩阵为：. 12184,104,115,10

13、3max08183010101011021131110111010210101JULDJ 故解此方程组的Jacobi方法收敛。解线性方程组的迭代法 012121011.,.kkknnkniiinnkkkkiiiiiiixxBBnu uuauBa B uau下面考察迭代法的收敛速度。设 有 个线性无关的特征向量相应的特征值为，由线性表示，基 10.1.0,10 .ln10lnkikksBinkBkBskB 可以看出当 0(i=1 n)即A的每一行对角元素绝对值严格大于同行其它元素绝对值之和。则称A为严格对角占优矩阵严格对角占优矩阵。nxnija )(iia1nijjjia定理定理 解方程组Ax=

14、b的G-S迭代法收敛的充分必要条件充分必要条件是G为G-S迭代矩阵。()1.G解线性方程组的迭代法（2）若 0(i=1 n)，且至少有一个不等式严格成立则称A为弱对角占优矩阵弱对角占优矩阵。iia1nijjj ia其中 为r阶子矩阵， 为n-r阶子矩阵（1rn),则称称矩阵矩阵A为为可约的可约的。若不存在排列矩阵P使上式成立，则称称A为不可约矩阵为不可约矩阵。定义：定义：（可约与不可约矩阵）设A= ，当n2时，如果存在n阶排列矩阵P使 = 成立。APTP2212110AAAnnija)(11A22A求解 。事实上，由AX=b化为：设 其 、 为r维向量()TTTP AP P xP b)(21y

15、yxpyT)(21ddbpT11dy 当A为可约矩阵，则AX=b可经过若干行列重排化为两个低阶方程组解线性方程组的迭代法另外，A为可约矩阵的充要条件充要条件：存在指标集J 使1,2,nJ0.kjakJjJ，证明证明： 1） A为严格对角占优阵，采用反证法。若detA=0，则Ax=0有非零解。设为0)(21 Tnxxxx 定理定理（对角占优定理）若 为严格对角占优阵或为不可约弱对角占优阵，则A是非奇异阵。nnijaA)(nkjjnkjjkjkjkjnkjjjkjkkkaxxaxaxa111 （1）设 由齐次方程中的第k个方程得：10maxikii nxxx 10nkijia x得：2222121

16、2111dyAdyAyA于是，求解 Ax=b 化为求解：解线性方程组的迭代法 2） A为不可约弱对角占优阵。采用反证法。设（由弱对角占优定义）成立。再定义下标集合：110.0.(2)nTnmmmjjjmxxxxAxmaa使。并令使,1,.kikjJk xxin xxj对某个. 021 nxxx 则J非空。否则J为空，有 即有： 这与严格对角占优阵矛盾，故detA 0nkjjkjkkaa1由此可见，当 否则，上式就与A为弱对角占优阵矛盾。）由（有1(/,1nkjjkjkjkkxxaaJk. 0,kjjkaxx时有对任意在（1）中取k=m。将导致与（2）的矛盾。故().J空集合解线性方程组的迭代法

17、 但对任意 从而A为可约矩阵，这与A为不可约矩阵假设矛盾。,0.,kjkjkJjJxxakJ jJ和必有因而定理定理:若 为严格对角占优矩阵或为不可约对角占优矩为严格对角占优矩阵或为不可约对角占优矩 阵阵，则对任意的初始向量 ，方程组Ax=b的Jacobi迭代法和G-S迭代法均收敛。且G-S迭代法比Jacobi迭代法收敛速度快。证明：设A为不可约对角占优矩阵，先证明G-S迭代法收敛。nnRA)0(x由弱对角占优阵假设知 而G-S迭代矩阵为),1.(0niaii1111().()0,()()() .( ()0( ()0.()GDLUdet DLdetIGdetIDLUdet DLdetDLUde

18、tdlUCDLU又即记解线性方程组的迭代法 则: 11121312122232123nnnnnnnaaaaaaaacaaaa这一结论表明detC=0 的根 均满足：1即 故G-S法收敛。. 1)(G在同一条件下，对于Jacobi方法 完全类似于上可证。 当A为严格对角占优阵时，证明方法完全类似。)(1ULDJ下面来证明当 这是因为A为不可约阵，则C也不可约，由A为弱对角矩阵，可得： 1,0.detC时且至少有一个不可约等式严格成立，这表明当 时，C为不可约弱对角占优矩阵，于是由前一个定理可知当111(1)iniiiiijijijjj ij icaaac 当11,0.detC时解线性方程组的迭代

19、法 逐次超松弛迭代法（Successive Over Relaxation Method.简称为SOR法）是Gauss-Seidel法的一种加速方法。这是解大型矩阵方程组的有效方法之一，具有计算公式简单，程序设计容易，占用计算机内存较少等优点，但需要选择好的加速因子，即最佳的加速因子。对x （）其中为非奇异矩阵，且设 ,分解： （）设已知第k次迭代向量，及第k次迭代向量的分量( j=1,2,i-1 ), 现在来计算分量:nnRA0.(1)iiain ) 1( kjx)1( kix)(kx4 解线性方程组的超松弛 迭代法解线性方程组的迭代法 先用迭代法求出辅助量（预测）)1(kix(1)1(1)

20、( )111(),(1 )(3)kinkkiiijjijjjj iiixba xa xina 将（）代入（4）即得解x的逐次超松弛迭代公式：再取为与的某种平均值（即加权平均）即(1)(1)(1)( )( )( )(1)()(4)iikkkkkkiiiixxxxxx（校正）)1( kix)(kix)1(kix1(1)( )(1)( )1( )( )( )( )12()(,),(0.1,1 )inkkkkiiiijjijjjj iiikkkknxxba xa xaxxxxkin（5）其中称 为松弛因子，或写为：解线性方程组的迭代法(1)( )1(1)( )1()(6)(0,1,1,2, )jkki

21、iiinkkiiijjijjj iiixxxxba xa xakin1显然时，解（）的法即为Gauss-Seidel迭代法。 法中每迭代一次，主要计算量是计算一次矩阵与向量乘法。由（）可见在计算机上用法解方程组只需一组工作单元，以便存放近似解。迭代算时，当时，称（）为低松弛法低松弛法；当时，称（）为超松弛法超松弛法。11)()1(1maxmaxkikiniiixxxp可用来控制迭代终止。解线性方程组的迭代法.) 1, 1, 1, 1(11114111141111411114*4321TxxxxxSOR其精确解为法解：例：用解线性方程组的迭代法解：取 。则SOR迭代公式为：0)0(x(1)( )

22、( )( )( )( )111234(1)( )(1)( )( )( )221234(1)( )(1)(1)( )( )331234(1)( )(1)(1)(1)( )441234(14/4(14/4(14/4(14/41.kkkkkkkkkkkkkkkkkkkkkkkkxxxxxxxxxxxxxxxxxxxxxxxx取(11)3,11( 0.99999646, 1.00000310, 0.99999953, 0.99999912)Tx 第 次迭代结果为：52*)11(2)11(1046. 0 xx 对 取其它值，迭代次数如下表，由此例可见，松弛因子选择得好，会使SOR迭代法的收敛大大加速。本

23、例中， 是最佳松弛因子。1.3解线性方程组的迭代法松弛因子 1.0 22 1.1 17 1.2 12 1.3* 11*最少迭代次数 1.4 14 1.5 17 1.6 23 1.7 33 1.8 53 1.9 109的迭代次数满足误差5*)(10 xxk解线性方程组的迭代法下面考察SOR迭代公式的矩阵形式，由（5）可改写为：1(1)( )(1)( )111)(1)( )( )(1)( )(1)(),1(7)()(1)(1),inkkkkiiiiiiiijjijjjj ikkkkkka xa xba xa xinADLUDxbLxUxDxDL xDU xb （由,则：即（(1)1( )1(1)( )11 0.1 ,0()(1)().,1 ,(8)()(1),()iikkiikkDLainLxDLDU xDLbao inSORxL xfLDLDUfDLb由于对任意，（）均为奇异阵（设而 为下三角阵，且对角线元素为）则：因