黄金分割算法（算法分析+python代码解释）

在上期，分析过成功-进退法之后，这期我们来看看另一种区间收缩法——黄金分割法（0.618算法）

背对人潮

2030人浏览 · 2023-10-22 17:39:19

背对人潮 · 2023-10-22 17:39:19 发布

在上期，分析过成功-进退法之后，这期我们来看看另一种区间收缩法——黄金分割法（0.618算法）

成功-失败算法（算法分析+python代码解释）https://blog.csdn.net/m0_61209712/article/details/133940690?spm=1001.2014.3001.5501 所谓区间收缩方法，指的是将含有最优解的区间逐步缩小，直至区间长度为零的方向。比如，为求函数 $f(x)$ 在区间[a，b]上的最小值点，可在该区间中任取两点 $x_{1},x_{2},$ 通过比较函数 $f(x)$ 在这两点的函数值或者导数值，来决定去掉一部分区间[a, $x_{1}$ ]或者[ $x_{2}$ ，b]，从而使搜索区间长度变小，如此迭代，直至区间收缩为某一点为止，或区间长度小于某给定的精度为止。

算法分析：

设 $f(x)$ 在[ $a_{1}$ ， $b_{1}$ ]上单峰，极小点 $\bar{x}$ $\in$ [ $a_{1}$ ， $b_{1}$ ]，又设进行第K次迭代时，有 $\bar{x}$ $\in$ [ $a_{k}$ ， $b_{k}$ ]为缩短包含极小点 $\bar{x}$ 的区间，取两个试探点λk，μk $\in$ [ $a_{k}$ ， $b_{k}$ ]，并规定λk $<$ μk，并计算函数值f(λk)，f(μk)，

若f(λk) $>$ f(μk)，则有 $\bar{x}$ $\in$ [λk， $b_{k}$ ]，因此令： $a_{k+1}$ = λk， $b_{k+1}$ = $b_{k}$ ；
若f(λk) $<$ f(μk)，则有 $\bar{x}$ $\in$ [ $a_{k}$ ，μk]，因此令： $a_{k+1}$ = $a_{k}$ ， $b_{k+1}$ = μk；

现在确定λk和μk，使其满足：

$b_{k}$ - λk = μk - $a_{k}$

$b_{k+1}$ - $a_{k+1}$ = α（ $b_{k}$ - $a_{k}$ ）

由此得出计算公式：

λk = $a_{k}$ + （1-α）（ $b_{k}$ - $a_{k}$ ）

μk = $a_{k}$ + α（ $b_{k}$ - $a_{k}$ ）

由此可以看出，在上述规定下，当α取某个数值时，每次迭代，只需再选择一个试探点，从而节省了计算量。

设在k次迭代中，有f（λk） $\leq$ f（μk），经迭代后含极小值的区间[ $a_{k+1}$ ， $b_{k+1}$ ] = [ $a_{k}$ ，μk]

为进一步缩短此区间，需要取试探点λk+1，μk+1，则有

μk+1 = $a_{k+1}$ + α（ $b_{k+1}$ - $a_{k+1}$ ）= $a_{k}$ + α（μk - $a_{k}$ ） = $a_{k}$ + α^2（ $b_{k}$ - $a_{k}$ ）

与下面式子比较：

λk = $a_{k}$ + （1-α）（ $b_{k}$ - $a_{k}$ ）

若令α^2 = 1 - α，则有μk+1 = λk，因此μk+1不必重新计算

$\Rightarrow$ α = （-1+ $\sqrt{5}$ ）/2 （α $>$ 0）

另当f（λk） $>$ f（μk）时，同理，最终可知0.618法计算试探点的公式：

λk = $a_{k}$ + 0.382（ $b_{k}$ - $a_{k}$ ）

μk = $a_{k}$ + 0.618（ $b_{k}$ - $a_{k}$ ）

如下图所示，为黄金分割法的示意图：

算法步骤：

步骤1：选取a $<$ b,及精度ε> 0，

步骤2：计算 $x_{1}$ :=a + 0.382(b-a), $x_{2}$ :=a + 0.618(b-a)。

步骤3：计算 $f_{1}$ ：= $f(x_{1})$ , $f_{2}$ ：= $f(x_{2})$ 。

