Fibonacci法.ppt

1、斐波那契法和二次插值法,小組成員：王娜 王慧紅 郭茜茜 解悅 曹文彥 蘇鵬,應(yīng)用領(lǐng)域： （1）可以用斐波那契數(shù)列的尋優(yōu)方法來(lái)計(jì)算交流電機(jī)驅(qū)動(dòng) 系統(tǒng)的效率，該方法的突出特點(diǎn)是與損耗模型無(wú)關(guān)，并能 使系統(tǒng)快速達(dá)到效率最大工作點(diǎn). （2）從運(yùn)籌學(xué)的斐波那契法來(lái)論述波浪理論，也可以從斐 波那契法的最優(yōu)分劃點(diǎn)來(lái)掌握波浪理論中的最佳投資. （3）插值法是現(xiàn)代數(shù)值計(jì)算的重要工具,是一種求解一元函 數(shù)極小點(diǎn)問(wèn)題最優(yōu)解的可行高效的方法,它的算法與連續(xù)平 均法和精確線性搜索計(jì)算精度高，收斂速度快. （4）二次插值在科技和生活應(yīng)用中有重要作用，比如理論 進(jìn)行信號(hào)處理的方法中,可以大大提高處理精度并節(jié)省數(shù)據(jù) 存儲(chǔ)空間

2、;求常規(guī)項(xiàng)目的內(nèi)部收益率該方法具有超線性收斂 速度.,4.1 Fibonacci法,這種方法與0.618法類似，也是用于單峰函數(shù)， 在計(jì)算過(guò)程中，也是第1次迭代需要計(jì)算兩個(gè)迭代點(diǎn)， 以后每次迭代只需新算一點(diǎn)，另一點(diǎn)取自上次迭代。 Fibonacci法與0.618法的主要區(qū)別在于:探索區(qū) 間長(zhǎng)度的縮短率不是采用黃金分割數(shù)，而是采用所 謂的Fibonacci數(shù),計(jì)算函數(shù)值的次數(shù)n也是已知的。,前節(jié)內(nèi)容：在逐次縮短區(qū)間時(shí)， 為第 k 次迭代的區(qū)間縮短率，對(duì)于 不外乎兩種情形：或者 為常數(shù)，這就是0.618法；或者 不為常數(shù)，這就是本節(jié)要講的Fibonacci法。,Fibonacci數(shù)： 數(shù)列 滿足條

3、件： 即 則稱 為Fibonacci數(shù)列,Fibonacci法的推導(dǎo)過(guò)程： (1)與黃金分割法一樣,設(shè)初始區(qū)間 上有唯一的極小值 點(diǎn)，規(guī)定一共算n次函數(shù)值，取試探點(diǎn) ， 并設(shè) 若 最小值點(diǎn)在 若 最小值點(diǎn)在 區(qū)間長(zhǎng)度為 區(qū)間長(zhǎng)度為,時(shí)，并在,的情形下，不影響我們的計(jì)算。,注意：,從而可知不論哪種情形都是將原區(qū)間長(zhǎng)度 變成新區(qū)間長(zhǎng)度 (2)如果新的區(qū)間為 ，我們將取兩個(gè)插入點(diǎn)為 我們自然希望會(huì)有下面情況之一發(fā)生： 因?yàn)槿绻l(fā)生一種，我們就又得到每迭代一次只計(jì)算一個(gè) 函數(shù)值的算法.下面用直接驗(yàn)證來(lái)解決這個(gè)問(wèn)題.,若 則有 注意:此時(shí)有 在 內(nèi)，由 的公式知道 剛好與 一致. 若 則 注意：此時(shí)有

4、在 內(nèi).由 的公式知道,剛好與 一致，這就說(shuō)明了保留的一點(diǎn)確實(shí)與新的插入點(diǎn) 之一重合，新的區(qū)間長(zhǎng)度為 此時(shí)我們一共迭代了2次.,(3)按這樣的辦法取點(diǎn)，我們計(jì)算第K-1次迭代時(shí)，區(qū)間將變 成 保留的一點(diǎn)是 或 ，區(qū)間長(zhǎng)度應(yīng)是 并且兩式中一定成立一個(gè) 此時(shí)我們有Fibonacci法在迭代過(guò)程中計(jì)算試點(diǎn)的公式：,(4)在進(jìn)行第K次迭代前，取試探點(diǎn) , 時(shí)，令 時(shí)，令,從上述兩種情況可看出不論屬于哪種情形，迭代后的區(qū)間長(zhǎng) 度迭代前的區(qū)間長(zhǎng)度之比均為 利用上述比值，可以計(jì)算出經(jīng)n-1次迭代(k=n-1)所得到的區(qū) 間長(zhǎng)度 所以，只要給定初始區(qū)間長(zhǎng)度 及精度要求(最終區(qū)間長(zhǎng) 度)L，就可以求出計(jì)算函數(shù)值

5、的次數(shù)n(不包括初始區(qū)間端點(diǎn) 函數(shù)值的計(jì)算)，令 即,由此可確定出計(jì)算函數(shù)值的次數(shù)n. 注意： 由于第1次迭代計(jì)算兩個(gè)試探點(diǎn)，以后每次計(jì)算一個(gè)，這樣 經(jīng)過(guò)n-1次迭代就計(jì)算完n個(gè)試探點(diǎn).但是，在第n-1次迭代中 并沒(méi)有選擇新的試探點(diǎn)，根據(jù)試探點(diǎn)的公式我們必有 而 和 中的一個(gè)是取自n-2次迭代之后，這時(shí)已確定 出 ，在 的右邊或左邊取一點(diǎn)，令 其中辨別常數(shù),Fibonacci法計(jì)算步驟如下： (1)給定初始區(qū)間 和最終長(zhǎng)度L。求計(jì)算函數(shù)值的次數(shù) n,使 ，辨別常數(shù) 計(jì)算試探點(diǎn) 和 ， 計(jì)算函數(shù)值 和 (2)若 則轉(zhuǎn)步驟(3);若 ,則轉(zhuǎn)步驟(4) (3)令 ，計(jì)算試點(diǎn) 若 則轉(zhuǎn)步驟(6);否則，計(jì)算函數(shù)值 轉(zhuǎn)步驟(5) (4)令 ，計(jì)算試點(diǎn) 若 則轉(zhuǎn)步驟(6);否則，計(jì)算函數(shù)值 轉(zhuǎn)步驟(5),(5) 置 轉(zhuǎn)至步驟(2) (6) 令 計(jì)算 和 若 則令 若 則令 停止計(jì)算，極小點(diǎn)含于,例：用Fibonacci法解下列問(wèn)題： 初始區(qū)間 ，精度 解：