5.優(yōu)化設(shè)計講稿

1、5 優(yōu)化設(shè)計1.優(yōu)化、優(yōu)化設(shè)計和機械優(yōu)化設(shè)計的含義優(yōu)化是萬物演化的自然選擇和必然趨勢。優(yōu)化作為一種觀念和意向，人類從很早開始就一直在自覺與不自覺地追求與探索。而優(yōu)化作為一門學科與技術(shù)，則是一切科學與技術(shù)所追求的永恒主題，旨在從處理各種事物的一切可能的方案中，尋求最優(yōu)的方案。優(yōu)化的原理與方法，在科學的、工程的和社會的實際問題中的應(yīng)用，便是優(yōu)化設(shè)計。優(yōu)化設(shè)計是在現(xiàn)代計算機廣泛應(yīng)用的基礎(chǔ)上發(fā)展起來的一項新技術(shù)。是根據(jù)最優(yōu)化原理和方法，以人機配合方式或“自動探索”方式，在計算機上進行的半自動或自動設(shè)計，以選出在現(xiàn)有工程條件下的最佳設(shè)計方案的一種現(xiàn)代設(shè)計方法。 優(yōu)化設(shè)計反映出人們對于設(shè)計規(guī)律這一客觀世界

2、認識的深化。（1）來源：優(yōu)化一語來自英文Optimization，其本意是尋優(yōu)的過程；（2）優(yōu)化過程：是尋找約束空間下給定函數(shù)取極大值（以max表示)或極小(以min表示)的過程。優(yōu)化方法也稱數(shù)學規(guī)劃，是用科學方法和手段進行決策及確定最優(yōu)解的數(shù)學； （3）優(yōu)化設(shè)計：根據(jù)給定的設(shè)計要求和現(xiàn)有的技術(shù)條件，應(yīng)用專業(yè)理論和優(yōu)化方法，在電子計算機上從滿足給定的設(shè)計要求的許多可行方案中，按照給定的目標自動地選出最優(yōu)的設(shè)計方案。（4）機械優(yōu)化設(shè)計 就是把機械設(shè)計與優(yōu)化設(shè)計理論及方法相結(jié)合，借助電子計算機，自動尋找實現(xiàn)預期目標的最優(yōu)設(shè)計方案和最佳設(shè)計參數(shù)。 工程設(shè)計中，設(shè)計者力求尋求一種合理的設(shè)計參數(shù)，以使得

3、由這組設(shè)計參數(shù)方法：進行最優(yōu)化設(shè)計時，首先必須將實際問題加以數(shù)學描述，形成一組由數(shù)學表達式組成的數(shù)學模型，然后選擇一種最優(yōu)化數(shù)值計算方法和計算機程序，在計算機上運算求解，得到一組由數(shù)學表達式組成的設(shè)計參數(shù)。這組設(shè)計參數(shù)就是設(shè)計的最優(yōu)解。2.優(yōu)化設(shè)計的發(fā)展概況歷史上最早記載下來的最優(yōu)化問題可追溯到古希臘的歐幾里得（Euclid，公元前300年左右），他指出：在周長相同的一切矩形中，以正方形的面積為最大。十七、十八世紀微積分的建立給出了求函數(shù)極值的一些準則，對最優(yōu)化的研究提供了某些理論基礎(chǔ)。然而，在以后的兩個世紀中，最優(yōu)化技術(shù)的進展緩慢，主要考慮了有約束條件的最優(yōu)化問題，發(fā)展了變分法。 直到本世紀

4、40年代初，由于軍事上的需要產(chǎn)生了運籌學，并使優(yōu)化技術(shù)首先應(yīng)用于解決戰(zhàn)爭中的實際問題，例如轟炸機最佳俯沖軌跡的設(shè)計等。 50年代末數(shù)學規(guī)劃方法被首次用于結(jié)構(gòu)最優(yōu)化，并成為優(yōu)化設(shè)計中求優(yōu)方法的理論基礎(chǔ)。數(shù)學規(guī)劃方法是在第二次世界大戰(zhàn)期間發(fā)展起來的一個新的數(shù)學分支，線性規(guī)劃與非線性規(guī)劃是其主要內(nèi)容。最優(yōu)化設(shè)計是在數(shù)學規(guī)劃方法的基礎(chǔ)上發(fā)展起來的，是6O年代初電子計算機引入結(jié)構(gòu)設(shè)計領(lǐng)域后逐步形成的一種有效的設(shè)計方法。利用這種方法，不僅使設(shè)計周期大大縮短，計算精度顯著提高，而且可以解決傳統(tǒng)設(shè)計方法所不能解決的比較復雜的最優(yōu)化設(shè)計問題。大型電子計算機的出現(xiàn)，使最優(yōu)化方法及其理論蓬勃發(fā)展，成為應(yīng)用數(shù)學中的一

