工程數(shù)學(xué)(10)解線性方程組的極小化方法

1、工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)第六節(jié)第六節(jié) 極小化方法極小化方法一、與線性方程組等價(jià)的變分問(wèn)題一、與線性方程組等價(jià)的變分問(wèn)題三、共軛斜量法三、共軛斜量法(共軛梯度法共軛梯度法)四、預(yù)條件共軛斜量法四、預(yù)條件共軛斜量法二、最速下降法二、最速下降法工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)一、與線性方程組等價(jià)的變分問(wèn)題一、與線性方程組等價(jià)的變分問(wèn)題12121(),(,.,) ,(,.,)n nTTijnnAAxbAaRxxxxbb bb 設(shè)設(shè)對(duì)對(duì)稱稱正正定定，求求解解的的線線性性方方程程組組為為（ ）其其中中111(,)( ,)2n nnnnijijiiijiRRxAx xb xa x xb x 對(duì)對(duì)應(yīng)應(yīng)

2、的的二二次次函函數(shù)數(shù) : : ，稱稱為為模模函函數(shù)數(shù)，定定義義為為1 11 1 ( ( ) )= =（ ）2 22 2221212124,10(64)(410bxxxxxxx 1 12 2設(shè)設(shè) A A = =2 26 61 1( ( ) )= =例例2 2：）工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)13nxRxxAx br 有有如如下下性性質(zhì)質(zhì)：（ ）對(duì)對(duì)一一切切，有有( ( ) )= =g gr ra ad d ( ( ) )= =- -（ ）11,1,2,.,( )nijjiijiTna xbrinxgradxAxbrxx 證證：221212124,10(64)(410Abxxxx xxx 1 1

3、2 2設(shè)設(shè) = =2 26 61 1( ( ) )例例= =2 2：）221212111062,42rxxxrxxx 111nnnijijiiijixa x xb x 1 1( () )2 2工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)22,1()(),)( ,)21(,)( ,)(,)( ,)(,)22( )(,)(,)42nx yRRxyA xyxyb xyAx xb xAx yb yAy yxAxb yAy y （2 2）對(duì)對(duì)一一切切（ ）(,)( ,)xAx xb x 1 1( ( ) )= =2 2工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)*,11( )()(,)( ,)(,)2211(,)(,)(,)2

4、21(),)52nxRxxAx xb xAxxAx xAxxAxxA xxxx 對(duì)對(duì)一一切切有有（ ）*1*1*11()( ,)(,)22xA bAxbxb A bAxx （3 3）設(shè)設(shè)= =為為的的解解, ,則則*(,)( ,)xAxxb x 1 1( () )= =2 2工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)*1*1*( )()min( )nxRAxA bAxbxxxA bxx 設(shè)設(shè) 對(duì)對(duì)稱稱正正定定，則則= =為為解解的的充充分分必必要要條條件件是是：是是二二次次函函數(shù)數(shù)的的極極小小值值點(diǎn)點(diǎn)，即即= =定定理理：*1*( )()0()( )( )nxA bAxxxxxRxx 必必要要性性：設(shè)設(shè)

5、= =，由由上上式式及及 的的正正定定性性，所所以以有有證證，即即使使達(dá)達(dá)明明：到到最最小小。*1( )()(),)2xxA xxxx*()()xxxxxAxbxAxb 充充 分分 性性 ： 若若使使取取 極極 小小 值值 ， 則則 有有g(shù) gr ra ad d= =- - = =0 0，即即是是 方方 程程 組組的的 解解 。xxx ( )=grad ( )=A -b工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué) ()()( )()min( )kkxxxx 求求二二次次函函數(shù)數(shù)極極小小值值點(diǎn)點(diǎn)的的一一般般方方法法是是：構(gòu)構(gòu)造造一一個(gè)個(gè)向向量量序序列列，使使(0)(1)()()()(12,(0,1,.)kk

6、kkkkxxxpk 可可以以采采取取以以下下方方法法：）任任取取一一個(gè)個(gè)初初始始向向量量，（ ）構(gòu)構(gòu)造造迭迭代代格格式式其其中中p p是是搜搜索索方方向向，是是搜搜索索步步長(zhǎng)長(zhǎng)，( )(1)( )( )( )( )*()()()()()min ( )nkkkkkkkkx Rxxpxxxx （3 3）選選擇擇p p和和使使得得則則當(dāng)當(dāng)k k時(shí)時(shí)，有有工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)( )(1)(4)kkxxx (k)(k)(k)(k)給給出出誤誤差差限限 ，直直到到 或 或 rb-Arb-A迭迭代代終終止止。工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)(1)()()(),(0,1,.)kkkkkkxxpk

