共轭梯度法

nullnull*主要内容主要内容一、共轭梯度法简介 二、共轭梯度法原理基本原理 2.1 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的等价 2.2 最速下降法 2.3 共轭梯度法 2.4 共轭梯度法共轭梯度法基本步骤 三、共轭梯度法的优缺点 四、共轭梯度法的适用范围 五、共轭梯度法的改进 **null从概率论观点来看，非线性反演可以分为：统计方法和确定性方法。非 线 性 反 演统计方法蒙特卡洛方法 模拟退火法 遗传算法 ……确定性方法最速下降法 牛顿法 共轭梯度法 变尺度法 ……**一、共轭梯度法简介一、共轭梯度法简介确定性非线性反演方法采用的反演策略是非线性问题的线性化,主要利用目标函数的梯度信息,通过反复迭代,寻找反演的最优解。 虽然统计类反演的最大优点是不完全依赖于初始猜测,理论上在反演过程中不会陷入局部极值。但是,这类方法的计算工作量巨大,效率很低。地球物理反演中涉及的模型参数成百上千,就目前的计算条件来说,统计类方法仍然不能满足大规模地球物理反演的要求。 **null共轭梯度法一开始是由Schmidt于1908年引入 梯度类方法计算效率高,特别是大约1951年，Hestenes和Stiefel经过不断的改进,并且和统计类反演方法结合形成了统计加迭代的组合反演方法,消除了依赖于初始猜测的缺点,成了一种广受欢迎的反演 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。 。一、共轭梯度法简介**二、共轭梯度法原理基本原理二、共轭梯度法原理基本原理通常对于一个反演问题，都是寻找目标函数的极值以获取对应的极小值解作为反演结果。 得目标函数： (1) 则2.1 问题的等价**2.2 最速下降法2.2 最速下降法基本思想： 任取一个迭代初始向量 x(0)，构造迭代序列 x(0), x(1) , x(2), . . . ，使得 (x(0)) > (x(1)) > (x(2)) > . . .，且每一步都以 “最快的速度” 下降到 (x) 的极小值，求得对应的x值即为反演的结果。 二、共轭梯度法反演的基本原理**null具体做法： (2) 该方向为： (3)2.2 最速下降法二、共轭梯度法反演的基本原理**null我们假设在点X0 处开始沿负梯度方向 搜索,到达点X1 ,即 为了使搜索能够快速到达极值点选取α使 达到最小,即 (4) 或者: (5) 2.2 最速下降法二、共轭梯度法反演的基本原理**2.2 最速下降法2.2 最速下降法(5)式说明,如果α的取值,使得φ’(x1 ) 与r0正交,即前一次搜索的方向必与下一次的搜索方向正交,这样使得最速下降的搜索路径成空间锯齿形,且下降方向是一组交替平行的梯度方向(右图) 。这启示我们,虽然最速下降的搜索过程有成百上千次,但实际上只需要一组n 个 彼此正交的梯度方向就可以搜索到极值解。最速下降法搜索路径二、共轭梯度法反演的基本原理**null2.3 共轭梯度法二、共轭梯度法反演的基本原理**null共轭向量的构造 设有一组n 维彼此关于n×n 的正定对称矩阵A共轭的向量 ，能够使我们分别沿着这n个共轭向量所指的方向各搜索一次,就可以达到极值点 。 设有一组线性无关的向量 ,可以通过对它们的线性组合构造出一组n个彼此共轭的向量。2.3 共轭梯度法二、共轭梯度法反演的基本原理**null共轭向量的构造 (6) (7) (8)2.3 共轭梯度法二、共轭梯度法反演的基本原理**null 2.4 共轭梯度法共轭梯度法基本步骤二、共轭梯度法反演的基本原理**null2.4 共轭梯度法共轭梯度法基本步骤二、共轭梯度法反演的基本原理(9)(10)**null (11) (12) 2.4 共轭梯度法共轭梯度法基本步骤二、共轭梯度法反演的基本原理**优 点优 点三、共轭梯度法的优缺点**计算效率比较计算效率比较最速下降法共轭梯度法三、共轭梯度法的优缺点**局限性局限性三、共轭梯度法的优缺点**局限性P1全局极小值P2局部极小值三、共轭梯度法优缺点局限性**局 限 性三、共轭梯度法的优缺点 局 限 性 从理论上说，共轭梯度法近乎完美，但自问世以来的几十年中，共轭梯度法仍然在不断改进中。在非线性反演中，共轭梯度法最大的局限性在于依赖于初始值，不能确保收敛到全局极小值。**null最速下降法反映的目标函数的一种局部性质,从局部看, 最速下降方向是目标函数值下降最快的方向,选择这样的方向进行搜索是有利的. 但从全局来看,由于锯齿现象的影响, 即使向着极小点移近不太大的距离,也要经历不小的”弯路”,因此收敛速度大为减慢. 最速下降法一般适用于计算过程的前期迭代,或者作为间插步骤. 四、共轭梯度法的适用范围 **null传统的共轭梯度法在地球物理反演和最优化等方面,得到了广泛的应用，但在非线性反演中，共轭梯度法在很大的程度上依赖于初始值的猜测，不能确保收敛到全局极小值，然而相对于其它的非线性反演方法,共轭梯度法效率高,计算稳定,适用于大规模的地球物理反演问题。四、共轭梯度法的适用范围 **null为了能够使共轭梯度法收敛到全局极小值，为此一些学者不断探索，提出了两种解决方案，一种是直接改进共轭梯度算法本身以达到有条件全局收敛的目的；另一种是利用启发式非线性反演具有全局搜索的能力，加上共轭梯度法的高效计算的混合算法。 五、共轭梯度法的改进 **五、共轭梯度法的改进五、共轭梯度法的改进该方法采用非启发式反演方法, 快速收敛到某一极值; 再用启发式反演方法跳出局部极值; 然后使用非启发式反演方法收敛到另一局部极值, 反复进行此过程; 并在解空间范围内搜索, 保留所有的局部极值, 最终确定最优解。它继承了随机爬山能够全局寻优、共轭梯度法计算速度快和精度高的优点, 能快速搜索到全局最优解。4.1 随机共轭梯度法**五、共轭梯度法的改进*五、共轭梯度法的改进4.1 随机共轭梯度法模型修改模型参数计算目标函数 S(x)和△S△S<0CG反演终止是否收敛是否是否4.1 随机共轭梯度法试验证明, 这种方法是一种高效的反演算法, 特别适用于求解非线性、多极值的最优化问题和地球物理反问题。4.1 随机共轭梯度法五、共轭梯度法的改进*null在大规模的地球物理反演中,需要象随机共轭梯度法这样既计算效率高,又能保证全局收敛的算法。 幸运的是,随机共轭梯度法继承了启发式非线性反演的能够并行化的优点。 合适的并行化,可以在像微机机群( PC - Cluster) 这样的计算机上进行大规模和超大规模的地球物理反演。4.2 随机共轭梯度法的并行化五、共轭梯度法的改进*null*