迭代法求解線性方程組

迭代法求解線性方程組第1頁，共25頁，2023年，2月20日，星期四Ax=bAx*=bx(k+1)=f(x(k))

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

第2頁，共25頁，2023年，2月20日，星期四怎樣設(shè)計迭代格式?B并不是唯一的,因此迭代格式也不是唯一的!Ax=bx=Bx+f

x(k+1)=Bx(k)

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

G-Sconverges.2.Aisstrictlydiagonallydominantorweaklydiagonallydominantandnotreducible

JandG-Sbothconverge.Strictlydiagonallydominantweaklydiagonallydominantorderrordern-rAreducible,elseAnotreducible.第18頁，共25頁，2023年，2月20日，星期四Example3G-SiterationdivergesJacobiiterationdivergesStrictlydiagonallydominantJ,G-Siterationconverge第19頁，共25頁，2023年，2月20日，星期四Example4StrictlydiagonallydominantJ,G-SiterationconvergeEuavalentreformation:2*(1)+(2)(1)+(3)!note:ifthegivenlinearsystemdoesn’tsatisfytheconvergencecondition,wecanmodifytheorderoftheequationsordosomelinearcombinationstogetanequivalentsystemsatisfyingtheconvergencecondition.第20頁，共25頁，2023年，2月20日，星期四JacobiorG-Siterationcanbeusedtosolvelinearsystemsbutsometimesitconvergesveryslowly,howtoaccelerateit?SOR:successiveoverrelaxedmethod—accelerationofG-Siteration第21頁，共25頁，2023年，2月20日，星期四WehopetheweightaveragingresulttobeclosertotherealrootSORW<1，W>1,overrelaxedW=1,G-SSuppose

hasbeenfoundbyusingG-S,nowwehavetofind

SOR—successiveoverrelaxedmethod—accelerationofG-SiterationResidualoftwosuccessiveiterationresults第22頁，共25頁，2023年，2月20日，星期四ConvergencyofSORConditionsofconvergence:necessarycondition.InordertoSORconverge,wemustchoose0<w<2,elseitmustdiverge.GivenAx=b,whereAissymmetricandpositivedefiniteand0<w<2SORconverges.Thistheoremincludesthecasew=1---G-S第23頁，共25頁，2023年，2月20日，星期四Example5SolvethefollowinglinearsystemusingJ,G-S,andSOR(w=1.15).Iterationhaltswhen

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

第24頁，共25頁，2023年，2月20日，星期四!NOTE:ThekeyprobleminSORishowtochoosesuchawthatSORconvergesfastest---theproblemofhowtochoosethebestrelaxedfactorw.Presently,theproblemhasbeensolvedforafewspecialmatrices.Forthegeneralcase,successivesearchingmethodisused.Atthestart,chooseoneormoredifferentwtotrySOR.Thenmodifywaccordingtothespeedofconvergenceandsuccessivelyfindthebestw.Finallyfixwandcontinueiteration.

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