7、對(duì)對(duì)迭迭代代格格式式關(guān)關(guān)鍵鍵是是要要確確定定搜搜索索方方向向p p和和搜搜索索步步長(zhǎng)長(zhǎng)。()()()kkkxxx （1 1）確確定定搜搜索索方方向向p p最最速速下下降降法法：p p取取為為模模函函數(shù)數(shù)( ( ) )減減少少最最快快的的方方向向，即即: : ( ( ) )的的負(fù)負(fù)梯梯度度方方向向- - g gr ra ad d( ( ( ( ) ) ). .共共軛軛斜斜量量法法：取取A A - - 共共軛軛方方向向p p。(1)( )( )( )( )( )(1)()()min ()()kkkkkkkkkkxxpxpx （2 2）確確定定搜搜索索步步長(zhǎng)長(zhǎng)確確定定使使得得從從k k步步到到k+1

8、k+1步步是是最最優(yōu)優(yōu)的的，即即：這這稱稱為為沿沿p p方方向向的的一一維維極極小小搜搜索索。是是局局部部極極小小。工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)( )(1)( )( )( )( )( )( )( )( )( )()()1( (),)( ,)2kkkkkkkkkkpFxxpA xpxpb xp 對(duì)對(duì)確確定定的的搜搜索索方方向向，構(gòu)構(gòu)造造一一個(gè)個(gè) 的的函函數(shù)數(shù)()()()()()()2()()2()()()()()2()()()()()1(,)( ,)(,)( ,)2(,)2()(,)(,)2()(,)(,)2kkkkkkkkkkkkkkkkkkAxxb xAxpb pAppxAxb pApp

