快捷導(dǎo)航

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

更新時間：2022年03月15日 10:07:31 作者：別團(tuán)等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ū)間中任取兩點x_1、x₂,通過比較函數(shù)f(x)在這兩點的函數(shù)值或者導(dǎo)數(shù)值等，來決定去掉一部分區(qū)間[a,x_1?]或者[x₂?,b],從而使搜索區(qū)間長度變小，如此迭代，直至區(qū)間收縮為一點為止，或區(qū)間長度小于某給定的精度為止。

對于區(qū)間[a,b]上的單峰函數(shù)f(x)，可以在其中任意選取兩點x₁?、x_2?，通過比較這兩點的函數(shù)值，就可以將搜索區(qū)間縮小。比如說，如果f(x₁?)<f(x₂?)，則選取[a₁?,b₁?]=[a,x₂?]，如果f(x₁?)> f(x_2?)，則選取[a_1?,b₁?]=[x₁?,b]，如果f(x₁?)=f(x₂)，則選取[a₁?,b₁?]=[x₁?,x₂?]，這樣就得到f(x)的更小的搜索區(qū)間[a₁?,b₁?]，然后根據(jù)這一方法再進(jìn)行劃分,得到一系列搜索區(qū)間滿足

于是對事先給定的某個精度ε,當(dāng)

時，可以將f(x)的最小值點近似地取為

單峰函數(shù)與搜索區(qū)間的定義如下：

如何選取x1和x2才能使得算法的效率更高？

這里推導(dǎo)過程不在詳細(xì)討論，直接給出滿足對稱取點、等比收縮和單點計算三個原則的分點。

或者

2、黃金分割法

算法描述如下：

這個算法非常理想，整個迭代過程中。除最初計算分點時使用過一次乘法外，后邊的分點全部都由加減法完成，并且每次迭代只需計算一個分點的函數(shù)值。但是，在實際應(yīng)用中，該方法存在一定的缺陷。這種缺陷主要來源于無理數(shù)(-1+√5)/2的取值。這里我們只取了小數(shù)點后三位數(shù)。因而有一定誤差，所以在迭代過程中，經(jīng)過多次累計，誤差就會很大，從而導(dǎo)致最終選取的兩點并不一定是我們所期望的那兩點，事實上，常常發(fā)生x2小于x1的情形。

為避免這種情況的出現(xiàn)，我們也可以通過將無理數(shù)(-1+√5)/2小數(shù)點后面的位數(shù)提高來避免算法的這一缺陷。不過這樣做的效果未必很好。因為我們不知道在算法中到底要經(jīng)過多少次迭代，當(dāng)?shù)螖?shù)很大時，這種做法依然是不能奏效的。因此，我們在程序中每次計算分點時不得不根據(jù)算法原理，使用一次乘法，即第二個分點不用加減法產(chǎn)生，而直接用乘法計算得出。由此即可避免累計誤差所帶來的缺陷。我們?nèi)约僭O(shè)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("迭代結(jié)束,迭代次數(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));
    }
}