迭代过程及算法框图分析

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

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

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

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，如图3-7所示。

图3-7 区间取舍

4）收敛判断：若区间的长度足够小，即满足|b-a|≤ε，则将区间中点作为一维极小点，即令，结束一维搜索；否则，转5）。

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

黄金分割法的迭代过程和程序框图如图3-8所示。

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

解：（1）确定初始区间

x₁=x₀=0，f₁=f（x₁）=2

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

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

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

由于f₂＜f₃可知初始区间已经找到，即［a，b]=［0，2]

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

1）第一次缩小区间：

图3-8 黄金分割法的程序框图

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

由于f₁＜f₂，故新区间［a，b]=［a，x₂]=［0，1.236](www.xing528.com)

因为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]

3）第三次缩小区间：

令

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

x₂=0.472+0.618×（1.236-0.472）=0.944，f₂=0.747

由于f₁＜f₂，故新区间为［a，b]=［a，x₂]=［0.472，0.944]

4）第四次缩小区间：

令

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

x₁=0.472+0.382（0.944-0.472）=0.652，f₁=0.223

由于f₁＜f₂，故新区间为［a，b]=［a，x₂]=［0.472，0.764]

因为b-a=0.764-0.472=0.292＞0.2，所以应继续缩小区间。

5）第五次缩小区间

令

x₂=x₁=0.652，f₂=f₁=0.223

x₁=0.472+0.382（0.764-0.472）=0.584，f₁=0.262

由于f₁＞f₂，故新区间为［a，b]=［x₁，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