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

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

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

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

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

5、立假定共軛梯度法計算到步出現(xiàn)，那么有此外，對計算過程中的任一步，有設(shè)是屬于的任一向量，則由定理5.2.1的（）知，可以表示為，于是而.，再利用定理 5.2.1的（）就可以推出于是定理得證定理證畢由定理 5.2.1 ，我們?nèi)菀椎贸鲇纱丝傻?5.2.4)另外，從理論上講，該迭代法經(jīng)次迭代，便能得到精確解但考慮到計算誤差，可以作為無限迭代算法進行計算，直到為止從而，我們得到如下實用的共軛梯度算法：預(yù)置步 任意，計算，并令?。褐付ㄋ惴ńK止常數(shù)，置，進入主步；主步 （）計算：，.（）如果，轉(zhuǎn)入（ 3）否則，終止算法，輸出計算結(jié)果（）計算：（）置，轉(zhuǎn)入（ 1）注：在算法主步中，引入變量，及，可以簡化計算。

6、結(jié)合程序設(shè)計的特點，共軛梯度法可改為如下實用形式：算法··（解對稱正定方程組：實用共軛梯度法）；whileandifelseendend.共軛梯度法作為一種實用的迭代法，它主要有下面的優(yōu)點：算法中，系數(shù)矩陣的作用僅僅是用來由已知向量產(chǎn)生向量，這不僅可充分利用的稀疏性，而且對某些提供矩陣較為困難而由已知向量產(chǎn)生向量又十分方便的應(yīng)用問題是很有益的；不需要預(yù)先估計任何參數(shù)就可以計算，這一點不像等；每次迭代所需的計算，主要是向量之間的運算，便于并行化。5.2.3收斂性分析將共軛梯度法作為一種迭代法，它的收斂性怎樣呢？這是本節(jié)下面主要討論的問題：定理 .2.3如果而且，則共軛梯度法至

7、多迭代步即可得到方程組的精確解。證明注意到蘊含著子空間的維數(shù)不會超過，由定理 .2.1 即知定理的結(jié)論成立。定理證畢定理 5·2·3 表明，若線性方程組（ 5·1·1）的系數(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”的偏差值最小的多項式。即于是，我們有因此，定理得證。定理證畢雖然定理 5· 2&