MATLAB黃金分割法課程論文

1、中南林業(yè)科技大學(xué)本科課程論文學(xué) 院： 理學(xué)院 專(zhuān)業(yè)年級(jí)： 14級(jí)信息與計(jì)算科學(xué)2班 學(xué)生姓名： 邱文林 學(xué) 號(hào)： 20144349 課 程： MATLAB程序設(shè)計(jì)教程 設(shè)計(jì)題目：基于MATLAB的黃金分割法 與拋物線插值法 指導(dǎo)教師： 龔志偉 2016年4月中文摘要 為了求解最優(yōu)化模型的最優(yōu)解，可使用基于MATLAB算法編程的黃金分割法與拋物線插值法，來(lái)實(shí)現(xiàn)求解的過(guò)程。黃金分割法是通過(guò)所選試點(diǎn)的函數(shù)值而逐步縮短單谷區(qū)間來(lái)搜索最優(yōu)點(diǎn)，利用迭代進(jìn)而得出結(jié)論。拋物線插值法亦稱(chēng)二次插值法，是一種多項(xiàng)式插值法，逐次以擬合的二次曲線的極小點(diǎn)，逼近原尋求函數(shù)極小點(diǎn)的一種方法。通過(guò)將MATLAB與最優(yōu)化問(wèn)題相

2、結(jié)合，不僅可以加深對(duì)黃金分割法、拋物線插值法的基本理解和算法框圖及其步驟的全面理解，也有利于幫助我們掌握MATLAB的使用方法。關(guān)鍵詞：MATLAB，黃金分割法，拋物線插值法，最優(yōu)解，迭代英文摘要In order to solve the optimization model of the optimal solution, using MATLAB algorithm based on the golden section method and the parabola interpolation method, to realize the process of solving. The

3、golden section method is used to search the most advantage through the function value of the selected pilot, which can be used to search for the most advantage. Parabolic interpolation method, also known as the two interpolation method, is a polynomial interpolation method, successive to fit the two

4、 curve of the minimum point, the original search function to find a very small point of the method. By combining MATLAB and optimization problems can not only deepen the comprehensive understanding of the golden section method, the parabola interpolation basic understanding and block diagram of the

5、algorithm and steps, but also conducive to help us to grasp the method of using MATLAB.Key words: MATLAB, golden section method, parabolic interpolation method, optimal solution, iteration目 錄1. 黃金分割法 21.1 算法原理21.2 算法步驟21.3黃金分割法算法框圖 32. 拋物線插值法42.1 算法原理42.2 算法步驟42.3 拋物線插值法算法框圖53. 算法的MATLAB實(shí)現(xiàn)63.1黃金分割法程

6、序代碼 63.2 實(shí)例驗(yàn)證63.3 誤差分析93.4 拋物線插值法程序代碼103.5 實(shí)例驗(yàn)證113.6 誤差分析123.7 黃金分割法與拋物線插值法的對(duì)比13參考文獻(xiàn)15引言為了對(duì)最優(yōu)化問(wèn)題進(jìn)行求解，為了更好的掌握MATLAB的運(yùn)用，本文主要介紹一維最優(yōu)化問(wèn)題的一維搜索法黃金分割法與拋物線插值法，利用MATLAB算法將其實(shí)現(xiàn)。黃金分割法也叫0.618法，它是一種基于區(qū)間收縮的極小點(diǎn)搜索算法，當(dāng)用進(jìn)退法確定搜索區(qū)間后，我們只知道極小點(diǎn)包含于搜索區(qū)間內(nèi)，但是具體是哪個(gè)點(diǎn)，無(wú)法得知。黃金分割法的思想很直接，既然極小點(diǎn)包含于搜索區(qū)間內(nèi)，那么可以不斷的縮小搜索區(qū)間，就可以使搜索區(qū)間的端點(diǎn)逼近到極小點(diǎn)。

