共軛方向法教學(xué)講義

1、&3.6 共軛方向法引言本節(jié)之后的方法大多屬于共軛方向法。3.6.1 共軛方向的概念若兩個向量，滿足如下關(guān)系： (3-6-1)其中，a為的對稱正定陣，則稱x和y是關(guān)于a共軛的，x和y稱之為共軛方向。注意：若，則稱x與y正交。實際上，共軛是正交的推廣。例1： 有兩個二維向量，判斷與是否關(guān)于a共軛，是否正交？解：，因此，與關(guān)于a共軛。，因此，與正交。3.6.2 共軛向量的概念如果有m個n維向量，滿足 (3-6-2)則稱這m個向量是a的共軛向量。如果維單位陣，則稱這m個為正交向量。3.6.3 共軛向量的幾何意義設(shè)目標(biāo)函數(shù)為 (3-6-3)其中，a為階的對稱正定陣。的梯度為： (3-6-4)設(shè)從某點出

2、發(fā)，沿方向進行搜索得到的極小點，則有 (3-6-5)設(shè)從某點出發(fā)，仍沿方向進行搜索得到的極小點，則有 (3-6-6)式(3-6-6)減(3-6-5)，可得： (3-6-7)這說明與是關(guān)于a共軛的。3.6.4 共軛方向法的原理考慮m個n維向量，滿足，則這m個向量一定是線性無關(guān)的。用反證法。假設(shè)線性相關(guān)，則一定存在一組不全為0的一組數(shù)，滿足 (3-6-8)則有 (3-6-8)其中，。因此有：，但這與原假設(shè)不符。因此，一定可以得出線性無關(guān)的結(jié)論。注意：在n維空間中的任意向量，均可以用n個線性無關(guān)的n維向量表示，也可以說，n維是由n個線性無關(guān)的n維向量張成的（此處還差一步：正交化）。那么，設(shè)目標(biāo)函數(shù)的

3、極小點為，初始點為，為關(guān)于的n個共軛向量，則有： (3-6-9)將式(3-6-9)寫成差分格式： (3-6-10)式中，表示經(jīng)過次迭代后，。該式表明，為目標(biāo)函數(shù)沿方向的一個極小點，則有： (3-6-11)即 (3-6-12)即可推導(dǎo)出： (3-6-13)式(3-6-13)表明，如果能夠構(gòu)造出一系列共軛向量，則可以求出，那么經(jīng)過k步迭代，可以求得。對于二次函數(shù)，。例2 求解解： 首先，構(gòu)造二次型： 即，。 取，取第0個搜索方向為：，則根據(jù)式(3-6-13)，有：由于與關(guān)于a共軛，則有上式與無窮多解，我們?nèi)稳?，則3.6.5 構(gòu)造共軛方向的一般方法在n維空間中，已知有n個單位向量：第i個分量為則n個

4、共軛方向可以這樣確定： (3-6-14)其中，為待定系數(shù)。由于，和關(guān)于a共軛，因此，即 (3-6-15)可得 (3-6-16)繼續(xù)，可以構(gòu)造 (3-6-17)考慮，即 (3-6-18)由于，式(3-6-19)化簡為： (3-6-19)即可推出： (3-6-20)同時考慮，即 (3-6-21)同理，由于，式(3-6-21)化簡為： (3-6-22)因此有 (3-6-23)特別注意：由于不僅與關(guān)于a共軛，同時也與關(guān)于a共軛，所以的表達(dá)式和在時的表達(dá)式(3-6-16)是不同的。由此可以類推，可得： (3-6-24)例題，見matlab程序3.6.6 共軛梯度法共軛梯度法是一種構(gòu)造共軛方向的方法。任取

5、一個初始點，經(jīng)過n次迭代，得到n個點，利用這n個點的梯度方向可以構(gòu)造一組共軛方向。具體做法為：設(shè)有一個n維函數(shù)，用梯度法經(jīng)過次迭代，即可以得到這個迭代點，這些點所對應(yīng)的函數(shù)的梯度為。即可以構(gòu)造一組共軛方向： (3-6-25)可以證明，按照式(3-6-25)構(gòu)造的n個方向是關(guān)于a共軛的。然后，即可按下式計算： (3-6-26)如果是二次函數(shù)，那么經(jīng)過n次迭代后必然可以收斂到極小點。如果按這樣的算法計算，則一定需要求得函數(shù)的海賽矩陣a，在實用性上存在困難，并且加大了計算負(fù)擔(dān)，因此我們需要想法避免在計算過程中出現(xiàn)a?，F(xiàn)在我們對以上公式作一些適當(dāng)?shù)暮喕?。設(shè)有一個二次函數(shù)，在進行極小化過程中，迭代公式為

6、： (3-6-27)設(shè)為迭代點的梯度，并且令： (3-6-28)這是前后兩相鄰迭代點的梯度之差。則有： (3-6-29)對n個共軛方向，有：故 (3-6-30)可見在迭代過程中，前后兩次迭代點的梯度之差與其他任一共軛方向是正交的。即 (3-6-31)設(shè)，則：(3-6-32)又因為式(3-6-31)，故有 (3-6-33)在此式中，是迭代點處的梯度，而是沿方向搜索新得之點。在梯度法中我們已經(jīng)證明了點處的梯度方向與求得點時的搜索方向是正交的，所以有： (3-6-34)則有： (3-6-35)這就是說，某迭代點的梯度方向與此點以前各點的搜索方向均是正交的。我們再回到構(gòu)造n個共軛方向的問題上來。已知式

7、(3-6-25)：那么，對于第r次迭代（其中），則有 (3-6-36)所以 (3-6-37)此處。將上式等號兩邊同時左乘，得到 (3-6-38)又因為，而，所以在上面和式中每一項均為零，即 (3-6-39)所以 (3-6-40)根據(jù)式(3-6-28)，已知：，所以 (3-6-41)將式(3-6-41)等號兩邊同時左乘，得： (3-6-42)考慮當(dāng)時，有 所以 (3-6-43)根據(jù)式(3-6-25)， ，且所以當(dāng)時，均有：，僅當(dāng)，。所以有： (3-6-44)再對此式作進一步的簡化： (3-6-45)代入上面(3-6-25)式，可得： (3-6-46)將式(3-6-46)兩邊分別左乘得： (3-6-47)因為和是a共軛方向所以 由前已知所以式(3-6-47)右邊各項中除兩項不等于零外，其余均等于零，于是有： (3-6-48)由此即可得到求的公式如下： (3-6-49)此式中不含海塞矩陣a，因而免去了許多繁瑣的計算，而且不用擔(dān)心a的正定及非奇異問題，對初始點的選擇無任何限值了。從以上分析，我們得出了共軛梯度法的計算步驟及迭代公式如下：1) 任選初始點，則： (3-6-50)2) 計算： (3-6-51)其中，。則可構(gòu)造n個共軛方向。3) 對于每個迭代點及每個共軛方向，求，使。4）按收斂判斷準(zhǔn)則判斷是否為極小點，若是，則可以停機，