Fibonacci法.ppt

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

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

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

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

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