25-共轭梯度法PPT课件.ppt

1、1预备知识最速下降法共轭梯度法数值试验算例*2.5 共轭梯度法2标题添加点击此处输入相关文本内容点击此处输入相关文本内容总体概述点击此处输入相关文本内容标题添加点击此处输入相关文本内容3( 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 = 0 2/16预备知识：内积的定义II 极

2、值问题: xbAxxxfTTRxn 21)(min设 , 记 ( x , y) = xT ynRyx ,4预备知识 梯度: : 12( )grad ( ),nTfffxxxf xf x 123( )fxfxfxf x *222112221Hessnnnffxx xfffxxx HessianHessian矩阵: :5预备知识 12,111( )(,)( , )2 =nnijijiii jif xAx xb xa x xb x gradfAxb222112221Hessnnnffxx xfAffxxx *6费马引理: :000( ),( ), ()=0 xf xf xxfx 设设是是的的一一个个

3、极极值值点点 且且在在处处导导数数存存在在 则则*注释: : 费马引理的价值在于将极值问题转化为方程的求解问题。7初等变分原理一、与方程组等价的二次泛函问题共轭梯度法将求解方程组问题等价转化为一个二次 泛函的极值问题。 定义二次函数:nRR 2( )TTH xx Axb x 1112nnnijijjjijja x xb x设 为对称正定矩阵，()n nijAaR ,Axb 其中1(,) ,Tnxxx 11*(,) ;.TnbbbxA b 8定理( (初等变分原理) ) 设A =(aij )nn为实对称正定矩阵, , ，则 x是二次函数 的极小值点 x 是线性方程组 Ax = b 的解。 nRb

4、x ,*2( )TTH xx Axb x 1112nnnijijjjijja x xb x9该性质说明：求解方程组的解等价于求上述二次函数的最小值。()min( ),nxRH xH x 若则由极值的必要条件得()H x Axb 22Axb 0. 迭代法构造思想：构造 使得( )kx011( )( )()( )*()()()()(),kkH xH xH xH xH x ( )*lim()()kkH xH x 且且，( )*limkkxx。10从瞎子下山到最优化方法*Science of BetterScience of Better11瞎子与计算机 瞎子: 能感觉到脚下的坡度(这是海拔函数在当前

5、点的梯度值),但不知道山上其它点的任何情况 计算机: 计算目标函数在该点的信息(如函数值和梯度值), 但不知道其它点的信息 *122.5.2 最速下降法 几何意义：等值线 x 0( )x最速下降法是指每次沿着函数值 下降最快的方向寻找最小值点。 而函数值下降最快的方向是函数的负梯度方向13 最速下降法实现过程：选取初始向量 ，由二次函数 的基本性质0( )x( )H x0( )()H x0( )r 如果 ，则 就是方程组的解；00( )r 0( )x如果 ，则沿 方向进行一维极小搜索：00( )r 0( )r求 使得 达到最小值, 则0 00( )( )()H xr 0000000012( )

6、( )( )( )( )( )( )( )()=()()()TTH xrxrA xrbxr 0( )bAx 1000( )( )( ).xxr 1400000( )( )( )( )(,)(,)rrArr 20000220( )( )( )( )()(,)dxrArrd 注意到00000( )( )( )( )min ()()xrxr 1000( )( )( )xxr 令 ，从而完成第一次迭代。下面以 为新的初值，重复上述过程。1( )x000( )( )()dH xrd 15 最速下降法的算法:选取初值0( )nxR For k=0,1,2,( )( )kkrbAx ( )( )( )( )

7、(,)(,)kkkkkrrArr 1()( )( )kkkkxxr 若 ，停止( )( )k Tkrr 否则，进行下一次循环10()( )(,)kkrr 搜索方向是正交的：11()()kkrbAx ( )( )()kkkbA xr ( )( )kkkrAr 缺陷：收敛速度慢！收敛速度？16解：易验证系数矩阵是对称正定的. .例：用最速下降法求解方程组:21211x2x 300100133x0000( )()Tx Step1计算003 1 3( )( )()TrbAx 000001955( )( )( )( )(,)(,)rrArr 1000193 1355( )( )( )()Txxr 17最

8、好 + + 最好 = = 最好 ? 方向( (最速下降) ) (best rk) 步长( (精确搜索) ) (best ) 是否最好 ?*k 1()( )( )kkkkxxr 18设 的特征值为 , ,A10n则由前述最速下降算法产生的序列 满足其中 。1xA b ( )kx( )(0)11kknAAnxxxx Th上述定理说明，当 时最速下降法收敛非常慢。1n19锯锯齿齿现现象象，其其等等值值面面近近似似数数可可以以用用二二次次函函数数近近似似在在极极小小点点附附近近，目目标标函函椭球面。椭球面。1x*x2x3x它它只只是是。标标函函数数的的一一种种局局部部性性质质最最速速下下降降方方向向反

9、反映映了了目目快快的的方方向向。局局部部目目标标函函数数值值下下降降最最注注的的算算法法。最最速速下下降降法法是是线线性性收收敛敛20f(x1, ,x2)= =100 x12+ +x22最速下降法*21f(x1, ,x2)= =100 x12+ +x22B Barzilai-arzilai-B Borweinorwein方法*22 最速下降法思想简单,但是收敛速度慢。本质上是因为负梯度方向函数下降快是局部性质。全局思想: :局部思想: : N 维空间的任意向量可以由N个线性无关的向量线性表示。*233 3、共轭梯度法/*Conjugate-Gradient Method*/共轭梯度法不仅是解决

10、大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。HestenesHestenes和StiefleStiefle（19521952）提出来的，用于解正定系数矩阵的线性方程组，FletcherFletcher和ReevesReeves（19641964）首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用与实际问题，已经成为求解大型稀疏线性方程组最受欢迎的一类方法。24* 共轭梯度法的关键是构造一组两两共轭的方向(即一组线性无关向量)。巧妙的是, 共轭方向可以由上次搜索方向和当前的梯度方向

11、之组合来产生。pk+1 := rk+1 + tau*pk The Best of the 20th Century: The Best of the 20th Century: Editors Name Editors Name Top 10 Top 10 Algorithms, Algorithms, SIAM SIAM News News 现代迭代方法: Krylov: Krylov子空间方法25共轭方向和共轭方向法定义定义共轭。共轭。关于关于和和，则称，则称若有若有AppAppT21210 ARpppnk它它们们两两两两关关于于中中一一组组非非零零向向量量，如如果果是是设设,21。共轭，

12、即共轭，即kjijiAppjTi,2, 1,0 共轭方向。共轭方向。组组共轭的，也称它们是一共轭的，也称它们是一则称这组方向是关于则称这组方向是关于AA注注：002121 pppIpTT21pp 共轭是正交的推广！，和和中的两个非零向量中的两个非零向量的对称正定矩阵，对于的对称正定矩阵，对于是是设设21ppRnnAn 是是单单位位矩矩阵阵，则则如如果果 A26选取初始向量 ， 0( )x00( )( ),pr 00000( )( )( )( )(,)(,)rpApp 1000( )( )( )xxp 11( )( ),rbAx共轭梯度法如何确定下一个搜索方向呢？27 共轭梯度法的实现过程选取初

13、始向量 ， 0( )x00( )( )pr 00000( )( )( )( )(,)(,)rrApp 100110( )( )( )( )( ),xxprbAx 确定下一个搜索方向：由过点 向量 和 所张成的下列二维平面内找出函数值下降最快的方向作为搜索方向1( )x1( )r0( )p1( )p (1)(1)(0)2:,xxrpR 282 (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)12TTHxrpxrpA xrpbxrp ( , ) 29(1)(

14、1)(1)(0)(1)(1)(1)(0)(0)(0)00TTTTTrArrAprrrAppAp 由极值的必要条件得(1)(1)(0)00 xxrp其中 满足00, (1)(1)(1)(0)(1)(1)00(1)(0)(0)(0)000TTTTTrArrAprrrAppAp 30取下一个搜索方向为(1)(1)(1)(0)0001()pxxrp 11111( )( )( )( )(,)(,)rpApp 沿该方向进行一维搜索得步长为记(1)(0)00(0)(0)0(,)(,)rAppAp (2)(1)(1)1xxp (1)(1)(0)0prp 下面以 为新的迭代值，重复上述过程即可2( )x31 共

15、轭梯度法的算法选取初值0( )nxR For k=0 , 1 , 2 , , n00( )( )pr 00( )( )rbAx 计算计算( )( )( )( )k Tkkk TkprpAp 1()( )( )kkkkxxp 1()( )( )kkkkrrAp 1( )()( )( )k Tkkk TkpArpAp 11()()( )kkkkprp 如果 ，停止10()kr 否则，计算进行下一次迭代32 共轭梯度法的算法选取初值0( )nxR For k=0 , 1 , 2 , , n00( )( )pr 00( )( )rbAx 计算计算( )( )( )( )(,)(,)kkkkkrrApp

16、 1()( )( )kkkkxxp 1()( )( )kkkkrrAp 11()()( )( )(,)(,)kkkkkrrrr 11()()( )kkkkprp 如果 ，停止10()kr 否则，计算进行下一次迭代33解：易验证系数矩阵是对称正定的. .例：用CG迭代法求解下列方程组:21211x2x 300100133x0000( )()Tx Step1计算0003 1 3( )( )( )()TprbAx 000001955( )( )( )( )(,)(,)rrApp 1000193 1355( )( )( )()Txxp 34Step2 计算1000616 155( )( )( )()T

17、rrAp 111115557( )( )( )( )(,)(,)rrApp 21111 1 1( )( )( )()Txxp 11000723025( )( )( )( )(,)(,)rrrr 11001141 1813025( )( )( )()Tprp 22000( )( )()TrbAx 迭代结束35由共轭梯度法计算得到的 近似解满足( )kxT h ( )(0)(0)min:,kxxxxA rk 或 ( )(0)(0)2( )021222min:,;12,1| | .kAAkkAAxxxxxxA rkKxxxxKKAA 36Axb 总结: :*37矩阵分解(1)特征值分解: A=CDC

18、T, C,D=eig(A)(2) LU分解: PA=LU, L,U,P=lu(A)(3)Cholesky分解: A=RTR, R=chol(A)* QR分解: A=QR, Q,R=qr(A) (5)奇异值分解: A=USVH, U,S,V = svd(A) (6) 非负矩阵分解Non-negative Matrix Factorization A=WH3811( )( )()|*|kkkXXXXBB *11( )*( )()|kkkLLxxxx ( )xx 11,xMNxM bAMN 其其中中迭代法构造收敛条件中止准则*(0)*( ), ( ), ()()1()N xxxN xxxxx 为为的

19、的不不动动点点在在 的的连连续续且且则则迭迭代代法法对对任任意意某某邻邻域域收收敛敛(0)X( )1| | |1fBB 对对任任意意的的 和和迭迭代代法法收收敛敛的的充充分分必必要要条条件件是是和和充充分分条条件件是是任任意意的的初初始始向向量量古典迭代法统一不动点框架39* 共轭梯度法的关键是构造一组两两共轭的方向(即一组线性无关向量)。巧妙的是, 共轭方向可以由上次搜索方向和当前的梯度方法之组合来产生。pk+1 := rk+1 + tau*pk 现代迭代方法: 共轭梯度方法The Best of the 20th Century: Editors Name Top 10 Algorithms, SIAM News 最速下降法思想简单,但收敛速度慢。本质上因为负梯度方向函数下降快是局部性质。40511223223435251622311311311131113113xxxxxx 算例1 141问题提问与解答问答HERE COMES THE QUESTION AND ANSWER SESSION42添加标题添加标题添加标题添加标题此处结束语点击此处添加段落文本 . 您的内容打在这里，或通过复制您的文本后在此框中选择粘贴并选择只保留文字43谢谢您的观看与聆听Thank you for watching and listening