5、個重要分支，并在許多科學技術(shù)領(lǐng)域中得到應(yīng)用。近十幾年來，最優(yōu)化設(shè)計方法已陸續(xù)用到建筑結(jié)構(gòu)、化工、冶金、鐵路、航天航空、造船、機床、汽車、自動控制系統(tǒng)、電力系統(tǒng)以及電機、電器等工程設(shè)計領(lǐng)域，并取得了顯著效果。其中在機械設(shè)計方面的應(yīng)用雖尚處于早期階段，但也已經(jīng)取得了豐碩的成果。一般說來，對于工程設(shè)計問題，所涉及的因素愈多，問題愈復雜，最優(yōu)化設(shè)計結(jié)果所取得的效益就愈大。l 第一階段人類智能優(yōu)化：與人類史同步，直接憑借人類的直覺或邏輯思維，如黃金分割法、窮舉法和瞎子爬山法等。l 第二階段數(shù)學規(guī)劃方法優(yōu)化：從三百多年前牛頓發(fā)明微積分算起，電子計算機的出現(xiàn)推動數(shù)學規(guī)劃方法在近五十年來得到迅速發(fā)展。l 第三

6、階段工程優(yōu)化：近二十余年來，計算機技術(shù)的發(fā)展給解決復雜工程優(yōu)化問題提供了新的可能，非數(shù)學領(lǐng)域?qū)＜议_發(fā)了一些工程優(yōu)化方法，能解決不少傳統(tǒng)數(shù)學規(guī)劃方法不能勝任的工程優(yōu)化問題。在處理多目標工程優(yōu)化問題中，基于經(jīng)驗和直覺的方法得到了更多的應(yīng)用。優(yōu)化過程和方法學研究，尤其是建模策略研究引起重視，開辟了提高工程優(yōu)化效率的新的途徑。l 第四階段現(xiàn)代優(yōu)化方法：如遺傳算法、 模擬退火算法、 蟻群算法、 神經(jīng)網(wǎng)絡(luò)算法等，并采用專家系統(tǒng)技術(shù)實現(xiàn)尋優(yōu)策略的自動選擇和優(yōu)化過程的自動控制，智能尋優(yōu)策略迅速發(fā)展。機械優(yōu)化設(shè)計應(yīng)用實例美國波音飛機公司對大型機翼用138個設(shè)計變量進行結(jié)構(gòu)優(yōu)化，使重量減少了三分之一；大型運輸艦用

7、10個變量進行優(yōu)化設(shè)計，使成本降低約10%。實踐證明，最優(yōu)化設(shè)計是保證產(chǎn)品具有優(yōu)良的性能，減輕自重或體積，降低產(chǎn)品成本的一種有效設(shè)計方法。同時也可使設(shè)計者從大量繁瑣和重復的計算工作中解脫出來，使之有更多的精力從事創(chuàng)造性的設(shè)計，并大大提高設(shè)計效率。51 優(yōu)化設(shè)計的數(shù)學模型511 數(shù)學模型的建立 數(shù)學模型：是對實際問題的數(shù)學描述和概括，是進行優(yōu)化設(shè)計的基礎(chǔ)。工程設(shè)計問題通常是相當復雜的，要建立便于求解的數(shù)學模型，必須對實際問題加以適當?shù)某橄蠛秃喕２煌暮喕椒ǖ玫降臄?shù)學模型和計算結(jié)果都不同。例5.1有一塊邊長為6m的正方形鋁板，四角各裁去一個小的方塊，做成一個無蓋的盒子。試確定裁去的四個小方塊的

