第7章共轭梯度法

1、Chater 7 最优化方法与最优化方法与共轭梯度法共轭梯度法/*Optimization Method and Conjugate Gradient Method*/一、与一、与方程组等价的方程组等价的变分变分问题问题思思想想共轭梯度共轭梯度法是一种法是一种变分变分方法，将方法，将求解线性方程组求解线性方程组问题问题等价等价转化为一个转化为一个二次函数二次函数的的极小值极小值问题问题 。设设 为对称为对称正定正定矩阵，矩阵，()n nijAaR Axb 其中其中12(,) ;Tnxxxx 12(,)Tnbb bb 定义定义二次二次函数函数:nRR 2( )TTxx Axx b 1112nnn

2、ijijjjijja x xb x 二次二次函数函数 的基本性质的基本性质：( )x 对对2,( )()nxRxAxb 设设 为为 的解，则的解，则Axb 1xA b ()(,)xAxx ，且对，且对 有有nxR 2( )()(, )(, )xxAx xAxx (,)Axx ( (),)A xxxx 7 1 .Th设设 对称对称正定正定，则，则 为为 的解的的解的Ax Axb 充要条件是充要条件是()min ( )nx Rxx 证明：证明： 必要性由上述性质必要性由上述性质易知，下证充分性：易知，下证充分性：定理定理7 7.1.1说明：求解方程组的解等价于求上述说明：求解方程组的解等价于求上述

3、二次二次函数的函数的最小值最小值。常用方法：。常用方法：迭代迭代解法解法()min ( )nx Rxx 如果如果则由极值的必要条件得则由极值的必要条件得20()()xAxb Axb 20( )xA 二、二、最速下降最速下降法法/*Steepest Descent Method*/思思想想最速下降法最速下降法是指每次沿着函数值是指每次沿着函数值 下降最快下降最快的方向寻找的方向寻找最小值点最小值点。 而函数值而函数值下降最快下降最快的方向是函数的的方向是函数的负梯度负梯度方向方向 几何几何意义：意义：等值线等值线 x 0( )x 最速下降最速下降法的实现过程法的实现过程选取初始向量选取初始向量

4、，由，由二次二次函数函数 的基本性质的基本性质0( )x( )x 00( )( )()xbAx 0( )r 如果如果 ，则，则 就是方程组的解；就是方程组的解；00( )r 0( )x如果如果 ，则沿，则沿 方向进行方向进行一维极小一维极小搜索：搜索：00( )r 0( )r求求步长步长 ，使得，使得 00( )( )min()xr 000( )( )()dxrd 0000002( )( )( )( )( )( )()()()TTxrA xrbxr 00000( )( )( )( )(,)(,)rrArr 2000020( )( )( )( )()(,)dxrArrd 注意到注意到00000(

5、 )( )( )( )min ()()xrxr 1000( )( )( )xxr 令令 ，从而完成第一次迭代。，从而完成第一次迭代。下面以下面以 为为新新的初值，的初值，重复重复上述过程。上述过程。1( )x 最速下降最速下降法的算法法的算法选取初值选取初值0( )nxR For k=0,1,2,( )( )kkrbAx ( )( )( )( )(,)(,)kkkkkrrArr 1()( )( )kkkkxxr 如果如果 ，停止停止( )kr 否则，进行下一次循环否则，进行下一次循环10()( )(,)kkrr 搜索方向是搜索方向是正交正交的：的：11()()kkrbAx( )( )()kkk

6、bA xr ( )( )kkkrAr 缺陷：收敛速度缺陷：收敛速度慢慢设设 的特征值为的特征值为 , ,A10n 则由前述最速下降算法产生的序列则由前述最速下降算法产生的序列 满足满足其中其中 。1xA b ( )kx( )(0)11kknAAnxxxx 7.2Th上述定理说明，当上述定理说明，当 时最速下降法收敛非常慢。时最速下降法收敛非常慢。1n三、三、共轭梯度共轭梯度法法/*Conjugate-Gradient Method*/设设 为对称为对称正定正定矩阵，矩阵，()n nijAaR Axb 其中其中12(,) ;Tnxxxx 12(,)Tnbb bb 思思想想Def设设 为对称为对称

7、正定正定矩阵，若矩阵，若 中向量组中向量组n nAR 01( )( )( ),lpppnR满足满足0( )( )(,)ijAppij 则称它是则称它是 中的一个中的一个 共轭共轭（ 正交正交）向量组。）向量组。nRA A 利用利用一维极小一维极小搜索方法确定一组搜索方法确定一组 共轭共轭方向方向A 代替代替最速下降最速下降法中的法中的正交正交方向来进行迭代。方向来进行迭代。 共轭梯度共轭梯度法的实现过程法的实现过程选取初始向量选取初始向量 ， ，0( )x00( )( )pr 00000( )( )( )( )( )(,)(,)rrApp 100110( )( )( )( )( ),xxprb

