方组迭代PPT学习教案

1、会计学1 方组迭代方组迭代 在用直接法解线性方程组时，要对系数 矩阵不断变换。如果方程组的阶数很高 ，则运算量将会很大并且大量占用计算 机资源，因此对线性方程组 要求找寻更经济、适用的数值解法。 ）（ 1bAx nnnn RxRbRA ,设 解线性方程组的迭代法 第1页/共62页 如果能将线性方程组(1)变换为 fBxx (2) nnnn RxRfRB ,其中 显然，(1)式和(2)式同解，我们称(1)(2)等价。 对线性方程组(2)，采用以下步骤: 可得代入取初始向量),2(, )0( x fBxx )0()1( 第2页/共62页 fBxx )1()2( fBxx kk )()1( ),2

2、, 1 ,0(k *)( limxx k k 这种方式就称为迭代法，以上过程称为迭代过程. 迭代法产生一个序列： 如果其极限存在，即 则称迭代法收敛，否则称为发散. 0 )( k x .(3) 第3页/共62页 例 用迭代法求解方程组，误差不超过1e-4. 12 33 20 412 1114 238 3 2 1 x x x 第4页/共62页 fxBx k J k )()1( ),2 , 1 ,0(nk 解 现将方程改写 )3636( 12 1 )334( 11 1 )2023( 8 1 213 312 321 xxx xxx xxx 或写为 x=BJ x+f 建立迭代公式： 任取初始值x(0)

3、=(0,0,0)T，代入公式右边， 12 33 20 412 1114 238 3 2 1 x x x 第5页/共62页 0 4 1 2 1 11 1 0 11 4 4 1 8 3 0 )3636( 12 1 )334( 11 1 )2023( 8 1 213 312 321 xxx xxx xxx 3 3 5 .2 3 2 1 x x x 3 2 1 x x x 第6页/共62页 fxBx J )0()1( 3 3 5 .2 0 0 0 T 3,3,5 .2 924.4 )0()1( xx 0 4 1 2 1 11 1 0 11 4 4 1 8 3 0 fxBx J )1()2( 3 3 5

4、 .2 3 3 5 .2 T 1 ,3636.2,875.21320.2 )1()2( xx 0 4 1 2 1 11 1 0 11 4 4 1 8 3 0 第7页/共62页 0 4 1 2 1 11 1 0 11 4 4 1 8 3 0 fxBx J )2()3( 3 3 5 .2 1 3636.2 875.2 T 9716.0,0455.2,1364.3 4127.0 )2()3( xx 依此类推，得方程组满足精度的解为x12： x4 = 3.0241 1.9478 0.9205 d = 0.1573 x5 = 3.0003 1.9840 1.0010 d = 0.0914 x6 = 2.

5、9938 2.0000 1.0038 d = 0.0175 x7 = 2.9990 2.0026 1.0031 d = 0.0059 x8 = 3.0002 2.0006 0.9998 d = 0.0040 x9 = 3.0003 1.9999 0.9997 d = 7.3612e-004 x10 = 3.0000 1.9999 0.9999 d = 2.8918e-004 x11 = 3.0000 2.0000 1.0000 d = 1.7669e-004 x12= 3.0000 2.0000 1.0000 d = 3.0647e-005 0000.1 0000.2 0000.3 3 2 1

6、 x x x 精确解为 第8页/共62页 11 ()IN P xN b ,0,ANPN 把矩阵把矩阵 A 分裂为分裂为 ()AxbNP xb则则 方程组方程组 (2.23) 与与 原方程组原方程组 Ax = b 同解同解. .xGxd(2.23) 记记 G = N- -1P， d = N- -1b， 则则 第9页/共62页 将（2.23）式写成迭代格式 上迭代过程称为迭代法，G 称为迭代矩阵。 ), 2 , 1 , 0(, )()1( kdGxx kk 给定初值x(0)，可得到向量序列 )()2()1( , k xxx 收敛定义：若存在常数向量 x* ,使 ， 则称迭代法收敛，否则,称其不收敛

7、或发散。 * )( lim xx k k 第10页/共62页 问题：x* 是否为方程组 Ax = b 的解？ 定理2.7* 任意给定初始向量 x（0），如果由逐次逼近法产生的向量序列收敛于向量 x*，那么，x* 是方程组 x = Gx + d 的解. * 1 limlim(). kk kk xGxdxGxd 证: 定理2.7 若有常数向量 x*，使对某种范数， 有 则必有 lim0, k k xx lim. k k xx 第11页/共62页 证 依据范数的等价定义，可设 lim0, k k xx 1 limmax ()()0, kii ki n xx 即，有 lim. k k xx 故 定义定

8、义 设方阵设方阵 A 的特征值是的特征值是 , 称称 为矩阵为矩阵 A 的谱半径。的谱半径。 12 , n ( )max | i i A 1 () ,() kkkn xxx 第12页/共62页 性质 谱半径的性质 （1）（特征值上界） 即A 的谱半径不超过A 的任何一种范数。 （2）如果A 为对称矩阵，则 .)(,AARA nn 则设 . 2 AA 第13页/共62页 补充定理 当k 时，G k 0 (G ) 1. 定理2.8 设线性方程组 x= Gx + d 有惟一解，那么，迭代法对任意初始向量 x收敛的充分必要条件是迭代矩阵 G 的谱半径 (G)1. * *1* 10 1 ()(). k

9、kk kk xGxd xxG xxGxx xGxd 证: *1 1 lim()0lim0( )1. k k kk xxGG 因此 用若当标 准形可证. 第14页/共62页 注:因为矩阵范数 都可以 直接用矩阵的元素计算，因此,用定理2.8*， 容易判别迭代法的收敛性。 1 ,G F G,G 第15页/共62页 定理2.9 (充分条件) 如果矩阵的某种范数|G| 1, 则迭代收敛，且有下列误差估计： 11 | (2) | 1 | kkk G xxxx G 1 110 | (1) | 1 | k k G xxxx G 证明：证明：(2) 1 11 *( *) ( *) kk kkk xxG xx

10、G xxxx 111 | *| |(| *|) kkkk xxGxxxx 误差表达式 及收敛速度 。 停机准则 。 第16页/共62页 1 1110 | | *|. 1 |1 | k kkk GG xxxxxx GG 1110 ()() k kkkk xxG xxGxx (1) 110 | | k kk xxGxx 11 | |*| 1 | kkk G xxxx G 第17页/共62页 nnnnnn nn nn bxaxaxa bxaxaxa bxaxaxa . . . . 2211 22222121 11212111 0 ii a 写成写成矩阵形式矩阵形式： A = L U D 分裂分裂 A

11、 = D+ L+U ;Axb 拆分A为三 个部分。 设线性方程组Ax = b的一般形式为 几种基本迭代法 第18页/共62页 令 0 00 000 21 21 nn aa a L 000 00 0 2 112 n n a aa U 11 22 , nn a a D a 第19页/共62页 11212111 bxaxaxa nn 22222121 bxaxaxa nn nnnnnn bxaxaxa 2211 ),2 , 1(0niaii设 i x则可从上式解出, )( 1 12121 11 1nnx axab a x 2.4.2 Jacobi 迭代法 ( Jacobi Iterative Met

12、hods ) )( 1 23231212 22 2nnx axaxab a x 第20页/共62页 )( 1 1 1 11 11 1 n j j jjx ab a x 依此类推，线性方程组Ax = b可化为 )( 1 2 1 22 22 2 n j j jjx ab a x )( 1 1 n ij j jiji ii i xab a x )( 1 1 n nj j jnjn nn n xab a x )( 1 1 11 11 1 n j jjx ab a x )( 1 1 22 22 2 n j jjx ab a x )( 1 1 n j jiji ii i xab a x )( 1 1 n

13、j jnjn nn n xab a x 第21页/共62页 对上式作迭代过程： ),2 , 1 , 0;,2 , 1(kni 则转化为矩阵形式： )( )(1)()1(kkk AxbDxx bDAxDxx kkk1)(1)()1( bDxADDx kk1)(1)1( )( )( 1 1 )()()1( n j k jiji ii k i k i xab a xx (1)() 1,2, 1 n ijkk i ijin j iiii ji a b xx aa bDxULDx kk1)(1) 1( )( 第22页/共62页 Jacobi 迭代矩阵 那么，原方程组与下面的迭代方程组同解：那么，原方程组

14、与下面的迭代方程组同解： () () AxbDLU xb DxLU xb 11 ()xDLU xD b dGJ D,L,U 的具 体形式为 bDxULDx kk1)(1) 1( )( 第23页/共62页 11 22 , nn a a D a 21 3132 123 0 0 0, 0 nnn a Laa aaa 12131 232 3 0 0 0 0 n n n aaa aa Ua 1 1 1213111 1 21 23222 3132 1, 1 12,1 () 00 00 00 00 J n n nn nnnn nn GDL U aaaa aaa a aa a aaa a 第24页/共62页

15、13112 111111 23221 222222 31323 333333 123 0 0 0 0 n n Jn nnn nnnnnn aaa aaa aaa aaa Gaaa aaa aaa aaa 第25页/共62页 第26页/共62页 先来讲一些预备知识。 严格对角占优矩阵与对角占优矩阵 定义1 设 A 是 n 阶方阵. 若 A 满足不等式 且至少有一个 i，使严格不等号成立，则称 A 为（按行）对角占优矩阵. 若对所有的 i =1,2,n，都有严格不等号成立，称 A 为（按行）严格对角占优矩阵。 1, 1, 2 , .,|, n ijii jji inaa 第27页/共62页 例：例

16、： 210 011 011 4100 1410 0141 0014 BA A为按行按列为按行按列严格严格对角占优阵；对角占优阵；B为按行对角为按行对角 占优阵。占优阵。 第28页/共62页 因而，aii0, i =1,2,n，D = diag(aii) 非奇异。令 A = D + L + U = D I + D-1( L + U ) = D(I- G) 其中， G = - D -1( L + U ) ，由 A 满足的条件可知 依定理1.5，知 I- G 非奇异，故 A 也非奇异。 1, max1 n ij i jj i ii a G a 1, 1,2,., n iiij jj i inaa 第

17、29页/共62页 第30页/共62页 1 1,1, 1,2,., nn iiijij jj ijj i inaaa 当 A 是按列严格占优阵时，有 1 1,1, 1,2,., nn jjijij iijiij jnaaa 点击看式(*) 第31页/共62页 第32页/共62页 1 1/10022 ()1/10201 1/3120 J GDLU 123 123 123 10 221 210 0.5 231 xxx xxx xxx 解 迭代矩阵为 00.20.2 0.200.1 1/32/30 - (L+U ) D-1 )( 1 ULDGJ 第33页/共62页 因因 , ,故故 J-迭代法收敛迭代

18、法收敛. . 1 2213 1 10315 J G (1)( )( ) 123 (1)( )( ) 213 (1)( )( ) 312 (0)(0)(0) 123 0.20.20.1 0.20.10.05 121 333 , kkk kkk kkk xxx xxx xxx xxx 任选 矩阵形式矩阵形式迭代公式为迭代公式为 1 ; kJk xG xd 分量形式分量形式的迭代公式为的迭代公式为 计算结果计算结果, ,见见P38 P38 表表2-1.2-1. 计算式 第34页/共62页 123 123 123 2 1 1 21 xxx xxx xxx 解 迭代矩阵为 , 0 2 1 2 1 101

19、 2 1 2 1 0 )( 1 ULDGJ 00.50.5 101 0.50.50 J G 第35页/共62页 其特征方程为 . 0)25. 1( 5 . 05 . 0 11 5 . 05 . 0 2 J GE GJ 的特征值为 因而, J-法不收敛. 0,1.25 ,1.25 ,()1.251, J iiG 第36页/共62页 124 1234 123 1234 102 52 9240 3 48 1 2 61 xxx xxxx xxx xxxx 解 此方程组是严格按行对角占优的, 所以使用J-法收敛. 第37页/共62页 Algorithm: Jacobi Iterative Method

20、Solve given an initial approximation . Input: the number of equations and unknowns n; the matrix entries a ; the entries b ; the initial approximation X0 ; tolerance TOL; maximum number of iterations Mmax. Output: approximate solution X or a message of failure. Step 1 Set k = 1; Step 2 While ( k Mma

21、x) do steps 3-6 Step 3 For i = 1, , n Set ; ( compute xk ) Step 4 If then Output (X ); STOP; ( successful ) Step 5 For i = 1, , n Set X 0 = X ; ( update X0 ) Step 6 Set k +; Step 7 Output (Maximum number of iterations exceeded); STOP. ( unsuccessful ) Axb0X ii n j ij jiji i a Xab X 1 )0( TOLXXXX ii

22、ni |0|max|0| 1 What if aii = 0? 迭代过程中，A 的元素 不改变，故可以事先调整好 A 使得 aii 0，否则 A不可逆。 必须等x(k)完全计算 好了才能计算x(k+1)，因此 需要两组向量存储。 A bit wasteful, isnt it? 第38页/共62页 分析Jacobi迭代法的迭代过程,将公式细化 )( 1 1 )( 11 11 )( 1 )1( 1 n j k jj kk xab a xx )( 1 1 )( 22 22 )( 2 )1( 2 n j k jj kk xab a xx 已经求出之前发现在 )1( 1 )1( 2 )1( 1 )1(

23、 , k i kkk i xxxx 进行迭代仍用时但当求 )( 1 )( 2 )( 1 )1( , k i kkk i xxxx ?, )1( 1 )1( 2 )1( 1 )1( 进行迭代呢利用时能否求 k i kkk i xxxx 2.2.3 Gauss - Seidel 迭代法 第39页/共62页 )( 1 1 )( 1 )( 414 )( 313 )( 212 11 )1( 1 bxaxaxaxa a x k nn kkkk )( 1 2 )( 2 )( 424 )( 323 )1( 121 22 )1( 2 bxaxaxaxa a x k nn kkkk )( 1 3 )( 3 )(

24、434 )1( 232 )1( 131 33 )1( 3 bxaxaxaxa a x k nn kkkk )( 1)1( 11 )1( 33 )1( 22 )1( 11 )1( n k nnn k n k n k n nn k n bxaxaxaxa a x 只存一组向量即可。 写成分量形式： 第40页/共62页 1 (1)(1)( ) 11 1 () in kkk iijjijji jj i ii xa xa xb a 1,2,., ;0,1,2,.in k 写成分量形式： 第41页/共62页 GGd 作 A 的另一个分裂： ()ADLU G-S 迭代 矩阵 Gauss - Seidel迭代

25、的矩阵形式： bLDUxLDx bLDUxLDx bUxxLD bxULDbAx kk1)(1)1( 11 )()( )()( )( )( 第42页/共62页 第43页/共62页 1 (1)( )( ) 11 1 ( (), in kkk iijjijji jj i ii xa xa xb a Jacobi迭代 1 (1)(1)( ) 11 1 ( (), in kkk iijjijji jj i ii xa xa xb a G-S迭代 Jacobi迭代、G-S迭代计算式： 第44页/共62页 例 用Gauss-Seidel迭代法求解补例. 从本例可以看出，Gauss-Seidel迭代法的 收

26、敛速度比Jacobi迭代法要快。 通过迭代,至第7步得到满足精度的解x7 . 第45页/共62页 (1)( )( ) 123 (1)(1)( ) 213 (1)(1)(1) 312 (0)(0)(0) 123 0.20.20.1 0.20.10.05 121 333 , kkk kkk kkk xxx xxx xxx xxx 任选 例 9:用 GS 和 Jacobi 迭代法求解例 6 中的方程组都收敛. 用GS法求解,说明这一结论. 要求 | xk- xk-1| 10-5. 解: GS 迭代矩阵为 1 06060 1 ()01242 300 02848 GDLU 迭代公式为因为 , 所以 GS

27、 法收敛. 1 150 1 300 G 第46页/共62页 123 0.231091,0.147058,0.508402.xxx 5 98 0.410 xx 因为 , 故方程组的近似解为 计算结果计算结果: : kx1(k)x2(k)x3(k) 0 0.00.00.0 1 0.1000000.700000.413333 2 0.1966670.130667 0.486000 3 0.2233330.143267 0.503289 8 0.2310870.147056 0.508399 9 0.2310910.147058 0.508402 第47页/共62页 例 10:方程组用 Jacobi

28、迭代法求解例 7 不收敛,但用GS 法求解收敛. 验证此结论! 证证 例例7已经说明用已经说明用J法不收敛法不收敛. .GS 法的迭代矩阵为法的迭代矩阵为 1 20001 100.50.5 11000100.50.5 112000000.5 gs G Ggs的的特征值为特征值为 0, -0.5, -0.5, (Ggs)= 0.5 0)称为称为松驰因子松驰因子。 第53页/共62页 SOR迭代的分量形式： )()( 1 1 ) 1() 1(k ii n ij k jij i j k jij ii k i xbxaxa a x 1,2,., ;0,1,2,.in k 注：显然，当 =1，SOR方法即为GS迭代法。 SOR方法每迭代一次主要运算量是计算一次矩阵与向量的 乘法。 当 1时，称为超松驰法；当1时，称为低松驰法。 第54页/共62页 SOR迭代的矩阵形式： )( )()()1()()1( bDxUxLxDxDx kkkkk i n ij k jij i j k jij ii k i k i bxaxa a xx )( 1 1 )1()()1( )( )()()1()