共軛方向法演講PPT

1、共軛方向法2022-7-81主要內(nèi)容n一：共軛方向和共軛向量的概念n二：共軛向量的幾何意義和性質(zhì)n三：構(gòu)造共軛方向法的原理和方法n四：共軛方向法的迭代計(jì)算步驟n五：求解非線性方程組的MATLAB程序?qū)崿F(xiàn)和相關(guān)算法的比較2022-7-82nRXnRY0TAXYnn0TX Y，滿足如下關(guān)系：的對(duì)稱正定陣，則稱X和Y關(guān)于A共軛。注：若若兩個(gè)非零向量其中，A為，X和Y稱之為共軛方向。，則稱X與Y正交。共軛是正交的推廣。設(shè)A為 對(duì)稱正定矩陣，若有m個(gè)n維向量12,.,mS SS滿足0,TijAijSS則稱這m個(gè)向量是A的共軛向量。注：若AI，則nn為正交向量。12,.,mS SS一、共軛方向和共軛向量的

2、概念共軛方向共軛向量2022-7-830X0P()F X1X設(shè)從某點(diǎn) 出發(fā)，沿 方向進(jìn)行搜索得到 的極小點(diǎn) ，有：1010()()0TTF XAXBPP0X()F X2X設(shè)從某點(diǎn) 出發(fā)，沿 方向進(jìn)行搜索得到 的極小點(diǎn)2020()()0TTF XAXBPP(1)-(2)，可得：210() A0TXXP)(12XX 0P所以，與 是關(guān)于A共軛的。(1)(2)1()ABC2TTF XXXX()F XBAXXF)( （A為n維階的對(duì)稱正定陣）的梯度為： 設(shè)目標(biāo)函數(shù)為0P，有：二、共軛向量的幾何意義和性質(zhì)2022-7-84n共軛方向法算法的構(gòu)造基于如下幾點(diǎn)：n（1）n維正定二次函數(shù)依次沿n個(gè)相互共軛的方

3、向作n次一維優(yōu)化搜索可達(dá)最優(yōu)點(diǎn)。n（2）二維正定二次函數(shù)的等值線為同心橢圓族。n（3）同心橢圓族的任意兩平行切線的切點(diǎn)連線方向與該切線的方向，即為共軛方向。n第1點(diǎn)是共軛方向法迭代模式的基礎(chǔ)，第2、3點(diǎn)是共軛方向法構(gòu)造共軛方向的方法依據(jù)。對(duì)于非二次型的目標(biāo)函數(shù)，由于許多目標(biāo)函數(shù)在極值點(diǎn)附近，都可以用二次函數(shù)作很好的近似，所以共軛方向法用于非二次的目標(biāo)函數(shù)也有很好的效果。相關(guān)性質(zhì)2022-7-85 共軛向量的兩個(gè)重要性質(zhì)共軛向量的兩個(gè)重要性質(zhì) n性質(zhì)性質(zhì)1. 1. 關(guān)于A A共軛的向量組必為線性無關(guān)，共軛向量組中，共軛向量共軛向量的個(gè)數(shù)最多等于維數(shù)的個(gè)數(shù)最多等于維數(shù)n n （矩陣A的維數(shù)為n）。

4、2022-7-86n原理：同心橢圓族的幾何性質(zhì)n在任意兩個(gè)同心橢圓上作兩條相平行的切線l1,l2 ，則兩切點(diǎn)的連線必過橢圓族的中心 切線的方向切線的方向S S1 1與兩切與兩切點(diǎn)連線的方向點(diǎn)連線的方向S S2 2 ，就，就是一對(duì)共軛方向。是一對(duì)共軛方向。 正定二次二元函數(shù)(等值線為同心橢圓族)，經(jīng)兩次共軛方向搜索，就可搜索到極小點(diǎn)(橢圓中心)。 2022-7-87方法：以X0(1)為初始點(diǎn)，以S1為搜索方向作一維優(yōu)化，再以X0 (2)為起點(diǎn)，用與S1相平行的方向作一維優(yōu)化，則最優(yōu)點(diǎn)，是直線l2 與另一橢圓的切點(diǎn)X(2)。以X(1)為起點(diǎn)，X(2)為終點(diǎn)的向量為：S2 X(2)-X(1)，S2

5、的方向就是兩切點(diǎn)連線的方向，因?yàn)閘1與l2 平行，因此S1與S2 共軛。其最優(yōu)點(diǎn)，就是直線l1與某一橢圓的切點(diǎn)X(1)，2022-7-88 構(gòu)造共軛方向數(shù)值方法的歸納構(gòu)造共軛方向數(shù)值方法的歸納n用某一個(gè)不變的方向S1, 以兩個(gè)不同的初始點(diǎn)作兩次一維優(yōu)化，得到兩個(gè)最優(yōu)點(diǎn)。n連接這兩個(gè)最優(yōu)點(diǎn)的連線方向S2 就是與S1共軛的方向。n對(duì)于n維問題，接著以S2 為搜索方向，重復(fù)上述步驟就可得到與S2 共軛的方向S3 ，n反復(fù)迭代，即可求得n個(gè)相互共軛的方向。2022-7-89n（1）置SS數(shù)組為n 階單位陣，迭代輪次k1。n對(duì)于二維問題1001SS(2) i1 to n 做n次一維優(yōu)化搜索，方向S取SS

