解线性方程组的迭代法PPT学习教案

1、会计学1 解线性方程组的迭代法解线性方程组的迭代法 经10次迭代解： 0002.0: )9998.0 ,9998.0,9998.1 ,0001.1 ( )10(* )10( xx x T 误差为 )2, 1 ,0( )315( 8 1 )211( 10 1 )325( 11 1 )26( 10 1 )( 3 )( 2 )1( 4 )( 4 )( 2 )( 1 )1( 3 )( 4 )( 3 )( 1 )1( 2 )( 3 )( 2 )1( 1 k xxx xxxx xxxx xxx kkk kkkk kkkk kk k 第1页/共36页 53 52 12 21 xx xx 精确解为 若取 T

2、x4, 3 .0 , 0 0 T x ., T k x 则 一般地，对于线性方程组 Ax=b .转化为等价方程组 x=Bx+f,设有唯一解 ，则 （1） 又设 为任取初值向量。按下列方式产生迭代向量序列： xfBxx 0 x 可见由迭代法产生的向量序列 逐次逼近方程组的精确解。但是，并不是对任何一个方程组，由迭代法产生的向量序列 均收敛到精确解的。如用迭代法解下面的线性方程组： k x k x fBxx fBxx fBxx kk1 12 01 k为迭代次数。 （2） 第2页/共36页 由（1），（2）得： ，从而递推得： 为讨论 收敛性，引进误差向量： . 11 xx kk 1 kk B 01

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

4、 ii a nn a a a 22 11 0 0 0 0 1,21 3231 21 nnnn aaa aa a 0 0 0 , 1 223 11312 nn n n a aa aaa A= - - =D-L-U (2) 第4页/共36页 （初始向量）， 其中： . 1 fJxx kk bDfULDJ 11 ),( （5） J称为称为Jacobi迭代法的迭代矩阵迭代法的迭代矩阵。 0 x 可得:Jacobi迭代公式： 特别地，若选取 M=D 则N=M-A=L+U 从而（1）化为： Dx=(L+U)x+b 对应于（3）可构造一个迭代过程：初始向量 ， ), 1 , 0.( 111 kbMNxMx

5、kk 0 x （4） Jacobi迭代法的分量形式： 引进记号： 为第k次近似， T k n kkk xxxx, 21 由（5）有: 第5页/共36页 Jacobi迭代公式简单，由公式（5），（6）可知，每迭代一次只 需计算一次矩阵与向量乘法，计算机中只需要两组工作单元用来保存 及 且可用 来控制迭代终止。由迭代计算公式可知，迭代法一个重要特征是计算过程中原来矩阵A数据始终不变。 前一个例子即为Jacobi法求解，在此不再举例。 1k x k x kk xx 1 T n xxxx 00 2 0 1 0 , , 1 , 0,1, 1 1 1 knixab a x n ij j k jiji ii

6、 k i （6） 第6页/共36页 在（3）中选取M=D-L（下三角阵），则N=M-A=U。 从而（1） 化为等价的：（D-L）x=Ux + b (7) 可得Gauss-Seidel迭代公式： 初始向量 x(0) ， ，其中 ， fGxx kk 1 ULDG 1 bLDf 1 （8） T k n kkk xxxx, 21 ,2,1 ,0,1 1 , 1 11 11 00 2 0 1 0 kni xaxab a x xxxx i j n ij k jij k jiji ii k i T n (9) ，有迭代公式（9） G称为称为Gauss-Seidel迭代矩阵迭代矩阵。G-S迭代法的分量形式为：

7、记 第7页/共36页 Gauss-Seidel迭代法每迭代一次只需计算一次矩阵与向量的乘法， 但G-S迭代法比Jacobi迭代法有一个明显的优点，那就是计算机上仅 需一组工作单元用来保存 分量（或 分量）当计算出 就冲掉旧的分量 。由G-S迭代公式（9）可看出在 的一步迭代中，计算分量 时利用了已计算出来的新分量 因此，G-S迭代法可以看作是Jacobi迭代法的一个修正。 1k j x 1 kk xx 1k j x 1k x k j x k x 1k i x .11ij 1583 11102 25311 6210 432 4321 4321 321 xxx xxxx xxxx xxx .1 ,

8、 1, 2 , 1 T x 例：用G-S方法解下面方程组，其精确解为： 第8页/共36页 解解：由（9）可得本题G-S迭代公式为： 1 3 1 2 1 4 4 1 2 1 1 1 3 43 1 1 1 2 32 1 1 315 8 1 211 10 1 325 11 1 26 10 1 kkk kkkk kkkk kkk xxx xxxx xxxx xxx , 2 , 1 , 0k 0 5 5 (0,0,0,0) 1.0001,2.0000,1.0000,1.0000 . 0.0001 T T x x xx 经5次迭代得: 第9页/共36页 从此例可见，G-S迭代法比Jacobi迭代法收敛快（

9、初始 向量相同，达到同样精度，所须迭代步数较少），但这 个结论对Ax=b的矩阵A满足某些条件才是对的，甚至有 这样的线性方程组，用Jacobi方法是收敛的，而用G-S 迭代法却是发散的。 此例用Jacobi迭代法收敛而G-S迭代法却发散。 简要分析如下：（需要下一节的知识需要下一节的知识） 122 1 132 321 321 321 xxx xxx xxx 如线性方程组： 第10页/共36页 100023023 110001024 021000002 ()21 G G 000 100 320 121 11 1 1 1U LDGG 特征方程 022 101 320 1 1 1 1 ULDG J

10、3 0.0 1 J G 第11页/共36页 1,2, lim,1lim. k kijij n n k ijijkk kk AakAa aai jnAAAA 定义：设有矩阵序列，及如果 ，成立，则称收敛于 。记为 21 2 2 12 , 000 00 1 00 kk k k k k AAA Ak 例如，矩阵序列 当时，当时 矩阵序列收敛的概念可以用任何矩阵范数来描述。 第12页/共36页 0 :lim0. 0. kk k kkk AAAAk B xxBk 充要条件是 我们要考虑迭代法收敛性，即要研究 在什么条件下使误差 向量趋于零向量。即 定理 ,0, 1 k ij n n BbBk B 定理：

11、设则零矩阵的充要 条件是:。证明见相关教材。 0 1 .1 )1. kk xBxf xf xBxfB 定理： 迭代法基本定理 设有方程组 对于任意初始向量及任意 ，解此方程组的迭代法（即 收敛的充要条件是： 此定理应用时要计算谱半径，不太方便。 形式。此定理可以修改为下面 第13页/共36页 10 ., . 1. kkk xBxf xxBxfx BBq 定理：（迭代法收敛的充分条件） 设有方程组且 为由迭代法产生的序列为初始任意向量。 若迭代矩阵 的某种范数满足则： 证明：（1） 101 1,. . . .0,1, kkk kkk BqIBx xBxf exxe eBeBek 由于则可逆，有唯

