3.2 搜索区间的确定与区间消去法原理

欲求一元函数 f ^（x） 的极小点 x ^* （为书写简便，这里仍用同一符号f表示相应的一元函数），必须先确定 x ^* 所在的区间。

1.确定搜索区间的外推法

在一维搜索时，我们假设函数 f ^（x） 具有如图3-1所示的单谷性，即在所考虑的区间［ a ， b ]内部函数 f ^（x） 有唯一的极小点 x ^* ，为了确定极小点 x ^* 所在的区间［ a ， b ]，应使函数 f ^（x） 在区间［ a ， b ]上形成“高-低-高”趋势。

为此，从 a =0开始，以初始步长 h ₀ 向前试探。如果函数值上升，则步长变号，即改变试探方向。如果函数值下降，则维持原来的试探方向，并将步长加倍。区间的始点、中间点依次沿试探方向移动一步。此过程一直迸行到函数值再次上升时为止，即可找到搜索区间的终点。最后得到的三点即为搜索区间的始点、中间点和终点，形成函数值的“高-低-高”趋势。

图3-2表示沿a的正向试探。每走一步都将区间的始点、中间点沿试探方向移动一步（迸行换名）。经过三步最后确定搜索区间［ a ₁ ， a ₃ ]，并巨得到区间始点、中间点和终点 a ₁ ＜ a ₂ ＜ a ₃ 所对应的函数值 y ₁ ＞ y ₂ ＜ y ₃ 。

图3-3所表示的情况是，开始是沿a的正方向试探，但由于函数值上升而改变了试探方向，最后得到始点、中间点和终点 a ₁ ＞ a ₂ ＜ a ₃ 及它们的对应函数值 y ₁ ＞ y ₂ ＜ y ₃ ，从而形成单谷区间［ a ₃ ， a ₁ ]为一维搜索区间。

上述确定搜索区间的外推法，其程序框图如图3-4所示。

2.区间消去法原理

搜索区间［a，b]确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解，假定在搜索区间内任取两点 a ₁ 、 b ₁ ， a ₁ ＜ b ₁ ，并计算函数值 f （ a ₁ ）、 f （ b ₁ ）。于是将有下列三种可能情形：

1） f （ a ₁ ）＜ f （ b ₁ ），如图3-5a所示。由于函数为单谷，所以极小点必在区间［a，b ₁ ]内。

2） f （ a ₁ ）＞ f （ b ₁ ），如图3-5b所示。同理，极小点应在区间［ a ₁ ， b ]内。

3） f （ a ₁ ）= f （ b ₁ ），如图3-5c所示，这时极小点应在［ a ₁ ， b ₁ ]内。

根据以上所述，只要在区间［ a ， b ]内取两个点，算出它们的函数值并加以比较，就可以把搜索区间［ a ， b ]缩短成［ a ， b ₁ ]或［ a ₁ ， b ]。应当指出，对于第一种情况，我们已算出区间［ a ， b ₁ ]内点 a ₁ 的函数值，如果要把搜索区间［ a ， b ₁ ]迸一步缩短，只需在其内再取一点算出函数值并与 f （ a ₁ ）加以比较，即可达到目的。对于第二种情况，同样只需再计算一点函数值就可以把搜索区间继续缩短。第三种情形与前面两种情形不同，因为在区间［ a ₁ ， b ₁ ]内缺少已算出的函数值。要想把区间［ a ₁ ， b ₁ ]迸一步缩短，需在其内部取两个点（而不是一个点）计算出相应的函数值再加以比较才行。如果经常发生这种情形，为了缩短搜索区间，需要多计算一倍数量的函数值，这就增加了计算工作量。因此，为了避免多计算函数值，我们把第三种情形合并到前面两种情形中去。例如，可以把前面三种情形改为下列两种情形：

1）若 f （ a ₁ ）＜ f （ b ₁ ），则取［ a ， b ₁ ]为缩短后的搜索区间。

2） f （ a ₁ ）＞ f （ b ₁ ），则取［ a ₁ ， b ]为缩短后的搜索区间。

a） f （ a ₁ ）＜ f （ b ₁ ） b） f （ a ₁ ）＞ f （ b ₁ ） c） f （ a ₁ ）= f （ b ₁ ） 6C6cPJIELSozyxngUM/JjWdNhSmxfHje702G27clLIRTLBQAPgDJQZ7wpg+aYnzz