非線性方程組數(shù)值解PPT課件

1、浙江大學(xué)研究生學(xué)位課程1 .1 引言引言在科學(xué)研究中，常常會遇到非線性方程 或非線性方程組的問題。例如解方程或一般的，我們記非線性方程為14024503510234xxxx2402sinxex 340 xf第1頁/共130頁浙江大學(xué)研究生學(xué)位課程24.1 非線性方程組的一般形式是：非線性方程組的一般形式是：0,0,0,21212211nnnnxxxfxxxfxxxf 其中fi（i=1,2,n）是n維實空間n 上的實值函數(shù)。用向量形式表示： 這里均是n維向量。為了方便計，還是用分別表示上述向量。 簡記為： 440 xf0,xf0 ,xf 0 xf第2頁/共130頁浙江大學(xué)研究生學(xué)位課程34.1c

2、adcadb3axydcxy32axydcxy2圖圖 4.1 非線性方程求根示意圖非線性方程求根示意圖第3頁/共130頁浙江大學(xué)研究生學(xué)位課程44.1 方程的解亦稱方程的根或函數(shù)的零點。 根可能是實數(shù)或復(fù)數(shù)。 若則稱為單根；若而，則稱為 k 重根。 常見的求解問題有兩種常見的求解問題有兩種：(1) 要求定出在給定范圍內(nèi)的某個解某個解。(2) 要求定出在給定范圍內(nèi)的全部解全部解。 非線性問題，除少數(shù)情況外，一般不能不利用公式求解。而要采用某種迭代解法。即構(gòu)造出一近似值序列逼近真解 。 , 0, 0ff 01kfff 0kfn,10第4頁/共130頁浙江大學(xué)研究生學(xué)位課程54.1 迭代過程的收斂性

3、收斂性一般與初值的選取和方程的性態(tài)有關(guān)，某些解法僅與初值有關(guān)。 收斂速度收斂速度一般由迭代方法所決定，方程的性態(tài)也會起一些作用。 本章主要介紹非線性方程組的解法本章主要介紹非線性方程組的解法， 而方程的解法用較少的篇幅在4.2中扼要介紹。解非線性方程和方程組有很大區(qū)別解非線性方程和方程組有很大區(qū)別。后者要困難得多困難得多。主要的區(qū)別在于一維情形可以找到一個根的范圍，然后縮小，最終找到根。而多維情況則很難確定根的存在多維情況則很難確定根的存在。直到你求得它的解。第5頁/共130頁浙江大學(xué)研究生學(xué)位課程64.2 非線性方程的解法非線性方程的解法二分法二分法對于連續(xù)函數(shù)，如果在 和處異號：則在內(nèi)至少

4、有一個根。 xfax bx 0bfaf xfba, 同號與否。與取決于代替前一步的或的方法，稱二分法。用減小一倍，即二分每步使長度的解。近似作為用足夠小時，。當(dāng)區(qū)間當(dāng)時已找到解，并保持逐步縮小區(qū)間2,2,2,02,0,bafafbabaabbababaxfbababfafba第6頁/共130頁浙江大學(xué)研究生學(xué)位課程7 用圖來表示這個過程：用圖來表示這個過程：yxababab 時零點。、只能求實函數(shù)的一個、方法穩(wěn)定，只要求、收斂速度慢，線性。3,210bacxf 確定根所在的范圍a,b對有的函數(shù)也是一件困難的事。所幸的是，在實際應(yīng)用中，根據(jù)其物理或工程的背景，在絕大部分場合是不困難的。對給定的函

5、數(shù)也有確定范圍的方法。圖圖 4.2 二分法方程求根二分法方程求根第7頁/共130頁浙江大學(xué)研究生學(xué)位課程8abbax1x1x2x3dcfc a b圖圖 4.3 尋找隔根區(qū)間示意尋找隔根區(qū)間示意1第8頁/共130頁浙江大學(xué)研究生學(xué)位課程9 xc1sin cxd1acb圖圖 4.4 尋找隔根區(qū)間示意尋找隔根區(qū)間示意2圖圖 4.5 尋找隔根區(qū)間示意尋找隔根區(qū)間示意3第9頁/共130頁浙江大學(xué)研究生學(xué)位課程10例如，在a,b之間尋找 f(x) 可能有的根可以用等分試探法：ab圖圖 4.6 等分試探法尋找隔根區(qū)間示意等分試探法尋找隔根區(qū)間示意第10頁/共130頁浙江大學(xué)研究生學(xué)位課程11用二分法求函數(shù)用

6、二分法求函數(shù)FUNC位于（位于（x1,x2）之間的根，準(zhǔn)確性為之間的根，準(zhǔn)確性為 XACC。FUNCTION RTBIS (FUNC,X1,X2,XACC)PARAMETER (JMAX=40)FMID=FUNC(X2)F=FUNC(X1)函數(shù)FUNC在x1,x2處不異號 RTIBIS=X1 DX=X2-X1ELSE RTBIS=X2 DX=X1-X2ENDIFDO 11 J=1, JMAX DX=DX*0.5 XMID=RTBIS+DX FMID=FUNC(XMID) IF (ABS(DX) .LT. XACC .OR. FMID .EQ. 0.) RETURN11 CONTINUE PAU

