第7章共軛梯度法

1、Chater 7 最優(yōu)化方法與最優(yōu)化方法與共軛梯度法共軛梯度法/*Optimization Method and Conjugate Gradient Method*/一、與一、與方程組等價的方程組等價的變分變分問題問題思思想想共軛梯度共軛梯度法是一種法是一種變分變分方法，將方法，將求解線性方程組求解線性方程組問題問題等價等價轉(zhuǎn)化為一個轉(zhuǎn)化為一個二次函數(shù)二次函數(shù)的的極小值極小值問題問題 。設(shè)設(shè) 為對稱為對稱正定正定矩陣，矩陣，()n nijAaR Axb 其中其中12(,) ;Tnxxxx 12(,)Tnbb bb 定義定義二次二次函數(shù)函數(shù):nRR 2( )TTxx Axx b 1112nnn

2、ijijjjijja x xb x 二次二次函數(shù)函數(shù) 的基本性質(zhì)的基本性質(zhì)：( )x 對對2,( )()nxRxAxb 設(shè)設(shè) 為為 的解，則的解，則Axb 1xA b ()(,)xAxx ，且對，且對 有有nxR 2( )()(, )(, )xxAx xAxx (,)Axx ( (),)A xxxx 7 1 .Th設(shè)設(shè) 對稱對稱正定正定，則，則 為為 的解的的解的Ax Axb 充要條件是充要條件是()min ( )nx Rxx 證明：證明： 必要性由上述性質(zhì)必要性由上述性質(zhì)易知，下證充分性：易知，下證充分性：定理定理7 7.1.1說明：求解方程組的解等價于求上述說明：求解方程組的解等價于求上述

3、二次二次函數(shù)的函數(shù)的最小值最小值。常用方法：。常用方法：迭代迭代解法解法()min ( )nx Rxx 如果如果則由極值的必要條件得則由極值的必要條件得20()()xAxb Axb 20( )xA 二、二、最速下降最速下降法法/*Steepest Descent Method*/思思想想最速下降法最速下降法是指每次沿著函數(shù)值是指每次沿著函數(shù)值 下降最快下降最快的方向?qū)ふ业姆较驅(qū)ふ易钚≈迭c最小值點。 而函數(shù)值而函數(shù)值下降最快下降最快的方向是函數(shù)的的方向是函數(shù)的負梯度負梯度方向方向 幾何幾何意義：意義：等值線等值線 x 0( )x 最速下降最速下降法的實現(xiàn)過程法的實現(xiàn)過程選取初始向量選取初始向量

4、，由，由二次二次函數(shù)函數(shù) 的基本性質(zhì)的基本性質(zhì)0( )x( )x 00( )( )()xbAx 0( )r 如果如果 ，則，則 就是方程組的解；就是方程組的解；00( )r 0( )x如果如果 ，則沿，則沿 方向進行方向進行一維極小一維極小搜索：搜索：00( )r 0( )r求求步長步長 ，使得，使得 00( )( )min()xr 000( )( )()dxrd 0000002( )( )( )( )( )( )()()()TTxrA xrbxr 00000( )( )( )( )(,)(,)rrArr 2000020( )( )( )( )()(,)dxrArrd 注意到注意到00000(

5、 )( )( )( )min ()()xrxr 1000( )( )( )xxr 令令 ，從而完成第一次迭代。，從而完成第一次迭代。下面以下面以 為為新新的初值，的初值，重復重復上述過程。上述過程。1( )x 最速下降最速下降法的算法法的算法選取初值選取初值0( )nxR For k=0,1,2,( )( )kkrbAx ( )( )( )( )(,)(,)kkkkkrrArr 1()( )( )kkkkxxr 如果如果 ，停止停止( )kr 否則，進行下一次循環(huán)否則，進行下一次循環(huán)10()( )(,)kkrr 搜索方向是搜索方向是正交正交的：的：11()()kkrbAx( )( )()kkk

6、bA xr ( )( )kkkrAr 缺陷：收斂速度缺陷：收斂速度慢慢設(shè)設(shè) 的特征值為的特征值為 , ,A10n 則由前述最速下降算法產(chǎn)生的序列則由前述最速下降算法產(chǎn)生的序列 滿足滿足其中其中 。1xA b ( )kx( )(0)11kknAAnxxxx 7.2Th上述定理說明，當上述定理說明，當 時最速下降法收斂非常慢。時最速下降法收斂非常慢。1n三、三、共軛梯度共軛梯度法法/*Conjugate-Gradient Method*/設(shè)設(shè) 為對稱為對稱正定正定矩陣，矩陣，()n nijAaR Axb 其中其中12(,) ;Tnxxxx 12(,)Tnbb bb 思思想想Def設(shè)設(shè) 為對稱為對稱

