共軛梯度法及其基本性質(zhì)

1、共軛梯度法及其根本性質(zhì)預(yù)備知識定義1 設(shè)是對稱正定矩陣。稱是A-共軛的，是指性質(zhì)1 設(shè)有是彼此共軛的維向量，即那么一定是線性無關(guān)的。證明假設(shè)有一組數(shù)滿足那么對一切一定有注意到，由此得出：即所有的因此，是線性無關(guān)的性質(zhì)設(shè)向量是線性無關(guān)的向量組，那么可通過它們的線性組合得出一組向量，而是兩兩共軛的證明我們用構(gòu)造法來證實上面的結(jié)論：??；：令，取m：令取容易驗證：符合性質(zhì)的要求性質(zhì)設(shè)是兩兩共軛的，是任意指定的向量，那么從出發(fā)，逐次沿方向搜索求的極小值，所得序列，滿足：證明由下山算法可知，從出發(fā)，沿方向搜索，獲得從而性質(zhì)設(shè)是兩兩共軛的，那么從任意指定的出發(fā)，依次沿搜索，所得序列滿足：，其中是方程組(5.

2、1.1)的解證明是性質(zhì)的直接推論，顯然成立由于是兩兩共軛的，故是線性無關(guān)的所以對于向量可用線性表出，即存在一組數(shù)使由于及，得出，于是，再由得出于是，與得出一樣地，我們可以陸續(xù)得出：比照和的表達(dá)式可知，證明完畢性質(zhì)是性質(zhì)的直接推論但它給出了一種求.的算法，這種算法稱之為共軛方向法結(jié)合性質(zhì)，我們可以得到如下的性質(zhì)性質(zhì)設(shè)是上的一組線性無關(guān)的向量，那么從任意指定的出發(fā)，按以下迭代產(chǎn)生的序列：取，；：計算，??；計算，得出；如此進(jìn)行下去，直到第n步：n：計算取計算，得出顯然：根據(jù)性質(zhì)可知，不管采用什么方法，只要能夠構(gòu)造個兩兩共軛的向量作為搜索方向，從任一初始向量出發(fā)，依次沿兩兩共軛的方向進(jìn)行搜索，經(jīng)步迭代

3、后，便可得到正定方程組的解共軛梯度法算法步驟如下：預(yù)置步任意，計算，并令?。褐付ㄋ惴ńK止常數(shù)，置，進(jìn)入主步；主步 如果，終止算法，輸出；否那么下行；計算：計算：置，轉(zhuǎn)入定理.2.1由共軛梯度法得到的向量組和具有如下性質(zhì)：，其中            5.2.1通常稱之為Krylov子空間證明用歸納法當(dāng)時，因為，因此定理的結(jié)論成立現(xiàn)在假設(shè)定理的結(jié)論對成立，我們來證明其對也成立利用等式及歸納假設(shè)，有又由于，故定理的結(jié)論對成立利用歸納假定有而由所證知，與上述子空間正交，從而有定理的結(jié)論對也成

4、立利用等式和，并利用歸納法假定和所證之結(jié)論，就有成立；而由的定義得這樣，定理的結(jié)論對也成立由歸納法假定知進(jìn)而于是再注意到和所證的結(jié)論說明，向量組和都是線性無關(guān)的，因此定理的結(jié)論對同樣成立定理證畢定理5.2.1說明，向量和分別是Krylov子空間的正交基和共軛正交基由此可見，共軛梯度法最多步便可得到方程組的解因此，理論上來講，共軛梯度法是直接法定理5.2.2用共軛梯度法計算得到的近似解滿足             5.2.或    

5、60;  5.2.其中，是方程組的解，是由5.2.1所定義的Krylov子空間證明注意到：，那么5.2.2和(5.2.3)是等價的，因此我們下面只證明(5.2.3)成立假定共軛梯度法計算到步出現(xiàn)，那么有此外，對計算過程中的任一步，有設(shè)是屬于的任一向量，那么由定理5.2.1的知，可以表示為，于是而，再利用定理5.2.1的就可以推出于是定理得證定理證畢由定理5.2.1，我們?nèi)菀椎贸鲇纱丝傻?#160;                

6、;       (5.2.4)另外，從理論上講，該迭代法經(jīng)次迭代，便能得到精確解但考慮到計算誤差，可以作為無限迭代算法進(jìn)行計算，直到為止從而，我們得到如下實用的共軛梯度算法：預(yù)置步任意，計算，并令取：指定算法終止常數(shù)，置，進(jìn)入主步；主步計算：，如果，轉(zhuǎn)入3否那么，終止算法，輸出計算結(jié)果 計算：置，轉(zhuǎn)入1注：在算法主步中，引入變量，及，可以簡化計算。結(jié)合程序設(shè)計的特點，共軛梯度法可改為如下實用形式：算法··解對稱正定方程組：實用共軛梯度法；while and if elseendend共軛梯度法作為一種實用的迭代法，

7、它主要有下面的優(yōu)點：算法中，系數(shù)矩陣的作用僅僅是用來由向量產(chǎn)生向量，這不僅可充分利用的稀疏性，而且對某些提供矩陣較為困難而由向量產(chǎn)生向量又十分方便的應(yīng)用問題是很有益的；不需要預(yù)先估計任何參數(shù)就可以計算，這一點不像等；每次迭代所需的計算，主要是向量之間的運(yùn)算，便于并行化。5.2.3 收斂性分析將共軛梯度法作為一種迭代法，它的收斂性怎樣呢？這是本節(jié)下面主要討論的問題：定理.2.3如果而且，那么共軛梯度法至多迭代步即可得到方程組的精確解。證明注意到蘊(yùn)含著子空間的維數(shù)不會超過，由定理.2.1即知定理的結(jié)論成立。定理證畢定理5·2·3說明，假設(shè)線性方程組5·1·1

8、的系數(shù)矩陣與單位相關(guān)一個秩的矩陣，而且很小時，那么共軛梯度法將會收斂得很快。定理5·2·4 用共軛梯度法求得的有如下的誤差估計               5·2·5其中證明 由定理5·2·1可知，對任意的，有記，那么是常數(shù)項為1的次實系數(shù)多項式。令為所有常數(shù)項為1的次數(shù)不超過的實系數(shù)多項式的全體，那么由定理5·2·2和引理5·1·1得其中是的特征值。由Chebyshev多項式逼近定理及Chebyshev多項式的性質(zhì)，定義在-1，1區(qū)間上的次Chebyshev多項式：是所有常數(shù)項為1的次數(shù)不超過的實系數(shù)多項式中，在-1，1上與“0的偏差值最小的多項式。且偏差值為1，對應(yīng)的交錯點組為：。因此，多項式是中在上與“0的偏差值最小的多項式。即于是，我們有因此，定理得證。定理