9、xrpApp ()()()()()0,(,)(,)0kkkkFrpApp 令令即即：工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)()()()()()()(,)(,)kkkkkkkkkrpxpApp 取取，是是 ( () )下下降降的的極極小小值值點(diǎn)點(diǎn)，即即是是k kk k+ +1 1步步的的最最優(yōu)優(yōu)步步長(zhǎng)長(zhǎng)。( )( )( )( )(,)(,)kkkkrpApp 得得()()()(,)0,()kkFAppA 正正定定()()()()()(,)(,)kkkkFrpApp 工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)二、最速下降法二、最速下降法).()(,)(,)()()(,)()0()0()0()0(xxxxnAxxx

10、xx 負(fù)梯度方向負(fù)梯度方向球面的球面的這就是正交于橢這就是正交于橢減小最快的方向減小最快的方向出發(fā)先找一個(gè)使出發(fā)先找一個(gè)使從從維空間的一個(gè)橢球面維空間的一個(gè)橢球面它是它是正定正定因?yàn)橐驗(yàn)榈牡戎得娴牡戎得媸鞘堑臉O小點(diǎn)的極小點(diǎn)出發(fā)尋找出發(fā)尋找從從xxxpxr ( (k k) )( (k k) )( (k k) )取取 模模 函函 數(shù)數(shù)( ( ) )減減 少少 最最 快快 的的 方方 向向 ，即即 : : ( ( ) )的的 負(fù)負(fù) 梯梯 度度 方方 向向 - - g gr ra ad d( ( ( ( ) ) )，- - g gr ra ad d( ( ( () ) )= =最最 速速 下下 降降

11、法法 ：p( (k k) )工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)clear;x=-18:0.5:18;y=x;X=ones(size(y)*x;Y=y*ones(size(x);Z=0.5*(X.2+6*Y.2+4*X.*Y)-(4*X+10*Y);meshc(Z);colormap(hot) xlabel(x),ylabel(y),zlabel(z) *x221212124,10(64)(4102*m in*1bxxxx xxxxxx 1 12 2例例 ： 設(shè)設(shè) A A= =2 26 61 1( () )= =）2 2( () )= =( () )= =- -9 9, ,工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)

12、工程數(shù)學(xué)(0)()()()()()()(1)()()(1)()0,1,2,.(,)(,)(3)nkkkkkkkkkkkkkxRkrbAxrrArrxxrxx 最最速速下下降降算算法法：( (1 1) )選選取取( (2 2) )對(duì)對(duì)當(dāng)當(dāng)時(shí)時(shí)，終終止止迭迭代代。(1)()06kkrr 不不難難驗(yàn)驗(yàn)證證，相相鄰鄰兩兩次次的的搜搜索索方方向向是是正正交交的的，即即（，）（ ）( )( )( )( )(,)(,)kkkkrpApp得工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué) ()1()(0)11112*,(,)kkknAAnnAxxxA bxxxxuAu u ( (k k) )k k容容易易看看到到， ( ()

13、 ) 是是單單調(diào)調(diào)下下降降有有界界序序列列，它它存存在在極極限限，可可以以證證明明l li im m而而且且其其中中分分別別是是對(duì)對(duì)稱稱正正定定陣陣A A的的最最大大、最最小小特特征征值值，1( )nkr當(dāng)當(dāng)時(shí)時(shí)，收收斂斂是是很很慢慢的的，當(dāng)當(dāng)很很小小時(shí)時(shí)，因因舍舍入入誤誤差差的的影影響響，計(jì)計(jì)算算將將出出現(xiàn)現(xiàn)不不穩(wěn)穩(wěn)定定現(xiàn)現(xiàn)象象。工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)三、共軛斜量法三、共軛斜量法 (CG) (共軛梯度法共軛梯度法) (0)(1)(1)()()()()min()kkkkkpppxpxp 設(shè)設(shè)按按方方向向, , , . . . . . . , ,已已進(jìn)進(jìn)行行k k次次一一維維搜搜索索，

14、求求得得，下下一一步步就就是是確確定定，再再求求解解一一維維極極小小化化問(wèn)問(wèn)題題()()()()(,)7(,)kkkkkrpApp 可可得得（ ）(1)( )( )(1)(1)( )( )(8)(9)kkkkkkkkkxxprbAxrAp 下下一一個(gè)個(gè)近近似似解解和和對(duì)對(duì)應(yīng)應(yīng)的的剩剩余余向向量量是是(0)(1)(0)(1)( )01kkkxxppp 不不失失一一般般性性地地設(shè)設(shè)=0=0，反反復(fù)復(fù)利利用用（8 8）有有+.+.+工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)(0)(1)pp現(xiàn)現(xiàn)在在考考慮慮, . . . 取, . . . 取什什么么方方向向(0)(0)( )kprp 設(shè)設(shè)= =，一一般般k1k

15、1時(shí)時(shí)的的確確定定，我我們們不不但但希希望望使使(1)( )( )()min ()(10)kkkxxp (0)()( )(1),.,()min( )(11)kkkx span pppxx 而而且且希希望望的的選選擇擇使使 (0)( )( )(0)(1),.,.,kkkxspan ppxypyspan ppR 若若，可可記記成成( )( )2( )( )( )(,)( )()( )( ,)(,)(12)2kkkkkxypyb pAy pApp 所所以以有有,y 為為了了把把極極小小化化問(wèn)問(wèn)題題分分離離為為對(duì)對(duì) 和和對(duì)對(duì)分分別別求求極極小小 令令工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué) ( )(0)(1)

16、( )( ),)0,.,)0,0,1,.,1kkjkAy pyspan ppAppjk 令令（即即（ ( )(0)( )( )( ),.,)0,klijpppAppijn nn n如如果果k=1,2,.k=1,2,.，每每步步都都如如此此選選擇擇，則則它它們們符符合合下下面面定定義義. .A A對(duì)對(duì)稱稱正正定定，若若R R 中中向向量量組組滿滿足足（則則稱稱它它為為R R 中中的的一一個(gè)個(gè)A A共共軛軛向向量量組組，或或稱稱A A定定義義正正交交向向量量組組。 1 1、當(dāng)當(dāng)lnln時(shí)時(shí)，不不含含零零向向量量的的A A共共軛軛向向量量組組線線性性無(wú)無(wú)關(guān)關(guān)；2 2、當(dāng)當(dāng)A=IA=I時(shí)時(shí)，A A共共

