最優(yōu)化方法的應(yīng)用

1、最優(yōu)化方法 姓名 張 炯學號 201200144423一、一維搜索方法的分類為了每次縮短區(qū)間，只需要在區(qū)間內(nèi)再插入一點并計算其函數(shù)值。然而，對于插入點的位置，是可以用不同的方法來確定的。 黃金分割法 一類稱作解析法或函數(shù)逼近法：構(gòu)造一個插值函數(shù)來逼近原來函數(shù)，用插值函數(shù)的極小點作為區(qū)間的插入點 牛頓法、二次插值法等黃金分割法黃金分割法要求插入點a1、a2的位置相對于原區(qū)間a,b的兩端點具有對稱性，即黃金分割法的搜索過程2 出初始搜索區(qū)間a,b及收斂精度e，將l賦以0.618按前頁中坐標點比例公式計算a1和a2 ，并計算其對應(yīng)的函數(shù)值f(aa1)和f（a2)。 比較函數(shù)值，利用進退法縮短搜索區(qū)間

2、檢查區(qū)間是否縮短到足夠小和函數(shù)值是否收斂到足夠近，如果條件不滿足則返回到步驟如果條件滿足則取最后兩試驗點的平均值作為極小點的數(shù)值近似值黃金分割法程序框圖牛頓法對于一維搜索函數(shù)，假定已給出極小點的一個較好的近似點a0，因為一個連續(xù)可微的函數(shù)在極小點附近與一個二次函數(shù)很接近，所以可以在a0點附近用一個二次函數(shù)來逼近函數(shù)，即在點a0將f(a)進行泰勒展開，并保留到二次項，有然后以二次函數(shù)的極小點作為極小點的一個新近似點，根據(jù)極值必要條件 得得牛頓法的計算步驟給定初始點a0，控制誤差e，令k=0計算f(x)在ak點的一階和二階導數(shù)利用牛頓法迭代公式求ak+1若|ak+1-ak|e，則求得近似解a*=a

3、k+1，停止計算，否則作第步令k=k+1，然后轉(zhuǎn)第步牛頓法的優(yōu)缺點最大優(yōu)點是收斂速度快缺點每一點處都要計算函數(shù)的導數(shù)和二階導數(shù)，因而增加了每次迭代的工作量用數(shù)值微分代替二階導數(shù)時，舍入誤差會影響牛頓法的收斂速度，當二階導數(shù)很小時問題更嚴重牛頓法要求初始點選得比較好，即不能離極小點太遠，否則在可能使極小化序列發(fā)散或收斂到非極小點二次插值法二次插值法又稱拋物線法，它的基本思路是：在尋求函數(shù)f()極小點的搜索區(qū)間內(nèi)，取三個點的函數(shù)值來構(gòu)造一個二次插值多項式p(),用它的極小點（第四個點）近似地作為原目標函數(shù)的極小點。若近似程度不滿足精度要求時，可以反復使用此法，從四個點中選取三個點，使函數(shù)值呈現(xiàn)“高

4、-低-高”變化的前提下逐漸的縮短搜索區(qū)間，二次插值多項式的極小點就逼近原目標函數(shù)的極小點。二次插值法區(qū)間縮短的4種情況 二次插值法的流程圖二、牛頓迭代法詳解牛頓迭代法（Newton's method）又稱為牛頓-拉夫遜（拉弗森）方法（Newton-Raphson method），它是牛頓在17世紀提出的一種在實數(shù)域和復數(shù)域上近似求解方程的方法。牛頓迭代法（Newton's method）又稱為牛頓-拉夫遜（拉弗森）方法（Newton-Raphson method），它是牛頓在17世紀提出的一種在實數(shù)域和復數(shù)域上近似求解方程的方法。多數(shù)方程不存在求根公式，因此求精確根非常困難，甚