8、邊長，以使做成的盒子具有最大的容積。解：設(shè)裁去的四個小方塊邊長為x，盒子的容積可表示成x的函數(shù)，上述問題可描述成求變量x，使函數(shù)極大化，這就是此問題的數(shù)學模型，其中x稱為設(shè)計變量；稱為目標函數(shù)。目標函數(shù)試設(shè)計變量的一元三次函數(shù)，且沒有附加的約束條件，所以此問題屬于一元非線性無約束優(yōu)化設(shè)計問題。512 數(shù)學模型的一般形式 數(shù)學模型的組成：優(yōu)化設(shè)計的數(shù)學模型由設(shè)計變量、目標函數(shù)和約束條件三部分組成，可寫成以下統(tǒng)一形式： 求變量 使極小化函數(shù) 滿足約束條件 不等式約束條件 等式約束條件數(shù)學模型可寫成以下向量形式：向量表示設(shè)計變量，表示向量X屬于n維實歐氏空間，用min、max表示極小化和極大化， ）

9、表示“滿足于”，m,p分別表示不等式約束和等式約束的個數(shù)。 （可省略） 不等式約束條件 等式約束條件分類：最優(yōu)化問題也稱為數(shù)學規(guī)劃問題。最優(yōu)化問題根據(jù)數(shù)學模型中是否包含約束條件而分為無約束優(yōu)化問題和約束優(yōu)化問題；根據(jù)設(shè)計變量的多少可分為單變量優(yōu)化和多變量優(yōu)化問題；根據(jù)目標函數(shù)和約束函數(shù)的性質(zhì)可分為線性規(guī)劃和非線性規(guī)劃問題。 當數(shù)學模型中的目標函數(shù)和約束函數(shù)均為設(shè)計變量的線性函數(shù)時，稱此設(shè)計問題為線性優(yōu)化問題或線性規(guī)劃問題。當目標函數(shù)和約束函數(shù)中至少有一個為非線性函數(shù)時，稱此設(shè)計問題為非線性優(yōu)化問題或非線性規(guī)劃問題。 513 設(shè)計變量與設(shè)計空間工程問題特征參數(shù)設(shè)計方案。這種代表設(shè)計方案的特征參數(shù)

10、一般應(yīng)選作該問題優(yōu)化設(shè)計的設(shè)計變量。一個工程問題的設(shè)計參數(shù)一般是相當多的，其中包括常量、獨立變量和因變量三類。優(yōu)化設(shè)計時，為了使建立的數(shù)學模型盡量簡單易解，只能選擇其中的獨立變量作為設(shè)計變量。但是，一個設(shè)計問題中，獨立變量和因變量的劃分并不是一成不變的。設(shè)計變量選擇：選擇那些與目標函數(shù)和約束函數(shù)密切相關(guān)的、能夠表達設(shè)計對象特征的獨立參數(shù)和尺寸。同時，還要兼顧求解的精度和復雜性方面的要求。設(shè)計變量分為連續(xù)變量和離散變量，可以在實數(shù)范圍內(nèi)連續(xù)取值的變量稱為連續(xù)變量，只能在給定數(shù)列或集合中取值的變量稱為離散變量。幾乎所有的優(yōu)化理論和方法都是針對連續(xù)變量提出來的，而實際問題往往包含有各種各樣的離散變量

11、，對于包含離散變量的優(yōu)化問題，一般先將離散變量當作連續(xù)變量，求出連續(xù)變量最優(yōu)解后，在作適當?shù)碾x散化處理。 由線性代數(shù)可知，若n個設(shè)計變量相互獨立，則由它們形成的向量的全體集合構(gòu)成一個n維實歐氏空間，稱為設(shè)計空間，記作，一組設(shè)計變量可看作設(shè)計空間中的一點，稱為設(shè)計點。設(shè)計變量的個數(shù)n稱為設(shè)計空間的維數(shù)。 5.1.4 約束條件與可行域約束：對任何設(shè)計都有若干不同的要求和限制，將這些要求和限制表示成設(shè)計變量的函數(shù)并寫成一系列不等式和等式表達式，就構(gòu)成了設(shè)計的約束條件，簡稱約束。約束條件的作用：是對設(shè)計變量的取值加以限制。約束條件分類：根據(jù)形式分為不等式約束和等式約束，根據(jù)性質(zhì)可分為邊界約束和性能約束

