共軛梯度法原理和演算法

⑴ 什麼是共軛梯度法

共軛梯度法是介於最速下降法與牛頓法之間的一個方法，它僅需利用一階導數信息，但克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣並求逆的缺點，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優化最有效的演算法之一。 共軛梯度法最早是又Hestenes和Stiefle（1952）提出來的，用於解正定系數矩陣的線性方程組，在這個基礎上，Fletcher和Reeves（1964）首先提出了解非線性最優化問題的共軛梯度法。由於共軛梯度法不需要矩陣存儲，且有較快的收斂速度和二次終止性等優點，現在共軛梯度法已經廣泛地應用與實際問題中。 共軛梯度法是一個典型的共軛方向法，它的每一個搜索方向是互相共軛的，而這些搜索方向d僅僅是負梯度方向與上一次迭代的搜索方向的組合，因此，存儲量少，計算方便

⑵ FR共軛梯度法的迭代公式

梯度的本意是一個向量（矢量），表示某一函數在該點處的方向導數沿著該方向取得最大值，即函數在該點處沿著該方向（此梯度的方向）變化最快，變化率最大（為該梯度的模）。

設二元函數

溫度梯度的表達式

在向量微積分中，標量場的梯度是一個向量場。標量場中某一點上的梯度指向標量場增長最快的方向，梯度的長度是這個最大的變化率。更嚴格的說，從歐幾里得空間Rn到R的函數的梯度是在Rn某一點最佳的線性近似。在這個意義上，梯度是雅可比矩陣的特殊情況。

在單變數的實值函數的情況，梯度只是導數，或者，對於一個線性函數，也就是線的斜率。

梯度一詞有時用於斜度，也就是一個曲面沿著給定方向的傾斜程度。可以通過取向量梯度和所研究的方向的點積來得到斜度。梯度的數值有時也被稱為梯度。

希望我能幫助你解疑釋惑。

⑶ 共軛梯度法的簡介

共軛梯度法最早是由Hestenes和Stiefle提出來在這個基礎上，Fletcher和Reeves （1964）首先提出了解非線性最優化問題的共軛梯度法。由於共軛梯度法不需要矩陣存儲，且有較快的收斂速度和二次終止性等優點，現在共軛梯度法已經廣泛地應用於實際問題中。
共軛梯度法是一個典型的共軛方向法，它的每一個搜索方向是互相共軛的，而這些搜索方向d僅僅是負梯度方向與上一次迭代的搜索方向的組合，因此，存儲量少，計算方便

⑷ 共軛梯度法與變尺度法的優缺點比較，相比而言，都有什麼優點和缺點

共軛梯度法：
計算簡單，收斂速度快；收斂速度比最速下降法大為加快，而計算又比牛頓法大為簡化；

變尺度法：
收斂快，效果好，被認為是目前最有效的無約束優化方法。適用於維數較高，具有一階偏導數的目標函數。

針對梯度法收斂速度慢，提出收斂速度更快的共軛梯度法；針對牛頓法的缺點提出了變尺度法。

⑸ 梯度法^[1，6]

設地球物理數據和模型參數之間滿足以下非線性關系:

d=f(m) (8.1)

其中:f表示非線性運算元;d、m都是列向量。

建立如下目標函數:

φ(m)=[d-f(m)]²=min (8.2)

目標函數在模型m_i處的梯度為

地球物理反演教程

梯度法的模型修改量是目標函數的負梯度:

m_i+1=m_i+Δm_i=m_i-λg_i(8.4)

其中:λ為步長因子，是一個數，用來控制修改量的大小;g、m都為列向量。

下面推導λ的計算公式。

將式(8.2)目標函數φ(m)按泰勒公式展開，並略去高次項得

地球物理反演教程

將式(8.4)中的Δm_i=-λg_i帶入式(8.5)得

地球物理反演教程

設經過修改模型後，目標函數φ(m_i+1)為零，有

地球物理反演教程

由上式可推出步長因子λ的計算公式:

地球物理反演教程

給定初始模型m_i後，首先計算出梯度g_i，然後按式(8.8)計算步長因子，最後按式(8.4)修改模型。如果:

φ(m_i+1)＜φ(m_i) (8.9)