17、軛軛性性質(zhì)質(zhì)就就是是一一般般的的正正交交性性；3 3、給給了了一一組組線線性性無(wú)無(wú)關(guān)關(guān)的的向向量量，可可以以按按SchmidtSchmidt正正交交化化的的方方法法得得到到對(duì)對(duì)應(yīng)應(yīng)的的A A共共注注：軛軛向向量量組組。工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)將將極極小小問(wèn)問(wèn)題題（1111）分分離離為為兩兩個(gè)個(gè)極極小小問(wèn)問(wèn)題題: : (0)(1)(0)(1)( )( ),.,.()min( )(11)kkky span ppppxxy 取取是是A A共共軛軛的的，設(shè)設(shè)已已是是前前一一步步極極小小問(wèn)問(wèn)題題的的解解，即即 (0)( )(1),.,()min( )kkx span ppxx 2( )( )(

18、)( )( )()( )( ,)(,)2kkkkxypyb pApp 由由（1 12 2）， ( )( )(0)(1),)0,.,kkkpAy pyspan pp 而而使使（ (0)()(0)(1)( ),.,2( )( )( ),.,min( )min ()min( )min(,)( ,)2kkkyx span ppkkky span ppxypyAppb p 工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué) ( )(0)(1)( )( ),.,)0,kkkkxspan ppAxp , ,故故（( )( )( )( )( ,),(,)kkkkkb pxApp第第一一問(wèn)問(wèn)題題的的解解為為第第二二問(wèn)問(wèn)題題的的解

19、解為為。( )( )( )( )( )( )( )( )( )( )( )( )( ,)(,)(,)( ,)(,)7(,)(,)kkkkkkkkkkkkkb pbAxprpb prpAppApp與與（ ）相相同同工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)( ):kp計(jì)計(jì)算算(0)(0)( )(0)(1)( )( )(1)( )( )(1)1,.,(13)kkkkkkkkkprpppAprpprp 取取= =，就就取取為為與與共共軛軛的的向向量量，這這樣樣的的向向量量不不是是唯唯一一的的，CGCG法法中中取取為為與與的的線線性性組組合合，設(shè)設(shè)( )(1)( )(1)(1)1( )(1)(1)(1)1( )

20、(1)1(1)(1)(,)(,)(,)(,)0(,)(14)(,)kkkkkkkkkkkkkkkkpAprpAprAppAprAppAp 利利用用，可可得得 ( )kpA 可可以以證證明明這這樣樣得得到到的的向向量量序序列列是是一一個(gè)個(gè)共共軛軛向向量量組組. .工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)公式化簡(jiǎn)公式化簡(jiǎn)( )( )(1)( )( )( )( )(1)( )( )( )( )( )(,)7(,)kkkkkkkkkkkkkkkkrprrApApprprpApp 由由（9 9）式式和和（ ）有有（，）（，）（，）=0=0( )( )( )( )(1)( )( )115kkkkkkkkrprrp

