资源描述:
《Numerical Solution of Linear Systems(121-156)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、5NumericalSolutionofLinearSystemsInthischapterwepresentseveralmethodsforsolvinglinearsystemsoftheformAx=b.HereAisa(m×m)matrixandbothxandbarem-dimensionalvectors.OurinterestinlinearsystemsisrelatedtothesolutionofPDEsandthereforewewillconsiderthecasewherethecoefficien
2、tmatrixAistridiagonal,i.e.,⎡⎤a1c1000⎢....⎥⎢b2a2..0⎥⎢⎥A=⎢.........0⎥.⎢0⎥⎢⎣....⎥⎦0..am−1cm−1000bmamInthefollowingwewilladoptthenotationtridiag({bi}i=2,...,n,{ai}i=1,...,n,{ci}i=1,...,n)todenoteatridiagonalmatrixwithdiagonalentriesgivenrespectivelyby{bi}i=2,...,n,{ai}
3、i=1,...,n,{ci}i=1,...,n.Asashorthandnotation,wewillalsowritetridiag(bi,ai,ci).Iftheentriesdonotdependontheindexi,wejustwritetridiag(b,a,c).Inthepreviouschapter,wesawthatwhenwedealwiththeimplicitortheCrank–NicolsondiscretizationofaPDE,wehavetosolveasystemoflinearequ
4、a-tionsateachtimestep.Inprinciple,ifwecomputetheinverseA−1,assumingthatitexists,thenthesolutionofthelinearsystemcanbeobtainedbymatrixvectormul-tiplication,x=A−1b.Indeed,thiswouldrequireanumberO(m3)ofoperations,towhichweaddfurtherO(m2)arithmeticoperationsformultiply
5、ingtheresultinginversematrixbyvectorb.TheproblemwithmatrixinversionisthatwelosethetridiagonalstructureofA,seeFig.5.1.Therefore,storagerequirementsofAforlargeenoughvaluesofmcanalsobecomeanissue.Fortunately,whenthematrixAhasatridiagonalstructure,wehavehighlyeffi-cient
6、algorithmsexploitingthisparticularstructureinthesolutionofthelinearsys-tematourdisposal.Therefore,inthischapter,wewillfocusourattentiononthesolutionoflinearsystemswherethecoefficientmatrixAistridiagonal.Wewilldis-tinguishbetweendirectanditerativemethods.Theformerpro
7、videasolutioninafinitenumberofsteps,i.e.theywillcomeuptoanexactsolutionofthelinearsys-teminasmanyasO(m)operations:astrikingimprovementwithrespecttomatrix1225NumericalSolutionofLinearSystemsFig.5.1.Thestructureofa(5×5)tridiagonalmatrixandthenon-sparsenessofitsinverse
8、.inversion.Iterativemethodsbeginwithaninitialvectorx(0)andgenerateasequenceofvectorsx(1),...,x(k),...whichconvergetowardthedesiredsolutionask→∞.T