7、SE 迭代次數(shù)越界 END第11頁/共130頁浙江大學(xué)研究生學(xué)位課程12FUNCTION FF(X)FF = X*X + 2.5*X + 0.5+SIN(X)ENDPROGRAM ROOTFINDEXTERNAL FFX1=-1.0X2=0.0ROOT=RTBIS(FF, X1, X2, 1.0E-5)PRINT *, 方程在（-1，0）區(qū)間內(nèi)有一個根，X=, ROOTSTOPEND 內(nèi)的一個根解題示例。，在區(qū)間求01)sin(5 . 05 . 2:2xxxxf第12頁/共130頁浙江大學(xué)研究生學(xué)位課程13線性插值法線性插值法（又稱弦位法）（又稱弦位法） 為止。逼近解如此反復(fù)，直到充分，重復(fù)上

8、述過程得到，代替似值。用的一個新的近為：的零點，并記為求構(gòu)造一線性函數(shù)，通過且。，的兩個近似解的解設(shè)31212222121222212211,0fffxLxfffxLffffffxfxf(x)2413圖 4.7 Secant Method第13頁/共130頁浙江大學(xué)研究生學(xué)位課程14cc3323323設(shè)迭代控制： 212333,01，則當(dāng)附近在零點如果程是發(fā)散的。當(dāng)超過這個數(shù)時認(rèn)為過，迭代次數(shù)故一般提供一個最多的收斂的，由于有時這個過程是不。作為解時認(rèn)為過程收斂，或滿足。則迭代過程如果一般取數(shù)。為絕對或相對誤差控制其中CxfkfC第14頁/共130頁浙江大學(xué)研究生學(xué)位課程15降低了收斂速度。，

9、但是卻法增加了收斂的可能性。簡稱個修改后的方法叫做。這定包含了解最近得到的。但它們一不一定是，解使它所保留的兩個近似修正一下這個算法，的原因之一。我們?nèi)绻麛俊＿@也是不能保證收不總是包含解之間并，的近似值解兩個最近的是所保留的線性插值法的一個缺點階。即超線性收斂。其收斂速度為的。時，線性插值法是收斂充分接近于FPMFPMMehtodPositionFalse.618. 12121第15頁/共130頁浙江大學(xué)研究生學(xué)位課程16收斂還要慢。插值法比二分法可以舉出例子說明線性。根必須包含，值法的初始所示。圖解的迭代過程如法及近似218 . 4FPMFPMf(x)x1432圖圖 4.8 線性插值法求根示

10、意線性插值法求根示意第16頁/共130頁浙江大學(xué)研究生學(xué)位課程17f(x)x1345圖圖 4.9 線性插值法發(fā)散示例線性插值法發(fā)散示例第17頁/共130頁浙江大學(xué)研究生學(xué)位課程18Newton 法法 111211111100ffxLfxfxLffffxfxf得令作記：存在。附近在解設(shè)F(x)x2111, fx圖圖 4.10 Newton 法示意法示意第18頁/共130頁浙江大學(xué)研究生學(xué)位課程19 。故求弦位法每迭代一次只需求值。必須對存在：法的收斂階為kkkkkkkfafffkfceeNewton.,3, 2 , 1020lim211F(x)21x11, f02f圖圖 4.11 導(dǎo)數(shù)變化對算法

11、的影響導(dǎo)數(shù)變化對算法的影響第19頁/共130頁浙江大學(xué)研究生學(xué)位課程20每次函數(shù)求值相當(dāng)?shù)氖諗侩A為：b. 求 fk 有時工作量大，甚至不可能。(4) 選用收斂域較大的方法（如二分法） 先進(jìn)行迭代，然后再用Newton法。組合方法。 二次插值法二次插值法設(shè) f(x)=0 的三個近似解及函數(shù)值 構(gòu)造二次函數(shù)g(y)使得： 。332211,fff414. 12 618. 1第20頁/共130頁浙江大學(xué)研究生學(xué)位課程21 PQXyfffffyfyfffffyfyfffffyfyygxLagrangeifgxii則求新的近似根，令插值：利用, 03 , 2 , 112322133121132231331

12、1第21頁/共130頁浙江大學(xué)研究生學(xué)位課程22133221213313223211111ffTffSffRfffffffffQTSRP其中：F(x)xg(x)f(x)1432圖圖 4.12 二次插值法求根示意二次插值法求根示意第22頁/共130頁浙江大學(xué)研究生學(xué)位課程23 (1) 要有三個初始值 (2) 當(dāng) 。且收斂速度 是 1.84 階。（單根） 二重根的收斂階是1.23。 (3) (4) 發(fā)生超射、越界。 21111,且 時收斂,03Cxf不同值。不同值。3 , 2 , 13 , 2 , 1ifiii方法名稱收斂速度有效指數(shù)重根情況二分法111, 偶重失敗線性插值法1.6181.6181

13、牛頓法21.4141二次插值法1.841.84二重時 1.23表表 4.1 各種插值方法的比較各種插值方法的比較第23頁/共130頁浙江大學(xué)研究生學(xué)位課程24 組合方法組合方法（Brent Method）能否有一種方法綜合上述方法的優(yōu)點呢？Brent 做了一些工作。Brent 把二分法和二次插值法結(jié)合起來。（）一定收斂。（）收斂速度至少線性。（）在解附近足夠光滑時，收斂速度將是 1.84 或 1.23。有關(guān)多項式的求根還有一些特殊方法。第24頁/共130頁浙江大學(xué)研究生學(xué)位課程25 4.3 非線性方程組及牛頓法 非線性方程組的向量形式可表示為 TnTnxffffxf,5402121其中解法：

14、1. 幾乎不可能用直接法 2. 線性化，迭代逼近。牛頓法 3. 最優(yōu)化，求函數(shù)極小值。下降法。 例如， 求 的極小值點。 最速下降法最速下降法，共軛梯度法共軛梯度法，變尺度方法變尺度方法。 2xfxi第25頁/共130頁浙江大學(xué)研究生學(xué)位課程26牛頓法牛頓法為方便計，用二維情形來討論。640,0,212211ff 假定（4-6）的解,0,021xCffx 。且存在一階偏導(dǎo)數(shù)。設(shè),0 xxk kkkxx2121,這里，作線性函數(shù)（Taylor 展開，取一階精度） 7422221112222221111111kxkxkkxkxkkkkkffxfxlffxfxl第26頁/共130頁浙江大學(xué)研究生學(xué)位

