一维迭代搜索(黄金分割法-抛物线法)课件

《一维迭代搜索(黄金分割法-抛物线法)课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3节一维搜索方法当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算:当方向给定，求最佳步长就是求一元函数:的极值问题，这一过程被称为一维搜索(单变量优化).一维搜索方法分类：(a)试探法；(b)插值法1、单谷(峰）区间在给定区间内仅有一个谷值(极大或极小)的函数称为单谷数，其区间称为单谷区间3.1一维搜索的基本思想Of(a)bx*xa函数值：“大－小－大”图形：“高—低—高”单谷区间中一定能求得一个极小点2、一维搜索的基本思想◆方向导数找初始单谷区间是一维搜索的第一步.◆第二步使区间缩小◆收敛精度或迭代精度ε3.2确定初始单谷区间的进退法基本思想：对f(x

2、)任选一个初始点a1及初始步长h，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高—低—高”形态步骤：（1）选定初始点x1，初始步长h，计算f1＝f(x1),f2＝f(x1+h)（2）比较f1和f2。（a）如f1>f2,向右前进；加大步长h＝2h，转（3）向前（b）如f10时，[a,b]=[a1,a3];h<0时，[a,b]=[a3

3、,a1];（b）如y2>y3,加大步长h＝2h，a1=a2,a2=a3,转（3）继续探测3.3黄金分割法(0.618法)区间消去法原理：搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解假定在搜索区间内[a,b]任取两点a1,b1;f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1a1b1baababb1b1f1＝f（a1），f2＝f（b1）f1＝f（a1），f2＝f（b1）(1)如f1f2,则缩小的新区间为[a1,b];(3)如f1=f2,则缩小的新区间为[a1,b]f(a1)f(b1

4、)f(a1)f(b1)f(a1)f(b1)a1a1a1b1baababb1b1综合为两种情况：①若则取为缩短后的搜索区间。②若则取为缩短后的搜索区间。黄金分割法黄金分割律是公元前六世纪，希腊的大数学家毕达哥拉斯发现的：如果把一条线段分成两部分，长段和短段的长度之比是1:0.618，整条线段和长段的比也是1:0.618时，才是和黄金一样最完美的分割，进行分割的这个点就叫黄金分割点黄金分割法适用于[a,b]区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其他要求，甚至可以不连续。因此，这种方法的适应面相当广黄金分割法也是建立在区间消去法原理基础上的试探方法。在搜索区间内[a

5、,b]适当插入两点，将区间分成三段；利用区间消去法，使搜索区间缩小，通过迭代计算，使搜索区间无限缩小，从而得到极小点的数值近似解将区间分成三段黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布f(a1)f(a2)f(a1)f(a2)a1a1a2ababa2黄金分割法要求插入两点：黄金分割法区间消去示意：黄金分割法的搜索过程：1）给出初始搜索区间及收敛精度，将赋以0.618。2）按坐标点计算公式计算,；并计算其对应的函数值。3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的

6、试验点及其函数值。如果，则新区间＝令,记N0=0;如果，则新区间＝，令,记N0=1;4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5）。5）产生新的插入点：如N0=0，则取；如N0=1，则取，转向3）进行新的区间缩小。f(a1)f(a2)f(a1)f(a2)a1(a)a1(a2)a2(b)ababa2(a1)a1a2黄金分割法例3-1用黄金分割法求函数f(x)=3x3-4x+2的极小点，给定x0=0,h=1,ε=0.2。解：1)确定初始区间x1=x0=0,f1=f(x1)=2x2=x0

7、+h=0+1=1,f2=f(x2)=1由于f1>f2,应加大步长继续向前探测。x3=x0+2h=0+2=2,f3=f(x3)=18由于f20.2第二次缩小区间：令x2=