Java實現(xiàn)黃金分割法的示例代碼
1、概述
黃金分割法是一種區(qū)間收縮方法。
所謂區(qū)間收縮方法,指的是將含有最優(yōu)解的區(qū)間逐步縮小,直至區(qū)間長度為零的方法。比如,為求函數(shù)f(x)在區(qū)間[a,b]上的最小值點,可在該區(qū)間中任取兩點x1、x2,通過比較函數(shù)f(x)在這兩點的函數(shù)值或者導數(shù)值等,來決定去掉一部分區(qū)間[a,x1?]或者[x2?,b],從而使搜索區(qū)間長度變小,如此迭代,直至區(qū)間收縮為一點為止,或區(qū)間長度小于某給定的精度為止。
對于區(qū)間[a,b]上的單峰函數(shù)f(x),可以在其中任意選取兩點x1?、x2?,通過比較這兩點的函數(shù)值,就可以將搜索區(qū)間縮小。比如說,如果f(x1?)<f(x2?),則選取[a1?,b1?]=[a,x2?],如果f(x1?)> f(x2?),則選取[a1?,b1?]=[x1?,b],如果f(x1?)=f(x2),則選取[a1?,b1?]=[x1?,x2?],這樣就得到f(x)的更小的搜索區(qū)間[a1?,b1?],然后根據(jù)這一方法再進行劃分,得到一系列搜索區(qū)間滿足
于是對事先給定的某個精度ε,當
時,可以將f(x)的最小值點近似地取為
單峰函數(shù)與搜索區(qū)間的定義如下:
如何選取x1和x2才能使得算法的效率更高?
這里推導過程不在詳細討論,直接給出滿足對稱取點、等比收縮和單點計算三個原則的分點。
或者
2、黃金分割法
算法描述如下:
這個算法非常理想,整個迭代過程中。除最初計算分點時使用過一次乘法外,后邊的分點全部都由加減法完成,并且每次迭代只需計算一個分點的函數(shù)值。但是,在實際應用中,該方法存在一定的缺陷。這種缺陷主要來源于無理數(shù)(-1+√5)/2的取值。這里我們只取了小數(shù)點后三位數(shù)。因而有一定誤差,所以在迭代過程中,經過多次累計,誤差就會很大,從而導致最終選取的兩點并不一定是我們所期望的那兩點,事實上,常常發(fā)生x2小于x1的情形。
為避免這種情況的出現(xiàn),我們也可以通過將無理數(shù)(-1+√5)/2小數(shù)點后面的位數(shù)提高來避免算法的這一缺陷。不過這樣做的效果未必很好。因為我們不知道在算法中到底要經過多少次迭代,當?shù)螖?shù)很大時,這種做法依然是不能奏效的。因此,我們在程序中每次計算分點時不得不根據(jù)算法原理,使用一次乘法,即第二個分點不用加減法產生,而直接用乘法計算得出。由此即可避免累計誤差所帶來的缺陷。我們仍假設f(x)是區(qū)間[a,b]上的單峰函數(shù)。修改后的黃金分割法的計算框圖如下圖所示。
3、修改后的黃金分割算法
修改后的黃金分割算法如下:
4、編程實現(xiàn)修改后的黃金分割算法
用黃金分割法求函數(shù) f(x)=x³-12x-11在區(qū)間[0,10]上的最小值點,取ε=0.01。
import java.math.BigDecimal; /** * 黃金分割法測試 */ public class GoldenCut { public static final BigDecimal C=new BigDecimal("0.01"); public static BigDecimal end=null; /** *x^3-12x-11 * @param x 輸入?yún)?shù)x * @return x^3-12x-11 */ public static BigDecimal ComputeFx(BigDecimal x){ return x.pow(3).subtract(new BigDecimal("12").multiply(x)).subtract(new BigDecimal("11")) .setScale(10,BigDecimal.ROUND_HALF_EVEN); } /** * a+0.382*(b-a) * @param a * @param b * @return a+0.382*(b-a) */ public static BigDecimal Compute382(BigDecimal a,BigDecimal b){ return a.add(new BigDecimal("0.382").multiply(b.subtract(a))) .setScale(10,BigDecimal.ROUND_HALF_EVEN); } /** * a+0.618(b-a) * @param a * @param b * @return */ public static BigDecimal Compute618(BigDecimal a,BigDecimal b){ return a.add(new BigDecimal("0.618").multiply(b.subtract(a))) .setScale(10,BigDecimal.ROUND_HALF_EVEN); } /** * a+b-x1 * @param a * @param b * @param x1 * @return */ public static BigDecimal Subtractabx1(BigDecimal a,BigDecimal b,BigDecimal x1){ return a.add(b).subtract(x1) .setScale(10,BigDecimal.ROUND_HALF_EVEN); } //判斷是否滿足精度 b-a<C? public static boolean OK(BigDecimal a,BigDecimal b){ return b.subtract(a).compareTo(C) < 0; } //輸出最優(yōu)解 public static BigDecimal Success(BigDecimal a, BigDecimal b){ return (a.add(b)).divide(new BigDecimal("2")) .setScale(10,BigDecimal.ROUND_HALF_EVEN); } //修改后的黃金分割法 public static void goldenTest1(BigDecimal a,BigDecimal b){ System.out.println("初始化"); BigDecimal x1=Compute382(a,b); BigDecimal x2=Subtractabx1(a,b,x1); BigDecimal f1=ComputeFx(x1); BigDecimal f2=ComputeFx(x2); System.out.println("x1="+x1); System.out.println("x2="+x2); System.out.println("f1="+f1); System.out.println("f2="+f2); System.out.println("迭代區(qū)間如下:"); int count=0; //迭代次數(shù) while(!OK(a,b)){//只要不滿足精度就一直迭代 System.out.println("["+a+"\t,\t"+b+"]"); count++; //迭代次數(shù)+1 if(f1.compareTo(f2)==1){//f1>f2 a=x1; if(OK(a,b)){ //精度判斷 end = Success(a, b); break; }else{ f1=f2; x1=x2; x2=Compute618(a,b); f2=ComputeFx(x2); } }else{ b=x2; if(OK(a,b)){ end = Success(a, b); break; }else{ f2=f1; x2=x1; x1=Compute382(a,b); f1=ComputeFx(x1); } } } System.out.println("迭代結束,迭代次數(shù)"+count); } public static void main(String[] args) { BigDecimal a=new BigDecimal("0"); BigDecimal b=new BigDecimal("10"); goldenTest1(a,b); System.out.println("最優(yōu)解為x*="+end); System.out.println("f(x*)="+ComputeFx(end)); } }
由運行結果可以看到,迭代次數(shù)15次,最優(yōu)解為x*=2.0009942948,f(x*)=-26.9999940673。迭代區(qū)間如下:
可以證明,黃金分割法是線性收斂的。
到此這篇關于Java實現(xiàn)黃金分割法的示例代碼的文章就介紹到這了,更多相關Java黃金分割法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
Mybatis-plus使用注解 @TableField(exist = false)
這篇文章主要介紹了Mybatis-plus使用注解 @TableField(exist = false),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2021-03-03springboot-dubbo cannot be cast to問題及解決
這篇文章主要介紹了springboot-dubbo cannot be cast to問題及解決方案,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2023-04-04編碼實現(xiàn)從無序鏈表中移除重復項(C和JAVA實例)
如果不能使用臨時緩存,你怎么實現(xiàn)無序鏈表中移除重復項(?C和JAVA實例無序鏈表中移除重復項。2013-10-10BigDecimal的toString()、toPlainString()和toEngineeringString()區(qū)
使用BigDecimal進行打印的時候,經常會對BigDecimal提供的三個toString方法感到好奇,以下整理3個toString方法的區(qū)別及用法,需要的朋友可以參考下2023-08-08