第六章線性方程組的迭代解法

/*iterationmethodsforthesolutionoflinearsystems*/Linearsystems：Ax=bMatrixform1Ax=bAx*=bx(k+1)=f(x(k))

x(k),k=0,1,2,…hopefully,limx(k)=x*x(0)Iterativemethod:givenalinearsystemAx=b,designaniterationformulax(k+1)=f(x(k))andchooseaninitialapproximatesolutionx(0).iterationresultsinaseriesapproximatesolutions{x(k)|kZ}whichapproachestotherealsolutionx*hopefully.

2怎樣設計迭代格式?B并不是唯一的,因此迭代格式也不是唯一的!Ax=bx=Bx+f

x(k+1)=Bx(k)

+f等價變換迭代矩陣迭代法思想：第一步第二步B與k無關，稱為一階定常迭代法收斂？發散？3判斷收斂的方法：計算中判斷迭代終止條件的方法：4LUD6.2基本迭代法5Jacobiiteration取M為DMatrixformJacobi迭代法簡單，迭代一次只需作一次矩陣與向量的乘法即可。6計算公式7Convenientinprogramming8Gauss-Seideliteration取M為D+L9Gauss-SeideliterationComponentformJacobi分量形式10comparisonJacobiiterationGauss-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個分量所占的存儲單元，無需開兩組存儲單元11ConvergenceofiterationConvergenceofmatrixErrorvectorofiterationexampleJacobiiterationG-SiterationInthisexample,G-SiterationconvergesfasterthanJacobiiteration.It’snotalwaystrue.Sometimesthelaterconvergesfaster.Forsomelinearsystems,G-SconvergeswhileJdiverges,andviceversa.12Howtocheckifacertainiterationsystemconvergesornot?ConditionsofconvergenceNotflexibletouseactuallyPosteriorerror–estimatedintheprocessofiterationPriorerror—estimatedbeforetheiterationBotherrorestimationcanbeusedtocontrolwhentohalttheiteration1314G-SiterationdivergesexampleJacobiiterationmatrixB=-D-1(L+U)G-SiterationmatrixG=-(D+L)-1UJacobiiterationdiverges15Convergencyfortwospecialmatrix1.Aissymmetricandpositivedefinite

G-Sconverges.2.Aisstrictlydiagonallydominantorweaklydiagonallydominantandnotreducible

JandG-Sbothconverge.Strictlydiagonallydominantweaklydiagonallydominantorderrordern-rAreducible,elseAnotreducible.16Example3G-SiterationdivergesJacobiiterationdivergesStrictlydiagonallydominantJ,G-Siterationconverge17Example4StrictlydiagonallydominantJ,G-SiterationconvergeEuavalentreformation:2*(1)+(2)(1)+(3)!note:ifthegivenlinearsystemdoesn’tsatisfytheconvergencecondition,wecanmodifytheorderoftheequationsordosomelinearcombinationstogetanequivalentsystemsatisfyingtheconvergencecondition.18JacobiorG-Siterationcanbeusedtosolvelinearsystemsbutsometimesitconvergesveryslowly,howtoaccelerateit?SOR:successiveoverrelaxedmethod—accelerationofG-Siteration19WehopetheweightaveragingresulttobeclosertotherealrootSORW<1，W>1,overrelaxedW=1,G-SSuppose

hasbeenfoundbyusingG-S,nowwehavetofind

SOR—successiveoverrelaxedmethod—accelerationofG-SiterationResidualoftwosuccessiveiterationresults20ConvergencyofSORConditionsofconvergence:necessarycondition.InordertoSORconverge,wemustchoose0<w<2,elseitmustdiverge.GivenAx=b,whereAissymmetricandpositivedefiniteand0<w<2SORconverges.Thistheoremincludesthecasew=1---G-S21Example5SolvethefollowinglinearsystemusingJ,G-S,andSOR(w=1.15).Iterationhaltswhen

Solution:take1.Jacobiiteration2.Gauss-Seideliteration3.SOR!note:wchosedwell,SORconvergesveryfast.AsforJandG-S,theconvergencespeeddependsonthespectralradiusoftheiterationmatrix.

22!NOTE:ThekeyprobleminSORishowtochoosesuchawthatSORconvergesfastest---theproblemofhowtochoosethebestrelaxedfactorw.Presently,theproblemhasbeensolvedforafewspecialmatrices.Forthegeneralcase,successivesearchingmethodisused.Atthestart,chooseoneormoredifferentwtotrySOR.Thenmodifywaccordingtothespeedofconvergenceandsuccessivelyfindthebestw.Finallyfixwandcontinueiteration.

Intheory,byiterationwecangetapproximatesolutiontoanyaccuracyexpected.Actually,however,duetothelimitofcomputerwordlength,wecan’tarriv