21、rr （，）（，）（，）（ ）()()()()()()()()()(,)(,)716(,)(,)00.kkkkkkkkkkkrprrAppAppr 代代回回（ ）有有（）當(dāng)當(dāng)時(shí)時(shí)， ( )( )( )( )( )( )()(,)0,(,)(,)0,ijijijkrrijApppApijpA 由由（7 7）（1 16 6）定定義義的的算算法法有有如如下下性性質(zhì)質(zhì)（1 1）。即即剩剩余余向向量量構(gòu)構(gòu)成成一一個(gè)個(gè)正正交交向向量量組組。（2 2）。即即為為一一個(gè)個(gè)共共軛軛定定理理向向量量組組。工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)公式化簡(jiǎn)公式化簡(jiǎn)(1)1( )(1)(1)( )( )( )( )( )(,(

22、)(,)(,)(,)kkkkkkkkkkkrrrrAppAppAp 1(1)(1)(1)(1)( )( )( )( )(,)(,)(,)(,)kkkkkkkkkrrrrpAprr (1)00.kkr 當(dāng)當(dāng)時(shí)時(shí)，工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)(0)()(0)(0)(0)(0)()()()()(1)()()(1)()()(1)(1)()()(1)(1)():(1)(2),(3)0,1,.,(,)(,)(,)(,)nkkkkkkkkkkkkkkkkkkkkkkCGxRrbAxprkrrAppxxprrAprrrrprp 算算法法，()*.kxx (k)(k)(k)在計(jì)算過(guò)程中，若遇r=0，或(p,

23、Ap)=0時(shí)，計(jì)算終止,工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)()*.kxx n n( (0 0) )( (1 1) )( (n n) )( (k k) )( (1 1) ) 剩剩余余向向量量相相互互正正交交，而而R R 中中至至多多有有n n個(gè)個(gè)相相互互正正交交的的非非零零向向量量，所所以以r r, ,r r, ,. . . ., ,r r 中中至至少少有有一一個(gè)個(gè)向向量量為為零零。若若r r= =0 0，則則注注：()(0).nxx ( (0 0) )( (1 1) )( (n n- -1 1) )( (2 2) )實(shí)實(shí)際際計(jì)計(jì)算算中中，由由于于舍舍入入誤誤差差的的影影響響，n n步步內(nèi)內(nèi)得得不

24、不到到準(zhǔn)準(zhǔn)確確解解，故故還還需需繼繼續(xù)續(xù)迭迭代代。一一般般因因p p, ,p p, ,. . . ., ,p p是是一一組組A A- -共共軛軛向向量量組組，繼繼續(xù)續(xù)迭迭代代時(shí)時(shí)，要要取取2()(0)2()1*2*()1kkAAcond Axxxxcond A ( (3 3) )由由誤誤差差估估計(jì)計(jì)式式當(dāng)當(dāng)A A的的條條件件數(shù)數(shù)很很小小時(shí)時(shí)，共共軛軛斜斜量量法法收收斂斂很很快快，但但當(dāng)當(dāng)A A是是病病態(tài)態(tài)嚴(yán)嚴(yán)重重的的矩矩陣陣時(shí)時(shí)，共共軛軛斜斜量量法法收收斂斂速速度度很很慢慢。可可采采用用預(yù)預(yù)處處理理技技術(shù)術(shù)，降降低低A A的的條條件件數(shù)數(shù)。工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)四、預(yù)條件共軛斜量法四

25、、預(yù)條件共軛斜量法(PCG)- -1 1- -T T尋尋找找一一個(gè)個(gè)非非奇奇異異矩矩陣陣C C，使使A A= =C C A AC C 的的條條件件數(shù)數(shù)比比原原系系數(shù)數(shù)矩矩陣陣A A的的條條件件數(shù)數(shù)得得到到改改善善. .1111,TTTTAxbCACC xC bAxbACACbC b xC x其其中中，1TCCxb 2 2令令M M= =稱稱為為預(yù)預(yù)優(yōu)優(yōu)矩矩陣陣，當(dāng)當(dāng)M M接接近近A A時(shí)時(shí)， A A接接近近單單位位陣陣，c co on nd d( (A A) ) 接接近近 ，對(duì)對(duì)A A用用共共軛軛斜斜量量法法求求解解，可可達(dá)達(dá)到到加加速速的的目目的的。1112,( )1TTTTTMCCAACA

26、CCMCC CC CIcond A工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)11()(0)()(0)(0)(0)(0)()()()()(1)()()(1)()()1,2,(1)(2),(3)0,1,.,(,)(,)TknkkkkkkkkkkkkkACACbCbAxbxxRrbAxprkrrA ppxxprrA p 、計(jì)計(jì)算算、解解得得，(1)(1)()()(1)(1)()()()(,)(,)3.kkkkkkkkkkkTrrrrprpxCx 、預(yù)條件共軛斜量法預(yù)條件共軛斜量法 實(shí)際計(jì)算，可通過(guò)變實(shí)際計(jì)算，可通過(guò)變換，轉(zhuǎn)化成用原方程組換，轉(zhuǎn)化成用原方程組的量來(lái)計(jì)算的量來(lái)計(jì)算。工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)工程數(shù)學(xué)(0)()(0)(0)(0)(0)(0)(0)(0)()()