15、課程27在內(nèi)用線性函數(shù)（4-7）代替非線性方程組(4-6)中的f1,f2, 從而,0 x kkkkkkkxkkkxxfffxfffkxkkxk22211122221221221111,這里， 如果在中矩陣（稱Jacobi矩陣）,0 x 8422122111kxkffffxDf非奇異，則可解出。第27頁/共130頁浙江大學(xué)研究生學(xué)位課程28 9421121kkkxkkxfxfDf 矩陣。從而稱為向量函數(shù)的JacobixDf kkkkkk22121111 10411kkxkkxfDfxx于是 kxnnnnnnkfffffffffxDfn21222121211164維情形：的牛頓迭代公式非線性方程組

16、第28頁/共130頁浙江大學(xué)研究生學(xué)位課程29 79. 073. 00 . 53 . 46 . 10 . 312. 8179. 073. 00 . 33 . 46 . 10 . 50 . 33 . 46 . 10 . 523,34122,2879. 0,73. 0,9 . 0, 4 . 00332,0224,1121122110212212211211020120201102221212122212221211021212121因此故再算解：設(shè)初始近似解為的近似解例：用牛頓法求方程組xTffffxDfffffffxff第29頁/共130頁浙江大學(xué)研究生學(xué)位課程30 0 . 0000000. 1

17、 ,500000. 0000138. 0 ,000174. 0999862. 0 ,500174. 0000138. 0013826. 0070392. 0084784. 0524. 3056. 5028. 2112. 6524. 3056. 5028. 2112. 6070392. 0 ,084784. 0,000. 1,514. 0100. 0,114. 03231223211211211111112110010 xfxfxxxxxxxxfxfxDfxxDfxfxfxxxxTTTTTTT且故再重復(fù)做一次，得故重復(fù)上述過程，故得：第30頁/共130頁浙江大學(xué)研究生學(xué)位課程31 迭代式。的改進(jìn)

18、為克服上述三個缺點，的逆矩陣工作量大。計算可能出現(xiàn)病態(tài)。很小。初始要求高，即。收斂。且收斂速度階為迭代式充分小，則且初值非奇。矩陣當(dāng)104322104,0, 1 , 010kkkxDfxDfxxkxDfJacobi 牛頓法的改進(jìn)牛頓法的改進(jìn)改進(jìn) 帶松弛因子的牛頓迭代格式改善了對初始值近似程度的要求。第31頁/共130頁浙江大學(xué)研究生學(xué)位課程32 (4-10) 中引入了松弛因子，有k 二次插值法求解。它可以用黃金分割法或極值問題。是一維的求取時，按即是牛頓法。收斂最快收斂。時當(dāng)或的選取滿足而1241243, 12114021124min114, 2 , 1 , 01111kkkkkkkkkkkk

19、kkxfxDfxfxfxfkxfxDfxx第32頁/共130頁浙江大學(xué)研究生學(xué)位課程33 滿足以上條件。上的凸函數(shù)，則是顯然，若，當(dāng)，當(dāng)內(nèi)滿足：在設(shè)內(nèi)的極小值。在法（優(yōu)選法）求函數(shù)baxxxxaxxbxxxxxbaxxbax,618. 0121122121abaxxb圖圖 4.13 凸函數(shù)示例凸函數(shù)示例第33頁/共130頁浙江大學(xué)研究生學(xué)位課程34 繼續(xù)進(jìn)行。否則，令若成立，則判別：顯然，否則取取則若計算兩個實驗點11111111111111,21?618. 0,618. 0382. 0bbaaabxabababbaxbbcadbaadcabadabac第34頁/共130頁浙江大學(xué)研究生學(xué)位課

20、程35 1 5 4 3 2acdbx21561803. 0,11,12wwwwwabadwwwadacwabac解得故從而則若根據(jù)等比收縮原則；1a1c1d1b圖圖 4.14 0.618法搜索極小點過程法搜索極小點過程第35頁/共130頁浙江大學(xué)研究生學(xué)位課程36 (2) 二次插值法求一維函數(shù)極小值：13245acb3 , 2 , 12 , 4 , 1 afbfcbcfbfabafbfcbcfbfabbxxcfcbfbafa2221,坐標(biāo)：拋物線的極小點的通過圖圖 4.15 二次插值法進(jìn)行一維極小點搜索二次插值法進(jìn)行一維極小點搜索第36頁/共130頁浙江大學(xué)研究生學(xué)位課程37 改進(jìn).帶阻尼因子

21、的牛頓迭代格式帶阻尼因子的牛頓迭代格式 克服了矩陣的奇異或病態(tài)。(4-10)中 引入阻尼因子：kxDfk, 2 , 1 , 013411kxfIxDfxxkkkkk 的選取可以在滿足(4-12)的前提下取很大值。（）改善對初值的要求（）當(dāng)時為牛頓法，收斂最快。（）為滿足(4-12)，實際上需要多次試算，工作量大。改進(jìn)3.修正牛頓法修正牛頓法 盡可能減少矩陣求逆次數(shù)。kk第37頁/共130頁浙江大學(xué)研究生學(xué)位課程38一種簡單的辦法是每次使用同一個Jacobi矩陣的逆。2 , 1 , 0101kxDfxDfk令但大大影響收斂速度。另一種辦法是若干次迭代后求一個矩陣逆：144, 1 , 0, 1,1

22、1,11,0,kxxmixfxDfxxxxmkkikkikikkk令 它減少了矩陣求逆，又保證了收斂。 換一個角度看，如果說它的求逆次數(shù)與牛頓法相同(k次)，則它的收斂階為m+1。第38頁/共130頁浙江大學(xué)研究生學(xué)位課程391 ,11 ,2,10,10,1 ,0,kkkkkkkkkkkxfxDfxxxxfxDfxxxx或154, 1 , 0111kxfxDfxfxfxDfxxkkkkkkk迭代格式(4-15)具有階收斂速度。 對一維情況，Newton法在幾何上表現(xiàn)為m步迭代過程保持斜率 f(xk) 不變。如圖4.16：f(x)x00,kxkx1 ,kx2,kx1kx1 , 1kx2, 1kx

