1、求解正定線性方程組的共軛梯度法CG方法 林華堂、張卜元、呂迪1.方法簡(jiǎn)介n 共軛梯度法已有五十多年的歷史,它最早是由Hestenes和Stiefel于1952年在求解線性方程組時(shí)提出的,并由Fletcher和Reeves于1964年推行到非線性優(yōu)化領(lǐng)域.后,Beale,Powell,Fletcher等著名的優(yōu)化專家對(duì)非線性共軛梯度法進(jìn)展了深化研討,獲得了非常優(yōu)秀的成果.但幾乎同時(shí)間世的擬牛頓方法由于其良好的計(jì)算表現(xiàn)以及豐富的收斂性分析很快遭到了青睞,從而在很長(zhǎng)一段時(shí)間里共軛梯度法被研討者所忽視.近年來(lái),隨著計(jì)算機(jī)的飛速開展以及實(shí)踐問(wèn)題的需求,大規(guī)模優(yōu)化問(wèn)題越來(lái)越遭到注重,而共軛梯度法正是求解大

2、規(guī)模問(wèn)題的一種主要方法.于是,共軛梯度法的實(shí)際研討又遭到人們的關(guān)注. 共軛梯度法Conjugate Gradient是介于最速下降法與牛頓法之間的一個(gè)方法，它僅需利用一階導(dǎo)數(shù)信息，但抑制了最速下降法收斂慢的缺陷，又防止了牛頓法需求存儲(chǔ)和計(jì)算Hesse矩陣并求逆的缺陷，共軛梯度法不僅是處理大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化最有效的算法之一。 在各種優(yōu)化算法中，共軛梯度法是非常重要的一種。其優(yōu)點(diǎn)是所需存儲(chǔ)量小，具有步收斂性，穩(wěn)定性高，而且不需求任何外來(lái)參數(shù)。2.方法實(shí)際與描畫nCG方法，它是一種極小化方法，對(duì)應(yīng)于求一個(gè)二次函數(shù)的極值。n為了引出CG方法，下面引見(jiàn)一些實(shí)際。n2.

3、1與方程組等價(jià)的變分問(wèn)題n n n 2.11bAxARbRAnn對(duì)稱正定，考慮方程組設(shè),n),(,21:nxbxAxxRR）（）（為定義二次函數(shù)n那么函數(shù) 有如下性質(zhì)：n1對(duì)一切 ，有n 2.12n2對(duì)一切 ,有n 2.13nRx bAxxgrad)(RRyxn,),(2),()(),(),(21)2yAyaybAxxyxbyxyxAyx（n3設(shè) 為方程組2.11的解，那么對(duì)一切 ，有n 2.14n那么xnRx），（）（）（xxxxAxx21),(21),(21),(),(21)(),(21)(,11111xAxbAbbAbbAbAAxbxAxxbAx所以證明：因?yàn)?()(),(21),(),