6、中的第i行數(shù)值，即sjssi , j、j=1，,n。 (3)計(jì)算S(k)=Xn(k)-X0 (k)(本輪初始點(diǎn) )以Xn(k)為起點(diǎn)，沿S(k)作一維優(yōu)化，將其最優(yōu)點(diǎn)作為X0(k+1)，(下一輪初始點(diǎn)) 2022-7-810n(4) 更新搜索方向向量組SSnjsssnjnisssskjjnji, 1, 1; 1, 1 )(, 1j i,(1)2)1(1s10sSSk=1時(shí)：(5) k=k+1，如果kn，轉(zhuǎn)步驟(6)，否則轉(zhuǎn)步驟(2) 。 2022-7-811(5) k=k+1，如果kn，轉(zhuǎn)步驟(6)，否則轉(zhuǎn)步驟(2) 。 (6) 檢驗(yàn)終止準(zhǔn)則，若滿足則退出計(jì)算， 若不滿足，將當(dāng)前最優(yōu)點(diǎn)作為新的

7、初始點(diǎn)，轉(zhuǎn)步驟(1)重新再進(jìn)行新的n次共軛方向的搜索計(jì)算。2022-7-812五、求解非線性方程組的MATLAB程序?qū)崿F(xiàn)和相關(guān)算法的比較)1()(T)()() 1()(kTkkgkgkgg（迭代形式為其中，在共軛方向法中，2022-7-813求解非線性方程組的MATLAB程序?qū)崿F(xiàn)niikkxFxF12)()()()(整個(gè)計(jì)算流程為:在MATLAB中沒有專門的函數(shù)實(shí)現(xiàn)共軛方向法求解非線性方程組，可以通過自定義F_ReevesGroundfun.m 函數(shù)實(shí)現(xiàn)共軛方向法。2022-7-814共軛方向法和阻尼牛頓法 的比較牛頓阻尼法需要計(jì)算Hesse矩陣計(jì)算量很大，計(jì)算量很大。最速下降法有鋸齒現(xiàn)像，收

8、斂速度很慢，同一種非線性方程，最速下降法的迭代次數(shù)是共軛方向法的30多倍（見下面實(shí)例）共軛方向法和最速下降法的比較算法比較而且Hesse矩陣可能奇異，或者接近奇異；即使該矩陣是可逆的，它也未必是正定矩陣。此時(shí)，導(dǎo)出的牛頓法迭代格式的二次函數(shù)不一定有極小點(diǎn)，甚至沒有駐點(diǎn)。2022-7-815function r,n = FastDownGroudfun(F,x0,h,eps)% FastDownGroudfun.m 為編寫利用最速下降算法求非線性方程組的解的函數(shù)% F為非線性方程組% x0為給定的初始值% h為數(shù)值微分增量步% eps為解的精度% r為求得非線性方程組的一組解% n為迭代步數(shù)fu

9、nction r,n = F_ReevesGroundfun (F,x0,h,eps)% F_ReevesGroundfun 為編寫利用共軛方向算法求非線性方程組的解的函數(shù)% F為非線性方程組% x0為給定的初始值% h為數(shù)值微分增量步% eps為解的精度% r為求得非線性方程組的一組解% n為迭代步數(shù)Matlab相應(yīng)程序的簡單介紹2022-7-816共軛方向法和最速下降法迭代次數(shù)的比較例：求解非線性方程組 調(diào)用MATLAB程序，用最速下降法求解如下：迭代步數(shù)n=822022-7-817共軛方向法和最速下降法迭代次數(shù)的比較例：求解非線性方程組 調(diào)用MATLAB程序，用共軛方向法求解如下迭代步數(shù)n=3最速下降法的迭代步數(shù)是共軛方向法的將近27倍2022-7-818一般目標(biāo)函數(shù)在最優(yōu)點(diǎn)附近呈現(xiàn)為二次函數(shù)，因此可以設(shè)想一個(gè)算法對(duì)于二次函數(shù)比較有效，就可能對(duì)一般函數(shù)也有較好效果。共軛方向