解线性方程组的迭代法

第四章4.1解线性方程组的迭代法信息科学技术系11112211211222221122(1)nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb,0,X,.11ijnnTAXbATnna,,),,)(x(bxbb矩阵表示记为这里我们假设A解线性方程组的两类方法直接法:经过有限次运算后可求得方程组精确解的方法(不计舍入误差!)迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。迭代法研究的主要问题1）迭代格式的构造；2）迭代的收敛性分析；3）收敛速度分析；4）复杂性分析；（计算工作量）5）初始值选择。迭代格式的构造把矩阵A分裂为则,0,AQCQ11()().AxbQCxbIQCxQbxBxg迭代过程B称为迭代矩阵。给定初值就得到向量序列定义：若称逐次逼近法收敛，否则，称逐次逼近法不收敛或发散。1,(2)kkxBxg0,x01,,,nxxx*lim,nnxx问题：是否是方程组（1）的解？定理1：任意给定初始向量，若由迭代公式（2）产生的迭代序列收敛到，则是方程组（1）的解。证：0x*x*x*x**1limlim().kkkkxBxgxBxg逐次逼近法收敛的条件定理2：对任意初始向量，由（2）得到的迭代序列收敛的充要条件是迭代矩阵的谱半径证：因此()1.B0x**1**1*10()().kkkkkxBxgxBxgxxBxxBxx*11lim()0lim0()1.kkkkxxBB要检验一个矩阵的谱半径小于1比较困难，所以我们希望用别的办法判断是否有定理3：若逐次逼近法的迭代矩阵足，则逐次逼近法收敛。Remark:因为矩阵范数，，都可以直接用矩阵的元素计算，因此，用定理3，容易判别逐次逼近法的收敛性。1lim0.kkB1B1BFBB问题：如何判断可以终止迭代？定理4：若迭代矩阵满足则（3）（4）Remark:1)(4)式给出了一个停止迭代的判别准则。2)(3）式指出越小收敛越快。，1B1*1101kkBxxxxB*111kkkBxxxxB1B证：**1221*221*11*11()()kkkkkkkkkkkkkxxxxxxxxxxBxxBxxBxxBxx1110kkkkkxxBxxBxxJacobi迭代1111221331121122223322311322333344331122,11+nnnnnnnnnnnnnnnaxaxaxaxaxaxaxaxaxaxbaxaxaxbaxaxaxbaxbDxLxUxJacobi迭代11(),xDLUxDb()(),0,ijijijijLllaijelsel()(),0,ijijijijDddaijelsed()ADLU分裂(),(AxbDxLUxb若|D|0)迭代过程：若记111(),kkxDLUxDb1(1)()()111(()),inkkkiijjijjijjiiixaxaxba(1)()()11().nkkkiiijjijiixbaxxa()()()12(,,,),kkkknxxxx算法描述1输入2if,then2.1for2.1.1s=0,2.1.2for2.1.32.1.4ifthen0,,,,.AbxMkM1,2,,in1,2,,jn0()ijjssax10()()/()iiiiixbsax01|()()|iixx01|()()|,iixx(1)()()11().nkkkiiijjijiixbaxxa2.2k=k+12.3ifthen2.3.12.3.2goto2else输出结束。else2.4输出迭代次数太大。3结束1,xk10xxGauss-Seidel迭代假设||0,D1(1)()()111(()),inkkkiijjijjijjiiixaxaxbaJacobi迭代1(1)(1)()111(()),inkkkiijjijjijjiiixaxaxba1(1)(1)()()11(),inkkkkiijjijjiijjiiixaxaxbxaAxb()ADLU分裂算法描叙1输入2if,then2.1for2.1.1s=0，2.1.2for2.1.30,,,,.AbxMkM1,2,,in1,2,,jn0()ijjssax0()itx00()()/()iiiiixbsax1(1)(1)()()11(),inkkkkiijjijjiijjiiixaxaxbxa2.1.4ifthen2.2k=k+12.3if,输出结果，结束。else2.4输出迭代次数太大。3结束0|()|,ixt0|()|ixtRemark:1)Gauss-Seidel迭代法的计算过程比Jacobi迭代法更简单。计算过程中只需用一个一维数组存放迭代向量。2)Gauss-Seidel迭代不一定比Jacobi迭代收敛快。例希望直接对系数矩阵A研究这俩种迭代收敛条件。定理5设A是有正对角元的n阶对称矩阵，则Jacobi迭代收敛A和2D-A同为正定矩阵。证：记则即，从而有相同的谱半径。1122(,,,),nnDdiagaaa12111111(,,,).Ddiagaaa111112222()JDIDADDIDAB1122()~JIDADB由A的对称性，也对称，因而特征值全为实数，记为则的任一特征值为。A，正定。故正定。111122()iijjijDADaaa,(1).iin1122IDAD1i()111102JiiB11222IDAD111122222(2)DADIDADD2DAA正定正定，特征值小于1。若2D-A正定,特征值小于1,所以特征值大于－1。1122DAD1122IDAD11112222(2)()IDDADIDADJB定理6A按行（列）严格对角占优，则Jacobi迭代收敛。引理A按行（列）严格对角占优（）证（提示）1.JB11.JB1,max||nijJjjiiiaBa定理7A按行严格对角占优，则Gauss-Seidel迭代收敛。证设是任一特征值，x是相应特征向量。设若则GSB||max||.ijxx1111()||||||||||||||.injiiijijjjjiiDLUxxDxLxUxxaaaxx||1,111||||||.iniiijijjjiaaa定理8A按列严格对角占优，则Gauss-Seidel迭代收敛。证设是的任一特征值，x是相应特征向量。设111()()(())(),DLUDLUDLDL1(())UDL||max||.ijxx111().niiiijijjijjijDLxUxaxaxax