解正定線性方程組的CG方法省公開課一等獎全國示范課微課金獎

求解正定線性方程組共軛梯度法（CG方法）

林華堂、張卜元、呂迪第1頁1.方法介紹共軛梯度法已經(jīng)有五十多年歷史,它最早是由Hestenes和Stiefel于1952年在求解線性方程組時提出,并由Fletcher和Reeves于1964年推廣到非線性優(yōu)化領(lǐng)域.后,Beale,Powell,Fletcher等著名優(yōu)化教授對非線性共軛梯度法進行了深入研究,取得了十分優(yōu)異結(jié)果.但幾乎同時間世擬牛頓方法因為其良好計算表現(xiàn)以及豐富收斂性分析很快受到了青睞,從而在很長一段時間里共軛梯度法被研究者所忽略.近年來,伴隨計算機飛速發(fā)展以及實際問題需要,大規(guī)模優(yōu)化問題越來越受到重視,而共軛梯度法正是求解大規(guī)模問題一個主要方法.于是,共軛梯度法理論研究又受到人們關(guān)注.

第2頁第3頁第4頁

共軛梯度法（ConjugateGradient）是介于最速下降法與牛頓法之間一個方法，它僅需利用一階導(dǎo)數(shù)信息，但克服了最速下降法收斂慢缺點，又防止了牛頓法需要存放和計算Hesse矩陣并求逆缺點，共軛梯度法不但是處理大型線性方程組最有用方法之一，也是解大型非線性最優(yōu)化最有效算法之一。在各種優(yōu)化算法中，共軛梯度法是非常主要一個。其優(yōu)點是所需存放量小，含有步收斂性，穩(wěn)定性高，而且不需要任何外來參數(shù)。第5頁2.方法理論與描述CG方法，它是一個極小化方法，對應(yīng)于求一個二次函數(shù)極值。為了引出CG方法，下面介紹一些理論。2.1與方程組等價變分問題

（2.11）第6頁則函數(shù)有以下性質(zhì)：（1）對一切，有（2.12）（2）對一切,有（2.13）第7頁（3）設(shè)為方程組（2.11）解，則對一切，有（2.14）則第8頁定理1

設(shè)A對稱正定，則為方程組（2.11）解充分必要條件是滿足證實：設(shè)為方程組（2.11）解，由式（2.14）及A正定性，有。反之，若有使到達最小，則故由式（2.14）可知又因A正定，所以。證畢。

由上述定理，求解線性方程組等價于求解變分問題，即求最小。求解方法普通是結(jié)構(gòu)一個向量序列｛｝,使。第9頁2.2共軛梯度（CG）法定義設(shè)是任意給定一個初始點，從點出發(fā)沿某一要求方向，求函數(shù)在直線上極小點，設(shè)求得極小點為。再從點出發(fā)沿某一要求方向，求函數(shù)在直線上極小點，設(shè)求得極小點為。如此繼續(xù)下去，普通地，從點出發(fā)沿某一要求方向，求函數(shù)在直線第10頁上極小點。稱為搜索方向。命題2對于已知上極小點為式中證實：記，欲確定系數(shù)使得一元函數(shù)時為極小。由式(2.13)得

第11頁第12頁注2在命題2中，余量命題2所得迭代公式（2.15）含有下降性第13頁假如搜索方向為中一個A共軛向量系，即有性質(zhì)（2.16）向量系，則稱迭代法（2.15）為共軛梯度法（CG法）。用表示線性無關(guān)向量系張成子空間，即令第14頁定理2從任意一點出發(fā)，得到點序列（2.17）充分必要條件是第15頁第16頁第17頁第18頁2.3共軛梯度法計算公式下面介紹共軛梯度法一個生成A共軛向量系詳細方法。對任意初始向量,取第一個搜索方向為由式(2.15)計算:再計算。第19頁令第20頁第21頁第22頁例題

201x13010x2=1102x33解：取初始近似第23頁第24頁3.共軛梯度法特點建立在二次模型上，含有二次終止性．(2)一個有效算法，克服了最速下降法鋸齒現(xiàn)象，又防止了牛頓法計算量大和局部收斂性缺點．(3)算法簡