三章節(jié)一維搜索方法ppt課件

1、第三章一維搜索方法1kkkkxxa d采用數(shù)學(xué)規(guī)劃法求函數(shù)極值點的迭代計算：K+1次迭代的搜索方向搜索的最佳步長因子當(dāng)搜索方向 給定，求最佳步長kakd就是求一元函數(shù)的極值。1kkkkkf xf xa da稱為一維搜索。 是優(yōu)化搜索方法的基礎(chǔ)。求解一元函數(shù) 的極小點a*a，可用解析法。 12TTf xadf xadf xadG ad上式求的極值，即求導(dǎo)數(shù)為零。 212TTf xdf xd Gd *0TTdf xd Gd那么 *TTdfxd Gd 從上式看，需要求導(dǎo)進行計算，對于函數(shù)關(guān)系復(fù)雜的，解析法十分不便。數(shù)值法的基本思路：確定 的搜索區(qū)間，在不斷縮小區(qū)間，最終獲得近似值。*第二節(jié) 搜索區(qū)間

2、的確定和區(qū)間消去法原理一、確定搜索區(qū)間的外推法圖3-2 正向搜索的外推法圖3-3 反向搜索的外推法三、區(qū)間消去法原理)a 11f af b 11)b f af b 11)c f af b為了避免多計算函數(shù)值，將第三種情況合并到前兩種情況中。)a 11f af b 11)b f af b三、一維搜索方法的分類從前面的分析可知，每次縮短區(qū)間，只需要在區(qū)間內(nèi)在插入一點并計算其函數(shù)值。而插入點的位置，可以由不同的方法來確定。就形成了不同的一維搜索方法。一維搜索方法分類試探法插值法黃金分割法二次插值法第三節(jié)一維搜索的試探法最常用的一維搜索試探法是黃金分割法，又稱0.618法。要求插入點a1、a2的位置相

3、對于區(qū)間a,b兩端點具有對稱性。1abba2aaba除對稱要求外，黃金分割法還要求在保留下來的區(qū)間再插入一點所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。212210 0.618所謂的“黃金分割是指將一線段分成兩段的方法，使整段長與較長段的長度比值等于較長段與較短段的比值，即1: 1第四節(jié)一維搜索的插值方法假定要在某一區(qū)間內(nèi)尋找函數(shù)的極小點的位置，雖然沒有函數(shù)表達式，但能夠給出若干試驗點處的函數(shù)值。我們可以根據(jù)這些點處的函數(shù)值，利用插值的方法建立函數(shù)的近似表達式，進而求處函數(shù)的極小點，作為原來函數(shù)的極小點的近似值。這種方法稱作插值法，也稱函數(shù)逼近法。一、牛頓法切線法） 2000001

4、2ffff yf一維搜索函數(shù)，假定一給出極小點的一個較好的近似點0，因為一個連續(xù)可微的函數(shù)在極小點附近與一個二次函數(shù)很接近，因而，在 點附近用一個二次函數(shù) 迫近。0 10 求二次函數(shù) 的極小點作為 f極小點的新近似點1即0000ff0100ff依次繼續(xù)下去，可得牛頓法迭代公式：1kkkkff0,1,2,.k 牛頓法的幾何解釋：牛頓法的計算步驟：給定初始點 ，控制誤差 ，并令k=0。01計算kfkf2求1kkkkff3)假設(shè)1kkaa則求得近似解*1kaa，停止計算，否則作4。4令1kk轉(zhuǎn)1。優(yōu)點：收斂速度快。缺點：每一點都要進行二階導(dǎo)數(shù)，工作量大；要求初始點離極小點不太遠，否則有可能使極小化發(fā)

5、散或收斂到非極小點。二、二次插值拋物線法）利用123 yf a在單谷區(qū)間中 的函數(shù)值123fff，作出如下的二次插值多項式 2012Paaa它應(yīng)滿足條件210112111Paaayf（1）220122222Paaayf230132333Paaayf從極值的必要條件求得1220ppPaa12/2paa （2）（3）要求出系數(shù) 和 ，聯(lián)立方程組1）、（2）、（3）。1a2a2212322323a aaaaayy2211221212aaaaaayy2222222313121231122331aayaayaayaaaaaaa2313121232122331aayaayaayaaaaaaa 222222231312123122313121231/22paa