23、2kx圖圖 4.16 m=2的迭代效果的迭代效果作為特例，取m=2:第39頁/共130頁浙江大學(xué)研究生學(xué)位課程40非線性代數(shù)方程組求解問題非線性代數(shù)方程組求解問題 1. Newton-Raphson 迭代法 2. 極值化求解。問題的轉(zhuǎn)化問題的轉(zhuǎn)化： xfxfxfxxxfnixxxfinxni0,min, 2 , 10,2121是一個非負(fù)函數(shù)，且設(shè)無約束最優(yōu)化問題 nibxaDxxxxxxxxfxfxxxfxfiiiTnnininini, 2 , 1,211221121這里，例：第40頁/共130頁浙江大學(xué)研究生學(xué)位課程41 4.4最速下降法方程組的主要方法。方法是解非線性最優(yōu)化極值化 極值化極

24、值化求解 164, 2 , 10,1221niinixfxfnixxxf等價于求解的零極值點零極值點。 求解(4-16)的極值點也是一個無約束的最優(yōu)化問題。第41頁/共130頁浙江大學(xué)研究生學(xué)位課程42求解最優(yōu)化問題，通常采用下降法求解最優(yōu)化問題，通常采用下降法。下降法下降法 一般描述如下： 增加最快的方向。顯然：梯度方向是函數(shù)的梯度。稱為其中：有即的初始估計。是點。是無約束問題局部極小設(shè)xfxxfxxfxfxfxfxfxxxTnDx,010min第42頁/共130頁浙江大學(xué)研究生學(xué)位課程43下降法的迭代步驟下降法的迭代步驟，迭代結(jié)束。置，轉(zhuǎn)置則轉(zhuǎn)且若計算，以保證選擇步長因子，使確定下降的搜索

25、方向121111:. 611:. 56. 4. 30. 20),(. 1kkkkkkkkkkkkkkkkxxkkxfxfxfhxxxfhxfhxfh第43頁/共130頁浙江大學(xué)研究生學(xué)位課程44 最速下降法最速下降法取 因此,kkxfh, 2 , 1 , 01kxfxxkkkk kkkkkkkkkkkkxfxfiixfxfxfi0min:210通過一維搜索確定，再檢驗。不成立時，讓檢驗，為給定常數(shù)取有為步長因子。它的取法其中第44頁/共130頁浙江大學(xué)研究生學(xué)位課程45等高線圖：f(x)=Cif(x1,x2)=Cix0 x1x0hkx1h1kxkhkkkkkkkkkkkkkhhxxhhxfhh

26、1min其大小應(yīng)滿足方向步長，為沿為反梯度方向， xfxkxxxfkx xf12kkkx21, kxfkxxf1kxxf2圖圖 4.17 等高線等高線圖圖 4.18 偏導(dǎo)數(shù)示意偏導(dǎo)數(shù)示意第45頁/共130頁浙江大學(xué)研究生學(xué)位課程46 xfxfxfkkk0lim單調(diào)下降這樣，討論與改進(jìn)討論與改進(jìn)優(yōu)點：優(yōu)點： . 程序簡單，每步迭代計算量少，存儲省。 . 對于不太好的初始點x0，往往也能收斂。缺點缺點：最速下降法是名不符實的，一般來說，它只有線性的收斂速度。第46頁/共130頁浙江大學(xué)研究生學(xué)位課程47 收斂很慢。出現(xiàn)鋸齒形。對于一族扁橢圓，迭代則可以證明：若好。這個方向并非最最快的方向，從整體看

27、只是局部下降得究其原因，iixfxfixfxfxfxfkTkkkkk0,min110 x1x2xkx1kxx圖圖 4.19 鋸齒形搜索路徑情況鋸齒形搜索路徑情況第47頁/共130頁浙江大學(xué)研究生學(xué)位課程48 成立。序列速下降法生成的使用精確一維搜索的最對正定二次函數(shù)或從而故而所以則證明：令kTTkTkkTkkTkkTkkxxnkxxkxxxxxxkkkkkxcxbAxxxfxfxfxfxfhxfhxfhfhfhfdxdfdxdfhxfxfhxfnkkkkk210000min111121011211111第48頁/共130頁浙江大學(xué)研究生學(xué)位課程49 法收斂慢。嚴(yán)重。故此時最速下降偏離指向極小點

28、方向橢圓扁長，負(fù)梯度方向時，的橢圓。當(dāng)離心率很大等高線是離心率為為例：中的正定二次函數(shù)以偏長的情形。幾何上可解釋為等高線，收斂速度越慢。越接近于時，當(dāng)?shù)慕咏潭?。和可見，收斂速度依賴于的最小、最大特征值。分別為這里其中：bababaqbaAbaxfRcxfqMmmMAMmxfxfmcmMmMqcqxxxfxfqxfxfkkkk2222222222221220220100121:1,1第49頁/共130頁浙江大學(xué)研究生學(xué)位課程50一般來說，開始幾步下降速度較快，但越靠近極小值點越慢。改進(jìn)改進(jìn)：elsexfiikifxxhkhxxParNewtonkkkkkkkk, 2 , 1,3, 2 , 1

29、, 0tan. 2. 121其中法法。后改用前幾步用最速下降法，第50頁/共130頁浙江大學(xué)研究生學(xué)位課程51 最速下降法算法框圖最速下降法算法框圖：0,0誤差控制取初值nRx ?00 xfg00, 0ghkkkkkkkkhxfxfhxx011min:求一維極值得?11kkxfg11kkgh1 kk停yes0 xx 解停yes1kxx解圖圖 4.20 最速下降法算法框圖最速下降法算法框圖第51頁/共130頁浙江大學(xué)研究生學(xué)位課程52 表數(shù)據(jù)：重復(fù)以上過程，可得下故求一維極值得設(shè)解：用最速下降法求取例：設(shè)TRxTxfxxxfxfxxfxfxfxxf1738,172617526180306612,

