线性方程组的共轭梯度法课件.ppt

1、线性方程组的共轭梯度法(Hestenes and Stiefel,1952)(1)1min()(2)2(0)()0TTAxbf xx Axb xf xAxb线性方程组可以看成是如下无约束最优化问题的驻点条件 梯度等于无约束最优化问题的共轭梯度法无约束最优化问题的共轭梯度法 正交方向 共轭方向 共轭梯度法21()2()0,()*.()*,()(*)(*)(*)1(*)(*)21(*)|*|.2()TTTfww wr wfwwrfwwrfwwTaylorfwfwfwwwwwI wwfwwwfw 考 虑 一 类 特 殊 的 正 定 二 次 函 数令得的 极 小 点将在处 进 行展 开 得 到因 此的

2、 等 高 面 是 一 簇 超 球 面.正交方向及其性质W(1)W(2)W(3)=W*沿两个相互正交的方向，进行精确一维搜索，即可得到最优解（二维情形）n:n,n,1()2*.TTf ww wr wwr维情形 沿相互正交的 个方向,进行精确一维搜索至多迭代 次即可得到正定二次函数的最优解11()2nn*?TTf xx Ax b xxA b那么对于正定二次函数(A对称正定)能否通过在 个方向上的一维搜索,至多迭代 次获得其最优解T()*,1()(*)(*)(*)(*)(*)21(*)(*)(*)2()TTf xxTaylorf xf xf xxxxxA xxf xxxA xxf x将在处进行展开

