解线性代数方程组的迭代法

第四章解线性代数方程组的迭代法三种基本的迭代方法及收敛条件4.1雅可比迭代4.2高斯-赛德尔(Gauss-Seidel)迭代4.3超松弛迭代求解线性方程组Ax=y，可用直接法。当A为稀疏矩阵时，直接法将破坏矩阵A的稀疏性。我们可以对线性方程组进行等价变换，构造出等价方程组x=Mx+g,由此构造迭代关系式例如，分解A=N-P，则(1)(),0,1,2,kkxMxgk1111(),(,),NPxyNxPxyxNPxNyMxgMNPgNy(0)(0)(0)(0)T12(1)(2)Takeanyinitialvector(,,,),weobtainiterativesequences,,Thisistheiterativemethodtobediscussed.nxxxxxx迭代法：构造一个向量序列{x(k)}，使其收敛到某个极限向量x*，即则x*就是线性方程组的解。常用迭代方法：雅可比迭代，高斯-赛德尔迭代，松弛迭代等。()*,kxx4.1雅可比迭代•迭代格式线性方程组Ax=y，即11112211211222221122(4.1)nnnnnnnnnnaxaxaxyaxaxaxyaxaxaxy若aii≠0,i=1,2,…,n,（6.1）可变为记则1311211231111111123221221322222222,112121nnnnnnnnnnnnnnnnnnnaaayxxxxaaaaaaayxxxxaaaaaaayxxxxaaaa/,/,ijijiiiiiibaagya1122133112211233221122,11nnnnnnnnnnnxbxbxbxgxbxbxbxgxbxbxbxg写成矩阵形式或简记为对任意初始向量构造迭代格式：(4.2)是称为简单迭代或雅可比迭代。1121311122123222331323331230000nnnnnnnnnxbbbxgxbbbxgxbbbxgxbbbxg(0)(0)(0)(0)12.(,,,),nxBxgxxxx(1)(),0,1,2,(4.2)kkxBxgk•雅可比迭代矩阵记所以称为雅可比迭代矩阵，是常数项向量。11221122diag(,,,),nnnnaaDaaaa1111,From,wehave()()()().ADADAxyDADxyDxDAxyxDDAxDyIDAxDy1(),BIDA1gDy如果通过(4.2)构造的迭代序列{x(k)}收敛，即则x*为Ax=y的解，即Ax*=y。事实上，对(4.2)取极限得()lim*,kkxx11***()*,*,i.e.*isasolutionof.xBxgxIDAxDyAxyxAxy•迭代格式的收敛性引理4.1(线性代数定理)设矩阵序列则（证明见关治和陈景良编《数值计算方法》P410-412）定理4.1设迭代格式为由初始向量x(0)产生的向量序列{x(k)}收敛的充分必要条件是证明必要性（）设则由（4.3）得(1)(),0,1,2,(4.3)kkxMxgk()1.M2,,,,,kIMMM()lim0()1.kkxM()lim*,kkxx**.(4.4)xMxg(4.3)-(4.4)得设第k次迭代的误差记为充分性（）设ρ(M)1,证{x(k)}收敛。如果ρ(M)1，则I-M为非奇异矩阵。事实上，因为ρ(M)1，λi1，因此λ=1不是M的特征值，即(1)()()*()(*)(*)kkkxxMxgMxgMxx()*,thuskkxx21110,kkkkMMM11(1)001limlimlim(*)0,.i.e.lim0.Fromwehave()1.kkkkkkkkMxxMM|1|||0.IMIMLemma4.1,所以方程组(I-M)x=f有惟一解x*,满足(I-M)x*=f，即x*=Mx*+f。于是由引理6.1知，()(1)2(2)(0)0*(*)(*)(*).kkkkkxxMxxMxxMxxM()()If()1,thenlim0,lim(*)0,i.e.lim*.kkkkkkMMxxxxThiscompletestheproof.例4.1设系数矩阵为判定雅可比迭代格式的收敛性。解雅可比迭代矩阵为特征方程为122111,221A022101,(/).220ijijiiMBbaa322||110,0,thus()1.22iIMM实际计算中，M的特征值难于计算，因此也难于判断。由于可用作为判断收敛的条件。定理4.2若则由迭代格式确定的迭代序列{x(k)}收敛，且有误差估计式()M(),MM1M1,qM(1)(),0,1,2,(4.3)kkxMxgk()()(1)()(1)(0)*,(a)1or*.(b)1kkkkkqxxxxqqxxxxq证明又因为()()1,fromTheorem4.1,{}converges.kMMx(1)()()(1)(1)(0)(1)()()(1)()(1)()(1)(1)()(1)(0)(()(),();(c)()kkkkkkkkkkkkkkkkkxxMxxMxxxxMxxMxxqxxxxMxxMx1)(0)(1)(0)(d).kxqxx(1)()()()()(1)(1)()(1)()*()(*)(*),**(*)kkkkkkkkkkxxMxgMxgMxxxxxxxxxxMxx分别把（c）和（d）代入（e）即得证（a）,（b）。注：是收敛的充分条件，但不是必要条件。因为收敛，不能推出。例如()()(1)()**kkkkxxxxqxx()()(1)When1,wehave1*(e)1kkkqxxxxq1M(){}kx(){}kx1M12()10.90,0.9,0.8,()1,0.20.8{}converges.Butmax{1.1,0.8}1.11.kMMxM定义4.1如果A的元素满足并且至少有一个不等式严格成立，则称A为行对角占优矩阵；如果A的元素满足则称A为严格行对角占优矩阵。同样可以定义列对角占优矩阵和严格列对角占优矩阵。引理4.2（对角优势定理）(3)若A为严格对角占优矩阵，则A非奇异，且aii≠0,i=1,2,…,n.1||||,1,2,,niiijjjiaain1||||,1,2,,niiijjjiaain证明由线性代数知识知，det(A)≠0Ax=0只有零解。反证法假定det(A)=0，则Ax=0有非零解，记为T121(,,,)0,thensatisfies0,1,2,,.(1)nnijjjxxxxxaxin10,thenthereexistssomepositiveinteger,suchthat||=max||0.From(1),wehavekjjnxknxx111.Contradiction.nnnkjjkjjkkkjkjjjkjkjkjkaxaxaaxxBythedefinitionofstrictlydiagonallydominant,0.iia当方程组的系数矩阵为严格对角占优时，关于雅可比迭代我们有下面的定理。定理4.3当系数矩阵为严格对角占优时，雅可比迭代收敛。证明方法一：根据严格对角占优矩阵的定义。雅可比迭代矩阵：(),where/,;0.ijnnijijiiiiBbbaajib111111||()maxmax||=max||/||1,Jacobiconverges.nnijijininiijjjinijiiinjjiaBBbaaa方法二：反证法。因为A为严格对角占优矩阵，由引理4.2知，aii≠0.11122,diag(,,,).nnBIDADaaa111Assume()1,thenmatrixexistssomeeigenvalue,suchthat||1,anddet()0.However,ontheonehand,()(),det()=det()det()=0.BBIBIBIIDADDADIBDDAD1det()0,det()=0.(1)DDADButontheotherhand,111212122212(2)nnnnnnaaaaaaDADaaa1Because||1,||||,1,2,,.isstrictlydiagonallydominant.niiiiijjjiaaainDADByLemma6.2,wehavedet()0(3)(3)contradictswith(1).Thus()1.DADB•雅可比迭代算法(1)(),0,1,2,(4.2)kkxBxgk(1)()()()112213311(1)()()()221123322(1)()()()331132233(1)()()(1122,11i.e.kkkknnkkkknnkkkknnkkkknnnnnnxbxbxbxgxbxbxbxgxbxbxbxgxbxbxbx)(4.5)ng算法描述：1.输入系数矩阵A和常数项向量y；2.形成雅可比迭代矩阵B和向量g3.赋初始值FOR=1,2,...,{/FOR=1,2,...,/0}iiiiijijiiiiingyajnbaabT()T(1)1{0,0,...,0}(standsfor)2{1,1,...,1}(standsfor)kkxxxx4.实现迭代5.输出方程组的解x2[i]，i=1,2,…,n.6WHILE12101:2FOR1,2,...,021FOR1,2,...,[,]*1[]2[][]ENxxxxunsxBxgvnssbuvxvxusguDWHILE4.2高斯-塞德尔(Gauss-Seidel)迭代•高斯-塞德尔迭代的计算在雅可比迭代(4.4)的迭代过程中，可用新求出的x(k+1)的分量来代替x(k)的分量参与计算，直到用x(k+1)的前n-1分量代替x(k)的前n-1个分量求出为止，即可由（4.5）得到高斯-塞德尔迭代：(1)()()()112213311(1)(1)()()221123322(1)(1)(1)()331132233(1)(1)(1)1122,1kkkknnkkkknnkkkknnkkknnnnnxbxbxbxgxbxbxbxgxbxbxbxgxbxbxb(1)1(4.6)knnxg(1)knx令B=L+U，其中则高斯-赛德尔迭代可写成矩阵形式或写成其中，为高斯-塞德尔迭代矩阵，121312123231321,,11200000,,000nnnnnnnnbbbbbbbbLUbbbb(1)(