共軛梯度法及其基本性質

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

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

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

4、立利用等式和，并利用歸納法假定和所證之結論，就有成立；而由的定義得這樣，定理的結論對也成立由歸納法假定知進而于是再注意到和所證的結論說明，向量組和都是線性無關的，因此定理的結論對同樣成立定理證畢定理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)，那么有此外，對計算過程中的任一步，有設是屬于的任一向量，那么由定理5.2.1的知，可以表示為，于是而，再利用定理5.2.1的就可以推出于是定理得證定理證畢由定理5.2.1，我們容易得出由此可得                 

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

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

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