5、至不可能，從而尋找方程的近似根就顯得特別重要。方法使用函數(shù)f(x）的泰勒級數(shù)的前面幾項來尋找方程f(x) = 0的根。牛頓迭代法是求方程根的重要方法之一，其最大優(yōu)點是在方程f(x) = 0的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復根，此時線性收斂，但是可通過一些方法變成超線性收斂。另外該方法廣泛用于計算機編程中。設(shè)r是 的根，選取 作為r的初始近似值，過點 做曲線 的切線L，L的方程為 ，求出L與x軸交點的橫坐標 ，稱x1為r的一次近似值。過點 做曲線 的切線，并求該切線與x軸交點的橫坐標 ，稱 為r的二次近似值。重復以上過程，得r的近似值序列，其中， 稱為r的 次近似值，上式

6、稱為牛頓迭代公式。用牛頓迭代法解非線性方程，是把非線性方程 線性化的一種近似方法。把 在點 的某鄰域內(nèi)展開成泰勒級數(shù) ，取其線性部分（即泰勒展開的前兩項），并令其等于0，即 ，以此作為非線性方程 的近似方程，若 ，則其解為 ， 這樣，得到牛頓迭代法的一個迭代關(guān)系式： 。已經(jīng)證明，如果是連續(xù)的，并且待求的零點是孤立的，那么在零點周圍存在一個區(qū)域，只要初始值位于這個鄰近區(qū)域內(nèi)，那么牛頓法必定收斂。 并且，如果不為0, 那么牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結(jié)果的有效數(shù)字將增加一倍。1 軍人在進攻時常采用交替掩護進攻的方式，若在數(shù)軸上的點表示A，B兩人的位置，規(guī)定在前

7、面的數(shù)大于后面的數(shù)，則是A>B，B>A交替出現(xiàn)。但現(xiàn)在假設(shè)軍中有一個膽小鬼，同時大家又都很照顧他，每次沖鋒都是讓他跟在后面，每當前面的人占據(jù)一個新的位置，就把位置交給他，然后其他人再往前占領(lǐng)新的位置。也就是A始終在B的前面，A向前邁進，B跟上，A把自己的位置交給B（即執(zhí)行B = A），然后A 再前進占領(lǐng)新的位置，B再跟上，直到占領(lǐng)所有的陣地，前進結(jié)束。像這種兩個數(shù)一前一后逐步向某個位置逼近的方法稱為迭代法。迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過程，跟迭代法相對應(yīng)的是直接法（或者稱為一次解法），即一次性解決問題。迭代算法是用計算機解決問題的一種基本方法。它利用計算機運算

8、速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）重復執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值。利用迭代算法解決問題，需要做好以下三個方面的工作：一、確定迭代變量在可以用迭代算法解決的問題中，至少存在一個可直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。二、建立迭代關(guān)系式所謂迭代關(guān)系式，指如何從變量的前一個值推出其下一個值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通?？梢允褂眠f推或倒推的方法來完成。三、對迭代過程進行控制在什么時候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地執(zhí)行下去。迭代過程的控制

9、通常可分為兩種情況：一種是所需的迭代次數(shù)是個確定的值，可以計算出來；另一種是所需的迭代次數(shù)無法確定。對于前一種情況，可以構(gòu)建一個固定次數(shù)的循環(huán)來實現(xiàn)對迭代過程的控制；對于后一種情況，需要進一步分析得出可用來結(jié)束迭代過程的條件。關(guān)于牛頓迭代法有一個很典型的例子是斐波那契（Fibonacci）數(shù)列。斐波那契數(shù)列為：0、1、1、2、3、5、8、13、21、，即 fib=0; fib=1;fib(n)=fib(n-1)+fib(n-2) （當n>2時）。在n>2時，fib(n)總可以由fib(n-1)和fib(n-2)得到，由舊值遞推出新值，這是一個典型的迭代關(guān)系，所以我們可以考慮迭代算法

10、。int Fib(int n) /斐波那契（Fibonacci）數(shù)列if (n < 1）/*預防錯誤*/return 0;if (n = 1 | n = 2)/*特殊值，無需迭代*/return 1;int f1 = 1,f2 = 1,fn;/*迭代變量*/int i;for(i=3; i<=n; +i)/*用i的值來限制迭代的次數(shù)*/fn = f1 + f2; /*迭代關(guān)系式*/f1 = f2;/f1和f2迭代前進，其中f2在f1的前面f2 = fn;return fn;三、牛頓迭代法的程序?qū)崿F(xiàn)牛頓迭代法Matlab程序（帶下山因子）本文程序可用于求解線性和非線性方程組，在使用牛

11、頓迭代法的同時，加入了下山因子，加入下山因子后，對于初值的選取更為寬泛。使用方法：請將本文function所定義的函數(shù)存為m文件，將matlab路徑改為存儲newton函數(shù)的路徑，然后參照本文例子的格式定義變量、表達式、初值、收斂閾值、迭代次數(shù)后，輸入X=newton(f,x,x0,esp,N)即可求解。%例子syms x1 x2 x3%定義變量名稱f1=x1+x2+x3+3;f2=2*x1-x2-x3;f3=x1+2*x2-2*x3-3;%定義方程表達式（方程全都移到等號左邊的表達式）f=f1;f2;f3;x=x1;x2;x3;x0=0;0;0;%設(shè)定初值esp=0.00001;0.0000

12、1;0.00001;%閾值N=1000;%迭代次數(shù)X=newton(f,x,x0,esp,N)%求解%真值為-1 0 -2%function x1=newton(f,x,x0,esp,N)%此函數(shù)用于解非線性方程，方法為牛頓下山法。R=jacobian(f,x);ph=size(f,1);ty(1:ph,1)=1;coo=1;while abs(coo-1)<1e-6%這代表coo=1 coo=0;R1=subs(R,x,x0);%f1=subs(f,x,x0);x1=x0-ty.*(R1f1);f11=subs(f,x,x1);f12=double(f1);f112=double(f11);for i=1:size(f12,1); j=