步骤4：如果 $f_{1}$ $>$ $f_{2}$ ，则令a:= $x_{1}$ ,若|b - a| $<$ ε，则转步骤5，否则令 $f_{1}$ ：= $f_{2}$ ， $x_{1}$ ：= $x_{2}$ ， $x_{2}$ ：=a + 0.618（b-a）， $f_{2}$ ：= $f(x_{2})$ ，转步骤4。否则令b:= $x_{2}$ ,若|b - a| $<$ ε，则转步骤5，否则令 $f_{2}$ ：= $f_{1}$ ， $x_{2}$ ：= $x_{1}$ ， $x_{1}$ ：=a + 0.382（b-a）， $f_{1}$ ：= $f(x_{1})$ ，转步骤4。

步骤5：停止，输出 $\bar{x}$ = （a+b)/2 。

缺点：收敛速度慢，无理数取小数点后三位，有一定误差。优点：不要求函数可微，且每次迭代只需计算一个函数值，计算量小。

例题分析：

例题：试用0.618法求目标函数 $f(x)=x^{3}-2x+1$ 的最优解。给定初始区间[0，2],收敛精度ε=0.002.

解：第一次区间缩短计算过程：计算两点及对应函数值：

a =0，b = 2,

$x_{1}$ =a + 0.382(b-a) = 0.764, $x_{2}$ =a + 0.618(b-a) = 1.236

$f(x_{1})$ = -0.0821， $f(x_{2})$ = 0.4162

可见： $f(x_{1})$ $<$ $f(x_{2})$ ，进行置换，b = $x_{2}$ = 1.236，[a，b] = [0，1.236],|b-a| = 1.236 $>$ ε.

第二次区间缩短计算过程：计算两点及对应函数值：

a =0，b = 1.236,

$x_{1}$ =a + 0.382(b-a) = 0.472, $x_{2}$ =a + 0.618(b-a) = 0.764

$f(x_{1})$ = 0.1612， $f(x_{2})$ =-0.0821

可见： $f(x_{1})$ $>$ $f(x_{2})$ ，进行置换，a = $x_{1}$ = 0.472，[a，b] = [0.472，1.236],|b-a| = 0.764 $>$ ε.

接着进行第三次，第四次迭代，直至|b-a| $<$ ε.结束迭代。

算法代码：

'''
黄金分割算法（0.618法）
2023.10.9
'''

def fun(x):
    return x**3-2*x+1
	
def run(a,b,ε):
	count = 0
	while True:
	    if abs(b-a) > ε:
	        x1 = a + 0.382 * (b - a)
	        x2 = a + 0.618 * (b - a)
	        count = count + 1
	        print("第{}次迭代".format(count))
	        if fun(x1) > fun(x2):
	            #print("置换x1")
	            a = x1
	            print("得到的新的区间为：[%f,%f]" %(a,b))
	            #print(abs(b-a))
	            continue
	        else:
	            #print("置换x2")
	            b = x2
	            print("得到的新的区间为：[%f,%f]" %(a,b))
	            #print(abs(b - a))
	            continue
	    elif abs(b-a) <= ε:
	        print("x的最优解是","{:.3}".format((b + a)/2))
	        print("函数在该精度上的最小值为",fun((b + a)/2))
	        break
	return a,b
run(a=0,b=2,ε=0.002)

用该代码所运算的结果为:

第1次迭代
得到的新的区间为：[0.000000,1.236000]
第2次迭代
得到的新的区间为：[0.472152,1.236000]
第3次迭代
得到的新的区间为：[0.472152,0.944210]
第4次迭代
得到的新的区间为：[0.652478,0.944210]
第5次迭代
得到的新的区间为：[0.763920,0.944210]
第6次迭代
得到的新的区间为：[0.763920,0.875339]
第7次迭代
得到的新的区间为：[0.763920,0.832777]
第8次迭代
得到的新的区间为：[0.790223,0.832777]
第9次迭代
得到的新的区间为：[0.806479,0.832777]
第10次迭代
得到的新的区间为：[0.806479,0.822731]
第11次迭代
得到的新的区间为：[0.812687,0.822731]
第12次迭代
得到的新的区间为：[0.812687,0.818894]
第13次迭代
得到的新的区间为：[0.815058,0.818894]
第14次迭代
得到的新的区间为：[0.815058,0.817429]
第15次迭代
得到的新的区间为：[0.815964,0.817429]
x的最优解是 0.817
函数在该精度上的最小值为 -0.08866201012410779