12、一解。设为 引进误差向量即得误差的递推公式： . 1 1 ).2( 1kkk xx q xx . 1 ).3( 01 xx q q xx k k 误差估计： .1 xfxBIx k 的唯一解收敛于方程组）（ 第14页/共36页 ., 0 00 00 xxek eqeBe k k k 时 于是 （2） kkk kkk kkkk kk kkkk xx q xx xxqxxxx xxxxxx eBe xxBxx 1 1 11 1 11 1 1 .1 即 则 又 由迭代公式有 1 1 kk xx q q 利用此递推式即可得误差估计。 第15页/共36页 例例：考察用Jacobi方法求解前例1中线性方程

13、组的收敛性. 解解： 0 10 310 0210 0130 012 01 0 8 10 11 10 8130 11012 31111 02110 A ULD 则Jacobi迭代矩阵为： . 1 2 1 8 4 , 10 4 , 11 5 , 10 3 max 0 8 1 8 3 0 10 1 0 10 1 10 2 11 3 11 1 0 11 1 0 10 2 10 1 0 1 J ULDJ 故解此方程组的Jacobi 方法收敛。 第16页/共36页 0 12 12 1 0 11 . ,. . kkk n n k nii i nn kkkk iiiii ii xxB Bnu uu au Ba

14、 B uau 下面考察迭代法的收敛速度。 设 有 个线性无关的特征向量相应的特征值为 ，由线性表示，基 10.1. 0 ,10 . ln10 ln k i k k s Bink B kB s k B 可以看出当 0(i=1 n) 即A的每一行对角元素绝对值严格大于同行其它元素绝对值之和。则称A为严格对角占优矩阵严格对角占优矩阵。 nxnij a )( ii a 1 n ij j ji a 定理定理 解方程组Ax=b的G-S迭代法收敛的充分必要条件充分必要条件是 G为G-S迭代矩阵。 ()1.G 第19页/共36页 （2）若 0(i=1 n)，且至少有一个不等式严格成立 则称A为弱对角占优矩阵弱

15、对角占优矩阵。 ii a 1 n ij j j i a 其中 为r阶子矩阵， 为n-r阶子矩阵（1rn),则称称矩阵矩阵A为可约的为可约的。若不存在排列矩阵P使上式成立，则称称A为不可约矩阵为不可约矩阵。 定义：定义：（可约与不可约矩阵）设A= ，当n2时，如果存在n阶排列矩阵P使 = 成立。 AP T P 22 1211 0A AA nnij a )( 11 A 22 A 求解 。事实上，由AX=b化为： 设 其 、 为r维向量 () TTT P AP P xP b )( 2 1 y y xpy T )( 2 1 d d bpT 11 dy 当A为可约矩阵，则AX=b可经过若干行列重排化为两

16、个低阶方程组 第20页/共36页 另外，A为可约矩阵的充要条件充要条件：存在指标集J 使 1,2,nJ 0. kj akJjJ， 证明证明： 1） A为严格对角占优阵，采用反证法。若detA=0，则Ax=0有非零解。设为 0)( 21 T n xxxx 定理定理（对角占优定理）若 为严格对角占优阵或为不可约弱对角占优阵，则A是非奇异阵。 nnij aA )( n kj j n kj j kjkjkj n kj j jkjkkk axxaxaxa 111 （1） 设 由齐次方程中的第k个方程得： 1 0 max i ki i n x xx 1 0 n kij i a x 得： 2222 1212

17、111 dyA dyAyA 于是，求解 Ax=b 化为求解： 第21页/共36页 2） A为不可约弱对角占优阵。采用反证法。 设 （由弱对角占优定义）成立。再定义下标集合： 1 1 0.0.(2) n T nmmmj j jm xxxxAxmaa 使。并令使 ,1,. kikj Jk xxin xxj对某个 . 0 21 n xxx 则J非空。否则J为空，有 即有： 这与严格对角占优阵矛盾，故detA 0 n kj j kjkk aa 1 由此可见，当 否则，上式就与A为弱对角 占优阵矛盾。 ）由（有1(/, 1 n kj j kjkjkk xxaaJk . 0, kjjk axx时有 对任意

18、 在（1）中取k=m。将导致与（2）的矛盾。故 ().J空集合 第22页/共36页 但对任意 从而 A为可约矩阵，这与A为不可约矩阵假设矛盾。 ,0., kjkj kJjJxxakJ jJ和必有因而 定理定理:若 为严格对角占优矩阵或为不可约对角占优矩为严格对角占优矩阵或为不可约对角占优矩 阵阵，则对任意的初始向量 ，方程组Ax=b的Jacobi迭代法和G-S 迭代法均收敛。且G-S迭代法比Jacobi迭代法收敛速度快。 证明：设A为不可约对角占优矩阵，先证明G-S迭代法收敛。 nn RA )0( x 由弱对角占优阵假设知 而G-S迭代矩阵为 ),1.(0niaii 11 1 1 ().()0

19、, ()() () .( ()0 ( ()0.() GDLUdet DL detIGdetIDLU det DLdetDLU detdlUCDLU 又 即记 第23页/共36页 则: 1112131 2122232 123 n n nnnnn aaaa aaaa c aaaa 这一结论表明detC=0 的根 均满足： 1 即 故G-S法收敛。. 1)(G 在同一条件下，对于Jacobi方法 完全类似于上可证。 当A为严格对角占优阵时，证明方法完全类似。 )( 1 ULDJ 下面来证明当 这是因为A为不可约阵，则C也不 可约，由A为弱对角矩阵，可得： 1,0.detC时 且至少有一个不可约等式严

20、格成立，这表明当 时，C为不可约弱对角占优矩阵，于是由前一个定理可知当 1 11 (1) in iiiiijijij jj ij i caaac 当 1 1,0.detC时 第24页/共36页 逐次超松弛迭代法（Successive Over Relaxation Method.简称为SOR法）是Gauss-Seidel法的一种加速方法。这是解大型矩阵方程组的有效方法之一，具有计算公式简单，程序设计容易，占用计算机内存较少等优点，但需要选择好的加速因子，即最佳的加速因子。 对x （） 其中为非奇异矩阵，且设 ,分解： （） 设已知第k次迭代向量，及第k次迭代向量的分量( j=1,2,i-1 )

21、, 现在来计算分量: nn RA 0.(1) ii ain ) 1( k j x )1( k i x )(k x 第25页/共36页 先用迭代法求出辅助量（预测） )1( k ix (1) 1 (1)( ) 11 1 (),(1 )(3) k in kk i iijjijj jj i ii xba xa xin a 将（）代入（4）即得解x的逐次超松弛迭代公式： 再取为与的某种平均值（即加权平均） 即 (1)(1) (1)( )( )( ) (1)()(4) ii kk kkkk iiii xxxxxx （校正） )1( k i x )(k i x )1( k ix 1 (1)( )(1)(

22、) 1 ( )( )( )( ) 12 () (,),(0.1,1 ) in kkkk iiiijjijj jj i ii kkkk n xxba xa x a xxxxkin （5） 其中称 为松弛因子，或写为： 第26页/共36页 (1)( ) 1 (1)( ) 1 ()(6) (0,1,1,2, ) j kk iii in kk iiijjij jj i ii xxx xba xa x a kin 1 显然时，解（）的法即为Gauss-Seidel迭代法。 法中每迭代一次，主要计算量是计算一次矩阵与向量乘法。由（）可见在计算机上用法解方程组只需一组工作单元，以便存放近似解。迭代算时， 当

23、时，称（）为低松弛法低松弛法； 当时，称（）为超松弛法超松弛法。 1 1 )()1( 1 maxmax k i k i ni i i xxxp 可用 来控制迭代终止。 第27页/共36页 .) 1, 1, 1, 1( 1 1 1 1 4111 1411 1141 1114 * 4 3 2 1 T x x x x x SOR 其精确解为 法解：例：用 第28页/共36页 解：取 。则SOR迭代公式为： 0 )0( x (1)( )( )( )( )( ) 111234 (1)( )(1)( )( )( ) 221234 (1)( )(1)(1)( )( ) 331234 (1)( )(1)(1)

24、(1)( ) 441234 (14/4 (14/4 (14/4 (14/4 1. kkkkkk kkkkkk kkkkkk kkkkkk xxxxxx xxxxxx xxxxxx xxxxxx 取 (11) 3,11 ( 0.99999646, 1.00000310, 0.99999953, 0.99999912)Tx 第 次迭代结果为： 5 2 *)11( 2 )11( 1046. 0 xx 对 取其它值，迭代次数如下表，由此例可见，松弛因子选择得好，会使SOR迭代法的收敛大大加速。本例中， 是最佳松弛因子。 1.3 第29页/共36页 松弛因子 1.0 22 1.1 17 1.2 12 1

25、.3* 11*最少迭代次数 1.4 14 1.5 17 1.6 23 1.7 33 1.8 53 1.9 109的迭代次数满足误差 5*)( 10 xx k 第30页/共36页 下面考察SOR迭代公式的矩阵形式，由（5）可改写为： 1 (1)( )(1)( ) 11 1)(1)( )( ) (1)( ) (1)(),1(7) ()(1) )(1), in kkkk iiiiiiiijjijj jj i kkkk kk a xa xba xa xin ADLUDxbLxUxDx DL xDU xb （ 由,则： 即（ (1)1( )1 (1)( ) 11 0.1 , 0 ()(1)(). ,1 , (8) ()(1),() ii kk ii kk DLain L xDLDU xDLb ao inSOR xL xf LDLDUfDLb 由于对任意，（）均为奇异阵（设 而 为下三角阵，且对角线元素为）则： 因此，若则得迭代公式为： 其中 称 为SOR方法的迭代矩阵，应用关于迭代法的收敛性定理于（8）可得： L 第31页/共36页 10,1 ), ii ain下面开考察对于方程组（）（超松弛因子在 什么范围内取值才可能收敛。 1