共轭梯度法原理和算法

⑴ 什么是共轭梯度法

共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算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次一维搜索之后，若还未获得极小点，则以负梯度方向作为初始方向重新构造共轭方向，继续搜索。