东大考博数值分析－解线性方程组的迭代法

1、第第3 3章章 解线性方程组的迭代法解线性方程组的迭代法 迭代法的基本思想是，把n元线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111 （3.1） 或 Ax=b改写成等价的方程组 nnnnnnnnnnngxmxmxmxgxmxmxmxgxmxmxmx2211222221212112121111 ，或x=Mx+g 迭代法是从某一取定的初始向量x x(0)出发,按照一个适当的迭代公式 ,逐次计算出向量x x(1), x x(2),使得向量序列x x(k)收敛于方程组的精确解.迭代法是一类逐次近似的方法.其优点是,算法简便,程序易于实现

2、.由此建立方程组的迭代公式 x(k+1)=Mx(k)+g , k=0,1,2, (3.2)其中M称为迭代矩阵迭代矩阵。 对任意取定的初始向量x x(0),由(3.2)式可逐次算出迭代向量x x(k),k=1,2, 如果向量序列x(k) 收敛于x*,由(3.2)式可得 x*=Mx*+g 从而x x*是方程组x=Mx+g的解,也就是方程组Ax=b的解. 这种求解线性方程组的方法称为迭代法迭代法 ,若迭代序列x(k)收敛,则称迭代法收敛,否则称迭代法发散. 1 Jacobi迭代法和迭代法和Gauss-Seidel迭代法迭代法 Jacobi方法是由方程组(3.1)中第k个方程解出x x(k),得到等价

