第二節(jié)單因素方法

第二節(jié)單因素方法第一頁，共十九頁，2022年，8月28日進(jìn)一步取點(diǎn)逐步縮小包含x*的區(qū)間范圍，利用有限次計(jì)算，使區(qū)間壓縮。問題：計(jì)算n次函數(shù)值，能把區(qū)間縮小到什么程度？找尋一個(gè)標(biāo)準(zhǔn)。aa1x*b1byxaa1x*b1bxy第二頁，共十九頁，2022年，8月28日設(shè)Fn為計(jì)算n次函數(shù)值能把區(qū)間縮小為單位區(qū)間的最大原區(qū)間的長度。稱為斐波那契數(shù)。F0=F1=1，F(xiàn)2=2，F(xiàn)3=3有遞推公式為：Fn=Fn-1+Fn-2。由此可得：計(jì)算n次函數(shù)值，壓縮區(qū)間的總壓縮率為：第三頁，共十九頁，2022年，8月28日斐波那契數(shù)1202年倫納德·斐波那契提出了這樣一個(gè)問題：假定一對兔子每個(gè)月都生一對新的兔子，新生的兔子隔一個(gè)月后就開始生育，其次，假定兔子都沒有死亡。這樣第一個(gè)月是F1=1，第二個(gè)月沒有生，F(xiàn)2=1；第三個(gè)月生了一對兔子，F(xiàn)3=2（老兔及第一對兔子）；第四個(gè)月，F(xiàn)4=3（老兔、第一、二對兔子）；第五個(gè)月，F(xiàn)5=5（老兔、第一、二、三對兔子及第一對兔子生的兔孫）；…這樣形成的數(shù)列稱為斐波那契數(shù)列。n01234567891011121123581321345589144233第四頁，共十九頁，2022年，8月28日第一次壓縮的壓縮率為：第二次壓縮的壓縮率為：第n次壓縮的壓縮率為：第五頁，共十九頁，2022年，8月28日利用壓縮率欲將原區(qū)間[a0,b0]壓縮為原長的δ倍，需計(jì)算幾次函數(shù)值？第六頁，共十九頁，2022年，8月28日斐波那契法的步驟：（1）確定試點(diǎn)個(gè)數(shù)n，令Fn>1/δ,查表確定試點(diǎn)個(gè)數(shù)n。（2）選取前兩個(gè)試點(diǎn)的位置第七頁，共十九頁，2022年，8月28日它們在區(qū)間的位置是對稱的。（3）計(jì)算函數(shù)值和,并比較它們的大小。第八頁，共十九頁，2022年，8月28日（4）計(jì)算或,如（3）步迭代。計(jì)算試點(diǎn)的一般公式為：第九頁，共十九頁，2022年，8月28日計(jì)算n次函數(shù)值，就可以達(dá)到預(yù)定的壓縮率。第十頁，共十九頁，2022年，8月28日0.618法利用斐波那契法壓縮區(qū)間壓縮率依次為：將數(shù)列分為可證這兩個(gè)數(shù)列收斂于同一極限。設(shè)k→∞時(shí)，若則λ=μ。又遞推公式得第十一頁，共十九頁，2022年，8月28日又因?yàn)閷ⅲ?）代入（2）中得：第十二頁，共十九頁，2022年，8月28日將斐波那契法中每次壓縮的不同的壓縮率都用0.618來代替，每次壓縮的壓縮率相同，簡化了求試點(diǎn)的計(jì)算，這種方法稱為0.618法。其遞推公式為：若給定，令求滿足條件的最小的n。第十三頁，共十九頁，2022年，8月28日牛頓法一原理：構(gòu)造函數(shù)逼近于已知函數(shù)，其最優(yōu)解也逼近于所求函數(shù)的最優(yōu)解。設(shè)y=f(x)在[a,b]區(qū)間是下單峰函數(shù)，在點(diǎn)處存在。構(gòu)造函數(shù)該函數(shù)是二次拋物線函數(shù)，且與f(x)共有一點(diǎn)可逼近于f(x)，以的極小點(diǎn)作為f(x)的極小點(diǎn)的近似

值。現(xiàn)求的極小點(diǎn)，有第十四頁，共十九頁，2022年，8月28日如果這個(gè)近似值不到預(yù)先給定的精確度，就在點(diǎn)構(gòu)造函數(shù)并求極小點(diǎn)，這樣繼續(xù)下去，逐步逼近f（x）的極小點(diǎn)，直到到達(dá)給定精確度為止。二牛頓法運(yùn)算步驟：（1）已知給定精確度ε>0。任取若則為的近似解即是f(x)的最優(yōu)解。（2）若則算出若則停止，為的近似解即是f(x)的最優(yōu)解。第十五頁，共十九頁，2022年，8月28日（3）一般地，若迭代至點(diǎn)，已知時(shí)為近似解，若令迭代直到滿足精確度為止。例1求函數(shù)在區(qū)間[3，4]上的最小值,精度=0.05。解：任取

故即是近似最優(yōu)解。第十六頁，共十九頁，2022年，8月28日拋物線法：一原理：利用構(gòu)造擬合（逼近）函數(shù)的方法，與牛頓法原理相同，但方法不同。設(shè)函數(shù)f(x)的三點(diǎn)x1<x2<x3，函數(shù)值(或試驗(yàn)結(jié)果)分別為y1,y2,y3。利用(x1,y1)、(x2,y2)、(x3,y3)擬合一條拋物線,使得：滿足條件的函數(shù)為：Φ(x)=

第十七頁，共十九頁，2022年，8月28日Φ(x)與f(x)擬合（共用三點(diǎn)）求Φ(x)的最小值點(diǎn)，得：二拋物線法的計(jì)算步驟：（1）選三個(gè)點(diǎn)x1<x2<x3,使其函數(shù)值之間關(guān)系為：

構(gòu)造Φ(x),并求其最小值。驗(yàn)證是否是f(x)的最優(yōu)解。（2）若第十八頁，共十九頁，2022年，8月28日(1)f(x4)≤f(x2)，則以（x2，x4，x3）為新的三點(diǎn)繼續(xù)迭代。(2)f(x2)<f(x4)≤f(x3)