則說明修正量合適，採用新模型繼續迭代。否則減小λ後再計算，一般λ減小一半。

梯度法的計算過程如下:

(1)給定初始模型m₀;

(2)進行正演計算;

(3)判斷是否滿足精度要求，是則反演結束，否則進行第(4)步;

(4)按照式(8.4)修改模型，轉第(2)步。

一般反演精度採用實測數據和理論數據的相對均方差來量度。

因為目標函數的梯度就是φ值下降最快的方向，所以梯度法又稱為「最速下降法」。下面用一個簡單的例子來說明梯度法的原理。設有如下一維目標函數:

φ(x)=f(x) (8.10)

從圖8.1可見，x0為目標函數的極小值點。g₁為x₁處的梯度，g₂為x₂處的梯度。如果初始模型為x₁，模型修改量應該為正值才能使目標函數向最小值前進。從圖上可知g₁為負值，負梯度為正，滿足修改方向。同理如果初始模型為x₂，模型修改量應該為負值。從圖上可知g₂為正值，負梯度為負值，滿足修改量為負值的要求。

圖8.1 一維目標函數示意圖

從這個例子容易看出即使初始模型遠遠偏離極小值點，只要按照負梯度方向修改模型參數，總能使目標函數達到極小值點。但是上圖的極小值點只有一個，容易達到全局極小，如果目標函數具有多個極小值點，那麼初始模型的選擇就很關鍵了，選的不好容易陷入局部極小。此外在極小值點附近梯度法反演收斂的速度將會很慢。因此一般在反演的開始採用梯度法，在反演的後期採用其他收斂速度快的反演方法，如前面所介紹的最小二乘法(或稱為高斯-牛頓法)。

圖8.2 最小二乘法和梯度法修正方向示意圖

最小二乘法和梯度法在極小值點附近的模型修正方向如圖8.2所示^[10]。這個圖形將形象的說明為何梯度法在極小值點附近收斂速度慢。

圖8.2是二維的簡單情況，目標函數是個橢圓面。在初始模型m₀處梯度法的修正方向是最速下降方向，也就是和等值線的切線垂直的方向，可見它的方向偏離橢圓的中心極小值點。而最小二乘法(高斯-牛頓法)是解橢圓函數最優化問題的精確方法^[6]，它的修正方向將會指向橢圓的中心極小值點。因此在接近極小值點附近最小二乘法的收斂速度要快於梯度法。

為了克服最速下降法收斂慢的缺點，1964年Fletcher和Reeves提出了無約束極小化的共軛梯度法，它是直接從Hestenes和Stiefel(1952)解線性方程組的共軛梯度法發展而來。共軛梯度法使最速下降方向具有共軛性，提高了演算法的有效性和可靠性^[6]。

梯度法的關鍵是計算目標函數的梯度，最終還是會歸結為計算觀測數據對模型參數的偏導數。在一維反演時可以用有限差分法進行偏導數的計算，在高維反演時可以採用其他快速計算偏導數的方法，如第9章將要介紹的利用互換定理計算二維直流電測深偏導數矩陣。

⑹ 梯度下降法和共軛梯度法有何異同

兩者的區別：

梯度下降法是沿著梯度的負方向最小化目標函數；共軛方向法是把x表示成相對於系數矩陣A共軛的一組基向量的線性組合，然後每次沿著共軛方向一維最小化目標函數。

梯度下降法就是常說的最速下降法，考慮一個n維空間，我任意選取一個初始點，然後每次迭代的時候都以該點的負梯度方向（如果目標函數求最小值）進行精確一維搜索，正因為是精確搜索，所以相鄰的迭代方向正交的，所以會出現「鋸齒」現象，可能剛開始下降很多，但到後面越來越慢，收斂速度很慢。

而共軛梯度法是共軛方向法的一種，它在最速下降法的基礎上對它進行了改良，初始點的下降方向仍是負梯度方向，但後面的迭代方向不再是該點的負梯度方向了，後面的迭代方向是該點的負梯度方向和前一次迭代方向形成的凸錐中的一個方向，這樣有效地避免了「鋸齒」現象。

總結如下：

共軛梯度法在空間尋找一組basis，然後把優化問題完全分解成n個等價的子問題（expanded subplane minimizer），用n個局部最優可以合成一個全局最優。

