共軛梯度法

共軛梯度法

共軛梯度法(Conjugate Gradient)是介於最速下降法牛頓法之間的一個方法,它僅需利用一階導數信息,但克服了最速下降法收斂慢的缺點,又避免了牛頓法需要存儲和計算Hesse矩陣並求逆的缺點,共軛梯度法不僅是解決大型線性方程組最有用的方法之一,也是解大型非線性最最佳化最有效的算法之一。 在各種最佳化算法中,共軛梯度法是非常重要的一種。其優點是所需存儲量小,具有步收斂性,穩定性高,而且不需要任何外來參數。

基本介紹

  • 中文名:共軛梯度法
  • 外文名:Conjugate gradient method
  • 提出者:Hestenes和Stiefle
  • 提出時間:1952
  • 用於:解正定係數矩陣線性方程組
  • 套用學科:數學
簡介,方法的表述,簡述,最後算法,作為直接法,作為疊代法,例子,

簡介

共軛梯度法最早是由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是對稱和正定的,所以左側定義了內積
若且唯若它們相對於該內積正交時,兩個向量是共軛的。 共軛是一個對稱關係:如果u與v共軛,則v與u共軛。 假設
是一組n維共軛向量。那么P 組成了
的基,在此基礎上我們表述
x為:
基於這個擴展,我們計算:
其中:
這給出了求解方程的以下方法:Ax = b:找到n個共軛方向的序列,然後計算係數αk。

作為疊代法

如果我們仔細選擇共軛向量pk,那么我們可能不需要所有這些來獲得解x*的好的近似值。 因此,我們將共軛梯度法視為疊代法。這也使我們能夠大致解決n大到非常大的系統,因為直接方法花費太多時間。
我們假設x0x的初始值,我們可以不失一般性的假設x0=0(否則,考慮用系統Az=bAx0代替)。
我們從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是系統的順序)理論上將達到精確的解。

相關詞條

熱門詞條

聯絡我們