迭代法求解线性方程组

迭代法求解线性方程组第一页，共二十五页，编辑于2023年，星期五Ax=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.

第二页，共二十五页，编辑于2023年，星期五怎样设计迭代格式?B并不是唯一的,因此迭代格式也不是唯一的!Ax=bx=Bx+f

x(k+1)=Bx(k)

+f等价变换迭代矩阵迭代法思想：第一步第二步B与k无关，称为一阶定常迭代法收敛？发散？第三页，共二十五页，编辑于2023年，星期五判断收敛的方法：计算中判断迭代终止条件的方法：第四页，共二十五页，编辑于2023年，星期五LUD6.2基本迭代法第五页，共二十五页，编辑于2023年，星期五Jacobiiteration取M为DMatrixformJacobi迭代法简单，迭代一次只需作一次矩阵与向量的乘法即可。第六页，共二十五页，编辑于2023年，星期五第七页，共二十五页，编辑于2023年，星期五计算公式第八页，共二十五页，编辑于2023年，星期五Convenientinprogramming第九页，共二十五页，编辑于2023年，星期五Gauss-Seideliteration取M为D+L第十页，共二十五页，编辑于2023年，星期五Gauss-SeideliterationComponentformJacobi分量形式第十一页，共二十五页，编辑于2023年，星期五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个分量所占的存储单元，无需开两组存储单元第十二页，共二十五页，编辑于2023年，星期五ConvergenceofiterationConvergenceofmatrixErrorvectorofiterationexampleJacobiiterationG-SiterationInthisexample,G-SiterationconvergesfasterthanJacobiiteration.It’snotalwaystrue.Sometimesthelaterconvergesfaster.Forsomelinearsystems,G-SconvergeswhileJdiverges,andviceversa.第十三页，共二十五页，编辑于2023年，星期五Howtocheckifacertainiterationsystemconvergesornot?ConditionsofconvergenceNotflexibletouseactuallyPosteriorerror–estimatedintheprocessofiterationPriorerror—estimatedbeforetheiterationBotherrorestimationcanbeusedtocontrolwhentohalttheiteration第十四页，共二十五页，编辑于2023年，星期五第十五页，共二十五页，编辑于2023年，星期五第十六页，共二十五页，编辑于2023年，星期五G-SiterationdivergesexampleJacobiiterationmatrixB=-D-1(L+U)G-SiterationmatrixG=-(D+L)-1UJacobiiterationdiverges第十七页，共二十五页，编辑于2023年，星期五Convergencyfortwospecialmatrix1.Aissymmetricandpositivedefinite

G-Sconverges.2.Aisstrictlydiagonallydominantorweaklydiagonallydominantandnotreducible

JandG-Sbothconverge.Strictlydiagonallydominantweaklydiagonallydominantorderrordern-rAreducible,elseAnotreducible.第十八页，共二十五页，编辑于2023年，星期五Example3G-SiterationdivergesJacobiiterationdivergesStrictlydiagonallydominantJ,G-Siterationconverge第十九页，共二十五页，编辑于2023年，星期五Example4StrictlydiagonallydominantJ,G-SiterationconvergeEuavalentreformation:2*(1)+(2)(1)+(3)!note:ifthegivenlinearsystemdoesn’tsatisfytheconvergencecondition,wecanmodifytheorderoftheequationsordosomelinearcombinationstogetanequivalentsystemsatisfyingtheconvergencecondition.第二十页，共二十五页，编辑于2023年，星期五JacobiorG-Siterationcanbeusedtosolvelinearsystemsbutsometimesitconvergesveryslowly,howtoaccelerateit?SOR:successiveoverrelaxedmethod—accelerationofG-Siteration第二十一页，共二十五页，编辑于2023年，星期五WehopetheweightaveragingresulttobeclosertotherealrootSORW<1，W>1,overrelaxedW=1,G-SSuppose

hasbeenfoundbyusingG-S,nowwehavetofind

SOR—successiveoverrelaxedmethod—accelerationofG-SiterationResidualoftwosuccessiveiterationresults第二十二页，共二十五页，编辑于2023年，星期五ConvergencyofSORConditionsofconvergence:necessarycondition.InordertoSORconverge,wemustchoose0<w<2,elseitmustdiverge.GivenAx=b,whereAissymmetricandpositivedefiniteand0<w<2SORconverges.Thistheoremincludesthecasew=1---G-S第二十三页，共二十五页，编辑于2023年，星期五Example5SolvethefollowinglinearsystemusingJ,G-S,andSOR(w=1.15).Iterationhaltswhen

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

第二十四页，共二十五页，编辑于2023年，星期五!NOTE:ThekeyprobleminSORishowtochoosesuchawthatSORconvergesfastest---theproblemofhowtochoosethebestrelaxedfactorw.Presently,theproblemhasbeensolvedforafewspecialmatrices.Forthegeneralcase,successivesearchingmethodisused.Atthestart,chooseoneormoredifferentwtotrySOR.Thenmodifywaccordingtothespeedofconvergenceandsuccessivelyfindthebestw.Finallyfixwandcontinueiteration.

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