25-共軛梯度法PPT課件(43頁P(yáng)PT)

1、預(yù)備知識(shí)最速下降法共軛梯度法數(shù)值試驗(yàn)算例*2.5 共軛梯度法1第1頁，共43頁。標(biāo)題添加點(diǎn)擊此處輸入相關(guān)文本內(nèi)容點(diǎn)擊此處輸入相關(guān)文本內(nèi)容總體概述點(diǎn)擊此處輸入相關(guān)文本內(nèi)容標(biāo)題添加點(diǎn)擊此處輸入相關(guān)文本內(nèi)容2第2頁，共43頁。( 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設(shè)A是 n 階對(duì)稱正定陣( Ax, y ) = ( x, Ay ) ;( Ax，x ) 0, 且( Ax, x) = 0 x = 0 2

2、/16預(yù)備知識(shí)：內(nèi)積的定義II 極值問題: 設(shè) , 記 ( x , y) = xT y3第3頁，共43頁。預(yù)備知識(shí) 梯度:*Hessian矩陣:4第4頁，共43頁。預(yù)備知識(shí) *5第5頁，共43頁。費(fèi)馬引理:*注釋: 費(fèi)馬引理的價(jià)值在于將極值問題轉(zhuǎn)化為方程的求解問題。6第6頁，共43頁。初等變分原理一、與方程組等價(jià)的二次泛函問題思想共軛梯度法將求解方程組問題等價(jià)轉(zhuǎn)化為一個(gè)二次 泛函的極值問題。 定義二次函數(shù)設(shè) 為對(duì)稱正定矩陣，其中7第7頁，共43頁。定理(初等變分原理) 設(shè)A =(aij )nn為實(shí)對(duì)稱正定矩陣, ，則 x是二次函數(shù) 的極小值點(diǎn) x 是線性方程組 Ax = b 的解。 *8第8頁

3、，共43頁。該性質(zhì)說明：求解方程組的解等價(jià)于求上述二次函數(shù)的最小值。若則由極值的必要條件得迭代法構(gòu)造思想：構(gòu)造 使得9第9頁，共43頁。從瞎子下山到最優(yōu)化方法*Science of Better10第10頁，共43頁。瞎子與計(jì)算機(jī)瞎子: 能感覺到腳下的坡度(這是海拔函數(shù)在當(dāng)前點(diǎn)的梯度值),但不知道山上其它點(diǎn)的任何情況計(jì)算機(jī): 計(jì)算目標(biāo)函數(shù)在該點(diǎn)的信息(如函數(shù)值和梯度值), 但不知道其它點(diǎn)的信息 *11第11頁，共43頁。2.5.2 最速下降法幾何意義：等值線思想最速下降法是指每次沿著函數(shù)值 下降最快的方向?qū)ふ易钚≈迭c(diǎn)。 而函數(shù)值下降最快的方向是函數(shù)的負(fù)梯度方向12第12頁，共43頁。最速下降法

4、實(shí)現(xiàn)過程：選取初始向量 ，由二次函數(shù) 的基本性質(zhì)如果 ，則 就是方程組的解；如果 ，則沿 方向進(jìn)行一維極小搜索：求 使得 達(dá)到最小值, 則13第13頁，共43頁。注意到令 ，從而完成第一次迭代。下面以 為新的初值，重復(fù)上述過程。14第14頁，共43頁。最速下降法的算法:選取初值For k=0,1,2,若 ，停止否則，進(jìn)行下一次循環(huán)搜索方向是正交的：缺陷：收斂速度慢！收斂速度？15第15頁，共43頁。解：易驗(yàn)證系數(shù)矩陣是對(duì)稱正定的.例：用最速下降法求解方程組:3xStep1計(jì)算16第16頁，共43頁。最好 + 最好 = 最好 ?方向(最速下降) (best rk)步長(精確搜索) (best )

