線性方程組的共軛梯度法

1、1線性方程組的共軛梯度法(Hestenes and Stiefel,1952)234(1)1min( )(2)2(0)( )0TTAxbf xx Axb xf xAxb線性方程組可以看成是如下無約束最優(yōu)化問題的駐點條件 梯度等于5無約束最優(yōu)化問題的共軛梯度法無約束最優(yōu)化問題的共軛梯度法 正交方向 共軛方向 共軛梯度法621()2()0,()*.()*,()(*)(*)(*)1(*)(*)21(*)|* | .2()TTTfww wr wfwwrfwwrfwwTaylorfwfwfwwwwwI wwfwwwfw 考 慮 一 類 特 殊 的 正 定 二 次 函 數(shù)令得的 極 小 點將在處 進(jìn) 行展

2、 開 得 到因 此的 等 高 面 是 一 簇 超 球 面 .7正交方向及其性質(zhì)W(1) W(2) W(3) =W* 沿兩個相互正交的方向，進(jìn)行精確一維搜索，即可得到最優(yōu)解（二維情形）8n:n,n,1( )2*.TTf ww wr wwr維情形 沿相互正交的 個方向,進(jìn)行精確一維搜索至多迭代 次即可得到正定二次函數(shù)的最優(yōu)解911( )2nn*?TTf xx Ax b xxA b那么對于正定二次函數(shù)(A對稱正定)能否通過在 個方向上的一維搜索,至多迭代 次獲得其最優(yōu)解10T( )*,1( )( *)( *) (*)(*)(*)21( *)(*)(*)2( )TTf xxTaylorf xf xf

