迭代法的收敛条件

1解线性方程组的迭代法3.5迭代法的收敛条件3.5.1矩阵的谱半径迭代法的收敛性与迭代矩阵的特征值有关。定义3.3设A为n阶方阵，),,2,1(nii为A的特征值，称特征值模的最大值为矩阵A的谱半径，记为1maxiin)223(12(,,,)n()A称为矩阵A的谱.2解线性方程组的迭代法由特征值的定义容易得出，矩阵个kkAAAA12(,,,)(1,2,),kkknk()[()]kkAA)233(矩阵的谱半径与范数有以下关系。的谱是因而3解线性方程组的迭代法定理3.3设A为任意n阶方阵，为任意由向量范数诱导出的矩阵范数，则()AA[证明]对A的任一特征值i及相应的特征向量,iu都有iiuiiuiAuiAu因为iu为非零向量，于是有Ai由i的任意性即得AA)(4解线性方程组的迭代法定理3.4设A为n阶方阵，则对任意正数,存在一种矩阵范数使得)(AA证明参看［１］.对任意n阶方阵A,一般不存在矩阵范数,使得().AA但若A为对称矩阵，则2()AA下面的结论对建立迭代法的收敛性条件非常重要。5解线性方程组的迭代法定理3.5设A为n阶方阵，则0limkkA()1.A［证明］必要性.若lim0kkA0limkkA而)(0kAkkAA)]([于是由极限存在准则，有0)]([limkkA由定义3.2得()1.A的充要条件为所以6解线性方程组的迭代法充分性.若()1,A取,02)(1A由定理3.4存在一种存在一种,使得)(AA12)(1A,kkAAkkAlimkkAlim0所以lim0kkA而于是7解线性方程组的迭代法3.5.2迭代法的收敛条件定理３.６对任意初始向量)0(x和右端项,g由迭代格式gMxxkk)()1(),2,1,0(k)243(产生的向量序列)(kx收敛的充要条件是()1M［证明］设存在n维向量*x使得()*limkkxx则*x满足gMxxp98解线性方程组的迭代法由迭代公式(3-24),有xxk)(2(2)()kMxx(1)kMxg)()1(xxMk)()0(xxMk于是有)(lim)0(xxMkk0)(lim)(xxkk因为)0(x为任意n维向量,因此上式成立必须0limkkM由定理3.51)(MMxg9解线性方程组的迭代法反之，若,1)(M则1不是M的特征值，因而有0,IM于是对任意n维向量g,方程组()IMxg有唯一解，记为,x即gMxx并且0limkkM又因为xxk)()()1(xxMk)()0(xxMk所以，对任意初始向量,)0(x都有)(lim)(xxkk0)(lim)0(xxMkk即由迭代公式(3-24)产生的向量序列kx收敛.p710解线性方程组的迭代法由定理3.4即得推论１在定理3.6的条件下,若,1M则kx收敛.推论２松弛法收敛的必要条件是02。［证明］设松弛法的迭代矩阵M有特征值12,,.n因为det()M12nnM)(由定理3.6，松弛法收敛必有1)det(Mp1911解线性方程组的迭代法又因为det()MUDLD)1()(11)(LDnnaaa22111UD)1(nnnaaa2211)1()det(M1)1(n于是有所以021()[(1)]MDLDU12解线性方程组的迭代法定理3.6表明，迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向量及方程组的右端项无关。对同一方程组，由于不同的迭代法迭代矩阵不同，因此可能出现有的方法收敛，有的方法发散的情形.13解线性方程组的迭代法例３讨论用Jacobi迭代法与Gauss-Seidel迭代法求解方程组的收敛性．［解］由定理3.6，迭代法是否收敛等价于迭代矩阵的谱半径是否小于１，因为123223xxx1232xxx123221xxx故应先求迭代矩阵。14解线性方程组的迭代法122111221A022001000LJacobi迭代法的迭代格式为100010001D000100220U1kx()kBxg迭代矩阵为p161BIDA15解线性方程组的迭代法BIDA1122111221I其特征方程为IB22112230因此有,1230于是,10)(B所以Jacobi迭代法收敛.02210122034442216解线性方程组的迭代法如果用Gauss-Seidel迭代，100110221DL容易求出1200110011LD于是迭代矩阵为ULDM1)((1)(),kkxMxd其中又ULDM1100022110001021000022023002p1417解线性方程组的迭代法其特征方程为MI0)2(222023002特征值为,2,0321故,12)(M所以，Gauss-Seidel迭代法发散.18解线性方程组的迭代法例３也说明了20确实只是松弛法收敛的必要条件，而非充要条件，因为Gauss-Seidel迭代即为1的情形.定理3.6虽然给出了判别迭代法收敛的充要条件，但实际使用是很不方便。因为求逆矩阵和特征值的难度并不亚于用直接方法求解线性方程组。推论１与推论２使用起来方便得多，但它们分别给出收敛的充分条件与必要条件，许多情形下，不能起作用.19解线性方程组的迭代法如例３中，两个方法均有,1B,1M由推论１无法判别收敛性。特殊的系数矩阵给出几个常用的判敛条件。下面对一些定义3.4(1)(严格对角占优)()ijnnAa设如果A满足1niiijjjiaa),,2,1(ni则称A为严格对角占优阵.20解线性方程组的迭代法nijjijiiaa1)253(),,2,1(ni且至少有一个i值，使上式中不等号严格成立，则称为A弱对角占优阵。定义3.5如果矩阵Ａ不能通过行的互换和相应列的互换成为形式1112220AAAA(2)若n阶方阵)(ijaA满足其中2211,AA为方阵，则称A为不可约.21解线性方程组的迭代法如例３的系数矩阵矩阵214031012A是可约的.)(ijaA为n阶方阵2n若存在非空集1,2,,,In使得当,Ii而0,ija显然,若A是可约的,则A所对应的线性方程组Axb可化为低阶方程组.jI时有则A是可约阵.122111221A是不可约的.而一般地，设22解线性方程组的迭代法几个常用的收敛条件.设有线性方程组,bAx下列结论成立：1.若A为严格对角占优阵或不可约弱对角占优阵,则Jacobi迭代法和Gauss-Seidel迭代法均收敛.01,02,02.2.若A为严格对角占优阵,则松弛法收敛.3.若A为对称正定阵,则松弛法收敛.因此有:若A为对称正定阵,则松弛法收敛的充分必要条件是4.若A为对称正定阵,则Gauss-Seidel迭代法收敛.23解线性方程组的迭代法例:考虑51121012110AA为严格对角占优阵，故Jacobi迭代法与Gauss-Seidel迭代均收敛.210121012A又如例２中，系数矩阵非严格对角占优,但A为对称正定矩阵,4.1故松弛法收敛。上述结论的证明可参看[1],[7].,bAx其中例对线性方程组123812xxx123202324xxx123231530xxx讨论Jacobi迭代法及Gauss-Seidel迭代法的收敛性.解:Jacobi迭代的迭代矩阵为1301020110,882301515JB525max,,20815JB113故Jacobi迭代法收敛.(1)()()1232324202020kkkxxx(1)()()2131112888kkkxxx(1)()()3122330151515kkkxxxGauss-Seidel迭代矩阵1()GMDLU024036010302552400038316002400GM114故Gauss-Seidel迭代法收敛.2023181,2315A2000080,0015D000100,230L023001000U26解线性方程组的迭代法,Axb111221112211122A讨论用三种迭代法求解的收敛性。10,1112211810221611122解:例4设有方程组其中11320,141227解线性方程组的迭代法02)（B1102211022110221IDA故不能用条件1判别Jacobi迭代的收敛性.因A为对称矩阵,且其各阶主子式皆大于零,故A为对称正定矩阵,由判别条件3,Gauss-Seidel迭代法与松弛法均收敛.A不是弱对角占优,Jacobi迭代法的迭代矩阵为max1,1,1B1故推论1不能用28解线性方程组的迭代法IB0)1()21(211221122112211111(1)2211221111(1)0021002其特征方程29解线性方程组的迭代法1.B（）值得指出的是，改变方程组中方程的次序，即将系系数矩阵作行交换，会改变迭代法的收敛性。例如方程组bAx的系数矩阵为49103A有根因而123112，，由定理3.6Jacobi迭代法不收敛.30解线性方程组的迭代法1003904B21503100M,Axb3015(),().22BMJacobi迭代与Gauss-Seidel迭代的迭代矩阵分别为它们的谱半径为由定理3.6这两种迭代均不收敛.但若交换两个方程的次序得原方程组的同解方程组其中31解线性方程组的迭代法10349AAxbA显然,是严格对角占优阵,因而对方程组用Jacobi迭代与Gauss-Seidel迭代求解均收敛.32解线性方程组的迭代法3.5.3误差估计定理3.7设有迭代格式(1)(),kkxMxg,x1,M()kxx)263(1()IM,x1(),xIMg(1)(0)1kMxxM若收敛于()kx则有误差估计式证明:因为()1,MM故0,IM于是存在,方程组xMxg(即有惟一解()IMxg)且从而有p3533解线性方程组的迭代法(0)()kMxx(0)1[()]kMxIMg1(0)()[()]kMIMIMxg1(0)(1)()()kMIMxx()kxx)273((1)()kMxx()kxx1(0)(1)()kMIMxx取范数得34解线性方程组