欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實現(xiàn)黃金分割法的示例代碼

 更新時間:2022年03月15日 10:07:31   作者:別團等shy哥發(fā)育  
黃金分割法是一種區(qū)間收縮方法。所謂區(qū)間收縮方法,指的是將含有最優(yōu)解的區(qū)間逐步縮小,直至區(qū)間長度為零的方法。本文將用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ù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

最新評論