4、(21),(21xxxAxxAxxAxxxxxAn定理定理1 設(shè)設(shè)A對(duì)稱正定，那么對(duì)稱正定，那么 為方程組為方程組2.11解的充分必要條件解的充分必要條件是是 n 滿足滿足n證明：設(shè)證明：設(shè) 為方程組為方程組2.11的解，的解， 由式由式2.14及及A的正定性，的正定性，有有 。n 反之，假設(shè)有反之，假設(shè)有 使使 到達(dá)最小，那么到達(dá)最小，那么n 故由式故由式2.14可知可知n 又因又因A正定，所以正定，所以 。證畢。證畢。n 由上述定理，求解線性方程組由上述定理，求解線性方程組 等價(jià)于求解變分問(wèn)題，即求等價(jià)于求解變分問(wèn)題，即求n 最小。求解的方法普通是構(gòu)造一個(gè)向量序列最小。求解的方法普通是構(gòu)造

5、一個(gè)向量序列 ,n 使使 。xx)(min)(xxnRxx最小。使即)(, 0)()(xxxxxx)(x。所以。又0)()(),()()()(xxxxxx0)()( 2),(xxxxxxAxxbAx)(xRxn，使kx)(min)(xxk2.2共軛梯度CG法的定義n設(shè) 是恣意給定的一個(gè)初始點(diǎn)，從點(diǎn) 出發(fā)沿某一規(guī)定的方向 ，求函數(shù) 在直線 n上的極小點(diǎn)，設(shè)求得的極小點(diǎn)為 。再?gòu)狞c(diǎn) 出發(fā)沿某一規(guī)定的方向 ，求函數(shù) 在直線 n上的極小點(diǎn)，設(shè)求得的極小點(diǎn)為 。如此繼續(xù)下去，普通地，從 點(diǎn) 出發(fā)沿某一規(guī)定的方向 ，求函數(shù) 在直線0 x0 x0p)(x00tpxx1x1x1p)(x11tpxx2xkxkp

6、)(xkktpxxn上的的極小點(diǎn) 。稱 為搜索方向。n命題2 對(duì)于知的 n上的極小點(diǎn) 為 n式中n證明：記 ，欲確定系數(shù) 使得一元函數(shù) 時(shí)為極小。由式(2.13)得n 1kxkp在直線函數(shù))(),0(,xppxkkkkktpxx1kxkkkkpxx1bAxrApprkkkkTk,p-Tkk)()(kktpxtfkktf當(dāng)),(2),()()(2kkkkkpAptpbAxtxtf得由, 0)( tfkTkkTkkTkkTkkAppprApppbAxat)(極小。從而時(shí)，因此又由于)(),0(0tfatpAppfkkkTk kkkkpxx1證畢。n注注2 在命題在命題2中，余量中，余量 命題命題2

7、所得所得的迭代公式的迭代公式n 2.15 n具有下降性具有下降性。)(kkkxgradbAxrkTkkTkkkkkkAppprpxx1)()(1kkxxn假設(shè)搜索方向n為 中的一個(gè)A共軛向量系，即有性質(zhì)n 2.16n的向量系 ，那么稱迭代法2.15為共軛梯度法CG法。n 用 表示線性無(wú)關(guān)的向量系 張成的子空間，即n令,210pppnR0jTiApp)(ji),2, 1 ,0(0,kppkk且kLkp1210,kkppppspanL。kkLuuxxS0n定理定理2 從恣意一點(diǎn)從恣意一點(diǎn) 出發(fā)，得到的點(diǎn)序列出發(fā)，得到的點(diǎn)序列n 2.17n的充分必要條件是的充分必要條件是0 x具有性質(zhì),21xx)(

8、min)(0uxxk)(Lku正交，即和且余量kkkkLrSx 0),(urk)(kLu)18.2(零，從而有沿任一方向?qū)?shù)必須為在極小點(diǎn)，因此上的在為二次函數(shù)表明，必要性。式證明：kkkxxSxx)()()17. 2() 1 (0),(),(uruxgradkk)(kLu 令充分性。任取,)2(kSxkkkkuxxuxxxxx00,于是則其中,kkkkuuxLuu),(21),()()(kkkkkxAxxrxx得由)18.2(0),(),(),(kkkkkururxr。證畢。故有正定，又因)()(,0),(kkkxxxAxA要結(jié)論：可得到共軛梯度法的重由定理23定理 。滿足式列由共軛梯度法得

9、到的點(diǎn))17. 2(kx正交。事實(shí)上有和且余量只需證明證明：由定理kkkkLrSx 2kikiikkkkkkkkkSpxppxpxx10011222111有因?yàn)閷?duì)任意, 1, 1 , 0kj0)()()()(),(001000000100100rprpAprprpbAxprprprpApprpApprpAprpbAxpprTjTjijiiTjTjjTjTjjTjTjjTjjTjiTjkiiTjikiiTjkTjjk正交。證畢。和所以kkLr4定理的解。步便得到方程組共軛梯度法至多進(jìn)行)11. 2(n因此無(wú)關(guān)，共軛向量系，必為線性為非零的而知和定理證明：由定理Apppniprnin110,),1

10、, 1 , 0(0),(320bAxrnn的解。證畢。一定是方程組故)11. 2(nx2.3共軛梯度法的計(jì)算公式n下面引見(jiàn)共軛梯度法一種生成A共軛向量系 的詳細(xì)方法。n 對(duì)恣意初始向量 ,取第一個(gè)搜索方向 為n由式(2.15)計(jì)算 :n再計(jì)算 。 ip0 x)(000bAxrp0p1x000000001AppprpxxTTbAxr11。方向張成的空間中搜索、于是可在因此而1010101,prrrrprn令0010011prrrp共軛，則為與要使App100)(000101ApprAppTT從而得到),/(),(00010AppApr:)15. 2(2x計(jì)算再由式111111112Appprpx

11、xTT再計(jì)算bAxr22令1122prp共軛，必須為與要使App210)(111212ApprAppTT從而得到),/(),(11121AppApr算依此類推，一般地，計(jì)bAxrkk11否則，令的解，停止計(jì)算為方程組則若;)11. 2(, 011kkxrkkkkprp11共軛，必須為與要使Appkk 1),/(),(1kkkkkAppApr的計(jì)算公式：這樣便得到共軛梯度法，取給定初始近似向量0 x)(000bAxrp計(jì)算對(duì)于, 2 , 1 , 0kkkkkkkkkkkkkkkkkkkkTkkTkkprpAppAprAprbAxrpxxApppr111111),/(),(的解，停止計(jì)算。為方程組

12、則計(jì)算過(guò)程中，若)11. 2(, 011kkxr例題 2 0 1 x1 3 0 1 0 x2 = 1 1 0 2 x3 3解：取初始近似，則Tx)0 , 0 , 0(0TbAxr)3, 1, 3(00Trp)3 , 1 , 3(00計(jì)算得對(duì)于, 0k55,)9 , 1 , 9(000AppApTT因此TTTpxxApppr) 3 , 1 , 3(5519,5519-000100000TTprpAppAprAprbAxr) 1,18, 1(551145572),/(),() 1 , 6, 1 (5562001120001000011計(jì)算得對(duì)于, 1k323112155196,) 1, 6 , 1(551918AppApTT因此TTTpxxApppr) 1 , 1 , 1 (19355-111211111，022bAxr。組的解故兩次迭代變得到方程Tx) 1 , 1 , 1 (23.共軛梯度法的特點(diǎn)n建立在二次模型上，具有二次終止性n(2) 一種有效的算法，