ch4一維搜索方法

《ch4一維搜索方法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第4章一維搜索方法14.1一維搜索方法對(duì)n元函數(shù),給定點(diǎn)x(k),向量pk,則f(x)從x(k),出發(fā)沿方向pk的直線上函數(shù)值的變化可以表示為一元函數(shù):該函數(shù)只有一個(gè)變量,且每一個(gè)λ值都對(duì)應(yīng)著直線上一個(gè)點(diǎn)。求函數(shù)f(x)的解,就轉(zhuǎn)化為沿直線求一元函數(shù)的極小值點(diǎn),因此本節(jié)先介紹一元函數(shù)f(x)的極小問(wèn)題。2§4.2二分法當(dāng)f(x)連續(xù)可導(dǎo)時(shí),在極小點(diǎn)x*處有,因此求一元函數(shù)f(x)的極小值點(diǎn)問(wèn)題就轉(zhuǎn)化為求解方程的根的問(wèn)題。稱的點(diǎn)為函數(shù)f(x)的駐點(diǎn)。設(shè)根,且,則有算法3算法4.1(二分法)1．輸入a,b及

2、精度ε>0。2.3．若或,輸出x*=x。否則轉(zhuǎn)4。4．求,若,則,否則5．輸出超過(guò)最大迭代次數(shù)的信息,停機(jī)。4§4.3Newton法假設(shè)f(x)二階連續(xù)可導(dǎo),對(duì)在xk處展開(kāi)為T(mén)aylor公式由此有迭代公式：算法4.2(Newton法求的根)1．對(duì);做到第6步。2．3．若d=0停止計(jì)算。4．計(jì)算5．若或,輸出x,停機(jī)。6．7．若迭代N0次后仍達(dá)不到精度要求,停機(jī)。5定義4.4.1設(shè)f(x):[a,b]→R若存在點(diǎn)x*∈(a,b)使f(x)在[a,x*]上是單調(diào)減小,在[x*,b]上是單調(diào)增加,則稱[a,b

3、]是f(x)的單峰區(qū)間。f(x)是[a,b]上的單峰函數(shù)如圖所示。其中圖(a),圖(c)是單峰函數(shù),圖(b)不是單峰函數(shù)。(a)(b)(c)6§4.40.618法(黃金分割法)假設(shè)f(x)是單峰函數(shù),但不知道極小點(diǎn)x*的位置。任取x1,x2∈[a,b],且x1f(x2)此時(shí)x*>x1,即x*∈[x

4、1,b]見(jiàn)圖(c)。為計(jì)算方便可將情況(1)歸結(jié)到情況(2)或情況(3)。為了尋找x*,在初始區(qū)間[a1,b1]內(nèi)任取兩點(diǎn);且,通過(guò)比較函數(shù)值,從而確定極小點(diǎn)x*是在或者[x1,b1]內(nèi)。取小區(qū)間代替[a1,b1]得新的x*的存在區(qū)間,記為[a2,b2],又任取且,通過(guò)比較函數(shù)值得新的小區(qū)間[a3,b3]·······x*的存在區(qū)間不斷縮小,最后便可確定出近似的極小點(diǎn),為了節(jié)省計(jì)算函數(shù)值的工作量,永遠(yuǎn)保證新區(qū)間的一個(gè)端點(diǎn)和原區(qū)間的一個(gè)端點(diǎn)重合。8設(shè)每次迭代的區(qū)間長(zhǎng)度按比例α縮小(0<α<1),設(shè)第k次迭

5、代后的區(qū)間為[ak,bk],則第k+1次的區(qū)間為或取不妨設(shè),經(jīng)迭代后包含極小點(diǎn)的區(qū)間為為了進(jìn)一步縮短此區(qū)間,取xk+1和且,9取同理,若可得相同的結(jié)論,故有定義4.4.2若實(shí)數(shù)滿足則稱為黃金分割數(shù),黃金分割數(shù)在單位長(zhǎng)度區(qū)間中對(duì)應(yīng)的點(diǎn)稱為黃金分割點(diǎn)。10算法4.3(0.618法)給定初值,誤差1．計(jì)算2．若,得最優(yōu)解,否則轉(zhuǎn)3。3．若則,轉(zhuǎn)4;若則,轉(zhuǎn)5;若則,轉(zhuǎn)1。4．計(jì)算,轉(zhuǎn)2。5．計(jì)算,轉(zhuǎn)2。1112§4.5Fibonacci法(分?jǐn)?shù)法)該方法也適用于單峰函數(shù),與0.618法的區(qū)別是每次迭代區(qū)間長(zhǎng)度

6、的縮短。不是按常數(shù)比率進(jìn)行而是由Fibonacci數(shù)確定的,而且可以預(yù)先確定迭代次數(shù)。定義4.5.1設(shè)數(shù)列{Fn}滿足稱數(shù)列{Fn}為Fibonacci數(shù)列,Fn為第n個(gè)Fibonacci數(shù),相鄰兩個(gè)Fibonacci數(shù)之比Fn-1/Fn稱為Fibonacci分?jǐn)?shù)。如下表：n01234567Fn1123581321Fn-1/Fn11/22/33/55/88/1513/2113用數(shù)學(xué)歸納法可以證明且設(shè)第k次迭代時(shí)的區(qū)間為[ak,bk],取14容易驗(yàn)證且當(dāng)時(shí),令。有當(dāng)時(shí),令。有特別當(dāng)k=n-1時(shí)有15由此可

7、知,只要給定了初始區(qū)間b1-a1的長(zhǎng)度和精度要求ε,就可計(jì)算出迭代的次數(shù)此時(shí)為了能在第n-1次迭代中使區(qū)間縮短,可在第n-2次迭代后在的右邊或左邊取一點(diǎn),令且16算法4.4(Fibonacci方法)(1)給定初始區(qū)間[a,b]和誤差要求ε>0,(2)(3)若,轉(zhuǎn)(4);否則轉(zhuǎn)(2)。(4)17(5)若轉(zhuǎn)(6);若轉(zhuǎn)(7)。(6)若k=n-2則轉(zhuǎn)(9);否則計(jì)算f(x)轉(zhuǎn)(8)。(7)若k=n-2則轉(zhuǎn)(9);否則計(jì)算f(x)轉(zhuǎn)(8)。(8),轉(zhuǎn)(5)。(9),若,則;否則(10)輸出例4.1分別用二分法、

8、Newton法、0.618法求解解:取精度,初值Newton法的迭代公式為：計(jì)算結(jié)果如下表18迭代次數(shù)二分法Newton法02.252.2511.8752.071428622.06252.008403431.968752.000137842.01562551.992187562.003906271.998361882.00113991.99975040.618法的計(jì)算結(jié)果如下表20迭代次數(shù)[ak,bk]xkf(xk)0[0,3]1.1458