共軛梯度算法

共軛梯度法算法步驟如下：［預(yù)置步］任意V瓦巳RK,計(jì)算廣口m如并令取：。=3指定算法終止常數(shù)￡>。，置4=。進(jìn)入主步；［主步］如果時(shí)“，終止算法，輸出;否則下行；計(jì)算：-召/&'E=&+皿/"膈=3—A.=- ，Pjt+i=門+i+昆％;計(jì)算： 辱皇置4=止+1,轉(zhuǎn)入(1).定理5.2.1由共軛梯度法得到的向量組和3」具有如下性質(zhì)：(1)P：烏=0,0<j<j<k\(2)=0,j,0<iJ<^,(3)(4)斐奶= = +l),其中長(zhǎng)04,之，用+1)=斐酒3p(),He，…，(5.2.1)通常稱之為Krylov子空間.［證明］用歸納法.當(dāng)止=1時(shí)，因?yàn)閮?布,A=牛一，Pi=門+0g，說(shuō)門二醇廣1二蚌(廣口—a^Ap^)=蒂離—Ap^=0,Pi^Pq=(/+■%)「/=氣或-:r；；忒擊。=。，因此定理的結(jié)論成立.現(xiàn)在假設(shè)定理的結(jié)論對(duì)止成立，我們來(lái)證明其對(duì)止+1也成立.膈=住-&俱及歸納假設(shè)，有玖5=恥一儀就雄=。,0<i<k-\.又由于- - =o,故定理的結(jié)論（1）對(duì)止+1成立.利用歸納假定有Spcm&Q,…，=Spcm{pQ,…，p而由（1）所證知，■^】與上述子空間正交，從而有定理的結(jié)論（2）對(duì)止+1也成立.利用等式Pk+l=1+1+扃/&和％=「％/，并利用歸納法假定和（2）所證之結(jié)論，就有映1=上叢（烏-％1）+烷孔壽"，=OX-^-1成立；而由昆的定義得夕富&^=（1+1+尻%）「&?&=-=0.這樣，定理的結(jié)論（3）對(duì)止+1也成立.由歸納法假定知EA.8長(zhǎng)皿為次+1）=斐奶｛號(hào)由口，…，#浦，進(jìn)而Apke斐奶｛由），瘁n…M叫Ju斐洌虹由）,應(yīng)?！唤小褂谑?+1=七一勺』％彌3皿止+2）=斐必虹/廣/叫』

夕所］=1+i+/4盧r已配（網(wǎng)/口，先+2）=斐白也｛個(gè)，』擊，???，網(wǎng)屎1尸」再注意到（2）和（3）所證的結(jié)論表明，向量組門，f…/隊(duì)1和外羽,??"知1都是線性無(wú)關(guān)的，因此定理的結(jié)論（4）對(duì)止+1同樣成立.定理證畢定理5.2.1表明，向量5皿…心和％羅1，…K分別是Krylov子空間反（&門，先+1）的正交基和共軛正交基.由此可見，共軛梯度法最多范步便可得到方程組的解川.因此，理論上來(lái)講，共軛梯度法是直接法.定理5.2.2用共軛梯度法計(jì)算得到的近似解五滿足『SQ=mm｛伊3）.,居際+長(zhǎng)3山,止）｝(5.2.2)(5.2.3)其中WL=氣斥，是方程組如=&的解，心"是由(5.2.1)所定義的Krylov子空間.證明注意到:『⑴+疽血=3-工*』3-崩，則(5.2.2)和(5.2.3)是等價(jià)的，因此我們下面只證明(5.2.3)成立.假定共軛梯度法計(jì)算到!步出現(xiàn)門=°,那么有X*=也=工41+=二匕+=^0+^0^0+ci/?i+-"+^-iA-i此外，對(duì)計(jì)算過(guò)程中的任一步SI,有硫=為+女口夕口+??+住卜1夕41E工口+尺(』,為，止).設(shè)應(yīng)是屬于曲+心&%??的任一向量，則由定理5.2.1的(4)知，二可以表示為工=誑 +nPi+"-+n-iP^i在一應(yīng)=（癡一孔）乩+（%一為）『1+…+怎卜1一斥_1）召Al+e妒&+…+%1如1，X*一氣=Ci^Jt+-"+CJ;_1A-l,再利用定理5.2.1的（3）就可以推出g一卻：二||0。一凡）h+，，.+Si一斥_i）Pi||：+|鬲山+…+%仍一1||：于是定理得證.定理證畢由定理5.2.1,我們?nèi)菀椎贸鲆怎?'F；玖='KGU6mPq= 以由此可得另外，從理論上講，該迭代法經(jīng)即次迭代，便能得到精確解.但考慮到計(jì)算誤差，可以作為無(wú)限迭代算法進(jìn)行計(jì)算，直到K懷，為止.從而，我們得到如下實(shí)用的共軛梯度算法：［預(yù)置步］任意s*，計(jì)算菁q-知，并令取：乩=小指定算法終止常數(shù)，置止：=口，進(jìn)入主步；［主步］計(jì)算： 及他& ，戢如果妣』＞￡，轉(zhuǎn)入(3).否則，終止算法，輸出計(jì)算結(jié)果%】四x昆=弋如1，Pa+i=l+i+6成a計(jì)算：門1置H，轉(zhuǎn)入(1)注：在算法［主步］中，引入變量"Ap&，p=誠(chéng)上及萬(wàn)二田/小，可以簡(jiǎn)化計(jì)算。結(jié)合程序設(shè)計(jì)的特點(diǎn)，共軛梯度法可改為如下實(shí)用形式:算法5-3-1(解對(duì)稱正定方程組：實(shí)用共軛梯度法)x=初值北=0,r=h—Ax;p=rTrwhile（福and、氏十氏畋）k=k+\if止=1else=plp\B=法施endw=Ap;a=prw7x=x+cpr=r-csw;p=p\p=，fend共軛梯度法作為一種實(shí)用的迭代法，它主要有下面的優(yōu)點(diǎn)：算法中，系數(shù)矩陣A的作用僅僅是用來(lái)由已知向量歹產(chǎn)生向量神=必，這不僅可