解线性方程组的迭代法

第五章解线性方程组的迭代法本章主要内容：迭代法收敛定义，矩阵序列收敛定义，迭代法基本定理，雅可比迭代法，高斯-塞德尔迭代法，系数矩阵为严格对角占优阵的采用雅可比迭代、高斯-塞德尔迭代的收敛性。教学目的及要求：使学生了解迭代法收敛定义，迭代法基本定理，掌握雅可比迭代法、高斯-塞德尔迭代法。教学重点：雅可比迭代法，高斯-塞德尔迭代法。教学难点：迭代法基本定理的证明以及作用。教学方法及手段：应用严格的高等代数、数学分析知识，完整地证明迭代法基本定理，讲清雅可比迭代法与高斯-塞德尔迭代法的关系，介绍雅可比迭代法与高斯-塞德尔迭代法在编程中的具体实现方法。在实验教学中，通过一个具体实例，让学生掌握雅可比迭代法与高斯-塞德尔迭代法的具体实现，并能通过数值计算实验，揭示高斯-塞德尔迭代法是对雅可比迭代法的一种改进这一事实。教学时间：本章的教学的讲授时间为6学时，实验学时4学时。教学内容：一迭代法定义对于给定的线性方程组xBxf，设它有唯一解*x，则**xBxf(6.1)又设(0)x为任取的初始向量，按下述公式构造向量序列(1)(),0,1,2,kkxBxfk(6.2)这种逐步代入求近似解的方法称为迭代法（这里B与f与k无关）。如果()limkkx存在（记为*x），称此迭代法收敛，显然*x就是方程组的解，否则称此迭代法发散。迭代法求方程近似解的关键是是讨论由(6.1)式所构造出来的向量序列(){}kx是否收敛。为此，我们引入误差向量(1)(1)*kkxx将(6.2)式与(6.1)式相减，我们可得(1)*()*()kkxxBxx(1)(),0,1,2,kkBk递推下去，得()(1)2(2)(0)kkkkBBxBx要考察(){}kx的收敛性，就要研究B在什么条件下有()lim0kk也就是要研究B在什么条件下有lim0kkB。二迭代法收敛性定理矩阵的收敛性定义设有矩阵序列()()knnkijAaR及()nnijAaR，如果nn个数列极限均存在且有()lim(,1,2,,)kijijkaaijn则称{}kA收敛于A，记为limkkAA。注：矩阵序列的收敛性是根据矩阵的每个分量序列的收敛性来定义的。【例题1】讨论约当块矩阵的幂次所构成的矩阵序列的收敛性。形如11nnJ的矩阵称之为n阶的约当块。它可以分解成为0010010JI下面，我们分几步来研究矩阵序列23,,,,,mJJJJ的收敛性。1矩阵的幂阵的性质我们不妨以4阶阵来看看这种性质。0101010，2001001000，30001000000，40000000000m的性质可归纳为以下两点：（1）如4m时，0m；（2）m=1时，的第2条对角线元素为1，其余为零；m=2时，2的第3条对角线元素为1，其余为零；m=3时，3的第4条对角线元素为1，其余为零。简言之，m的第m+1条对角线元素为1，其余为零（当没有第m+1条对角线时，m应理解为零矩阵）。2计算约当块的幂次。当mn时，10001()mnmmkkmkmkkmkmmmkkJICCC11nmkkmkmkIC11221(1)112211mmmnmnmmmmmmmmmmmmCCCCCC3一个极限性质因为lim0(01,0)kmmmcck，得到lim01kmkmmC这里，注意事实(1)(1)!kkmmmmkCmk4约当块幂阵的收敛性结论当1时，{}mJ收敛于零矩阵；当1，{}mJ发散。矩阵序列极限的概念可以用矩阵范数来描述。【定理1】limlim0kkkkAAAA，其中为矩阵的任意一种范数。证明显然有limlim0kkkkAAAA再利用矩阵范数的等价性，可证明定理对其他矩阵范数也成立。【定理2】limkkAA的充要条件是nxR，有limkkAxAx。证明必要性记kkBAA，据limkkAA，可知lim0kkB。设()()kkijBb，对于1(1,0,,0)T，有()()()111211(,,,)kkkTknBbbb由lim0kkB可知，1lim0kkB。类似地，可证明lim0(1,2,,)kikBin。这里，12,,,n是nR中的基本单位向量组。nxR，则1122nnxxxx1122kkknknBxxBxBxB1122limlimlimlim0kkknknkkkkBxxBxBxB即lim()0kkAAx，lim()0kkAxAx亦即limkkAxAx。充分性据limkkAxAx，有lim()0kkAAx，lim0kkBx由x的任意性，如果取1x，则()()()111211(,,,)kkkTknBbbb，1lim0kkB亦即()1lim0(1,2,,)kikbin类似地，可分别让2,,nx，可得()lim0(1,2,,,1,2,,)kijkbinjn故lim0kkB从而limkkAA。【定理3】设nnBR，则lim0kkB的充要条件是1B。证明由高等代数知识，存在非奇奇异矩阵P使121rJJPBPJJ其中约当块11iiiiiinnJ且1niinn，显然有1BPJP1kkBPJP其中12kkkkrJJJJ于是lim0lim0lim0(1,2,,)kkkikkkBJJir据例题1的结论，lim0kikJ的充要条件是1i(1,2,,)ir故lim0kkJ的充要条件是()1B。【定理4】（迭代法基本定理）设有方程组xBxf以及迭代法(1)()kkxBxf对任意选取初始向量(0)x，迭代法收敛的充要条件是矩阵B的谱半径()1B。证明充分性设()1B则矩阵AIB的特征值均大于零，故A非奇异。Axf有唯一解*x，且*Axf，即**xBxf。误差向量()()*(1)*(1)(0)()kkkkkxxBxxBB由设()1B，应用定理3，有lim0kkB。于是，对任意(0)x，有lim0kk，即()*limkkxx。必要性设对任意(0)x有()*limkkxx其中(1)()kkxBxf，显然，极限*x是方程组xBxf的解，且对任意(0)x有()()*(0)0()kkkxxBk由定理2知lim0kkB。再由定理3，即得()1B。判断迭代收敛时，需要计算B，一般情况下，这不太方便。由于()BB，在实际应用中，常常利用矩阵B的范数来判别迭代法的收敛性。【定理5】（迭代法收敛的充分条件）设有方程组,nnxBxfBR以及迭代法(1)()kkxBxf（0,1,2,k）如果有B的某种范数1Bq，则（1）迭代法收敛，即对任取(0)x有()*limkkxx且**xBxf。（2）(1)*1(0)*kkxxqxx。（3）(1)*(1)()1kkkqxxxxq。（4）1(1)*(1)(0)1kkqxxxxq。证明（1）由基本定理4，结论（1）是显然的。（2）由关系式(1)*()*()kkxxBxx，有(1)*()*2(1)*1(0)*kkkkxxqxxqxxqxx（3）(1)()*()*(1)*()*(1)()kkkkkkxxxxxxxxxx*()*()*()(1)kkkxxqxxqxx即*()(1)()()(1)111kkkkkqxxxxxxqq显然(1)*(1)()1kkkqxxxxq亦成立。（4）21(1)*(1)()()(1)(1)(0)111kkkkkkqqqxxxxxxxxqqq。注：该定理中的第3款可作为误差的事后估计式。三几种常见的迭代法及收敛性下面，我们讨论线性方程组Axb如何用迭代法求近似解的问题。这里，()nnijAaR为非奇异矩阵，12(,,,)TnnbbbbR。（一）雅可比迭代法。设0(1,2,,)iiain，将A分解成以下三部分11121112221212111112112100000000nnnnnnnnnnnnnnnnaaaaaaaaAaaaaaaaaDLU11()()()AxbDLUxbDxLUxbxDLUxDb记1()BDLU，1fDb那么xBxf形成迭代式对于任意初值(0)x，(1)()kkxBxf（0,1,2,k）这就是雅可比迭代法。注：1形成雅可比迭代式的条件是A的主对角线元素均非零。2雅可比迭代收敛的条件是1()(())1BDLU。【例题2】对于线性方程组69228281027321321321xxxxxxxxx利用雅可比迭代法求其近似解（允许的最大迭代次数N，近似解的精度eps，由用户设定）。（二）高斯-塞德尔迭代法。从雅可比迭代的分量形式可以发现，在进行第k次迭代时，利用()1kx，()2kx，…，()knx，生成向量(1)kx，其分量产生的次序是(1)1kx，(1)2kx，…，(1)knx。我们对雅可比方法进行以下改变设计：步1应用信息()1kx，()2kx，…，()knx，据雅可比迭代分量式，生成分量(1)1kx；步2应用信息(1)1kx，()2kx，…，()knx，据雅可比迭代分量式，生成分量(1)2kx；步3应用信息(1)1kx，(1)2kx，…，()knx，据雅可比迭代分量式，生成分量(1)3kx；……步n应用信息(1)1kx，(1)2kx，…，(1)1knx，()knx，据雅可比迭代分量式，生成分量(1)knx。如此生成(1)kx的设计方案，是想更好地利用已有的最新有用信息。有理由相信，如此所获得的迭代式，其计算效果应该会更好一些。下面，我们具体给出这种迭代法的表达形式。(1)()()()()111122111111(0)/kkkkknnnnxbxaxaxaxa(1)(1)()()()222112211222(0)/kkkkknnnnxbaxxaxaxa(1)(1)(1)()()33311322311333()/kkkkknnnnxbaxaxaxaxa……(1)(1)(1)(1)()112211(0)/kkkkknnnnnnnnnnxbaxaxaxxa即(1)()()()()1111112211110kkkkknnnnaxbxaxaxax(1)(1)()()()2222211221120kkkkknnnnaxbaxxaxax(1)(1)(1)()()33333113223113kkkkknnnnaxbaxaxaxax……(1)(1)(1)(1)()1122