12、。邊界約束實對設(shè)計變量本身所加的直接限制；性能約束在形式上是對某些技術(shù)性能指標或參數(shù)所加的限制，是對設(shè)計變量所加的間接限制。約束問題的可行域：每一個不等式或等式約束都將設(shè)計空間分為兩個部分，滿足所有約束的部分形成一個交集，該交集稱為此約束問題的可行域，記作。5.1.5 目標函數(shù)與等值線要尋求設(shè)計問題的最優(yōu)解就必須有判別設(shè)計方案好壞的尺度目標函數(shù)目標函數(shù)：是關(guān)于設(shè)計變量的函數(shù)，是用于衡量設(shè)計方案優(yōu)劣的定量標準。對極小化問題來說，目標函數(shù)的值越小，對應(yīng)的設(shè)計方案越好，目標函數(shù)的最小值及其對應(yīng)的設(shè)計變量的取值稱為設(shè)計問題的最優(yōu)解。 要知道一個目標函數(shù)的最優(yōu)點在設(shè)計空間中所處的位置，就需要了解目標函數(shù)

13、的變化規(guī)律。對于簡單的問題，等值線或等值面不僅可以直觀地描繪函數(shù)的變化趨勢，而且還可以直觀地給出極值點的位置。 令函數(shù)，滿足此式的點X在設(shè)計空間中定義了一個點集，當n=2，該點集是設(shè)計平面中的一條直線或曲線，當時，該點集是設(shè)計空間中的一個平面、曲面或超曲面。在這些線或面上所有點的函數(shù)值均相等，這些線或面就稱為函數(shù)的等值線或等值面。516 優(yōu)化問題的圖解法對簡單的二維優(yōu)化問題，可以在設(shè)計平面內(nèi)直觀地作出約束可行域，畫出目標函數(shù)的簇等值線，并且可以根據(jù)等值線與可行域的相互關(guān)系確定出最優(yōu)點的位置。這種求解優(yōu)化問題的方法就是圖解法。圖解法的步驟一般為：確定設(shè)計空間，作出約束可行域，畫出目標函數(shù)的一簇等

14、值線，最后判斷確定最優(yōu)點。 建立數(shù)學模型的一般過程：步驟名稱說明1分析設(shè)計問題，初步建立數(shù)學模型。    即使是同一設(shè)計對象，如果設(shè)計目標和設(shè)計條件不同，數(shù)學模型也會不同。因此，要首先弄清問題的本質(zhì)，明確要達到的目標和可能的條件，選用或建立適當?shù)臄?shù)學、物理、力學模型來描述問題。2抓住主要矛盾，確定設(shè)計變量。    設(shè)計變量越多，設(shè)計自由度就越大，越容易得到理想的結(jié)果。但隨著設(shè)計變量的增多，問題也隨之復雜。因此，應(yīng)抓住主要矛盾，適當忽略次要因素，合理簡化。3根據(jù)工程實際，提出約束條件。    約束條件的數(shù)目

15、多，則可行的設(shè)計方案數(shù)目就減少，優(yōu)化設(shè)計的難度增加。理論上講，利用一個等式約束，可以消去一個設(shè)計變量，從而降低問題的階次，但工程上往往很難做到設(shè)計變量是一定值常量，為了達到效果，總是千方百計使其接近一常量，反而使問題過于復雜化。另外，某些優(yōu)化方法不支持等式約束。因此，實際上利用等式約束需很慎重，尤其結(jié)構(gòu)優(yōu)化設(shè)計盡量少采用等式約束。4對照設(shè)計實例，修正數(shù)學模型。    初步建立模型之后，應(yīng)與設(shè)計問題加以對照，并對函數(shù)值域、數(shù)學精確度和設(shè)計性質(zhì)等方面進行分析，若不能正確、精確地描述設(shè)計問題，則需用逐步逼近的方法對模型加以修正。5正確求解計算，估價方法誤差。 

