-
共軛梯度法
鎖定
- 中文名
- 共軛梯度法
- 外文名
- Conjugate gradient method
- 提出者
- Hestenes和Stiefle
共軛梯度法簡介
共軛梯度法是一個典型的共軛方向法，它的每一個搜索方向是互相共軛的，而這些搜索方向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是系統的順序）理論上將達到精確的解。