7、拋物線插值法(parabolic interpolation met-hod)亦稱(chēng)二次插值法一種多項(xiàng)式插值法.逐次以擬合的二次曲線的極小點(diǎn)，逼近原尋求函數(shù)極小點(diǎn)的一種方法,能求得精度較高的解，但速度會(huì)比較慢。時(shí)至今日，經(jīng)過(guò)Math Works公司的不斷完善，MATLAB已經(jīng)發(fā)展成為適合多學(xué)科、多種工作平臺(tái)的功能強(qiáng)勁的大型軟件。在國(guó)外，MATLAB已經(jīng)經(jīng)受了多年考驗(yàn)。在歐美等高校，MATLAB已經(jīng)成為線性代數(shù)、自動(dòng)控制理論、數(shù)理統(tǒng)計(jì)、數(shù)字信號(hào)處理、時(shí)間序列分析、動(dòng)態(tài)系統(tǒng)仿真等高級(jí)課程的基本教學(xué)工具；成為攻讀學(xué)位的大學(xué)生、碩士生、博士生必須掌握的基本技能。在設(shè)計(jì)研究單位和工業(yè)部門(mén)，MATLAB被廣

8、泛用于科學(xué)研究和解決各種具體問(wèn)題。1. 黃金分割法1.1 算法原理黃金分割法的基本原理：黃金分割法又稱(chēng)0.618法，它是通過(guò)不斷縮短搜索區(qū)間的長(zhǎng)度來(lái)尋求一維函數(shù)的極小點(diǎn)。這種方法的原理是：在搜索區(qū)間a, b內(nèi)按如下規(guī)則對(duì)稱(chēng)地取兩點(diǎn)：計(jì)算它們的函數(shù)值 f1=f(a1), f2=f(a2) ,比較它們的大小，結(jié)果有兩種可能：1.2 算法步驟（1）f1>f2,如圖1所示，極小點(diǎn)必在a1, b內(nèi)，消去區(qū)間a, a1), 令a=a1，產(chǎn)生新區(qū)間a, b,到此區(qū)間縮短了一次。值得注意的是新區(qū)間的a1點(diǎn)與原區(qū)間的a2點(diǎn)重合，可令a1=a2,這樣可少找一個(gè)新點(diǎn)和節(jié)省一次函數(shù)值計(jì)算。（2）f1<=f

