2.5-共轭梯度法解析

预备知识最速下降法共轭梯度法数值试验算例16:19§2.5共轭梯度法(x,y)=(y,x);(tx,y)=t(x,y);(x+y,z)=(x,z)+(y,z);(x,x)≥0,且(x,x)=0x=0;I方程组问题:Ax=b设A是n阶对称正定阵(Ax,y)=(x,Ay);(Ax，x)≥0,且(Ax,x)=0x=02/16预备知识：内积的定义II极值问题:xbAxxxfTTRxn21)(min设,记(x,y)=xTynRyx,预备知识梯度:12()grad(),,,nTfffxxxfxfx123()fxfxfxfx16:19222112221HessnnnffxxxfffxxxHessian矩阵:预备知识12,111()(,)(,)2=nnijijiiijifxAxxbxaxxbxgradfAxb222112221HessnnnffxxxfAffxxx16:19费马引理:000(),(),()=0xfxfxxfx设是的一个极值点且在处导数存在则16:19注释:费马引理的价值在于将极值问题转化为方程的求解问题。初等变分原理一、与方程组等价的二次泛函问题思想共轭梯度法将求解方程组问题等价转化为一个二次泛函的极值问题。定义二次函数:nRR2()TTHxxAxbx1112nnnijijjjijjaxxbx设为对称正定矩阵，()nnijAaR,Axb其中1(,,),Tnxxx11*(,,);.TnbbbxAb定理(初等变分原理)设A=(aij)n×n为实对称正定矩阵,，则x是二次函数的极小值点x是线性方程组Ax=b的解。nRbx,16:192()TTHxxAxbx1112nnnijijjjijjaxxbx该性质说明：求解方程组的解等价于求上述二次函数的最小值。()min(),nxRHxHx若则由极值的必要条件得()HxAxb22Axb0.迭代法构造思想：构造使得(){}kx011()()()()*()()()()(),kkHxHxHxHxHx()*lim()()kkHxHx且，()*limkkxx。从瞎子下山到最优化方法16:19ScienceofBetter瞎子与计算机•瞎子:能感觉到脚下的坡度(这是海拔函数在当前点的梯度值),但不知道山上其它点的任何情况•计算机:计算目标函数在该点的信息(如函数值和梯度值),但不知道其它点的信息16:192.5.2最速下降法几何意义：等值线x0()x思想最速下降法是指每次沿着函数值下降最快的方向寻找最小值点。而函数值下降最快的方向是函数的负梯度方向最速下降法实现过程：选取初始向量，由二次函数的基本性质0()x()Hx0()()Hx0()r如果，则就是方程组的解；00()r0()x如果，则沿方向进行一维极小搜索：00()r0()r求使得达到最小值,则000()()()Hxr0000000012()()()()()()()()()=()()()TTHxrxrAxrbxr0()bAx1000()()().xxr00000()()()()(,)(,)rrArr20000220()()()()()(,)dxrArrd注意到00000()()()()min()()xrxr1000()()()xxr令，从而完成第一次迭代。下面以为新的初值，重复上述过程。1()x000()()()dHxrd最速下降法的算法:选取初值0()nxRFork=0,1,2,…()()kkrbAx()()()()(,)(,)kkkkkrrArr1()()()kkkkxxr若，停止()()kTkrr否则，进行下一次循环10()()(,)kkrr搜索方向是正交的：11()()kkrbAx()()()kkkbAxr()()kkkrAr缺陷：收敛速度慢！收敛速度？？？？？解：易验证系数矩阵是对称正定的.例：用最速下降法求解方程组:21211x2x300100133x0000()()TxStep1计算00313()()()TrbAx000001955()()()()(,)(,)rrArr10001931355()()()()Txxr最好+最好=最好?•方向(最速下降)(bestrk)•步长(精确搜索)(best)•是否最好?16:19k1()()()kkkkxxr设的特征值为,A10n则由前述最速下降算法产生的序列满足其中。1xAb()kx()(0)11kknAAnxxxxTh上述定理说明，当时最速下降法收敛非常慢。1n锯齿现象，其等值面近似数可以用二次函数近似在极小点附近，目标函椭球面。1x*x2x3x它只是。标函数的一种局部性质最速下降方向反映了目快的方向。局部目标函数值下降最注的算法。最速下降法是线性收敛f(x1,x2)=100x12+x22最速下降法16:19f(x1,x2)=100x12+x22Barzilai-Borwein方法16:19最速下降法思想简单,但是收敛速度慢。本质上是因为负梯度方向函数下降快是局部性质。全局思想:局部思想:N维空间的任意向量可以由N个线性无关的向量线性表示。16:193、共轭梯度法/*Conjugate-GradientMethod*/共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。Hestenes和Stiefle（1952）提出来的，用于解正定系数矩阵的线性方程组，Fletcher和Reeves（1964）首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用与实际问题，已经成为求解大型稀疏线性方程组最受欢迎的一类方法。16:19共轭梯度法的关键是构造一组两两共轭的方向(即一组线性无关向量)。巧妙的是,共轭方向可以由上次搜索方向和当前的梯度方向之组合来产生。pk+1:=rk+1+tau*pkTheBestofthe20thCentury:EditorsNameTop10Algorithms,SIAMNews现代迭代方法:Krylov子空间方法共轭方向和共轭方向法定义共轭。关于和，则称若有AppAppT21210ARpppnk它们两两关于中一组非零向量，如果是设,,,21。共轭，即kjijiAppjTi,,2,1,,,0共轭方向。组共轭的，也称它们是一则称这组方向是关于AA注：002121pppIpTT21pp共轭是正交的推广！！，和中的两个非零向量的对称正定矩阵，对于是设21ppRnnAn是单位矩阵，则如果A选取初始向量，0()x00()(),pr00000()()()()(,)(,)rpApp1000()()()xxp11()(),rbAx共轭梯度法如何确定下一个搜索方向呢？共轭梯度法的实现过程选取初始向量，0()x00()()pr00000()()()()(,)(,)rrApp100110()()()()(),xxprbAx确定下一个搜索方向：由过点向量和所张成的下列二维平面内找出函数值下降最快的方向作为搜索方向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)12TTHxrpxrpAxrpbxrp(,)(1)(1)(1)(0)(1)(1)(1)(0)(0)(0)00TTTTTrArrAprrrAppAp由极值的必要条件得(1)(1)(0)00xxrp其中满足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(,)(,)rAppAp(2)(1)(1)1xxp(1)(1)(0)0prp下面以为新的迭代值，重复上述过程即可2()x共轭梯度法的算法选取初值0()nxRFork=0,1,2,…,n00()()pr00()()rbAx计算计算()()()()kTkkkTkprpAp1()()()kkkkxxp1()()()kkkkrrAp1()()()()kTkkkTkpArpAp11()()()kkkkprp如果，停止10()kr否则，计算进行下一次迭代共轭梯度法的算法选取初值0()nxRFork=0,1,2,…,n00()()pr00()()rbAx计算计算()()()()(,)(,)kkkkkrrApp1()()()kkkkxxp1()()()kkkkrrAp11()()()()(,)(,)kkkkkrrrr11()()()kkkkprp如果，停止10()kr否则，计算进行下一次迭代解：易验证系数矩阵是对称正定的.例：用CG迭代法求解下列方程组:21211x2x300100133x0000()()TxStep1计算000313()()()()TprbAx000001955()()()()(,)(,)rrApp10001931355()()()()TxxpStep2计算1000616155()()()()TrrAp111115557()()()()(,)(,)rrApp2111111()()()()Txxp11000723025()()()()(,)(,)rrrr110011411813025()()()()Tprp22000()()()TrbAx迭代结束由共轭梯度法计算得到的近似解满足()kxTh()(0)(0)min:,,kxxxxArk或()(0)(0)2()021222min:,,;12,1||||||||.kAAkkAAxxxxxxArkKxxxxKKAAAxb总结:16:19矩阵分解(1)特征值分解:A=CDCT,[C,D]=eig(A)(2)LU分解:PA=LU,[L,U,P]=lu(A)(3)Cholesky分解:A=RTR,R=chol(A)16:19(4)QR分解:A=QR,[Q,R]=qr(A)(5)奇异值分解:A=USVH,[U,S,V]=svd(A)(6)非负矩阵分解Non-negativeMatrixFactorizationA=WH11()()()||||||||||*||||||kkkXXXXBB16:1911()*()()||||kkkLLxxxx()xx11,xMNxMbAMN其中迭代法构造收敛条件中止准则**(0)***(),(),()()1()NxxxNxxxxx为的不动点在的连续且则迭代法对任意某邻域收敛(0)X()1||||1fBB