conjugate gradient method.pdf

《conjugate gradient method.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、EE236C(Spring2011-12)3.Conjugategradientmethod•conjugategradientmethodforlinearequations•convergenceanalysis•conjugategradientmethodasiterativemethod•nonlinearconjugategradientmethod3-1Unconstrainedquadraticminimization1TTminimizef(x)=xAx−bx2nwithA∈S++•equivalenttosolvingAx=b•r

2、esidualr=b−Axisnegativegradientatx:r=−∇f(x)conjugategradientmethod•inventedbyHestenesandStiefelaround1951•themostwidelyusediterativemethodforsolvingAx=b,withA≻0•canbeextendedtonon-quadraticunconstrainedminimizationConjugategradientmethod3-2Krylovsubspacesdefinition:asequenceofne

3、stedsubspaces(K0⊆K1⊆K2⊆···)k−1K0={0},Kk=span{b,Ab,...,Ab}fork≥1ifKk+1=Kk,thenKi=Kkforalli≥kkeyproperty:A−1b∈K(evenwhenK6=Rn)nnCayley-Hamiltontheorem:p(A)=An+aAn−1+···+aI=0where1nnn−1p(λ)=det(λI−A)=λ+a1λ+···+an−1λ+an1
−1n−1n−2thereforeAb=−Ab+a1Ab+···+an−1banConjugategradientmet

4、hod3-3KrylovsequenceCGalgorithmisarecursivemethodforcomputingtheKrylovsequence(k)x=argminf(x),k≥0x∈Kk•frompreviouspage,x(n)=A−1b•wewillseethereisasimpletwo-termrecurrence(k+1)(k)(k)(k)(k−1)x=x−ak∇f(x)+bk(x−x)example2201010xA=,b=201010420100x1Conjugategradientmethod3-4Re

5、sidualsofKrylovsequence•optimalityconditionsindefinitionofKrylovsequence(k)(k)(k)⊥x∈Kk,∇f(x)=Ax−b∈Kk•hence,residualsr=b−Ax(k)satisfyk⊥rk∈Kk+1,rk∈Kk(firstpropertyfollowsfromb∈Kandx(k)∈K)1k(nonzero)residualsformanorthogonalbasisfortheKrylovsubspacesTKk=span{r0,r1,...,rk−1},rirj=0(i

6、6=j)Conjugategradientmethod3-5Conjugatedirectionsthevectorsv=x(i)−x(i−1)satisfyiTTTviAvj=0fori6=j,viAvi=viri−1•directionsare‘conjugate’:orthogonalforinnerproducthv,wi=vTAw•inparticular,ifvi6=0itisindependentofv1,...,vi−1•Kk=span{v1,v2,...,vk}(proofsonnextpage)conjugatevectors:d

7、efinedasp=v/α,scaledsothatrTp=krk2iiii−1ii−12vTrkrk2ii−1i−12αi==krk2pTApi−12iiConjugategradientmethod3-6proofofpropertiesonpage3-6(assumej

8、)2TTf(x+tvi)=f(x)+tviAvi−tviri−12•secondexpressionforα