A First Course in the numerical analysis of differential equations 2ed.pdf

《A First Course in the numerical analysis of differential equations 2ed.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、252Classicaliterativemethodsdwherethed×diterationmatrixHandv∈Rareindependentofk.(Ofcourse,bothHandvmustdependonAandb,otherwiseconvergenceisimpossible.)Lemma12.1Givenanarbitrarylinearsystem(12.1),alinearone-stepstationarydscheme(12.3)convergestoauniqueboundedlimitxˆ∈R,reg

2、ardlessofthechoiceofstartingvaluex[0],ifandonlyifρ(H)<1,whereρ(·)denotesthespectralradius(A.1.5.2).Providedthatρ(H)<1,xˆisthecorrectsolutionofthelinearsystem(12.1)ifandonlyifv=(I−H)A−1b.(12.4)ProofLetuscommencebyassumingρ(H)<1.InthiscaseweclaimthatlimHk=O.(12.5)k→∞Toprov

3、ethisstatement,wemakethesimplifyingassumptionthatHhasacompletesetofeigenvectors,hencethatthereexistanonsingulard×dmatrixVandadiagonald×dmatrixDsuchthatH=VDV−1(A.1.5.3andA.1.5.4).HenceH2=VDV−1×VDV−1=VD2V−1,H3=VD3V−1and,ingeneral,itistrivialtoprovebyinductionthatHk=VDk

4、V−1,k=0,1,2,...Therefore,passingtothelimit,limHk=VlimDkV−1.k→∞k→∞TheelementsalongthediagonalofDaretheeigenvaluesofH,henceρ(H)<1impliesDkk−→→∞Oandwededuce(12.5).Ifthesetofeigenvectorsisincomplete,(12.5)canbeprovedjustaseasilybyusingaJordanfactorization(seeA.1.5.6andExer

5、cise12.1).Ournextassertionisthatx[k]=Hkx[0]+(I−H)−1(I−Hk)v,k=0,1,2,...;(12.6)notethatρ(H)<1implies1∈σ(H),whereσ(H)isthesetofalleigenvalues(thespectrum)ofH,thereforetheinverseofI−Hexists.Theproofisbyinduction.Itisobviousthat(12.6)istruefork=0.Hence,letusassumeitfork≥0and

6、attemptitsverificationfork+1.Usingthedefinition(12.3)oftheiterativeschemeintandemwiththeinductionassumption(12.6),wereadilyobtainx[k+1]=Hx[k]+v=HHkx[0]+(I−H)−1(I−Hk)v+v=Hk+1x[0]+(I−H)−1(H−Hk+1)+(I−H)−1(I−H)v=Hk+1x[0]+(I−H)−1(I−Hk+1)vandtheproofof(12.6)iscomplete.Letting

7、k→∞in(12.6),(12.5)impliesatoncethattheiterativeprocessconverges,limx[k]=xˆ:=(I−H)−1v.(12.7)k→∞12.1Linearone-stepstationaryschemes253Wenextconsiderthecaseρ(H)≥1.Providedthat1∈σ(H),thematrixI−Hisinvertibleandxˆ=(I−H)−1vistheonlypossibleboundedlimitoftheiterativescheme.For

8、,supposetheexistenceofaboundedlimityˆ.Thenyˆ=limx[k+1]=Hlimx[k]+v=Hyˆ+v,(12.8)k→∞k→∞thereforeyˆ=xˆ.Even