30、23min,4 , 2221230001020001221012122212k0-2411.529412.2352920.9417701.0588231.010381.0242240.9988471.0011551.000201.0004860.9999771.0000271.000001.0000181.000001.0000012210 x1x2x3xx圖圖 4.21 搜索路徑示意搜索路徑示意第52頁/共130頁浙江大學(xué)研究生學(xué)位課程53 4.5 共軛梯度法 （Conjugate Gradient Methods） 共軛方向共軛方向ABDCO0h0h00|,hCDOCDhBAD點且過的兩個

31、切點給定方向橢圓中心為共軛方向。與為共軛直徑。與則CDABCDAB圖圖 4.22 共軛方向共軛方向第53頁/共130頁浙江大學(xué)研究生學(xué)位課程54 共軛。關(guān)于這種關(guān)系稱則有那么若令方向由下式?jīng)Q定并且及兩個初始點給定方向其中維二次函數(shù)引理：對稱正定為凸函數(shù)：時的二次函數(shù)可表示為“共軛”關(guān)系：對二次函數(shù)來討論這種AhhAhhxxhhxfxfhxfxfhxxhxxxxhAAcxbAxxxfnAxxAxfcxbAxxcbbaaaacbbaaaxfnTTTTTTT,0,minmin,02102121212121001111000100010101000100021212122121211212211222

32、221122111第54頁/共130頁浙江大學(xué)研究生學(xué)位課程55 000002121210101101101101011111112211221122222221121122111AhhAhxxhxxAhxfxfhxfhxfbAxbbaaaaxfbaaafcbbbaaaaaaxfTTTTTTnnnnnninniiiinnnnnnnnn所以故又故所以證明：第55頁/共130頁浙江大學(xué)研究生學(xué)位課程560h0h1x1x1h0 x0 x cbxAxxxfTT210 ,x xf21圖圖 4.23 二次函數(shù)的共軛方向二次函數(shù)的共軛方向圖圖 4.24 二次函數(shù)二次函數(shù)第56頁/共130頁浙江大學(xué)研究生學(xué)位

