第四章共轭梯度法ppt课件.ppt

第四章 共轭梯度法,数学系 罗芳,4.2 共轭梯度法,上节一般地讨论了共轭方向法，在那里,而如何获得这些共轭方向并为提及。本节讨论一种重要的共轭方向法共轭梯度法。这种方法在迭代过程中通过对负梯度方向进行适当校正获得共轭方向，故而称之为共轭梯度法。,个共轭方向是预先给定的，,（,），,（4.4）,共轭方向的修正公式为：,（4.6）,由下面诸式之一计算：,（Crowder-Wolfe公式） （4.7）,（Fletcher-Reeves公式） （4.8）,（Polak-Ribiere-Polyak 公式） （4.9）,（Dixon公式） （4.10）,其中，,1）,2),3）,4）,定理4.4 设水平集,有界，,是,偏导数的凸函数。,是由Fletcher-Reeves共轭梯度算法产生的迭代点列。则,为严格单调下降序列，且,存在。,的任意聚点都是最优解，于是：,。,上具有一阶连续,1）,2）,注：由这个定理的证明过程易见：上述收敛定理对其它几种共轭梯度算法也是成立的。,定理4.6 （Polak-Ribbiere-Polyak算法的总体收敛性）设,二阶连续可微，水平集,有界。又设存在常数,，使得对,收敛于,的唯一极小点。,，有：,则采用精确一维搜索的P-R-P共轭梯度算法产生的点列,定理4.8 设,二阶连续可微，水平集,有界。设,. （1）,由Wolfe-Powell准则确定，那么Fletcher-Reeves共轭梯度,算法产生的点列总体收敛，即有,定理4.9 设函数f(x)连续可微, f(x)满足Lipschitz条件,若在共轭梯度法中步长 由Wolfe-Powell准则确定,且下降方向 和,之间的夹角 满足 ，则对于共轭梯度法产生的点列 ，或者,存在某个 ，使得 ，或者 或者,共轭梯度法的收敛速度,前面已经讲过，共轭梯度法具有二次终止性，即对于二次函数，采用精确一维搜索的共轭梯度法在n次迭代后终止。对于二次目标函数，共轭梯度法的收敛速度至少是线性的。,由于采用精确线性搜索的共轭梯度法至多迭代n步可求得二次凸函数的极小点，相当于牛顿法执行一步。因此，若将n次迭代看作一次大的迭代，则共轭梯度法就应该与牛顿法有类似的收敛速度。下面的定理表明：在适当的条件下，共轭梯度法具有n步二阶收敛性。 假设条件1： ，即 三次连续可微。 假设条件2：设存在常数 ，使得,其中 是有界水平集。,定理4.9 假定假设条件1和2满足，那么，每r步再开始的PRP和FR共轭梯度法产生的迭代点列 n步二阶收敛，即存在常数c0，使得,这个定理的证明用以下两个定理。,定理4.10 设定理4.7的条件满足，并设在每一个点 定义二次函数 为,设 表示应用到 上的共轭梯度法，并且令,又设,那么，如果对于,成立，其中 是小于等于n的整数，满足,表示函数 的极小点，则再开始PRP和FR共轭梯度法产生的点列满足（2）,引理4.3.9,其中,引理4.3.10,引理4.3.11 对于PRP公式，,对于FR公式，,引理4.3.12,引理4.3.13,引理4.3.14 对于PRP公式，有,对于FR公式，有,引理4.3.15 我们有,引理4.3.16 我们有,定理4.3.17 设定理4.8的条件满足，那么,其中，对于所有k和,综合定理4.3.8和定理4.3.17，我们便可得到再开始共轭梯度法的n步二阶收敛定理4.3.7,