迭代法求解线性方程组

第六章线性方程组的迭代解法/*iterationmethodsforthesolutionoflinearsystems*/Linearsystems：11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxbAx=b1112111212222212nnnnnnnnaaaxbaaaxbaaaxbMatrixformAx=bAx*=bx(k+1)=f(x(k))x(k),k=0,1,2,…hopefully,limx(k)=x*Iterativemethod:givenalinearsystemAx=b,designaniterationformulax(k+1)=f(x(k))andchooseaninitialapproximatesolutionx(0).iterationresultsinaseriesapproximatesolutions{x(k)|k∈Z}whichapproachestotherealsolutionx*hopefully.x(0)Howtodesigntheiterationformula?Bisnotunique,sotheiterationformulaisnotunique!11111..()00iiiiegAIAIxIAxbADADxIDAxDbxDbAxaALDUxDLUxDbaAx=bx=Bx+fx(k+1)=Bx(k)+fEquavalentreformationIterationmatrix迭代法思想：第一步fBxxxfBxxbAx***为精确解，设转化为等价方程组：将第二步fBxxxxkkk)()1()()0(}{,入方法构造按逐次代始向量构造迭代格式，任取初B与k无关，称为一阶定常迭代法收敛？发散？否则此迭代法发散。为方程的解。则称迭代法收敛，且若**,lim)(xxxkk判断收敛的方法：)0(1)()()()1()1()()(*)(**,0||||lim||*||limkkkkkkkkkkBBxxBfBxfBxxxxx＝则此迭代法收敛。＝若0,0,0lim0lim:2)(kknkkBRxxAA即有据定理计算中判断迭代终止条件的方法：)1()()1(*,||||kkkxxxx121311112111212322122222313211212300000000nnnnnnnnnnnnnnnaaaaaaaaaaaaaaAaaaaaaaaaaLUD6.2基本迭代法即可得等价方程组。令则非奇异，称为分裂矩阵bMfNMBbNxMxbNxMxbxNMbAxMNMA111,)()(,则可得不同的迭代法。选不同的,MJacobiiteration取M为DMatrixform(1)()1()1kkkxBxfDLUxDb，初始向量)0(xJacobi迭代法简单，迭代一次只需作一次矩阵与向量的乘法即可。。的矩阵迭代形式并求解写出，取初始向量例：JacobixxxxxxxxxxT,)0,0,0(5223122)0(321321321,...1,0,531022101220)()1(kxxkk5,)5,3,1(,)0,0,0()0()1()1()0(xxxxTT8,)3,3,5()1()2()2(xxxT0,)1,1,1(4,)1,1,1()4()4()4()2()3()3(xxxxxxTTTxx)1,1,1(*)4(所以Componentform1111221331111112221123322222111221111,1...1......1...1,1,2,...,kkkknnkkkknnkkkknnnnnnnnnnnnkkiiijjjjiiiiibxaxaxaxaabxaxaxaxaabxaxaxaxaaborxaxinaa1/)225(1/)3(1/)221()0,0,0()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1)0(kkkkkkkkkTxxxxxxxxxx为上面例对应的分量形式TTTxxx)3,3,5()5,3,1()0,0,0()2()1()0(Gauss-Seideliteration高斯－塞德尔迭代法取M为D+LbLDUxLDxxbLDUxLDxbUxLDxbUxxLDbAxkk1)(1)1)0(111)()()()()()()(（，初始向量迭代格式为：bUxLxDxbUxxLDLDkkkkk)()1()1()()1(1)()(原式难求Gauss-Seideliteration11,1,1,2,...,nkkiiijjjjiiiiibxaxinaa111111,1,2,...,inkkkiiijjijjjjiiiiibxaxaxinaaComponentform11111,1,2,...,inkkkiiijjijjjjiiiiibxaxaxinaaJacobi分量形式次。的分量形式，并迭代一写出，取初始向量例：SGxxxxxxxxxxT,)0,0,0(5223122)0(3213213211/)225(1/)3(1/)221()0,0,0()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1)0(kkkkkkkkkTxxxxxxxxxx为上面例对应的分量形式TTxx)1,2,1()0,0,0()1()0(－comparisonJacobiiterationGauss-Seideliteration计算x(k+1)时需要x(k)的所有分量，因此需开两组存储单元分别存放x(k)和x(k+1)计算xi(k+1)时只需要x(k)的i+1~n个分量，因此x(k+1)的前i个分量可存贮在x(k)的前i个分量所占的存储单元，无需开两组存储单元迭代收敛性|kknnnnijijAaRkZAaR定义3矩阵收敛性Errorvectorofiteration0kBAAAAnjiaakkijkijlim}{,...,1,,lim)(，记为收敛于则称例20||limlimAAAAkkHowtocheckifacertainiterationsystemconvergesornot?定理3迭代收敛的等价条件2.lim01kxBB*1.limlim0kkkkxxBNotflexibletouseactually1,.3qB＝使得至少存在一种矩阵范数取为模。为复数，若的谱半径矩阵迭代收敛的充要条件|||},max{|)(1.5iiiBBTh1)(;1B必有证明迭代格式发散时，即可时，只要任一种范数所以证明迭代格式收敛*)()0()()1(lim1,6xxxqBBfBxxkpkk，则对任意＝的某种算子范数若有对于件：迭代法收敛的充分条定理Posteriorerror–estimatedintheprocessofiterationPriorerror—estimatedbeforetheiterationBotherrorestimationcanbeusedtocontrolwhentohalttheiteration称收敛速度。度，简为迭代法的渐近收敛速定义)(ln)(:5BBRexample1231021321011512510xxx*951230.99981.99982.99980.99971.99992.9999tttxxxJacobiiterationG-SiterationInthisexample,G-SiterationconvergesfasterthanJacobiiteration.It’snotalwaystrue.Sometimesthelaterconvergesfaster.Forsomelinearsystems,G-SconvergeswhileJdiverges,andviceversa.收敛速度，例：5223122321321321xxxxxxxxx022101220jB200320220SGBG-Siterationconvergesexample123111222111122011122xxx110221102211022BJacobiiterationmatrixB=-D-1(L+U)110221104431088GG-SiterationmatrixG=-(D+L)-1UJacobiiterationdiverges312,311det()(431)01,()124BIB212,3157det()(851)00,()0.35361816iGIGConvergencyfortwospecialmatrix1.A是对称正定矩阵G-S收敛.2.A是严格对角占优矩阵或A是弱对角占优，且不可约矩阵，则J和G-S均收敛。Strictlydiagonallydominant1,,1,2,,niiijjjiaain000001,1,,1,2,,,..nniiijiiijjjijjiaainandistaaweaklydiagonallydominant111222,..0tAApermutationmatrixPstPAPAorderrordern-rAreducible,elseAnotreducible.Example3122958313xx12902()det()12022()221803JJJBDLUBIB112902()det()(12)00,12()121012GSGSGSBDLUBIBG-SiterationdivergesJacobiiterationdiverges128313295xxStrictlydiagonallydominantJ,G-SiterationconvergeExample412351201181214238xxx