黄金分割法求函数极小值点的搜索过程

1.黄金分割法的基本原理

黄金分割法也称为0.618法，它是按照对称原则选取中间插入点而缩小区间的一种一维搜索方法。这种方法的基本原理如下：

在搜索区间[a，b]内按如下规则对称地取两点x₁和x₂，即

x₁=a+0.382（b-a），x₂=a+0.618（b-a）

计算它们的函数值f₁=f（x₁），f₂=f（x₂），比较f₁与f₂的大小，有两种可能：

1）若f₁＞f₂，如图3-4a所示。极小点必在区间[x₁，b]内，消去区间[a，x₁），令a=x₁，产生新区间[a，b]，至此，区间收缩了一次。值得注意的是接着在进行第二次区间收缩运算时，新插入的x′₁点直接取前一次收缩运算的x₂点，f（x′₁）=f（x₂）。这样可以少找一个新点，省去一次函数值计算时间，这也是黄金分割法的一大优点。

2）若f₁≤f₂，如图3-4b所示。极小点必在区间[a，x₂]内，消去区间（x₂，b]，令b=x₂，产生新区间[a，b]，至此，区间收缩了一次。同样接着在进行第二次区间收缩运算时，新插入的x′₂点直接取前一次收缩运算的x₁点，f（x′₂）=f（x₁）。这样可以少找一个新点，省去一次函数值计算时间。

当缩短的新区间长度小于或等于某一收敛精度ε，即b-a≤ε时，则取为近似极小点。

2.黄金分割法的区间收缩率及计算步骤

每次缩小所得的新区间长度与缩小前区间长度之比，称为区间收缩率，以λ表示。如图3-5所示，为加快区间收缩应保证区间收缩率不变，因此，必须在搜索区间[a，b]内对称地取计算点x₁，x₂。设初始区间长度为l，则第一次和第二次收缩得到的新区间长度分别为λl和（1-λ）l。根据收缩率相等的原则，可得

λl∶l=（1-λ）l∶λl

即 λ²+λ-1=0

该方程的正根为λ≈0.618，这就是在区间内按上式规则取两对称点的原因。

综上所述，黄金分割法的计算步骤如下：

1）给定初始区间[a，b]和收敛精度ε。

2）产生中间插入点并计算其函数值。

图3-3 进退法计算框图

x₁=a+0.382（b-a），f₁=f（x₁）

x₂=a+0.618（b-a），f₂=f（x₂）

3）比较函数值f₁和f₂，确定区间的取舍：若f₁≤f₂，则产生新区间[a，b]=[a，x₂]，令b=x₂，x₂=x₁，f₂=f₁，记N₀=0；若f₁＞f₂，则产生新区间[a，b]=[x₁，b]，令a=x₁，x₁=x₂，f₁=f₂，记N₀=1。

4）收敛判断：当缩短的新区间长度小于或等于某一收敛精度ε，即|b-a|≤ε时，则取为近似极小点，结束一维搜索；否则转5）。

图3-4 黄金分割法区间收缩

a）f₁＞f₂ b）f₁≤f2

5）产生新的插入点：若N₀=0，则取x₁=a+0.382（b-a），f₁=f（x₁）；若N₀=1，则取x₂=a+0.618（b-a），f₂=f（x₂），转3）进行新的区间缩小。(www.xing528.com)

黄金分割法的计算框图如图3-6所示。

例3-1 用黄金分割法求函数f（x）=3x³-4x+2的极小值点，给定x₀=0，h=1，ε=0.2。

图3-5 取点规则

图3-6 黄金分割法的计算框图

解：（1）确定搜索区间

x₁=x₀=0，f₁=f（x₁）=2；x₂=x₀+h=1，f₂=f（x₂）=1

由于f₁＞f₂，应加大步长继续向前探测。令

x₃=x₀+2h=2，f₃=f（x₃）=18

由f₂＜f₃可知，初始搜索区间已经找到，即[a，b]=[0，2]。

（2）用黄金分割法缩小区间

1）第一次缩小区间。令

x₁=0+0.382×（2-0）=0.764，f₁=0.282

x₂=0+0.618×（2-0）=1.236，f₂=2.72

由于f₁＜f₂，故新区间[a，b]=[a，x₂]=[0，1.236]。因为b-a=1.236＞0.2，所以应该继续缩小区间。

2）第二次缩小区间。令

x₂=x₁=0.764，f₂=f₁=0.282

x₁=0+0.382×（1.236-0）=0.472，f₁=0.317

由于f₁＞f₂，故新区间[a，b]=[x₁，b]=[0.472，1.236]。因为b-a=0.764＞0.2，所以应该继续缩小区间。

如此继续迭代下去，经过五次区间缩小之后迭代精度满足要求。黄金分割法的搜索过程见表3-1。

表3-1 黄金分割法的搜索过程

因为b-a=0.764-0.584=0.18＜0.2，所以得到极小点和极小值。，f^∗=0.222