下载掌阅APP，畅读海量书库
立即打开
黄金分割法亦称0.618法，它是按照对称原则选取中间插入点而缩小区间的一种一维搜索算法。
设区间［ a ， b ]内的两个中间插入点由以下方式产生：
若缩小一次后的新区间为［ a ， x 2 ]，则如图3-6所示，由于新旧区间内中间插入点应具有相同位置关系，原区间内的点 x 1 和新区间内的点 x 2 实际上是同一个点，故有
λ 2 = λ -1
由此解得
代入式（3-1）有
x 1 = a +0.382（ b - a ）
x 2 = a +0.618（ b - a ）
图3-6 新旧区间比例关系
这就是黄金分割法的迭代公式，0.618法也因此而得名。
黄金分割法以区间长度是否充分小作为收敛准则，并以收敛区间的中点作为一维搜索的极小点，即当 b - a ≤ ε 时，取
不难看出，黄金分割法每次区间缩小的比率是完全相等的。如果将新区间的长度和原区间的长度之比称作区间缩小率，则黄金分割法的区间缩小率等于常数0.618。如果给定收敛精度ε、初始区间长度 b - a ，则完成一维搜索所需缩小区间的次数 n 可以由下式求出：
综上所述，黄金分割法的计算步骤如下：
1）给定初始区间［a，b]和收敛精度ε。
2）产生中间插入点并计算其函数值：
x 1 =a+0.382（b-a）， f 1 = f （ x 1 ）
x 2 =a+0.618（b-a）， f 2 = f （ x 2 ）
3）比较函数值f 1 和f 2 ，确定区间的取舍：
若 f 1 ＜ f 2 ，则新区间［a，b]=［ a ， x 2 ]，令 b = x 2 ， x 2 = x 1 ，f 2 =f 1 ，记N 0 =0；
若 f 1 ＞ f 2 ，则新区间［a，b]=［ x 1 ， b ]，令 a = x 1 ，x 1 = x 2 ，f 1 =f 2 ，记N 0 =1，如图3-7所示。
图3-7 区间取舍
4）收敛判断：若区间的长度足够小，即满足|
b
-
a
|≤
ε
，则将区间中点作为一维极小点，即令
，结束一维搜索；否则，转5）。
5）产生新的插入点：若 N 0 =0，则取 x 1 = a +0.382（b-a）， f 1 = f （ x 1 ）；若 N 0 =1，则取 x 2 =a+0.618（b-a）， f 2 = f （x 2 ）。转3）迸行新的区间缩小。
黄金分割法的迭代过程和程序框图如图3-8所示。
例3-1 用黄金分割法求函数 f （ x ）=3 x 3 -4 x +2的极小点，给定 x 0 =0， h =1， ε =0.2。
解：（1）确定初始区间
x 1 = x 0 =0， f 1 = f （ x 1 ）=2
x 2 = x 0 + h =0+1=1， f 2 = f （ x 2 ）=1
由于 f 1 ＞f 2 应加大步长继续向前探测。令
x 3 = x 0 +2 h =0+2=2， f 3 = f （ x 3 ）=18
由于 f 2 ＜ f 3 可知初始区间已经找到，即［ a ， b ]=［0，2]
（2）用黄金分割法缩小区间
1）第一次缩小区间：
图3-8 黄金分割法的程序框图
x 1 =0+0.382（2-0）=0.764， f 1 =0.282
由于 f 1 ＜ f 2 ，故新区间［ a ， b ]=［ a ， x 2 ]=［0，1.236]
因为 b - a =1.236＞0.2所以应继续缩小区间。
2）第二次缩小区间：
令
x 2 = x 1 =0.764， f 2 = f 1 =0.282
x 1 =0+0.382（1.236-0）=0.472， f 1 =0.317
由于 f 1 ＞ f 2 ，故新区间为［ a ， b ]=［ x 1 ， b ]=［0.472，1.236]
3）第三次缩小区间：
令
x 1 = x 2 =0.764， f 1 = f 2 =0.282
x 2 =0.472+0.618×（1.236-0.472）=0.944， f 2 =0.747
由于 f 1 ＜ f 2 ，故新区间为［ a ， b ]=［ a ， x 2 ]=［0.472，0.944]
4）第四次缩小区间：
令
x 2 = x 1 =0.764， f 2 = f 1 =0.282
x 1 =0.472+0.382（0.944-0.472）=0.652， f 1 =0.223
由于 f 1 ＜ f 2 ，故新区间为［ a ， b ]=［ a ， x 2 ]=［0.472，0.764]
因为 b - a =0.764-0.472=0.292＞0.2，所以应继续缩小区间。
5）第五次缩小区间
令
x 2 = x 1 =0.652， f 2 = f 1 =0.223
x 1 =0.472+0.382（0.764-0.472）=0.584， f 1 =0.262
由于 f 1 ＞ f 2 ，故新区间为［ a ， b ]=［ x 1 ， b ]=［0.584，0.764]
因为 b - a =0.764-0.584=0.18＜0.2
所以得到极小点和极小值分别为
x * =0.5×（0.584+0.764）=0.674， f * =0.222