33、課程57 0)(0, 2 , 11, 2 , 1, 2 , 1, 1,;02, 01,2211221121212121mmTimmiiimjTiTnnnmhhhAhhhhmihmihmihIAAhhhmjijiAhhAhhAhhARRARhhh得事實上，由線性無關(guān)。：共軛向量組性質(zhì)具有以下性質(zhì)：共軛向量組是共軛的特殊情況。交的向量。因此，正交是一組正時，顯然，當(dāng)共軛的向量組。是則稱若共軛的；是和則稱向量若為對稱正定。定義：第57頁/共130頁浙江大學(xué)研究生學(xué)位課程58 bAxxfnkhxffxxxfhxfxfhhhnihmimiAhhAmiAhhmihkTknnkkkniiiiTiiTiii2

34、, 2 , 1010min, 2 , 1. 2, 2 , 10, 2 , 10, 2 , 10, 2 , 1,111012一維搜索滿足：證明：為凸若和有為搜索方向的搜索方法向量共軛，則相繼以設(shè)性質(zhì)可知的正定性。即由共軛，故有因為第58頁/共130頁浙江大學(xué)研究生學(xué)位課程59 畢為凸函數(shù)，故又設(shè)，得由性質(zhì)的共軛性。得及，由.01, 2 , 103, 2 , 1211111111111111xxfxfnjhAhAhxfhAhAhxfhAhxfhxfnihAhxfxxAxfAxxfAxxfnnjTjjTnnTjjTnnTnnTnjTnnTnjTnikkkkkkkkkk第59頁/共130頁浙江大學(xué)研究

35、生學(xué)位課程60共軛梯度法共軛梯度法 Conjugate Gradient Method利用共軛方向，對二次型求極值問題可以得到n步收斂的結(jié)果。現(xiàn)在的問題是：1.如何構(gòu)造n個共軛方向？2.對一般的非線性函數(shù)f(x)怎么辦？3.由于舍入誤差等影響，n次迭代不收斂時怎么辦？ 如下：和定義向量序列為任意向量階對稱正定矩陣是設(shè)iiThggbxAxxxfnnA021第60頁/共130頁浙江大學(xué)研究生學(xué)位課程61 雙正交化方法。一般稱其為共軛向量序列的方法。和一是構(gòu)造一正交向量序列故可以證明：因此一共軛正交使選擇SchmidtGramnjijihAhjigghAhAhghAhAhgAhgggAhgggAhA

36、hgghghAhgghgjTijTiiTiiTiiiTiiiTiiTiiTiiiTiiiTiiTiiTiiiiiiiiiii184,174194,000184000,174111111100第61頁/共130頁浙江大學(xué)研究生學(xué)位課程62 畢而，由事實上，引理：證明：改寫，把公式為盡可能不使用矩陣iTiiTiiTiiiiTiiTiiTiiTiiTiiTiiTiiiTiiiTiiiiiTiiTiiTiiiTiTiiTiiiiTiiiTiiiiTiiTiiTiiTiiiTiiTiiiiTiiTiiTiiTiiTiiTiiiTiiTiiiTiiTiiAhhhgAhhhhgAhgggggggAhhAhg

37、AhhAhgAhggggAhggggghghghghgghgAhgAhhAhgAhhgAhhhgAhhAhgAhhhggggggggggA1111111110101012121111111111111111117400204184第62頁/共130頁浙江大學(xué)研究生學(xué)位課程63 kTkkTkkkTkkTkkkkkkkTkkTkkkkkkiiiiTiiTiiiTiiTiiiTiiTiigggggggggghhghAhhhghxxkxfghAhhhgggggggggg11110011111112342 , 1 , 0184174224214共軛梯度法：為時，下面的極值算法稱當(dāng)令是共軛的，并且構(gòu)成的向

38、量，由第63頁/共130頁浙江大學(xué)研究生學(xué)位課程64 kkkkkkkiAhgbhxAggxfghx100001184,式：的第滿足容易說明：這樣定義的其中，初始近似為00minmin111kTkkTkkkkkggxfxfhxfxf即時，的選取用一維極值當(dāng)方法。式子時，叫做個取第方法，而方法或稱為一個等式時，叫做取第中的當(dāng)共軛梯度法RPRibierePolakRFevesFletcherkk2Re234第64頁/共130頁浙江大學(xué)研究生學(xué)位課程65共軛梯度法是從梯度向量出發(fā)構(gòu)造共軛向量。 * 由于誤差積累等因素，對二次型，迭代 n次也未能達(dá)到極小點。* F-R方法和P-R方法的區(qū)別在于它們對二

39、次型是一樣的。而對一般函數(shù)用P-R方法 可能更合適。* 共軛梯度法具有二次收斂速度。那么對一般的函數(shù)的共軛梯度法 又是怎樣的呢？第65頁/共130頁浙江大學(xué)研究生學(xué)位課程66在極小值點附近進(jìn)行二次逼近：在極小值點附近進(jìn)行二次逼近： AxxbxcxxxxfxxfPfxfTjijiPjiiiPii2121,2 kkkkkkxxkPjiijhxfhxffxfAxxfAPfbPfcji0 2min:,.234244我們采用一維搜索求避免求的二階偏導(dǎo)數(shù)。為因此需要計算時要用到知，求由共軛梯度法其中第66頁/共130頁浙江大學(xué)研究生學(xué)位課程67但是求導(dǎo)數(shù)f(xk)是必須的。 另外，我們總假定f(x)在極值

40、點附近性質(zhì)足夠好，滿足各種要求。 對一般函數(shù)f(x)，共軛梯度法(4-23)有 限步收斂幾乎是不可能的。如果迭代k 步 達(dá)到精度（kn）,則xk就作為x*的近似。 當(dāng)經(jīng)過n步迭代仍不可能滿足要求時，令再進(jìn)行第二次循環(huán)。但是，實際計算中，不一定迭代k=n 步才進(jìn)行“重置”。nnxfgkxx000而第67頁/共130頁浙江大學(xué)研究生學(xué)位課程68 (1)在極小點附近是一個高度偏心的二次函數(shù)。則進(jìn)行（m+n）次迭代（mn）就收斂了。而進(jìn)行 k 次迭代（k n）就重置的話，有可能會不收斂。 (2)在極小點附近或稍遠(yuǎn)處不是二次函數(shù)。此時稱“扭曲”現(xiàn)象。則留有非二次函數(shù)的痕跡，故可能對收斂很有害。此時最好重

41、置。kkh第68頁/共130頁浙江大學(xué)研究生學(xué)位課程69 共軛梯度法共軛梯度法 Conjugate Gradient Methods 算法框圖算法框圖0,0誤差控制取初值nRx?00 xfg00, 0ghkkkkkkkkhxfxfhxx011min:求一維極值得?00 xfg?nk kkkkkTkkTkkkTkkTkkhghggggggggg1111111 kk1010kkggxx停yes0 xx 解no停1kxx解yesnonoyes圖圖 4.25 共軛梯度法算法框圖共軛梯度法算法框圖第69頁/共130頁浙江大學(xué)研究生學(xué)位課程70(3) 如何判別是高度偏心的二次函數(shù)還是 扭曲的函數(shù)呢？ 啟發(fā)

42、性的辦法是： 對一般非二次函數(shù)，若x0離x*較遠(yuǎn)， 則迭代n次不收斂時，就重置。但以后不 再重置。 對既高度偏心，又嚴(yán)重扭曲的函數(shù)， 則經(jīng)常性的重置是有好處的。 5210201041101212221241212212xxxxxxxfxxxxf即：函數(shù)例如：第70頁/共130頁浙江大學(xué)研究生學(xué)位課程71它在點（1,1）處有極小值4. 其圖象為：1x2x圖圖 4.26 函數(shù)等高線圖函數(shù)等高線圖第71頁/共130頁浙江大學(xué)研究生學(xué)位課程72 表4.3最速下降法計算結(jié)果最速下降法計算結(jié)果X1X2fX1X2f-1.200-0.993-0.793-0.663-0.552-0.388-0.3060.633

43、0.6250.6540.6481.0001.0710.4930.5380.2180.2750.0370.3610.3820.3920.41110.7768.0457.4036.8626.4836.0815.7394.1514.1414.1324.1250.6720.6670.6890.6830.7030.6980.7160.7110.7280.7240.4200.4370.4440.4600.4660.4810.4870.5000.5050.5174.1184.1124.1064.1014.0964.0914.0874.0834.0804.077第72頁/共130頁浙江大學(xué)研究生學(xué)位課程73表

44、4.4 各種重置循環(huán)的共軛梯度法計算結(jié)果各種重置循環(huán)的共軛梯度法計算結(jié)果ABCx1x2fx1x2fx1x2f-1.200G-.993-.657-.409-.241-.112-.0030.010.191.287.390.504.636.792.9861.2491.4181.0001.071.275-.073-.227-.302-.335-.342-.327-.290-.226-.125.029.267.6491.3011.94310.7768.0456.9926.5646.3556.2246.1296.0485.9735.8935.8025.6895.5425.3405.0454.6024.18

45、6-1.200G-.993-.657-.409-.241G.059.289.582.767G.792.928.965.969G.9691.0001.0001.0001.071.275-.073-.227-.100.008.235.628.616.834.935.937.938.998.99910.7768.0456.9926.5646.3554.9794.5654.2834.0704.0444.0134.0014.0014.0014.0004.000-1.200G-.993-.657G-.49-.132G.837.833G.842.972G.9651.000G1.0001.0001.071.2

46、75.346-.098.681.688.694.926.930.999.99910.7768.0456.9926.3325.4164.0304.0284.0274.0044.0014.0004.000第73頁/共130頁浙江大學(xué)研究生學(xué)位課程744.6 牛頓過程及變度量法Newton-Raphson 迭代把函數(shù)f(x)在第k次近似解 xk 附近進(jìn)行Taylor展開： xxfxfxxJxxxxxfxfxfkkTkkTkk之極小點：求記21第74頁/共130頁浙江大學(xué)研究生學(xué)位課程75 考查下例可能奇異。收斂到鞍點。有些問題可能發(fā)散，或斂。是二次函數(shù)，則一步收若收斂階為收斂快。迭代格式。這就是即k

47、kkkkkkkkkkkkxiiJiviiixfiiiraphsonNewtonxfJxxxfxJxJxxJxfxfnifxf. 20, 2 , 1011第75頁/共130頁浙江大學(xué)研究生學(xué)位課程76 稍有增加。出發(fā)的第一步，函數(shù)值從極小點支配。的二次函數(shù)受到極小點，因為其附近斂更接近鞍點，但它卻收雖比小點；受極小點影響收斂到極鞍點；在鞍點的影響下收斂到所示。見圖出發(fā)的幾條極小化路徑方法分別從應(yīng)用設(shè)CivACiiiBiiAiCBARaphoonNewtonxxxxxxxxxxf27. 4,44292222121222122141第76頁/共130頁浙江大學(xué)研究生學(xué)位課程77ACB1x2x圖圖 4

48、.27 初值對初值對Newton-Raphson 方法的影響方法的影響第77頁/共130頁浙江大學(xué)研究生學(xué)位課程78 下降法避免收斂到極大點。斂可能性。加快收斂速度和增加收其優(yōu)點有：極小化。使這里進(jìn)是：這個方法一個有效的改一個鞍點是該函數(shù)的極值點為：iiixfffkk1493. 1,6117. 05134. 0028. 1,053. 19855. 0854. 3,941. 1kkkkkxfJxx11第78頁/共130頁浙江大學(xué)研究生學(xué)位課程79然而這個方法的致命弱點是要計算Jk-1。4.2提供的辦法，即迭代若干次修改一次Jk-1，是一種方案。但不是最好的。 變量的尺度變換變量的尺度變換為改變函

49、數(shù)的偏心程度，從而改變極小化方法的收斂性質(zhì)，采用變量替換是個 很好的措施。 212121222144414484144xxxxxxxxxfT例：第79頁/共130頁浙江大學(xué)研究生學(xué)位課程80 多。的極小化方法要穩(wěn)定得求此的偏心程度小得多。因比的等高線圖，顯然和比較得：作變換xfxfxfxfxfxxxxxxxxxxfxfxxxxT16161131,21001212121212221212121第80頁/共130頁浙江大學(xué)研究生學(xué)位課程811x2x2x1x圖圖 4.28 函數(shù)進(jìn)行尺度變換的效果函數(shù)進(jìn)行尺度變換的效果第81頁/共130頁浙江大學(xué)研究生學(xué)位課程82尺度變換尺度變換目的是把函數(shù)的偏心程度

50、降到最低限度（它放大或縮小各個坐標(biāo)），但并不能完全消除偏心問題。把尺度變換應(yīng)用于各種算法，都有一定效果。一般地一般地IATTTAxATTxcBxAxxnnTxTxTTTT使是正定的，則若則二次項為考慮極小化二次函數(shù)階矩陣。是非奇異的這里2121第82頁/共130頁浙江大學(xué)研究生學(xué)位課程83即變換后的二次函數(shù)偏心率為，它是圓。它用最速下降法一步可以達(dá)到極小點?，F(xiàn)在希望直接處理原來的函數(shù)，而定義一個算子。用它產(chǎn)生通過極小點的向量?？紤]這樣的：11ATTIATTTATIATTTTTT從Newton-Raphson 過程kkkkkxfJxx11第83頁/共130頁浙江大學(xué)研究生學(xué)位課程84變尺度法的基

