机械优化设计作业-10-搜索区间的确定与区间消去法原理-副本

1、/ Northeast Arloiltui-aJ Untversity机械优化设计课程作业（2014至2015学年度 第2学期）班级学号姓名1第二节 搜索区间的确定与区间消去法原理欲求一元函数f( a极小点a (为书写方便，这里仍用同一符号f表示相应 的一兀函数)，必须先确定a所在的区间。、确定搜索区间的外推法在一维搜索时，假设函数f( a具有如图3-1所示的单谷性，即在所考虑的区 间内部，函数f( a有唯一的极小点a?。为了确定极小点a所在的区间a，b，应 使函数f( a)在区间a， b里形成“高一低一高”趋势。为此，从c=0开始，以初始步长h°向前试探。如果函数值上升，则步长变号

2、， 即改变试探方向；如果函数值下降，则维持原来的试探方向，并将步长加倍。区 间的始点、中间点依次沿试探方向移动一步。此过程一直进行到函数值再次上升 时为止，即可找到搜索区间的终点。最后得到的三点即为搜索区间的始点、 中间 点和终点，形成函数值的“高一低一高”趋势。图3-2表示沿a的正向试探。每走一步都将区间的始点、中间点沿试探方向 移动一步(进行换名)。经过三步，最后确定搜索区间a，al并且得到区间始点、 中间点和终点a < a < a对应的函数值yi > y2 < y3 。图3-3所示的情况是，开始沿a的正方向试探，但由于函数值上升面改变了 试探方向，最后得到始点、中

3、间点和终点a > a2> a3及它们的对应函数值yi > V2 < V3 ,从而形成单谷区间a3 , a 为一维搜索区间上诉确定搜索区间的外推法，其程序框图如图3-4所示68、区间消去法原理搜索区间a,b确定之后，采用区间消去法逐步缩短搜索区间，从而找到极 小点的数值近似解。假定在搜索区间a,b内任取两点ai、bi,且ai<bi，并计算 函数值f( aj、f( b1)。于是可能有下列三种情况：1) f(ajvf( bj,如图3-5a所示。由于函数为单谷，所以极小点必在区间 a, bi内，2) f( ai)>f( bi),如图3-5b所示。同理，极小点应在区间

4、ai,b内。3) f( ai)=f( bi),如图3-5c所示，这是极小点应在ai, bi内。根据以上所述，只要在区间a,b内取两个点，算出它们的函数值并加以比 较，就可以把搜索区间a,b缩短成ai, bi、a, bi或ai,b。应当指出，对 于第一种情况，我们已算出区间a, bi内ai点的函数值，如果要把搜索区间a, bi进一步缩短，只需在其内再取一点算出函数值并与f( ai)加以比较，即可 达到目的。对于第二种情况，同样只需再计算一点函数值就可以把搜索区间继续 缩短。第三种情况与前面两种情况不同，因为在区间a bi内缺少已算出的函数值，要想把区间ai, bi进一步缩短，需在其内部取两个点(

5、而不是一个点) 计算出相应的函数值再加以比较才行。如果经常发生这种情况，为了缩短搜索区间，需要多计算一倍数量的函数值，这就增加了计算工作量。因此，为了避免多 计算函数值，应把第三种情况合并到前面两种情形中去。例如，可以把前面三种情况改为下列两种情况：1) 若f (ai)<f( bi),则取a, bi为缩短后的搜索区间。2) 若f( ai )>=f( bi ),则取ai ,b为缩短后的搜索区间。三、一维搜索方法的分类从上述的分析中可知，每次为了缩短区间，只需要在区间内再插入一点并计 算其函数值。然而，对于插入点的位置，则可以通过不同的方法来确定。这样就 形成了不同的一维搜索方法。 概括起来， 可将一维搜索方法分成两大类。 一类称 为试探法。 这类方法是按某种给定的规律来确定区间内插入点的位置的。 此点位 置的确定仅考虑加快区间缩短速度， 而不顾及函数值的分布关系。 属于试探法一 维搜索方法的有黄金分割法、斐波那契( Fibonacci )法等。另一类一维搜索方 法称为插值法或函数逼近法。 这类方法根据某些点处的某些信