⑺ 什麼是共軛梯度法

數學上，共軛梯度法實求解特定線性系統的數值解的方法，其中那些矩陣為對稱和正定。共軛梯度法是一個迭代方法，所以它適用於稀疏矩知陣系統，因為這些系統對於象喬萊斯基分解這樣的直接方法太大了。這種系統在數值求解偏微分方程時相當常見。
共軛梯度法道也可以用於求解無約束優化問題。
雙共軛梯度法提供了一種處理非對稱矩陣情況的推廣。

⑻ 共軛梯度法的演算法介紹

又稱共軛斜量法，是解線性代數方程組和非線性方程組的一種數值方法，例如對線性代數方程組 Ax=ƒ, (1)式中A為n階矩陣，x和ƒ為n維列向量,當A對稱正定時,可以證明求(1)的解X*和求二次泛函
的極小值問題是等價的。此處(x,у)表示向量x和у的內積。由此，給定了初始向量x（0），按某一方向去求(2)式取極小值的點x(1),就得到下一個迭代值x(2),再由x(2)出發，求x(3)等等，這樣來逼近x*。若取求極小值的方向為F在 x(k=1,2,…)處的負梯度方向就是所謂最速下降法，然而理論和實際計算表明這個方法的收斂速度較慢，共軛梯度法則是在 x(k-1)處的梯度方向r(k-1)和這一步的修正方向p(k-1)所構成的二維平面內，尋找使F減小最快的方向作為下一步的修正方向p(k),即求極小值的方向p（其第一步仍取負梯度方向）。計算公式為
再逐次計算(k=1,2,…)。可以證明當i≠j時，
從而平p(1),p(2)形成一共軛向量組;r(0),r(1),…形成一正交向量組。後者說明若沒有舍入誤差的話，至多 n次迭代就可得到(1)的精確解。然而在實際計算中,一般都有舍入誤差，所以r(0),r(1),…並不真正互相正交，而尣(0)尣(1),…等也只是逐步逼近(1)的真解,故一般將共軛梯度法作為迭代法來使用。
近來在解方程組(1)時,常將共軛梯度法同其他一些迭代法結合作用。特別是對病態方程組這種方法往往能收到比較顯著的效果。其方法是選取一對稱正定矩陣B並進行三角分解，得B=LLT。將方程組(1)化為 hу=b, (3)
此處y=lTx,b=l-1ƒ,h=l-1Al-T,而
再對(3)用共軛梯度法，計算公式為
k=0,1,2,…)適當選取B，當B很接近A時，h的條件數較之A大大減小,從而可使共軛梯度法的收斂速度大為加快，由一些迭代法的矩陣分裂A=M -N，可選取M 為這里的B，例如對稱超鬆弛迭代(SSOR)，強隱式迭代(SIP)等,這類方法常稱為廣義共軛梯度法或預條件共軛梯度法，它也可用於解代數特徵值問題。

⑼ 如何直觀地理解「共軛」這個概念

如下：

共軛在數學、物理、化學、地理等學科中都有出現。 本意：兩頭牛背上的架子稱為軛，軛使兩頭牛同步行走。共軛即為按一定的規律相配的一對。通俗點說就是孿生。在數學中有共軛復數、共軛根式、共軛雙曲線、共軛矩陣等。

共軛方向法：

以一組共軛方向作為搜索方向來求解無約束非線性規劃問題的一類下降演算法。是在研究尋求具有對稱正定矩陣Q的n元二次函數：

f(x)=1/2xQ x+bx+c。

最優解的基礎上提出的一類梯度型演算法，包含共軛梯度法和變尺度法。根據共軛方向的性質，依次沿著對Q共軛的一組方向作一維搜索，則可保證在至多n步內獲得二次函數的極小點。

共軛方向法在處理非二次目標函數時也相當有效，具有超線性的收斂速度，在一定程度上克服了最速下降法的鋸齒形現象，同時又避免了牛頓法所涉及的海色(Hesse) 矩陣的計算和求逆問題。

對於非二次函數，n步搜索並不能獲得極小點，需採用重開始策略，即在每進行n次一維搜索之後，若還未獲得極小點，則以負梯度方向作為初始方向重新構造共軛方向，繼續搜索。