16、   如果數(shù)學模型的數(shù)學表達式比較復雜，無法求出精確解，則需采用近似的數(shù)值計算方法，此時應(yīng)對該方法的誤差情況有一個清醒的估計和評價。6進行結(jié)果分析，審查模型靈敏性。    數(shù)學模型求解后還應(yīng)進行靈敏度分析，也即在優(yōu)化結(jié)果的最優(yōu)點處，稍稍改變某些條件，檢查目標函數(shù)和約束條件的變化程度。若變化大，則說明靈敏性高，就需要重新修正數(shù)學模型。因為，工程實際中設(shè)計變量的取值不可能與理論計算結(jié)果完全一致，靈敏性高，可能對最優(yōu)值產(chǎn)生很大影響。5.2 優(yōu)化方法的數(shù)學基礎(chǔ) 工程設(shè)計一般歸結(jié)為多變量、多約束的非線性優(yōu)化問題，首先對多變量約束優(yōu)化問題的求解方法所涉及的

17、數(shù)學概念及有關(guān)理論進行補充和擴展。多元函數(shù)的梯度、二階導數(shù)矩陣和泰勒展開等基本概念，以及數(shù)值迭代解法的基本格式。5.2.1梯度函數(shù)在點的梯度是由函數(shù)在該點的各一階偏導數(shù)組成的向量函數(shù)的梯度的性質(zhì)：（1）函數(shù)在一點的梯度是一個向量。梯度的方向是該點函數(shù)值上升得最快的方向，與梯度相反的方向是該點函數(shù)值下降得最快的方向，梯度的大小就是它的模長。（2）一點的梯度方向 是與過該點的等值線或等值面的切線或切平面相垂直的方向，或說是該點等值線或等值面的法線方向。（3）梯度是函數(shù)在一點鄰域內(nèi)局部形態(tài)的描述。在一點上升得快的方向，離開該鄰域后就不一定上升的快，甚至可能下降。5.2.2 多元函數(shù)的泰勒展開為了便于

18、數(shù)學問題的分析和求解，需要將一個復雜的非線性函數(shù)簡化成線性函數(shù)或二次函數(shù)，簡化方法可以采用泰勒展開式。一元函數(shù)若在點的領(lǐng)域內(nèi)n階可導，則函數(shù)可在該點的領(lǐng)域內(nèi)作泰勒展開： 為余項多元函數(shù)在點作泰勒展開，取前三項：此式稱為函數(shù)的泰勒二次近似式。是有函數(shù)在點的所有二階偏導數(shù)組成的矩陣，稱為函數(shù)在點的二階導數(shù)矩陣由于n元函數(shù)的偏導數(shù)有個，而且偏導數(shù)的值與求導次序無關(guān)，所以函數(shù)的二階導數(shù)是一個階對稱矩陣。例5.4 用泰勒展開的方法將函數(shù)在點簡化成線性函數(shù)和二次函數(shù)。解：分別求函數(shù)在點的函數(shù)值、梯度和二階導數(shù)矩陣： =展開式的二次項： 5.2.3 二次函數(shù)二次函數(shù)是最簡單的非線性函數(shù)，在最優(yōu)化理論中具有重

19、要的意義。二次函數(shù)寫成向量形式：式中：B常數(shù)向量；H階常數(shù)矩陣稱為二次型，H稱為二次型矩陣，相當于函數(shù)的二階導數(shù)矩陣。矩陣有正定和負定之分，對于所有的非零向量X：（1）若有，則稱矩陣H是正定的；（2）若有，則稱矩陣H是半正定的；（3）若有，則稱矩陣H是負定的；（4）若有，則稱矩陣H是半負定的；（5）若有，則稱矩陣H不正定的；上式的二次型矩陣H是正定的，則函數(shù)稱正定二次函數(shù)。在最優(yōu)化理論中正定二次函數(shù)具有特殊的作用，因為許多優(yōu)化理論和優(yōu)化方法都是根據(jù)正定二次函數(shù)提出并加以證明的，而且正定二次函數(shù)適用并有效的優(yōu)化算法，對一般非線性函數(shù)也適用和有效。正定二次函數(shù)的性質(zhì)：（1）正定二次函數(shù)的等直線或等