3、xxxxxA xxf xxxA xxf x將在處進(jìn)行展開 得到因此的等高面是一簇超橢球面.11d(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 從出發(fā) 沿作一維搜索與等高面相切于記再沿作一維搜索即可得到最優(yōu)解由于(因此也就是說沿滿足的兩個方(1)(2),n,.dd向作一維搜索即可得到二維正定二次函數(shù)的最小點.對于 維

4、的正定二次函數(shù)亦有相同的結(jié)論12A共軛方向n(1)(2)(1)(2)n(1)(2)(k)( )( ):AnR()0A,A.RkA,()0, ,1,A,Ak.:AA=I,A.TiTjdddA dddddA dij i jk定義設(shè) 是 階對稱正定矩陣.若中的兩個方向和滿足則稱這兩個方向關(guān)于 共軛 或稱它們關(guān)于 正交若中的 個方向, ,它們兩兩關(guān)于共軛 即則稱這k個方向是 共軛的 或稱它們?yōu)?的 個共軛方向注共軛是正交的推廣,當(dāng)時共軛即為正交13(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,( )R

5、ddddddxddxxxf xxxf x性質(zhì) 設(shè),是中 的 個非零共軛方向,則,線性無關(guān)性質(zhì) 設(shè),是中 的 個非零共軛方向,從任意的初始點出發(fā) 分別沿,進(jìn)行一維搜索 得到,則是 維正定二次函數(shù)在 維線性流形上的唯一極小點.特別地 當(dāng) = 時是在上的唯一( )k1. |,(,).kiiiix xd 極小點 這里14(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性質(zhì) 的證明設(shè)+對任意的上式兩邊左乘(得(+

6、(+(由于(故得因此,線性無關(guān)15(k+1)(1)(k+1)(k+1)k( )ki21m+1mm+2m+1(2)(1)(1m+212: ( ),( )k()g().k1,g.kmn,g,g.g(immmmf xxf xxxf xf xAxbA xd 性質(zhì) 的證明 由于是嚴(yán)格凸函數(shù) 要證明是在 維線性流形上的唯一極小點,只要證在處函數(shù)的梯度與子空間正交.用數(shù)學(xué)歸納法證明.記當(dāng)時 由一維搜索的要求知假設(shè)時現(xiàn)要證)(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

7、,() g0.A()0() g0g.kn,mmiTiTiTmmTiTiTmiTbAddddAddddddAddd 當(dāng)時由一維搜索的要求知當(dāng)時 由歸納假設(shè)有因,關(guān)于 共軛當(dāng)時,(n)n(1)n+1Rg0( ).ndxf x是的一組基是的唯一極小點16A共軛方向的生成：共軛梯度法(1)(1)(1)(1)(1)1(2)(1)(1)11( )( )( )( )(1)( )( )( )( )kk( )( )(1)(,min(,.,argmin()kkkTkkkkkkkkTkkdf xdf xdxxdxddg dxxdf xddAdxk+1(1)令=-)=-g ,沿進(jìn)行一維搜索即解一維問題+)得令+(2)

8、一般地 若已知點和搜索方向則沿進(jìn)行一維搜索,得+)=-( 若 g=0,則即為所( )(1)(1)( )(1)( )(1)( )( )1( )( )(1)(1),A,)0,)(3)3,.kkkkkkkkTkkTkkkTkkkdddddddAddAgdAdxdk+1k+1求 停止計算;否則用-g和構(gòu)造下一個搜索方向,并使和關(guān)于 共軛,即-g+ 根據(jù)(可得( )再從出發(fā) 沿進(jìn)行一維搜索17共軛梯度法基本性質(zhì)定理: 對于正定二次函數(shù)， 采用精確一維搜索的共軛梯度法在nm 步后終止， 且對1im成立下列關(guān)系式：( )()( )( )(1) ()0 ,1, 2,1,()(2)0 ,1, 2,1,()(3)

9、, (0)()iTjTijTiTiiiidAdjiggjigdggd 共 軛 性正 交 性蘊(yùn) 含下 降 性,18(1)1T(1)2T21T(2)T(1)T222122:i=1,.(3).i=2,(1).g0()g g0,(2)gg ( g)g g ,(3).im,(1),(2),(3),i+1dgddd 證明 用數(shù)學(xué)歸納法證明.當(dāng)時 由于因此關(guān)系成立當(dāng)時 關(guān)系顯然成立由精確一維搜索的要求可得從而關(guān)系也成立.根據(jù)關(guān)系也成立設(shè)對某個關(guān)系均成立現(xiàn)證明對這些關(guān)系也成立19( )(1)( )( )( )( )( )( )(1)( )( )1( )TT( )( )(1)i+1jij1T( )( )( )i

10、j2,)(*)g gg g()(),ji,g g()()TiTiiiiiiiiiTiiTiiiiiiiiiiTjjijiTjig dg gxxddAddAdgAxbAxAdbgAddAdddAdd先證關(guān)系( ).根據(jù)迭代公式=-(由歸納法假設(shè) 當(dāng)時(1)Ti+1jTT( )(i)TTi+1iiiiiii0g g0;j=ig gg g()g gg g0.(2).TjiTiAddAd當(dāng)時故關(guān)系成立20(1)( )( )( )( )( )( )111(i)( )1i(1)( )1( )1i( )( )(1)(1).()()()()()()ji,()=0(1ji),()0;ji,)()iTjiTjTj

11、iTjiiiijjTTjijTiTjijTiiiTiiTdAdgdAdgAddAdgggdAdggdAdgAddAddAd 再證關(guān)系當(dāng)時 由歸納假設(shè)和有當(dāng)時 根據(jù)得( )(i)( )11i( )1111111()()()()0(1).iTTiiiiiTTiTTiiiiiiiiiiiiigggdAdggggggggAdgg 故關(guān)系成立21(1)( )111( )11111(3).()(1).,i+1,(1),(2),(3).TiTiiiiiTTiiiiiTiigdggdgggdgg 最后證關(guān)系易知故關(guān)系成立綜上所述 對于關(guān)系也成立22k的不同計算公式( )1( )( )1111)(Hestene

12、s and Stiefel)(FR)()(FRP)kTkkkTkTkkkTkkTkkkkTkkdAgdAdggg ggggg g(23正定二次函數(shù)的共軛梯度法(1)( )( )( )(1)111( )( )( )k( )( )(1)( )k,1(0,*(3):,1,0,(FR)(FRP).(4):min(,)kkkkkkkTkkkkkTkkkxf xxxddkg df xddAdxxkkk(1)給定初始點置k= .(2)計算g =).若 g則停止計算,;否則轉(zhuǎn)下一步.構(gòu)造搜索方向令-g +其中當(dāng)時否則按或公式計算一維搜索 解一維問題+)得=-(令+( )(1).,*;1,(2).kkdknxx

13、kk(5)若則停止計算 得否則令轉(zhuǎn)步驟24一般可微函數(shù)的共軛梯度法(1)( )( )( )(1)111( )( )k(1)( )( )k,1(,*(3):,1,0,(FR)(FRP).(4):min(,.kkkkkkkkkkkkxf xxxddkf xdxxdkkkk(1)給定初始點和精度要求置k= ,j=1.(2)計算g =).若 g則停止計算,;否則轉(zhuǎn)下一步.構(gòu)造搜索方向令-g +其中當(dāng)時否則按或公式計算一維搜索 解一維問題+)得令+(5)若,1, 1(2).nkk則令否則令k= ,j=j+1,轉(zhuǎn)步驟25共軛梯度法的特點 具有二次終止性，即對正定二次函數(shù)經(jīng)過有限步迭代必達(dá)到最優(yōu)解。 為下降

14、算法，可看成最速下降算法的一般化或推廣（最速下降法相繼搜索的兩個方向是正交的，而共軛梯度法相繼搜索的兩個方向是共軛的） 存儲量少（僅需存儲三個維向量x(k),g(k),d(k)），較適用于大規(guī)模問題26正定對稱方程組的共軛梯度法(1)( )( )( )(1)121121( )( )( )2k( )( ),10,*(3):,|,1,0,FR).|(4):min(|)kkkkkkkkkkkTkkkkTkxAxbxxddgkgf xdg dgdAdkkk(1)給定初始點置k= .(2)計算g =- .若 g則停止計算,;否則轉(zhuǎn)下一步.構(gòu)造搜索方向令-g +其中當(dāng)時否則(公式一維搜索 解一維問題+)得

15、=-(1)( )( )k( )( )(1),.),*;1,(2).kkkkTkkxxddAdknxxkk令+(5)若則停止計算 得否則令轉(zhuǎn)步驟27一般對稱矩陣方程組的共軛梯度法(1)( )( )( )(1)121121( )( )2(k( )( ),1,*(3):,|,1,0,.|(4):min(|,)kkkkkkkkkkkkkkTkxAxxxddgkgf xdgxdAdkkk(1)給定初始點和精度要求置k= ,j=1.(2)計算g =-b.若 g則停止計算,;否則轉(zhuǎn)下一步.構(gòu)造搜索方向令-g +其中當(dāng)時否則一維搜索 解一維問題+)得令(1)( )( )k.,1, 1(2).kkxdknkk+(5)若則令否則令k= ,j=j+1,轉(zhuǎn)步驟2812(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