3、方程组:从而得迭代公式nnnnnnnnnnnnnnnnnnnabxaaxaaxaaxabxaaxaaxaaxabxaaxaaxaax1122112222223222312221211111131113211121, 3 , 2 , 1,) 3 . 3()(1)(2)(1)1(222)(222)(2223)(2221)1(111)(111)(1113)(1112)1(112131232kabxaaxaaxaaxabxaaxaaxaaxabxaaxaaxaaxnnnknnnnknnnknnnkknkkkknkkknnnn式(3.3)称为JacobiJacobi迭代法迭代法,简称为J J迭代法迭代法

4、. . ,则J迭代法可写成 x x(k+1)=BxBx(k)+g g k=0,1,2, 可见 ,J J迭代法的迭代矩阵为0002122222211111112nnnnnnnnaaaaaaaaaaaaBTnnnababab),(222111g若记, 2 , 1 , 0, 2 , 1,)(11)(11)()1(knixaxabaxnijkijijkijiiikjji J J法也记为G-SG-S迭代法也可记为, 3 , 2 , 1,)4 . 3()1(1)1(2)1(1)1(222)(222)(2223)1(2221)1(111)(111)(1113)(1112)1(112131232kabxaax

5、aaxaaxabxaaxaaxaaxabxaaxaaxaaxnnnknnnnknnnknnnkknkkkknkkknnnn式(3.4)称为Gauss-SeidelGauss-Seidel迭代法迭代法,简称为G-SG-S迭代法迭代法. . 若在J J迭代法中,充分利用新值, 则可以得到如下的迭代公式, 2 , 1 , 0, 2 , 1,)(11)(11)1()1(knixaxabaxnijkijijkijiiikjji方程组的精确解为x x*=(1,1,1)T. 解解 J J迭代法计算公式为例例1 用J法和G-S法求解线性方程组141035310214310321321321xxxxxxxxx5

6、7)(2103)(1101)1(321)(3103)(151)1(257)(3101)(2103)1(1kkkkkkkkkxxxxxxxxx取初始向量x x(0)=(0,0,0)T,迭代可得4 . 1, 5 . 0, 4 . 1)1(3)1(2)1(1xxx11. 1, 2 . 1,11. 1)2(3)2(2)2(1xxx计算结果列表如下:可见,迭代序列逐次收敛于方程组的解, 而切迭代7次得到精确到小数点后两位的近似解.kx1(k)x2(k)x3(k)x(k)-x*0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550

7、.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636 G-S G-S迭代法的计算公式为: 同样取初始向量x x(0)=(0,0,0)T, 计算结果为 由计算结果可见,G-S迭代法收敛较快.取精确到小数点后两位的近似解,G-S迭代法只需迭代3次,而J迭代法需要迭代7次.57)1(2103)1(1101)1(321)(3103)1(151)1(257)(3101)(2103)1(1kkkkkkkkkxxxxxxxxxkx1(k

8、)x2(k)x3(k)x(k)-x*012301.41.06340.995104400.781.020480.9952756801.0260.9875161.0019068610.40.06340.0048956 为了进一步研究,从矩阵角度来讨论上述迭代法. 对线性方程组AxAx=b b,记 D D=diag(a11,a22,ann)000121323121nnnnaaaaaaL000,122311312nnnnaaaaaaU则有 A A=D D-L L-U U于是线性方程组 AxAx=b b 可写成 (D D-L L-U U)x x=b b等价于 DxDx=(L L+U U)x x+b b

9、或或 x x=D D-1(L L+U U)x x+D D-1b b 由此建立J J迭代法迭代公式 x x(k+1)=D D-1(L L+U U)x x(k)+D D-1b b k=0,1,2,或写成 x x(k+1)=BxBx(k)+g g k=0,1,2,其中000)(21222222111111121nnnnnnnnaaaaaaaaaaaaULDBnnnababab2221111,bDgG-SG-S迭代法迭代公式可写成 x x(k+1)=D D-1LxLx(k+1)+D D-1UxUx(k)+D D-1b b 讨论迭代法 x(k+1)=Mx(k)+g k=0,1,2, Dx Dx(k+1)

10、=LxLx(k+1)+UxUx(k)+b b (D D-L L)x x(k+1)=UxUx(k)+b b x x(k+1)=(D D-L L)-1UxUx(k)+(D D-L L)-1b b 所以G-SG-S迭代法可以写成 x x(k+1)=GxGx(k)+g g k=0,1,2,其中 G G=(D D-L L)-1U U , g g=(D D-L L)-1b b 2 2 迭代法的收敛性迭代法的收敛性的收敛性. 记误差向量e e(k)=x x(k)-x x*,则迭代法收敛就是e e(k)0 0.由于 x(k+1)=Mx(k)+g k=0,1,2, x*=Mx*+g k=0,1,2,所以 e(k

11、+1)=Me(k) , k=0,1,2,递推可得 e(k)=Mke(0) , k=0,1,2,可见,当k时, e e(k)0 0 Mk O O. 对任意初始向量x x(0),迭代法收敛(M)1.定理定理3.1 证证 若Mk0, 则k(M)=(Mk)Mk0,所以(M)1. 若(M)0,使得(M)+1.则MkMk (M)+)k 0. 若若M1,则对任意x x(0),迭代法收敛,而且 定理定理3.2)6 . 3(0)(1)k*(k)xxM1Mxx)5 . 3(1)1()(*)(kkkxxMMxx 证证 由于 x(k+1)=Mx(k)+g x(k)=Mx(k-1)+g x*=Mx*+g所以 x(k+1

12、) -x(k)=M(x (k) -x(k-1) ) , x(k+1) x*=M(x (k) x* )于是有 x(k+1) -x(k) Mx (k) -x(k-1) x(k+1) x*Mx (k) x* x(k) x*=(x (k) x(k+1)+(x(k+1) x* ) x (k) x(k+1)+x(k+1) x* x(k) x* Mx (k) x(k-1) +Mx(k) x* 所以( )*( )(1)1kkkMxxxxM)0()1(1xxMMk 定理3.2只是收敛的充分条件,并不必要,如7 . 005 . 08 . 0M则M1=1.2,M=1.3,M2=1.09,MF=1.17但(M)=0.

13、81, 所以对应的迭代法是收敛的. 由(3.5)式可见,x (k) -x(k-1) 很小时,x(k) x*就很小,实际上用x (k) -x(k-1) 作为迭代终止的条件。例如，例1中J-法计算结果如下：kx1(k)x2(k)x3(k)x(k)-x*0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.00176

14、36x (6) -x(5) =0.011339,x(7) x(6)=0.0056695 由(3.6)式可得:若使x(k) x* ,只需可以事先估计达到某一精度需要迭代多少步。)0()1(1xxMMk , 即M(0)(1)xx)M(1ln/ )ln(k 用J J迭代法求例1中方程组的解,取x(0)=(0,0,0)T,若使误差x(k)-x*10-5,问需要迭代多少次? 解解 由例1知,x x(1)=(1.4,0.5,1.4)T,于是有,x x(1)-x x(0)=1.4 ,B B=0.5 .例例2 00010310110351101103Bk应满足095.185 . 0ln/ )4 . 1105

15、. 0ln(5k故取k=19, 即需要迭代19次.3 J3 J迭代法和迭代法和G-SG-S迭代法的收敛性迭代法的收敛性 定理定理3.33.3 J J迭代法收敛(B)1;若B1J J迭代法收敛; G-SG-S迭代法收敛(G)1;若G1 G-SG-S迭代法收敛; 定义定义3.13.1 若n阶矩阵A=(aij)满足:niaaiinijjij, 2 , 1,1则称矩阵A是严格对角占优矩阵严格对角占优矩阵. 引理引理 若A是严格对角占优矩阵, 则det(A)0. 证证 A=D-L-U=D(E-D-1(L+U)=D(E-B)因此, (B)B1,故=1不是B B的特征值,det(E E-B B)0。 定理定

16、理3.43.4 设A是严格对角占优矩阵,则解线性方程组Ax=b的J J迭代法和G-SG-S迭代法均收敛。 因为A是严格对角占优矩阵, 所以det(D)0, 而且1max11nijjiiijniaaB所以, det(A)0. 证证 由于B1, 所以J J迭代法收敛。 设是G G的任一特征值, 则满足特征方程 det(E-G)= det(E-(D-L)-1U)所以有 det(D-L)-U)=0nnnnnnaaaaaaaaa212222111211UL)(D 若|1, 则矩阵(D-L)-U 是严格对角占优矩阵, 这与 det(D-L)-U)=0矛盾, 所以|1,于是(G)1时称为超松弛迭代超松弛迭代

17、, , 当当1时称为欠松弛迭代欠松弛迭代. ., 2 , 1 , 0, 2 , 1)7 . 3()()(11)1()()1(knixaxabaxxnijkijijkijiiikikjji 其矩阵形式 x(k+1)=x(k)+D-1(b+Lx(k+1)+(U-D)x(k) , k=0,1,2,于是有 Dx(k+1)=Dx(k)+(b+Lx(k+1)+(U-D)x(k) 所以 x(k+1)=(D-L)-1 (1-)D+Ux(k)+(D-L)-1b ,k=0,1,2,因此,SOR方法的迭代矩阵为 =(D-L)-1 (1-)D+U SORSOR方法收敛( )1;若 1,则SORSOR方法收敛. 定理定

18、理3.73.7 若SORSOR方法收敛, 则02.定理定理3.6 证证 设SORSOR方法收敛, 则( )1,所以 |det( )| =|12 n|1而 det( ) =det(D-L)-1 (1-)D+U) =det(E-D-1L)-1 det(1-)E+D-1U) =(1-)n于是 |1-|1, 或 02定理定理3.8 设A是严格对角占优矩阵,则解方程组Ax=b的SORSOR方法,当01时收敛. 定理定理3.93.9 设A是对称正定矩阵, 则解方程组Ax=b的SORSOR方法,当00 (Uy,y)=(y,Ly)=(Ly,y) =-i 0(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y)

19、 =-2所以)()()1 (ii2222222)()(|当02时,有 (-+)2-(-)2= (2-)(2-) = (2-)(2-)0所以|21, 因此( )1,即S0R方法收敛.可得 =2/ 设是B的任一特征值, y是对应的特征向量, 则 (L+U)y=Dy于是 (Ly,y)+(Uy,y)=(Dy,y)当A对称正定时,即2-0时,|0而 (2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y) =+2即,当A对称正定时,JacobiJacobi迭代法收敛2D-A正定. SORSOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即选取=*,使( )达到最小,是一个尚

20、未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.41.6. 用SORSOR方法解线性方程组7910431017210424321321321xxxxxxxxx 解解 SORSOR方法迭代公式为方程组的精确解是x x*=(2,1,-1)T.例例4)91047(9)101723(17)42410(4)(3)1(2)1(1)(3)1(3)(3)(2)1(1)(2)1(2)(3)(2)(1)(1)1(1kkkkkkkkkkkkkkkxxxxxxxxxxxxxxx取x x(0)=(0,0,0)T,=1.46,计算结果如下:kx1(k)x2(k)x3(k)01232003.652.321669102.56613991.999998700.88458820.42309390.69482611.00000130-0.2021098-0.22243214-0.4952594-1.0000034 从结果可见 ,迭代20次时已获得精确到小数点后五位的近似解.如果取=1.25,则需要迭代56次才能得到具有同样精度的近似解;如果取=1,则需迭代110次以上.练习题练习题第第75页页 习题习题33-2, 3-3