20、值面是一簇同心橢圓或同心橢球，且橢圓簇或橢球簇的中心就是該二次函數(shù)的極小點。（2）非正定二次函數(shù)在極小點附近的等直線或等值面近似于橢圓或橢球。5.2.4 下降迭代算法工程設(shè)計問題一般可歸結(jié)為多變量、多約束的非線性優(yōu)化問題，這樣的問題一般只能用數(shù)值迭代法求解，對于極小化問題，這種方法就是下降迭代算法下降迭代算法：按照某一迭代格式，從一個初始點.出發(fā)逐步產(chǎn)生一個點列，若該點列所對應(yīng)的目標函數(shù)值呈下降趨勢，并且該點列的極限就是目標函數(shù)的極小點，則構(gòu)成此點列的方法就是優(yōu)化問題的一種數(shù)值解法，稱下降迭代算法。并稱此點列收斂于極小點。5241 下降迭代算法的基本格式在優(yōu)化算法中，一般采用如下迭代算式： (

21、5.9)式中 搜索方向； 步長因子。（1） 給定一個初始點和收斂精度；（2） 選取一個搜索方向；（3） 確定步長因子，按式5.9得到新的迭代點；（4） 收斂判斷：若滿足收斂精度，則以作為最優(yōu)點，終止計算；否則，以作為新的起點，轉(zhuǎn)(2)進行下一輪迭代。 由此不難看出，一個下降迭代算法的構(gòu)成需要解決以下三個基本問題 (1)選擇搜索方向。不同的搜索方向，構(gòu)成不同的下降迭代算法 (2)確定步長因子。一般通過一維搜索法取得最優(yōu)步長因子 (3)給定收斂準則。用以判斷迭代點是否能夠作為近似的最優(yōu)點。5242 算法的收斂性如前所述，當?shù)惴óa(chǎn)生的點列滿足式(58)時，稱該點列收斂于極小點，即稱此下降迭代算法

22、具有收斂性。點列向極小點逼近的速度稱該算法的收斂速度。作為一種優(yōu)化算法必須具有較好的收斂性和較快的收斂速度。沒有收斂性的算法在理論上是不能成立的，而收斂速度較慢的算法對于實際應(yīng)用來說也是沒有意義的。53 一維搜索法是優(yōu)化方法中最基本、最常用的方法。所謂搜索，就是一步一步的查尋，直至函數(shù)的近似極值點處。其基本原理是區(qū)間消去法原則，即把搜索區(qū)間a, b分成3段或2段，通過判斷棄除非極小段，從而使區(qū)間逐步縮小，直至達到要求精度為止，取最后區(qū)間中的某點作為近似極小點。概念：在優(yōu)化設(shè)計的迭代運算中，在搜索方向上尋求最優(yōu)步長的方法稱一維搜索法。其實，一位搜索法就是一元函數(shù)極小化的數(shù)值迭代算法，其求解過程稱

23、一維搜索。從點出發(fā)，在方向上的一維搜索的數(shù)學表達式： 此式表示對包含唯一變量的一元函數(shù)求極小值，得到最優(yōu)補償因子和方向上唯一的極小點方法：一維搜索的數(shù)值解法可分兩步進行。首先在方向上確定個包含極小點的初始區(qū)間，然后縮小區(qū)間或插值逼近的方法逐步得到最優(yōu)步長和維極小點。531 確定初始區(qū)間的進退法理論：在函數(shù)的任一單谷區(qū)間上必存在一個極小點，而且在極小點的左側(cè)，函數(shù)呈下降趨勢，在極小點的右側(cè)，函數(shù)呈上升趨勢。若方向上的三點 及其函數(shù)值，和，可通過比較三個函數(shù)值的大小估計出極小點所在的位置。（1） 若，則極小點位于右端點的右側(cè)；（2） 若，則極小點位于左端點的左側(cè)；（3） 若，則極小點位于和之間，就