5、 是否最好 ?*17第17頁，共43頁。設(shè) 的特征值為 ,則由前述最速下降算法產(chǎn)生的序列 滿足其中 。上述定理說明，當(dāng) 時(shí)最速下降法收斂非常慢。18第18頁，共43頁。19第19頁，共43頁。f(x1,x2)=100 x12+x22最速下降法*20第20頁，共43頁。f(x1,x2)=100 x12+x22Barzilai-Borwein方法*21第21頁，共43頁。 最速下降法思想簡單,但是收斂速度慢。本質(zhì)上是因?yàn)樨?fù)梯度方向函數(shù)下降快是局部性質(zhì)。全局思想:局部思想: N 維空間的任意向量可以由N個(gè)線性無關(guān)的向量線性表示。*22第22頁，共43頁。3、共軛梯度法/*Conjugate-Grad

6、ient Method*/共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化最有效的算法之一。Hestenes和Stiefle（1952）提出來的，用于解正定系數(shù)矩陣的線性方程組，F(xiàn)letcher和Reeves（1964）首先提出了解非線性最優(yōu)化問題的共軛梯度法。由于共軛梯度法不需要矩陣存儲(chǔ)，且有較快的收斂速度和二次終止性等優(yōu)點(diǎn)，現(xiàn)在共軛梯度法已經(jīng)廣泛地應(yīng)用與實(shí)際問題，已經(jīng)成為求解大型稀疏線性方程組最受歡迎的一類方法。23第23頁，共43頁。* 共軛梯度法的關(guān)鍵是構(gòu)造一組兩兩共軛的方向(即一組線性無關(guān)向量)。巧妙的是, 共軛方向可以由上次搜索方向和當(dāng)前的梯度方向之組合來

7、產(chǎn)生。pk+1 := rk+1 + tau*pk The Best of the 20th Century: Editors Name Top 10 Algorithms, SIAM News 現(xiàn)代迭代方法: Krylov子空間方法24第24頁，共43頁。共軛方向和共軛方向法共軛是正交的推廣！25第25頁，共43頁。選取初始向量 ， 共軛梯度法如何確定下一個(gè)搜索方向呢？26第26頁，共43頁。共軛梯度法的實(shí)現(xiàn)過程選取初始向量 ， 確定下一個(gè)搜索方向：由過點(diǎn) 向量 和 所張成的下列二維平面內(nèi)找出函數(shù)值下降最快的方向作為搜索方向27第27頁，共43頁。、 和 的幾何意義此時(shí) 在 上可表示為28第2

8、8頁，共43頁。由極值的必要條件得其中 滿足29第29頁，共43頁。取下一個(gè)搜索方向?yàn)檠卦摲较蜻M(jìn)行一維搜索得步長為記下面以 為新的迭代值，重復(fù)上述過程即可30第30頁，共43頁。共軛梯度法的算法選取初值For k=0 , 1 , 2 , , n計(jì)算計(jì)算如果 ，停止否則，計(jì)算進(jìn)行下一次迭代31第31頁，共43頁。共軛梯度法的算法選取初值For k=0 , 1 , 2 , , n計(jì)算計(jì)算如果 ，停止否則，計(jì)算進(jìn)行下一次迭代32第32頁，共43頁。解：易驗(yàn)證系數(shù)矩陣是對(duì)稱正定的.例：用CG迭代法求解下列方程組:3xStep1計(jì)算33第33頁，共43頁。Step2計(jì)算迭代結(jié)束34第34頁，共43頁。由

9、共軛梯度法計(jì)算得到的 近似解滿足或35第35頁，共43頁?？偨Y(jié):*36第36頁，共43頁。矩陣分解(1)特征值分解: A=CDCT, 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) 非負(fù)矩陣分解Non-negative Matrix Factorization A=WH37第37頁，共43頁。*迭代法構(gòu)造收斂條件中止準(zhǔn)則古典迭代法統(tǒng)一不動(dòng)點(diǎn)框架38第38頁，共43頁。* 共軛梯度法的關(guān)鍵是構(gòu)造一組兩兩共軛的方向(即一組線性無關(guān)向量)。巧妙的是, 共軛方向可以由上次搜索方向和當(dāng)前的梯度方法之組合來產(chǎn)生。pk+1 := rk+1 + tau*pk 現(xiàn)代迭代方法: 共軛梯度方法The Best of the 20th Century: Editors Name Top 10 Algorithms, SIAM News 最速下降法思想簡單,但收斂速度慢。本質(zhì)上因?yàn)樨?fù)梯度方向函數(shù)下降快是局部性質(zhì)。39第39頁，共43頁。算例140第40頁，共43頁。問題提問與解答問答HERE COMES THE QUESTION AND ANSWER S