9、2,極小點(diǎn)必在a, a2內(nèi)，消去區(qū)間 (a2,b,令b=a2,產(chǎn)生新區(qū)間a ,b,到此區(qū)間縮短了一次。同樣新區(qū)間a2點(diǎn)與原區(qū)間的a1點(diǎn)重合，可令a2=a1,f2<=f1。（3）當(dāng)縮短的新區(qū)間長(zhǎng)度小于等于某一精度，即b-a<=時(shí)，取a* =(a1+a2)/2。1.3黃金分割法算法框圖給定 a,b,ea+0.382(b-a) a1, f(a1) f1a+0.618(b-a) a2, f(a2) f2NYf1 > f2 ?a=a1 , a1 =a2 , f1 =f2a2 =a+0.618(b-a)f2 = f(a2)b=a2 ,a2 =a1 , f2= f1a1=a+0.382(b

10、-a)f1 = f(a1)結(jié)束輸出： a*=(a+b)/2NYb a < e?2. 拋物線插值法2.1 算法原理: 拋物線也叫二次插值法，其理論依據(jù)為二次多項(xiàng)式可以在最優(yōu)點(diǎn)附近較好的逼近函數(shù)的形狀，做法是在函數(shù)f(x)的最優(yōu)點(diǎn)附近取三個(gè)構(gòu)造點(diǎn)，然后用這三個(gè)點(diǎn)構(gòu)造一條拋物線，把這條拋物線的極值點(diǎn)作為函數(shù)f(x)的極值點(diǎn)的近似。每次構(gòu)造一條拋物線后，拋物線的極值點(diǎn)就可作為一個(gè)新的構(gòu)造點(diǎn)，新的構(gòu)造點(diǎn)與原來(lái)的三個(gè)構(gòu)造點(diǎn)經(jīng)過(guò)某種算法，得到下一步拋物線逼近的三個(gè)構(gòu)造點(diǎn)，這就是拋物線法的算法過(guò)程。 2.2 算法步驟：用拋物線求無(wú)約束問(wèn)題minf(x),xR的算法步驟如下： 確定初始區(qū)間a,b,選定初始

11、插值內(nèi)點(diǎn)t0(a,b)及精度e>0,令a0=a,b0=b,k=0; 求二次插值多項(xiàng)式的極小點(diǎn)：tk+1= . (2.10) 若f(tk+1) f(tk),則當(dāng)|tk+1 -tk|e時(shí)，停止迭代輸出tk+1;否則轉(zhuǎn); 若f(tk+1) f(tk),則當(dāng)|tk+1 -tk|e時(shí)，停止迭代輸出tk;否則轉(zhuǎn); 若tk+1 tk,令ak+1=ak,bk+1=tk,tk+1=tk+1;置k=k+1轉(zhuǎn),否則令ak+1=tk,bk+1=bk,tk+1=tk+1;置k=k+1轉(zhuǎn)。 若tk+1 tk,令 ak+1=tk+1,bk+1=tk,tk+1=tk;置k=k+1轉(zhuǎn),否則令ak+1=ak,bk+1=tk

12、+1,tk+1=tk;置k=k+1轉(zhuǎn)。初始插值內(nèi)點(diǎn)可以取搜索區(qū)間a, b的中點(diǎn)。2.3拋物線插值法算法框圖開(kāi)始確定tk,ak,bk,要求f(ak) f(tk),f(bk) f(tk)按（2.10）計(jì)算tk+1t*=tk+1 ,f*=f(tk+1)|tk+1 -tk|eYN輸出t*,f*Ntk+1tk ?結(jié)束Yf(tk+1) f(tk)?f(tk+1) f(tk) ?ak=tk+1,f(ak)=f(tk+1)YYbk=tk, tk=tk+1,f(bk)=f(tk),f(tk)=f(tk+1)ak=tk, tk=tk+1,f(ak)=f(tk),f(tk)=f(tk+1)bk =tk+1 ,f(b

13、k)=f(tk+1)3. 算法的MATLAB實(shí)現(xiàn)3.1 黃金分割法程序代碼在MATLAB中編程實(shí)現(xiàn)的黃金分割法函數(shù)為: golden。功能：用黃金分割法求解一維函數(shù)的極值。調(diào)用格式：tmin=golden(f,a,b,e)其中， f=目標(biāo)函數(shù)； a=極值區(qū)間左端點(diǎn)； b=極值區(qū)間右端點(diǎn)； e=精度； tmin=目標(biāo)取最小值時(shí)的自變量值；黃金分割法的MATLAB程序代碼如下：主程序：syms t a b e ;a=input('搜索區(qū)間第一點(diǎn) a=');b=input('搜索區(qū)間第二點(diǎn) b=');e=input('搜索精度ne=');disp(&#

14、39;需求的最優(yōu)化函數(shù) f=f(t),tmin=golden(f,a,b,e)'); m文件：function tmin=golden(f,a,b,e)format long;k=0;a1=b-0.618*(b-a);a2=a+0.618*(b-a);while b-a>e y1=subs(f,a1); y2=subs(f,a2);if y1>y2 a=a1; a1=a2; y1=y2; a2=a+0.618*(b-a);else b=a2; a2=a1; y2=y1; a1=b-0.618*(b-a);endk=k+1;endtmin=(a+b)/2;fmin=subs(

15、f,tmin)fprintf('k=n');disp(k);x=-3:0.001:5;y=x.*(x+2);plot(x,y,'k-',tmin,fmin,'bp');3.2 實(shí)例驗(yàn)證minf(t)=t*(t+2), 已知初始單谷區(qū)間a,b=-3,5,按精度e=0.001計(jì)算。代入到主程序代碼：搜索區(qū)間的第一點(diǎn) a=-3搜索區(qū)間的第二點(diǎn) b=5搜索精度e=0.001需求的最優(yōu)化函數(shù) f=f(t),tmin=golden(f,a,b,e)>> f=t*(t+2) f = t*(t + 2) >> tmin=golden(f,

16、a,b,e)k= 19tmin =>> fmin=tmin*(tmin+2)fmin = -0.999999985524973目標(biāo)函數(shù)的曲線圖如圖1-1所示:注： 圖中所標(biāo)識(shí)的點(diǎn)為黃金分割法所求的極小點(diǎn)。 圖1-1 函數(shù)f(t)=t(t+2)的曲線圖3.3 誤差分析:1. f(t)=t*(t+2) 的精確解如下：f=1,2,0;p=polyder(f);t1=roots(p)f1=polyval(f,t1)t1 = -1f1 = -1極小點(diǎn)誤差： e1=(tmin-t1)/t1=(-(-1)/(-1) 1e-4極小值誤差： e2=(f1-fmin)/f1=( -1 +0.99999

17、9985524973)/(-1) 1e-8結(jié)論：在精度e=0.001的情況下，通過(guò)黃金分割法經(jīng)過(guò)19次迭代，求得：tmin=,與精確值的誤差e1=1e-4<e=0.001,滿(mǎn)足題目要求，黃金分割法是正確的，也可預(yù)見(jiàn)，隨著精度e的提高，tmin的值會(huì)越來(lái)越接近極小點(diǎn)，最終會(huì)等于精確值-1.由圖1-1也可以看出，圖中所標(biāo)識(shí)的位置幾乎就在t=-1的位置上。3.4 拋物線插值法程序代碼在MATLAB中編程實(shí)現(xiàn)的拋物線法函數(shù)為: minPWX。功能：用拋物線插值法求解一維函數(shù)的極值。調(diào)用格式：x,minf=minPWX(f,a,b,e)其中， f:目標(biāo)函數(shù)； A:初始搜索區(qū)間左端點(diǎn)； b:初始搜索

18、區(qū)間右端點(diǎn)； e:精度； x:目標(biāo)取最小值時(shí)的自變量值； minf:目標(biāo)函數(shù)的最小值。拋物線法的MATLAB程序代碼如下：function x,minf=minPWX(f,a,b,e)%目標(biāo)函數(shù)：f;%初始搜索區(qū)間左端點(diǎn)：a;%初始搜索區(qū)間右端點(diǎn)：b;%精度：e;%目標(biāo)函數(shù)取最小值時(shí)的自變量值: x;%目標(biāo)函數(shù)的最小值: minf format long;if nargin = 3 e=1.0e-3;endt0=(a+b)/2;k=0;tol=1; while tol>e fa=subs(f,findsym(f),a); %區(qū)間左端點(diǎn)函數(shù)值 fb=subs(f,findsym(f),b)

19、; %區(qū)間右端點(diǎn)函數(shù)值 ft0=subs(f,findsym(f),t0); %內(nèi)插點(diǎn)函數(shù)值 tu=fa*(b2-t02)+fb*(t02-a2)+ft0*(a2-b2); td=fa*(b-t0)+fb*(t0-a)+ft0*(a-b); t1=tu/2/td;%插值多項(xiàng)式的極小點(diǎn) ft1=subs(f,findsym(f),t1); %插值多項(xiàng)式的極小值 tol=abs(t1-t0); if ft1<=ft0 if t1<=t0 b=t0; t0=t1; else a=t0; t0=t1; end k=k+1; else if t1<=t0 a=t1; else b=t1; end k=k+1; endendx = t1;minf= subs(f,findsym(f),x);format short; 3.5 實(shí)例驗(yàn)證 用拋物線法求函數(shù)f(t)=t*(t+2)，已知初始單谷區(qū)間a,b=-3,5,按精度e=0.001計(jì)算。解： 在MATLAb 命令窗口中輸入：>> syms t;>> f=t*(t+2);>> tmin,fmin=minPWX(f,-3,5)tmin =-1fmin = -1目標(biāo)函數(shù)的曲線圖如圖1-2所示:注： 圖中O所標(biāo)識(shí)的點(diǎn)為拋物線插值法