使用黃金分割法確定步長的牛頓法

1、沙理工大數(shù)學(xué)與計(jì)算科學(xué)學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)項(xiàng)目名稱使用黃金分割法確定步長的牛頓法所屬課程名稱最優(yōu)化方法實(shí)驗(yàn)類型算法編程實(shí)驗(yàn)日期201班級信學(xué)號姓名一、實(shí)驗(yàn)概述：【實(shí)驗(yàn)?zāi)康摹?1)掌握Matlab數(shù)值計(jì)算的基本方法；(2)掌握最速下降法；(3)掌握黃金分割法確定步長?！緦?shí)驗(yàn)原理】1.黃金分割法：一維搜索是解函數(shù)極小值的方法之一，其解法思想為沿某一已知方向求目標(biāo)函數(shù)的極小值點(diǎn)。一維搜索的解法很多，這里主要采用黃金分割法(0.618法)。該方法用不變的區(qū)間縮短率0.618代替斐波那契法每次不同的縮短率，從而可以看成是斐波那契法的近似，實(shí)現(xiàn)起來比較容易，也易于人們所接受。黃金分割法是用于一元函數(shù)f(x)在

2、給定初始區(qū)間a,b內(nèi)搜索極小點(diǎn)xmin的一種方法。它是優(yōu)化計(jì)算中的經(jīng)典算法，以算法簡單、收斂速度均勻、效果較好而著稱，是許多優(yōu)化算法的基礎(chǔ)，但它只適用于一維區(qū)間上的凸函數(shù)，即只在單峰區(qū)間內(nèi)才能進(jìn)行一維尋優(yōu)，其收斂效率較低。其基本原理是：依照“去劣存優(yōu)”原則、對稱原則、以及等比收縮原則來逐步縮小搜索區(qū)間。具體步驟是：在區(qū)間a,b內(nèi)取點(diǎn)：a1,a2把a(bǔ),b分為三段。如果f(a1)f(a2)，令a=a1,a1=a2,a2=a+0.618*(b-a);如果f(a1)23+21=01=0618所謂的“黃金分率廠是指將一線段分成兩段的方.法，使整成K與較長段的長度比值等于較長段與較短段的比曲，即:A=A:

3、(-A)算法流程圖：圖12.牛頓法：設(shè)f(x)是二次可微實(shí)函數(shù)，xkwRn,Hesse矩陣bf(xk)正定。在xk附近用二次Taylor展開近似f,f(xk+s)qtk)(s)=f(xkTs+f(xkfs+1sT2f(xk)s2s=x-xk,q(k*s)為f(x)的二次近似。將上式右邊極小化，便得：_.-4xk4t=xk-f(xk)1Vf(xk),這就是牛頓法的迭代公式。在這個公式里，步長因子=1。令Gk=2f(Xk)項(xiàng)=Vf(Xk),則上式也可寫成：1xki=xk-Gkgk顯然，牛頓法也可以看成在橢球范數(shù)|L下的最速下降法。事實(shí)上，對于f(Xk+s產(chǎn)f(Xk)+g：s,TSk是極小化問題mi

4、n猾的解。該極小化問題依賴于所取的范數(shù)，當(dāng)采取12范sRn閭數(shù)時，Sk=-gk,所得方法為最速下降法。當(dāng)采用橢球范數(shù)Uh時，W=-Gjgk,所得方法即為牛頓法。【實(shí)驗(yàn)環(huán)境】Windows7Matlab7.0二、實(shí)驗(yàn)內(nèi)容：【實(shí)驗(yàn)方案】算例：f(x1,x2)=x12+x22x1x210x14x2+60的極小值，00.001o要求：1、利用使用黃金分割法確定步長的牛頓法編寫一維搜索方法(含黃金分割法確定步長)；2、在使用共物梯度法梯度法進(jìn)行搜索時可以調(diào)用一維搜索方法?！緦?shí)驗(yàn)過程】1.黃金分割法程序流程圖1/?F-steplengtli=07336683bb=0T000001x01=7.99988(1

5、xtl=S.999869最后結(jié)毗解為,-xLI1=5.999869最小值為：迭央次數(shù)為：n=42Pressanykeytocontinue【實(shí)驗(yàn)小結(jié)】（收獲體會）這次實(shí)驗(yàn)，使戢優(yōu)化方法這門課的一些理論知識與實(shí)踐相結(jié)合，更加深刻了我對這門課的認(rèn)識，鞏固了我的理論知識。我個人得到了不少的收獲，一方面加深了我對課本理論的認(rèn)識，另一方面也提高r個人對于實(shí)際問題的解答能力。對于牛頓法和黃金分割法的原理與應(yīng)用有個深刻認(rèn)識，也將老師在課堂上的講解真正的融會貫通，這次的實(shí)驗(yàn)非常后意義.三、指導(dǎo)教師評語及成績：評語評語等級優(yōu)良中及格/、及格1.實(shí)驗(yàn)報(bào)告按時完成，字跡清楚，文字?jǐn)⑹隽鲿?，邏輯性?qiáng)2.實(shí)驗(yàn)方案設(shè)計(jì)合

6、理3.實(shí)驗(yàn)過程（實(shí)驗(yàn)步驟詳細(xì)，記錄完整，數(shù)據(jù)合理，分析透徹）4實(shí)驗(yàn)結(jié)論正確.成績：指導(dǎo)教師簽名：批閱日期：附錄1:源程序#include#include#include/原函數(shù)#definef(x1,x2)x1*x1+x2*x2-x1*x2-10*x1-4*x2+60梯度模#definetdm(x1,x2)sqrt(2*x1-x2-10)*(2*x1-x2-10)+(2*x2-x1-4)*(2*x2-x1-4)/x1的偏導(dǎo)數(shù)#defineG1(x1,x2)2*x1-x2-10/x2的偏導(dǎo)數(shù)#defineG2(x1,x2)2*x2-x1-4/一維搜索/進(jìn)退法求搜索區(qū)間constfloateps=

7、0.001;/eps為計(jì)算精度；doubleHJFC(doublex1,doubles1)(intk=1,i,j;doublea0=1,b0=0.5,a1,b1,a3,f3,y32,m,n,ak2,c;/a0為初始步長，b0為初始步長增量；a1,b1為進(jìn)退法確定的最終區(qū)間;a0=a0;a1=a0+b0;for(i=0;i2;i+)for(j=0;j2;j+)yij=x1j+ai*s1j;for(i=0;if1)while(k)(b0=2*b0;a2=a1+b0;for(j=0;jf1)(m=a0;n=a2;k=0;else(k=1;a1=a2;f1=f2;elsewhile(k)(b0=2*b

8、0;a2=a0-b0;for(j=0;jf0)(m=a2;n=a1;k=0;else(k=1;a0=a2;f0=f2;/黃金分割法求最佳步長a1=m;b1=n;a0=n-0.618*(n-m);a1=m+0.618*(n-m);for(i=0;i2;i+)for(j=0;j2;j+)yij=x1j+ai*s1j;for(i=0;i2;i+)fi=f(yi0,yi1);do(if(f0f1)(n=a1;a1=a0;f1=f0;a0=n-0.618*(n-m);for(j=0;j2;j+)y0j=x1j+a0*s1j;f0=f(y00,y01);else(m=a0;a0=a1;f0=f1;a1=m

9、+0.618*(n-m);for(j=0;jeps);ak2=(m+n)/2;returnak2;共輾梯度法voidmain()doublex2,s2,g4,bita,arph;arph/x數(shù)組為函數(shù)解白轉(zhuǎn)置矩陣；s數(shù)組為搜索方向的轉(zhuǎn)置矩陣；g數(shù)組為梯度轉(zhuǎn)置矩陣;為最優(yōu)步長；intk=1;/k為迭代次數(shù)；賦初值；printf(請輸入初始x1、x2:nn);scanf(%d%d,&x0,&x1);printf(過程如下：nn);g0=G1(x0,x1);g1=G2(x0,x1);while(tdm(x0,x1)eps)迭代終止準(zhǔn)則；if(k=1)s0=-g0;s1=-g1;bita=0;else

10、bita=(g0*g0+g1*g1)/(g2*g2+g3*g3);s0=-g0+bita*s0;s1=-g1+bita*s1;10arph=HJFC(x,s);x0=x0+arph*s0;x1=x1+arph*s1;g2=g0;g3=gi;g0=G1(x0,x1);g1=G2(x0,x1);printf(第次迭代：nn,k);printf(步長steplength=%ft,arph);printf(bb=%ftn,bita);printf(x0=%ftx1=%fnnn,x0,x1);k+;)k-;printf(最后結(jié)果為：n);printf(最優(yōu)解為：nx0=%fnx1=%fn最小值為：min=%fn迭代次數(shù)為：n=%dn,x0,x1,f(x0,x1),k);)附錄2:實(shí)驗(yàn)報(bào)告填寫說明1 .實(shí)驗(yàn)項(xiàng)目名稱：要求與實(shí)驗(yàn)教學(xué)大綱一致。2 .實(shí)驗(yàn)?zāi)康模耗康囊鞔_，要抓住重點(diǎn)，符合實(shí)驗(yàn)教學(xué)大綱要求。3 .實(shí)驗(yàn)原理：簡要說明本實(shí)驗(yàn)項(xiàng)目所涉及的理論知識。4 .實(shí)驗(yàn)環(huán)境：實(shí)驗(yàn)用的軟、硬件環(huán)境。5 .實(shí)驗(yàn)方案（思路、步驟和方法等）：這是實(shí)驗(yàn)報(bào)告極其重要的內(nèi)容。概括整個實(shí)驗(yàn)過程。對于驗(yàn)證性實(shí)驗(yàn)，要寫明依據(jù)何種原理、操作方法進(jìn)行實(shí)驗(yàn)，要寫明需要經(jīng)過哪幾個步驟來實(shí)現(xiàn)其操作。對于設(shè)計(jì)性和綜合性實(shí)驗(yàn)，在上述內(nèi)容基礎(chǔ)上還應(yīng)該畫出流程圖、設(shè)計(jì)思路和設(shè)計(jì)方法，再配以相應(yīng)的文字說明。對于創(chuàng)新