24、是一個包含極小點的區(qū)間?？梢姡谀骋环较蛏习匆欢ǚ绞街鸫萎a(chǎn)生一些探測點，并比較這些探測點上函數(shù)值的大小，找出函數(shù)值呈“大小大”變化的三個相鄰點，其中兩個端點所確定的閉區(qū)間必定包含著極小點，這樣的區(qū)間稱初始區(qū)間，記作，這種尋找初始區(qū)間的方法稱進退法。方法：這種尋找初始區(qū)間的方法稱進退法，其具體探測步驟如下： (1)給定初始點，初始步長，； (2)產(chǎn)生新的探測點，； (3)比較函數(shù)值和的大小，確定向前或向后探測的策略。 若>，則加大步長人，令，轉(zhuǎn)(4)向前探測；若<，則調(diào)轉(zhuǎn)方向，令，轉(zhuǎn)(4)向后探測。(4)產(chǎn)生新的探測點，令；(5)比較函數(shù)值和的大??；若，則初始區(qū)間已經(jīng)得到，令，當時，

25、當時，若，則繼續(xù)加大步長，令，轉(zhuǎn)(4)向前探測。532 黃金分割法黃金分割法是采用黃金分割點（0.618）不斷縮小區(qū)間得到極小點的一維搜索算法?？s小區(qū)間采用序列消去法：在已知區(qū)間，任選兩個中間插入點和（），比較兩點的函數(shù)值：若，則根據(jù)單谷區(qū)間的性質(zhì)，極小點必在a和之間，于是消去區(qū)間，得到包含極小點的區(qū)間；若，則極小點必位于和b之間，消去區(qū)間，得到包含極小點的區(qū)間。不斷重復上述過程，將包含極小點的區(qū)間逐漸縮小，當區(qū)間長度b-a小于給定精度時，將區(qū)間內(nèi)的一點作為該方向上的極小點。不同的中間插入點產(chǎn)生不同的一維搜索算法，黃金分割法是其中常用的算法。設(shè)區(qū)間內(nèi)插入點和：，若縮小一次后的新區(qū)間為，由于新舊

26、區(qū)間內(nèi)中間插入點應(yīng)具有相同的位置關(guān)系，原區(qū)間內(nèi)的點和新區(qū)間內(nèi)的點實際上是同一個點：，解得：代入上式得：，黃金分割法以區(qū)間長度是否充分小作為收斂準則，并以收斂區(qū)間的中點作為一維搜索的極小點，即當時，取黃金分割法每次區(qū)間縮小的比率是完全相等的。如果將新區(qū)間的長度和原區(qū)間的長度之比稱作區(qū)間縮小率，則黃金分割法的區(qū)間縮小率等于常數(shù)0.618。如果給定收斂精度，初始區(qū)間長度b-a，則完成一維搜索所需縮小區(qū)間的次數(shù)n可以由下式求出：綜上所述，黃金分割法的計算步驟如(p165-166)：（1）給定初始區(qū)間和收斂精度（2）產(chǎn)生中間插入點并計算其函數(shù)值： （3）比較函數(shù)值和，確定區(qū)間的取舍：若，則新區(qū)間=，令，

27、記若，則新區(qū)間，令，記（4）收斂判斷：若區(qū)間的長度足夠小，即滿足，則將區(qū)間中點作為一維極小點，即令，結(jié)束一維搜索，否則轉(zhuǎn)（5）。（5）產(chǎn)生新的插入點：若，則??；若，則取，轉(zhuǎn)（3）進行新的區(qū)間縮寫。例5.5用黃金分割法求函數(shù)的極小點，給定。解：（1）確定初始區(qū)間： 由于，應(yīng)加大步長繼續(xù)向前探測。令由于，初始區(qū)間找到，即。（2）用黃金分割法縮小區(qū)間第一次縮小區(qū)間： 由于，故新區(qū)間。因為，所以應(yīng)繼續(xù)縮小空間。第二次縮小區(qū)間。令 由于，故新區(qū)間，因為，所以應(yīng)繼續(xù)縮小區(qū)間。第三次縮小區(qū)間。令由于，故新區(qū)間，因為，所以應(yīng)繼續(xù)縮小區(qū)間。第四次縮小區(qū)間。令由于，故新區(qū)間。因為，所以應(yīng)繼續(xù)縮小區(qū)間。第五次縮小區(qū)間。令由于，故新區(qū)間，所以得到極小點和極小值533 二次插值法二次插值法又稱拋物線法，它是以目標函數(shù)的二次插值函數(shù)的極小點作為新的中間插入點，進行區(qū)間縮小的一維搜索算法。在確定初始區(qū)間時得到相鄰的三個點及其對應(yīng)的函數(shù)值，記。在fox坐