基本介紹
簡介,方法的表述,簡述,最後算法,作為直接法,作為疊代法,例子,
簡介
共軛梯度法最早是由Hestenes和Stiefle提出來的，在這個基礎上，Fletcher和Reeves （1964）首先提出了解非線性最最佳化問題的共軛梯度法。由於共軛梯度法不需要矩陣存儲，且有較快的收斂速度和二次終止性等優點，現在共軛梯度法已經廣泛地套用於實際問題中。
共軛梯度法是一個典型的共軛方向法，它的每一個搜尋方向是互相共軛的，而這些搜尋方向d僅僅是負梯度方向與上一次疊代的搜尋方向的組合，因此，存儲量少，計算方便。
方法的表述
簡述
設我們要求解下列線性系統
其中n-×-n矩陣A是對稱的（也即AT=A），正定的（也即xTAx> 0對於所有非0向量x屬於R），並且是實係數的。
將系統的唯一解記作x*。
最後算法
經過一些簡化，可以得到下列求解Ax=b的算法，其中A是實對稱正定矩陣。
x0= 0
k= 0
r0=b-Ax
直到rk足夠小：
k=k+1
ifk = 1
p1=r0
else
end if
其中xk=xk-1+ αkpk，rk=rk-1- αkApk。
end repeat
結果為xk。
作為直接法
我們說兩個非零向量u和v是共軛的（相對於A），如果
由於A是對稱和正定的，所以左側定義了內積：
是一組n維共軛向量。那么P 組成了
的基，在此基礎上我們表述
解x∗為：
其中：
這給出了求解方程的以下方法：Ax = b：找到n個共軛方向的序列，然後計算係數αk。
作為疊代法
如果我們仔細選擇共軛向量pk，那么我們可能不需要所有這些來獲得解x*的好的近似值。 因此，我們將共軛梯度法視為疊代法。這也使我們能夠大致解決n大到非常大的系統，因為直接方法花費太多時間。
我們假設x0是x∗的初始值，我們可以不失一般性的假設x0=0(否則，考慮用系統Az=b−Ax0代替)。
我們從x0開始搜尋解決方案，在每次疊代中，我們需要一個指標來告訴我們我們是否更接近解決方案x*（這對我們來說是未知的）。
該度量來自於以下事實：解x *也是以下二次函式的唯一最小值：
這表明在x = x0處採用第一基矢量p0為f的梯度的負值。 f的梯度等於Ax-b。 從“猜測的解決方案”x0開始（如果我們沒有理由猜測其他任何東西，我們總是猜測x0 = 0），這意味著我們取p0 = b - Ax0。
在此基礎上的其他向量將與梯度共軛，因此稱為共軛梯度法。
讓rk成為第k步的殘差：
注意，rk是x = xk處的f的負梯度，因此梯度下降法將是沿rk方向移動。 在這裡，我們堅持方向pk彼此共軛。 我們還要求下一個搜尋方向由當前的殘差和所有先前的搜尋方向構成，這在實踐中是足夠合理的。
共軛約束是一種正交類型約束，因此該算法與Gram-Schmidt正交歸一化相似。
給出以下表達式：
按照這個方向，下一個最佳位置由下式給出：
其中
由於pk和xk是共軛的，所以最後一個等式成立。
例子
考慮線性系統Ax = b由下式給出
我們將從初始猜測開始執行共軛梯度法的兩個步驟：
作為參考，確切的解決方案是：
我們的第一步是計算與x0相關的殘差向量r0。 該殘差由公式r0 = b-Ax0計算，在該情況下等於
由於這是第一次疊代，我們將使用剩餘向量r0作為初始搜尋方向p0；選擇pk的方法將在進一步的疊代中改變。
我們現在使用關係計算標量α0：
我們現在可以使用公式計算x1：
該結果完成了第一次疊代，結果是對系統的“改進”近似解。 我們現在可以使用公式來移動並計算下一個殘差向量r1：
我們的這個過程的下一步是計算最終用於確定下一個搜尋方向p1的標量β0。
現在，使用這個標量β0，我們可以使用關係計算下一個搜尋方向p1，
我們現在使用與用於α0的方法相同的方法，使用我們新獲取的p1來計算標量α1。
最後，我們使用與用於查找x1相同的方法計算x2。
結果x2是系統解決方案中比x1和x0更好的近似值。
如果在該示例中使用精確的算術而不是有限的精度，那么在n = 2次疊代之後（n是系統的順序）理論上將達到精確的解。
