第三章解线性方程组的迭代法20141011

第3章解线性方程组的迭代法迭代法的基本思想是，把n元线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.........................................................22112222212111212111（3.1）或Ax=b改写成等价的方程组nnnnnnnnnnngxmxmxmxgxmxmxmxgxmxmxmx2211222221212112121111，或x=Mx+g迭代法是从某一取定的初始向量x(0)出发,按照一个适当的迭代公式,逐次计算出向量x(1),x(2),…,使得向量序列{x(k)}收敛于方程组的精确解.迭代法是一类逐次近似的方法.其优点是,算法简便,程序易于实现.由此建立方程组的迭代公式x(k+1)=Mx(k)+g,k=0,1,2,…(3.2)其中M称为迭代矩阵。对任意取定的初始向量x(0),由(3.2)式可逐次算出迭代向量x(k),k=1,2,…,如果向量序列{x(k)}收敛于x*,由(3.2)式可得x*=Mx*+g从而x*是方程组x=Mx+g的解,也就是方程组Ax=b的解.这种求解线性方程组的方法称为迭代法,若迭代序列{x(k)}收敛,则称迭代法收敛,否则称迭代法发散.§1Jacobi迭代法和Gauss-Seidel迭代法Jacobi方法是由方程组(3.1)中第k个方程解出x(k),得到等价方程组:从而得迭代公式nnnnnnnnnnnnnnnnnnnabxaaxaaxaaxabxaaxaaxaaxabxaaxaaxaax1122112222223222312221211111131113211121,3,2,1,)3.3()(1)(2)(1)1(222)(222)(2223)(2221)1(111)(111)(1113)(1112)1(112131232kabxaaxaaxaaxabxaaxaaxaaxabxaaxaaxaaxnnnknnnnknnnknnnkknkkkknkkknnnn式(3.3)称为Jacobi迭代法,简称为J迭代法.,则J迭代法可写成x(k+1)=Bx(k)+gk=0,1,2,…可见,J迭代法的迭代矩阵为0002122222211111112nnnnnnnnaaaaaaaaaaaaBTnnnababab),,,(222111g若记,2,1,0,,2,1,)(11)(11)()1(knixaxabaxnijkijijkijiiikjjiJ法也记为G-S迭代法也可记为,3,2,1,)4.3()1(1)1(2)1(1)1(222)(222)(2223)1(2221)1(111)(111)(1113)(1112)1(112131232kabxaaxaaxaaxabxaaxaaxaaxabxaaxaaxaaxnnnknnnnknnnknnnkknkkkknkkknnnn式(3.4)称为Gauss-Seidel迭代法,简称为G-S迭代法.若在J迭代法中,充分利用新值,则可以得到如下的迭代公式,2,1,0,,2,1,)(11)(11)1()1(knixaxabaxnijkijijkijiiikjji方程组的精确解为x*=(1,1,1)T.解J迭代法计算公式为例1用J法和G-S法求解线性方程组141035310214310321321321xxxxxxxxx57)(2103)(1101)1(321)(3103)(151)1(257)(3101)(2103)1(1kkkkkkkkkxxxxxxxxx取初始向量x(0)=(0,0,0)T,迭代可得4.1,5.0,4.1)1(3)1(2)1(1xxx11.1,2.1,11.1)2(3)2(2)2(1xxx计算结果列表如下:可见,迭代序列逐次收敛于方程组的解,而且迭代6次得到精确到小数点后两位的近似解.kx1(k)x2(k)x3(k)‖x(k)-x*‖012345601.40001.11000.92900.99061.01161.000300.50001.20001.05500.96450.99531.005801.40001.11000.92900.99061.01161.000310.50000.20000.07100.03550.01160.0058G-S迭代法的计算公式为:同样取初始向量x(0)=(0,0,0)T,计算结果为可见G-S迭代法收敛较快.取精确到小数点后两位的近似解,G-S迭代法只需迭代4次,而J迭代法需要迭代6次.57)1(2103)1(1101)1(321)(3103)1(151)1(257)(3101)(2103)1(1kkkkkkkkkxxxxxxxxxkx1(k)x2(k)x3(k)‖x(k)-x*‖0123401.40001.06340.99511.001200.78001.02050.99531.000801.02600.98751.00190.999610.40000.06340.00490.0012为了进一步研究,从矩阵角度来讨论上述迭代法.对线性方程组Ax=b,记D=diag(a11,a22,…,ann)000121323121nnnnaaaaaaL000,122311312nnnnaaaaaaU则有A=D-L-U于是线性方程组Ax=b可写成(D-L-U)x=b等价于Dx=(L+U)x+b或x=D-1(L+U)x+D-1b由此建立J迭代法迭代公式x(k+1)=D-1(L+U)x(k)+D-1bk=0,1,2,…或写成x(k+1)=Bx(k)+gk=0,1,2,…其中000)(21222222111111121nnnnnnnnaaaaaaaaaaaaULDBnnnababab2221111,bDgG-S迭代法迭代公式可写成x(k+1)=D-1Lx(k+1)+D-1Ux(k)+D-1b讨论迭代法x(k+1)=Mx(k)+gk=0,1,2,…Dx(k+1)=Lx(k+1)+Ux(k)+b(D-L)x(k+1)=Ux(k)+bx(k+1)=(D-L)-1Ux(k)+(D-L)-1b所以G-S迭代法可以写成x(k+1)=Gx(k)+gk=0,1,2,…其中G=(D-L)-1U,g=(D-L)-1b§2迭代法的收敛性的收敛性.记误差向量e(k)=x(k)-x*,则迭代法收敛就是e(k)0.由于x(k+1)=Mx(k)+gk=0,1,2,…x*=Mx*+gk=0,1,2,…所以e(k+1)=Me(k),k=0,1,2,…递推可得e(k)=Mke(0),k=0,1,2,…可见,当k时,e(k)0MkO.对任意初始向量x(0),迭代法收敛(M)1.定理3.1证若‖Mk‖0,则k(M)=(Mk)‖Mk‖0,所以(M)1.若(M)1,则存在0,使得(M)+1.则‖Mk‖‖M‖k((M)+)k0.若‖M‖1,则对任意x(0),迭代法收敛,而且定理3.2)6.3((0)(1)k*(k)xxM1Mxx)5.3(1)1()(*)(kkkxxMMxx证由于x(k+1)=Mx(k)+gx(k)=Mx(k-1)+gx*=Mx*+g所以x(k+1)-x(k)=M(x(k)-x(k-1)),x(k+1)–x*=M(x(k)–x*)于是有‖x(k+1)-x(k)‖‖M‖‖x(k)-x(k-1)‖‖x(k+1)–x*‖‖M‖‖x(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（k)‖-‖Ｍ‖‖x(k)–x*‖所以()*kxx)1()(1kkxxMM)0()1(1xxMMk定理3.2只是收敛的充分条件,并不必要,如7.005.08.0M则‖M‖1=1.2,‖M‖=1.3,‖M‖2=1.09,‖M‖F=1.17但(M)=0.81,所以迭代法是收敛的.由(3.5)式可见,‖M‖越小收敛越快,且当‖x(k)-x(k-1)‖很小时,‖x(k)–x*‖就很小,实际上用‖x(k)-x(k-1)‖作为迭代终止的条件.例如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.0017636‖x(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迭代法求例1中方程组的解,取x(0)=(0,0,0)T,若使误差x(k)-x*10-5,问需要迭代多少次?解由例1知,x(1)=(1.4,0.5,1.4)T,于是有,x(1)-x(0)=1.4,B=0.5.例200010310110351101103Bk应满足095.185.0ln/)4.1105.0ln(5k故取k=19,即需要迭代19次.§3J迭代法和G-S迭代法的收敛性定理3.3J迭代法收敛(B)1;若‖B‖1J迭代法收敛;G-S迭代法收敛(G)1;若‖G‖1G-S迭代法收敛;定义3.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)‖B‖1,故=1不是B的特征值,det(E-B)0.定理3.4设A是严格对角占优矩阵,则解线性方程组Ax=b的J迭代法和G-S迭代法均收敛.因为A是严格对角占优矩阵,所以det(D)0,而且1max11nijjiiijniaaB所以,det(A)0.证由于‖B‖1,所以J迭代法收敛.设是G的任一特征值,则满足特征方程det(E-G)=det(E-(D-L)-1U)=det((D-L)-1)det((D-L)-U)=0所以有det((D-L)-U)=0nnnnnnaaaaaaaaa212222111211UL)(D若||1,则矩阵(D-L)-U是严格对角占优矩阵,这与det((D-L)-U)=0矛盾,所以||1,于是(G)1.定理3.5设A是对称正定矩阵,则解方程组Ax=