8、Ax 如何确定下一个搜索方向呢？如何确定下一个搜索方向呢？在过点在过点 的由向量的由向量 和和 所张成的下列二维平所张成的下列二维平面内找出函数值下降最快的方向作为搜索方向面内找出函数值下降最快的方向作为搜索方向1( )x1( )r0( )p1( )p (1)(1)(0)2: ,xxrpR 2 (1)x(1)r(0)p(1)px 、 和和 的几何意义的几何意义1( )r0( )p1( )p此时此时 在在 上可表示为上可表示为( )x 2 (1)(1)(0)(1)(1)(0)(1)(1)(0)(1)(1)(0)2TTxrpxrpA xrpbxrp ( , ) (1)(1)(1)(0)(1)(1)

9、(1)(0)(0)(0)2020TTTTTrArrAprrrAppAp 由极值的必要条件得由极值的必要条件得(1)(1)(0)00 xxrp其中其中 满足满足00, (1)(1)(1)(0)(1)(1)00(1)(0)(0)(0)000TTTTTrArrAprrrAppAp 取下一个搜索方向为取下一个搜索方向为(1)(1)(1)(0)0001()pxxrp 11111( )( )( )( )(,)(,)rpApp 沿该方向进行一维搜索得步长为沿该方向进行一维搜索得步长为记记(1)(0)00(0)(0)0(,)(,)ArpApp (2)(1)(1)1xxp (1)(1)(0)0prp 下面以下面

10、以 为为新新的迭代值，的迭代值，重复重复上述过程即可。上述过程即可。2( )x( )( )( )( )(1)( )( )(1)(1)(1)( )( )( )(1)(1)( )k Tkkk TkkkkkkkkTkkk TkkkkkrppApxxprbAxrAppApprp 一般地，设已经得到一般地，设已经得到 ，则第，则第k+1步迭代的计算公式为步迭代的计算公式为( )kp终止条件：终止条件：(1)0kr 同时注意到同时注意到11( )( )( )( )()( )( )(,)(,)(,)kkkkkkkkrprrprr 11()( )()( )(,)(,)kkkkrpbAxp0( )( )( )(

11、 )(,)(,)kkkkkrpApp ( )( )( )( )(,)(,)kkkkkrrApp 1()( )( )( )(,)(,)kkkkkrAppAp 111()( )()( )( )(,()(,)kkkkkkrrrpAp 111()()( )( )(,)(,)kkkkkrrpAp 11()()( )( )(,)(,)kkkkkrrrr 共轭梯度共轭梯度法的算法法的算法选取初值选取初值0( )nxR For k=0 , 1 , 2 , , n00( )( )pr 00( )( )rbAx 计算计算计算计算( )( )( )( )(,)(,)kkkkkrrApp 1()( )( )kkkkx

12、xp 1()( )( )kkkkrrAp 11()()( )( )(,)(,)kkkkkrrrr 11()()( )kkkkprp 如果如果 ，停止停止10()kr 否则，计算否则，计算进行下一次迭代进行下一次迭代7 3 .Th由由共轭梯度共轭梯度法得到的法得到的 满足性质：满足性质： 0 0( )( ),jirpijk ( )( ),iirp 00( )( ),jirriji jk 00( )( ),jiAppiji jk (0)( )(0)( )(0)(0)(0)(0),1,kkkspan rrspan ppA rkspan rArA r Krylov ( (克雷洛夫克雷洛夫) )子空间子

13、空间定理定理7.3表明：向量组表明：向量组 和和 分别是分别是Krylov子空间的正交基和子空间的正交基和共轭共轭正交基。因此，共轭正交基。因此，共轭梯度法最多用梯度法最多用n步便可得到方程组的精确解。步便可得到方程组的精确解。01( )( )( ),krrr01( )( )( ), ,kppp由由共轭梯度共轭梯度法计算得到的法计算得到的 近似解满足近似解满足( )kx54 .Th ( )(0)(0)min:,kxxxxA rk 或或 ( )(0)(0)min:,kAAxxxxxxA rk 解：解：易验证系数矩阵是对称正定的易验证系数矩阵是对称正定的. .例：例：用用CG迭代法求解下列方程组迭代法求解下列方程组:21211x2x 300100133x0000( )()Tx Step1计算计算0003 1 3( )( )( )()TprbAx 000001955( )( )( )( )(,)(,)rrApp 100019