3、得到因此的等高面是一簇超椭球面.d(1)x(1)x(2)x(3)=x*d(2)(1)(1)(2)(2)*(2)(2)*(1)(2)(1)(2)(1)*(2)(1)*(2)(1)(2)(1)(2)(1)(2),.)()0,()()()()()()()()()0.()0TTTTTTTxdxdxxdxdf xdA ddA xxdAxAxdbAxdf xdA d 从出发 沿作一维搜索与等高面相切于记再沿作一维搜索即可得到最优解由于(因此也就是说沿满足的两个方(1)(2),n,.dd向作一维搜索即可得到二维正定二次函数的最小点.对于 维的正定二次函数亦有相同的结论A共轭方向n(1)(2)(1)(2)n(

4、1)(2)(k)()():AnR()0A,A.RkA,()0,1,A,Ak.:AA=I,A.TiTjdddA dddddA dij i jk定义设 是 阶对称正定矩阵.若中的两个方向和满足则称这两个方向关于 共轭 或称它们关于 正交若中的 个方向,它们两两关于共轭 即则称这k个方向是 共轭的 或称它们为 的 个共轭方向注共轭是正交的推广,当时共轭即为正交(1)(k)n(1)(k)(1)(k)n(1)(1)(k)(2)(k+1)(k+1)(1)k(n+1)n1:RAk.2:RAk,n()k,k n,()Rddddddxddxxxf xxxf x性质 设,是中 的 个非零共轭方向,则,线性无关性质

5、 设,是中 的 个非零共轭方向,从任意的初始点出发 分别沿,进行一维搜索 得到,则是 维正定二次函数在 维线性流形上的唯一极小点.特别地 当=时是在上的唯一()k1.|,(,).kiiiix xd 极小点 这里(1)()(k)1()T()T(1)()T()()T(k)1()T(j)(1)(k)1:01ik,)A,)A)A)A00,j=i)A,0,ji0,1,2,.iiiiiiiiiiddddddddddddikdd kk性质 的证明设+对任意的上式两边左乘(得(+(+(由于(故得因此,线性无关(k+1)(1)(k+1)(k+1)k()ki21m+1mm+2m+1(2)(1)(1m+212:()

6、,()k()g().k1,g.kmn,g,g.g(immmmf xxf xxxf xf xAxbA xd 性质 的证明 由于是严格凸函数 要证明是在 维线性流形上的唯一极小点,只要证在处函数的梯度与子空间正交.用数学归纳法证明.记当时 由一维搜索的要求知假设时现要证)(1)m+11()()()(1)m+2m+11(m 1)m+2()(1)(m 1)m+1()(1)()m+2m+2m+1(1)g()g()g()im1,()g01im+1,()g0.A()0()g0g.kn,mmiTiTiTmmTiTiTmiTbAddddAddddddAddd 当时由一维搜索的要求知当时 由归纳假设有因,关于 共

7、轭当时,(n)n(1)n+1Rg0().ndxf x是的一组基是的唯一极小点A共轭方向的生成：共轭梯度法(1)(1)(1)(1)(1)1(2)(1)(1)11()()()()(1)()()()()kk()()(1)(,min(,.,argmin()kkkTkkkkkkkkTkkdf xdf xdxxdxddg dxxdf xddAdxk+1(1)令=-)=-g,沿进行一维搜索即解一维问题+)得令+(2)一般地 若已知点和搜索方向则沿进行一维搜索,得+)=-(若 g=0,则即为所()(1)(1)()(1)()(1)()()1()()(1)(1),A,)0,)(3)3,.kkkkkkkkTkkTk

8、kkTkkkdddddddAddAgdAdxdk+1k+1求 停止计算;否则用-g和构造下一个搜索方向,并使和关于 共轭,即-g+根据(可得()再从出发 沿进行一维搜索共轭梯度法基本性质定理:对于正定二次函数，采用精确一维搜索的共轭梯度法在nm 步后终止，且对1im成立下列关系式：()()()()(1)()0,1,2,1,()(2)0,1,2,1,()(3),(0)()iTjTijTiTiiiidAdjiggjigdggd 共 轭 性正 交 性蕴 含下 降 性,(1)1T(1)2T21T(2)T(1)T222122:i=1,.(3).i=2,(1).g0()g g0,(2)gg(g)g g,(

9、3).im,(1),(2),(3),i+1dgddd 证明 用数学归纳法证明.当时 由于因此关系成立当时 关系显然成立由精确一维搜索的要求可得从而关系也成立.根据关系也成立设对某个关系均成立现证明对这些关系也成立()(1)()()()()()()(1)()()1()TT()()(1)i+1jij1T()()()ij2,)(*)g gg g()(),ji,g g()()TiTiiiiiiiiiTiiTiiiiiiiiiiTjjijiTjig dg gxxddAddAdgAxbAxAdbgAddAdddAdd先证关系().根据迭代公式=-(由归纳法假设 当时(1)Ti+1jTT()(i)TTi+1

10、iiiiiii0g g0;j=ig gg g()g gg g0.(2).TjiTiAddAd当时故关系成立(1)()()()()()()111(i)()1i(1)()1()1i()()(1)(1).()()()()()()ji,()=0(1ji),()0;ji,)()iTjiTjTjiTjiiiijjTTjijTiTjijTiiiTiiTdAdgdAdgAddAdgggdAdggdAdgAddAddAd 再证关系当时 由归纳假设和有当时 根据得()(i)()11i()1111111()()()()0(1).iTTiiiiiTTiTTiiiiiiiiiiiiigggdAdggggggggAdgg

11、 故关系成立(1)()111()11111(3).()(1).,i+1,(1),(2),(3).TiTiiiiiTTiiiiiTiigdggdgggdgg 最后证关系易知故关系成立综上所述 对于关系也成立k的不同计算公式()1()()1111)(Hestenes and Stiefel)(FR)()(FRP)kTkkkTkTkkkTkkTkkkkTkkdAgdAdggg ggggg g(正定二次函数的共轭梯度法(1)()()()(1)111()()()k()()(1)()k,1(0,*(3):,1,0,(FR)(FRP).(4):min(,)kkkkkkkTkkkkkTkkkxf xxxddk

12、g df xddAdxxkkk(1)给定初始点置k=.(2)计算g=).若 g则停止计算,;否则转下一步.构造搜索方向令-g+其中当时否则按或公式计算一维搜索 解一维问题+)得=-(令+()(1).,*;1,(2).kkdknxxkk(5)若则停止计算 得否则令转步骤一般可微函数的共轭梯度法(1)()()()(1)111()()k(1)()()k,1(,*(3):,1,0,(FR)(FRP).(4):min(,.kkkkkkkkkkkkxf xxxddkf xdxxdkkkk(1)给定初始点和精度要求置k=,j=1.(2)计算g=).若 g则停止计算,;否则转下一步.构造搜索方向令-g+其中当

13、时否则按或公式计算一维搜索 解一维问题+)得令+(5)若,1,1(2).nkk则令否则令k=,j=j+1,转步骤共轭梯度法的特点 具有二次终止性，即对正定二次函数经过有限步迭代必达到最优解。为下降算法，可看成最速下降算法的一般化或推广（最速下降法相继搜索的两个方向是正交的，而共轭梯度法相继搜索的两个方向是共轭的）存储量少（仅需存储三个维向量x(k),g(k),d(k)），较适用于大规模问题正定对称方程组的共轭梯度法(1)()()()(1)121121()()()2k()(),10,*(3):,|,1,0,FR).|(4):min(|)kkkkkkkkkkkTkkkkTkxAxbxxddgkgf

14、 xdg dgdAdkkk(1)给定初始点置k=.(2)计算g=-.若 g则停止计算,;否则转下一步.构造搜索方向令-g+其中当时否则(公式一维搜索 解一维问题+)得=-(1)()()k()()(1),.),*;1,(2).kkkkTkkxxddAdknxxkk令+(5)若则停止计算 得否则令转步骤一般对称矩阵方程组的共轭梯度法(1)()()()(1)121121()()2(k()(),1,*(3):,|,1,0,.|(4):min(|,)kkkkkkkkkkkkkkTkxAxxxddgkgf xdgxdAdkkk(1)给定初始点和精度要求置k=,j=1.(2)计算g=-b.若 g则停止计算,

15、;否则转下一步.构造搜索方向令-g+其中当时否则一维搜索 解一维问题+)得令(1)()()k.,1,1(2).kkxdknkk+(5)若则令否则令k=,j=j+1,转步骤12(1)(1)(1)T111(2)(1)(1)1111(1)(1)(2)2312:110:0 0,:2 0,|20,2 0,41,2/3 0)123:02/3,|TTTTTTxxxgAxbgdgg gxxddAdgAxbg 例子用共轭梯度法求解下列正定矩阵方程组解 取初始点则第一次迭代=(第二次迭代222(2)(1)T12121(3)(2)(2)T2222(2)(2)(3)33(3)T|2/30,|/|(4/9)/4=1/9,2/9 2/3,2/33,1 1)4/920 0,|0,*1 1.TTTggdgdg gxxddAdgAxbgxx=(故一般线性方程组的共轭梯度法,TTAxb AA AxA bAxb可逆