7、正定正定矩陣，若矩陣，若 中向量組中向量組n nAR 01( )( )( ),lpppnR滿足滿足0( )( )(,)ijAppij 則稱它是則稱它是 中的一個中的一個 共軛共軛（ 正交正交）向量組。）向量組。nRA A 利用利用一維極小一維極小搜索方法確定一組搜索方法確定一組 共軛共軛方向方向A 代替代替最速下降最速下降法中的法中的正交正交方向來進行迭代。方向來進行迭代。 共軛梯度共軛梯度法的實現(xiàn)過程法的實現(xiàn)過程選取初始向量選取初始向量 ， ，0( )x00( )( )pr 00000( )( )( )( )( )(,)(,)rrApp 100110( )( )( )( )( ),xxprb

8、Ax 如何確定下一個搜索方向呢？如何確定下一個搜索方向呢？在過點在過點 的由向量的由向量 和和 所張成的下列二維平所張成的下列二維平面內(nèi)找出函數(shù)值下降最快的方向作為搜索方向面內(nèi)找出函數(shù)值下降最快的方向作為搜索方向1( )x1( )r0( )p1( )p (1)(1)(0)2: ,xxrpR 2 (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)2TTxrpxrpA xrpbxrp ( , ) (1)(1)(1)(0)(1)(1)

9、(1)(0)(0)(0)2020TTTTTrArrAprrrAppAp 由極值的必要條件得由極值的必要條件得(1)(1)(0)00 xxrp其中其中 滿足滿足00, (1)(1)(1)(0)(1)(1)00(1)(0)(0)(0)000TTTTTrArrAprrrAppAp 取下一個搜索方向為取下一個搜索方向為(1)(1)(1)(0)0001()pxxrp 11111( )( )( )( )(,)(,)rpApp 沿該方向進行一維搜索得步長為沿該方向進行一維搜索得步長為記記(1)(0)00(0)(0)0(,)(,)ArpApp (2)(1)(1)1xxp (1)(1)(0)0prp 下面以下面

10、以 為為新新的迭代值，的迭代值，重復重復上述過程即可。上述過程即可。2( )x( )( )( )( )(1)( )( )(1)(1)(1)( )( )( )(1)(1)( )k Tkkk TkkkkkkkkTkkk TkkkkkrppApxxprbAxrAppApprp 一般地，設(shè)已經(jīng)得到一般地，設(shè)已經(jīng)得到 ，則第，則第k+1步迭代的計算公式為步迭代的計算公式為( )kp終止條件：終止條件：(1)0kr 同時注意到同時注意到11( )( )( )( )()( )( )(,)(,)(,)kkkkkkkkrprrprr 11()( )()( )(,)(,)kkkkrpbAxp0( )( )( )(

11、 )(,)(,)kkkkkrpApp ( )( )( )( )(,)(,)kkkkkrrApp 1()( )( )( )(,)(,)kkkkkrAppAp 111()( )()( )( )(,()(,)kkkkkkrrrpAp 111()()( )( )(,)(,)kkkkkrrpAp 11()()( )( )(,)(,)kkkkkrrrr 共軛梯度共軛梯度法的算法法的算法選取初值選取初值0( )nxR For k=0 , 1 , 2 , , n00( )( )pr 00( )( )rbAx 計算計算計算計算( )( )( )( )(,)(,)kkkkkrrApp 1()( )( )kkkkx

12、xp 1()( )( )kkkkrrAp 11()()( )( )(,)(,)kkkkkrrrr 11()()( )kkkkprp 如果如果 ，停止停止10()kr 否則，計算否則，計算進行下一次迭代進行下一次迭代7 3 .Th由由共軛梯度共軛梯度法得到的法得到的 滿足性質(zhì)：滿足性質(zhì)： 0 0( )( ),jirpijk ( )( ),iirp 00( )( ),jirriji jk 00( )( ),jiAppiji jk (0)( )(0)( )(0)(0)(0)(0),1,kkkspan rrspan ppA rkspan rArA r Krylov ( (克雷洛夫克雷洛夫) )子空間子

13、空間定理定理7.3表明：向量組表明：向量組 和和 分別是分別是Krylov子空間的正交基和子空間的正交基和共軛共軛正交基。因此，共軛正交基。因此，共軛梯度法最多用梯度法最多用n步便可得到方程組的精確解。步便可得到方程組的精確解。01( )( )( ),krrr01( )( )( ), ,kppp由由共軛梯度共軛梯度法計算得到的法計算得到的 近似解滿足近似解滿足( )kx54 .Th ( )(0)(0)min:,kxxxxA rk 或或 ( )(0)(0)min:,kAAxxxxxxA rk 解：解：易驗證系數(shù)矩陣是對稱正定的易驗證系數(shù)矩陣是對稱正定的. .例：例：用用CG迭代法求解下列方程組迭代法求解下列方程組:21211x2x 300100133x0000( )()Tx Step1計算計算0003 1 3( )( )( )()TprbAx 000001955( )( )( )( )(,)(,)rrApp 100019