51、礎(chǔ)。的方法思想將是一種收斂很好量變換的不過由此引出的有關(guān)度甚至是奇異的。這是困難的。有時是正定的。實際上但是我們要求。就可以顯著減小偏心率或如果得到近似的因此我們不用求，這個向量就是可知，對二次函數(shù)來說kkTkkTkkJJTTTJxfTTxfAh111,第84頁/共130頁浙江大學(xué)研究生學(xué)位課程85變尺度法變尺度法 DFP方法 BFGS方法 常用的度量是常用的度量是通過極小點。對于正定二次函數(shù)，它記方法的搜索方向是：而方向用這種度量得最速下降kkkkkkniiTxfAxfJhRaphsonNewtonxfhxxxx11122第85頁/共130頁浙江大學(xué)研究生學(xué)位課程86 kkTkkTkkTkk

52、kTxfhxxxxfxfxfOxfxfxfxfxfxOxxfxfxxf而下降方向是量是故最速下降法采用的度對充分小的量最速下降法所采用的度,222222第86頁/共130頁浙江大學(xué)研究生學(xué)位課程87 下的最速下降法。就是在新度量意義因此，由于是正定的，引進(jìn)度量設(shè)kkkkTkkTkkTkkTkkkkTxfAhxfAxfAAxfAxfAAxfAxfAAxfAxfAxfxfxfAxfAxxxA121111111112212121的最速下降法。牛頓法就是在新度量下第87頁/共130頁浙江大學(xué)研究生學(xué)位課程88度和性質(zhì)。速，并且保持一定的收斂來代替近似度量簡單的說，我們用一個）它也叫變矩陣法（變化的。另

