文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java实现黄金分割法的示例代码

2024-04-02 19:55

关注

1、概述

黄金分割法是一种区间收缩方法。

所谓区间收缩方法,指的是将含有最优解的区间逐步缩小,直至区间长度为零的方法。比如,为求函数f(x)在区间[a,b]上的最小值点,可在该区间中任取两点x1、x2,通过比较函数f(x)在这两点的函数值或者导数值等,来决定去掉一部分区间[a,x1​]或者[x2​,b],从而使搜索区间长度变小,如此迭代,直至区间收缩为一点为止,或区间长度小于某给定的精度为止。

对于区间[a,b]上的单峰函数f(x),可以在其中任意选取两点x1​、x2​,通过比较这两点的函数值,就可以将搜索区间缩小。比如说,如果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)的更小的搜索区间[a1​,b1​],然后根据这一方法再进行划分,得到一系列搜索区间满足

于是对事先给定的某个精度ε,当

时,可以将f(x)的最小值点近似地取为

单峰函数与搜索区间的定义如下:

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

这里推导过程不在详细讨论,直接给出满足对称取点、等比收缩和单点计算三个原则的分点。

或者

2、黄金分割法

算法描述如下:

这个算法非常理想,整个迭代过程中。除最初计算分点时使用过一次乘法外,后边的分点全部都由加减法完成,并且每次迭代只需计算一个分点的函数值。但是,在实际应用中,该方法存在一定的缺陷。这种缺陷主要来源于无理数(-1+√5)/2的取值。这里我们只取了小数点后三位数。因而有一定误差,所以在迭代过程中,经过多次累计,误差就会很大,从而导致最终选取的两点并不一定是我们所期望的那两点,事实上,常常发生x2小于x1的情形。

为避免这种情况的出现,我们也可以通过将无理数(-1+√5)/2小数点后面的位数提高来避免算法的这一缺陷。不过这样做的效果未必很好。因为我们不知道在算法中到底要经过多少次迭代,当迭代次数很大时,这种做法依然是不能奏效的。因此,我们在程序中每次计算分点时不得不根据算法原理,使用一次乘法,即第二个分点不用加减法产生,而直接用乘法计算得出。由此即可避免累计误差所带来的缺陷。我们仍假设f(x)是区间[a,b]上的单峰函数。修改后的黄金分割法的计算框图如下图所示。

3、修改后的黄金分割算法

修改后的黄金分割算法如下:

4、编程实现修改后的黄金分割算法

用黄金分割法求函数 f(x)=x³-12x-11在区间[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;

    
    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);
    }

    
    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);
    }

    
    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);
    }
    
    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;
    }
    //输出最优解
    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("迭代区间如下:");
        int count=0;    //迭代次数
        while(!OK(a,b)){//只要不满足精度就一直迭代
            System.out.println("["+a+"\t,\t"+b+"]");
            count++;    //迭代次数+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("迭代结束,迭代次数"+count);
    }
    public static void main(String[] args) {
        BigDecimal a=new BigDecimal("0");
        BigDecimal b=new BigDecimal("10");

        goldenTest1(a,b);
        System.out.println("最优解为x*="+end);
        System.out.println("f(x*)="+ComputeFx(end));
    }
}

由运行结果可以看到,迭代次数15次,最优解为x*=2.0009942948,f(x*)=-26.9999940673。迭代区间如下:

可以证明,黄金分割法是线性收敛的。

到此这篇关于Java实现黄金分割法的示例代码的文章就介绍到这了,更多相关Java黄金分割法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