53、外，是隨的度量矩陣度量變度量法的名稱是因為。度，又不要計算頓法的收斂速而變度量法既保持了牛。及其逆要計算二階偏導(dǎo)數(shù)矩陣速度，但是它牛頓法具有很好的收斂111211kkkkkkTkkkkJHMethodsMatrixVariablexJxJxxJJ第88頁/共130頁浙江大學(xué)研究生學(xué)位課程89 iikkvHHHHivhxxhxfhxfiiigHxfHhiikHRxiHHHHkkkkkkkkkkkkkkkkkkknkkkk轉(zhuǎn)：不滿足結(jié)束條件時令計算令求記正定矩陣取算法的步驟：修正值的產(chǎn)生又比較方便：而1,min:; 0,1110001第89頁/共130頁浙江大學(xué)研究生學(xué)位課程90 使之滿足上面等式

54、。構(gòu)造，故其中由中值定理，記擬牛頓性質(zhì)性，穩(wěn)定性。擬牛頓性質(zhì)，二次收斂的原則構(gòu)造1112110,2kkkkkkkkkkkkkkkkkjikkkkkkkkkHxgAxhxAxghxggggJxxfAxxxgggxfgiH第90頁/共130頁浙江大學(xué)研究生學(xué)位課程91 kkkkkkTkkkkkknnkkkxfxfHgHgxfxfkxfxfiiiAHAhhhniiDFPxgH對適當(dāng)小的正定時，總有故當(dāng)事實上，即穩(wěn)定性：軛的向量組，且共構(gòu)成到極小點，這就要求步達(dá)法至多用于凸二次函數(shù)時，算二次收斂性條件此式稱為擬牛頓方程1111121121, 2 , 1 , 0,第91頁/共130頁浙江大學(xué)研究生學(xué)位課

55、程92 kkkkkTkkTkTkTkkkkTkkTkkTkkkkTkkkkTkkkTkkkkkkkkkkkkkkkkkgHgHgqgxxqgqggqgHgxgHqgHxHgHxgHxgHHDFPHHHDFPHH,1:31可取為：這樣的即可。只要求令故條件：滿足要求方法。變度量方法。這里介紹種方法的不同，形成了各構(gòu)造具體構(gòu)造第92頁/共130頁浙江大學(xué)研究生學(xué)位課程93 謝如彪，姜培慶非線性數(shù)值分析，陳開周最優(yōu)化計算方法，詳細(xì)證明可參考：正定二次收斂性可以證明：變度量算法迭代公式。這就是得代入21, 3 , 21kHiiiDFPgHgHggHgxxxHHkkkTkTkTkkkkTkTkkkk第9

56、3頁/共130頁浙江大學(xué)研究生學(xué)位課程94 變尺度法變尺度法 Variable Matrix Methods 算法框圖：算法框圖：0,0誤差控制取初值nRx?00 xfgyes停0 xx 解noIHk0, 0:kkkkkkkhxfxfhxx011min:求一維極值得kkkgHh?11kkxfgyes停1kxx解?nk noyes1010nnggxxnokTkTkkkTkTkkkkkkkkkkkkkggxxxHHgHgggxxx111,1 kk圖圖 4.29 變尺度法算法框圖變尺度法算法框圖第94頁/共130頁浙江大學(xué)研究生學(xué)位課程95 89124124138598619212149581122

57、4171100117901721061712121761730176041738217261712176173817261752122642126421212236 ,126 ,12,4 , 2,2212310000001110220000000001212221HggHgxxfgxhxfgHhgxfxfxIHxfTTT故故得按精確一維搜索法不難而記首先計算之極小點。求取例：設(shè)第95頁/共130頁浙江大學(xué)研究生學(xué)位課程96 11211111121111311121833357357153986441189189813061744366986117121768912412413859861171

58、2176,17211791738117261110231112100,02,0113,211129212991729173817261729292129917121768912412413859861AHHgHgxbAcbAcxbAxxxfxfxfxgHhTT繼續(xù)計算下去，則其極小點為則寫成事實上，將的極小點。不難驗證此即故作一維搜索，得再循環(huán)一次：第96頁/共130頁浙江大學(xué)研究生學(xué)位課程97 ,5141kkkkkTkkTkkTkkkkkkTkkkkkTkkkTkkkkdcbagvgugHdxcvgHbxauvgHuxHHHuang個參數(shù)這個公式含有且滿足：其中：公式：族是一般的變度量算法主

59、要變度量算法的校正公式第97頁/共130頁浙江大學(xué)研究生學(xué)位課程98 數(shù)值穩(wěn)定性最好的。它是當(dāng)前變度量方法中公式：即得重要的，令族公式。即，令公式。即，令較重要的三種公式是：個獨立參數(shù)個關(guān)系式，故有但有kTkkkTkkkTkkTkkTkkkTkkkkkkkkkkkkgxgHggxHgxxgHxxHHBFGSdcbiiiBroydencbiiDFPbci1, 01,1, 01321第98頁/共130頁浙江大學(xué)研究生學(xué)位課程99 方性 法 質(zhì)牛頓法DFP（擬牛頓法）共軛梯度法（重置初值）二次終止性質(zhì)一步終止（=1）n 步(精確一維搜索)終止n步(精確一維搜索)終止收 斂fC(3)且有界凸，x0充分

60、接近 x*,k1fC(3)在 L(x0)上有界凸，L(x0)有界（精確一維搜索）fC(3)在 L(x0)上有界凸，L(x0)有界（精確一維搜索）局部收斂性同上二階收斂同上，且f(x)是Lipschitz 連續(xù)。超線性收斂。同上，超線性收斂優(yōu)缺點要計算二階偏導(dǎo)數(shù)計算量大。n 大時存貯量亦大計算量少，程序簡單；n 大時存貯量也大計算程序簡單，存貯量相對較小 稱水平集。注：,00 xfxfRxxLn表表4.5 各種方法比較各種方法比較第99頁/共130頁浙江大學(xué)研究生學(xué)位課程1004.7 （Simplex, Powell）大量的目標(biāo)函數(shù)是很復(fù)雜的，有時連解析式都沒有，因而它的導(dǎo)數(shù) f(x)很難求，有