1、：对于：对于单个变量单个变量（一维问题一维问题）的直接探索（搜索）的直接探索（搜索 或寻查）。或寻查）。多维多维问题的数值迭代法问题的数值迭代法1(0,1,2,)kkkkxxdk1()()()minkkkkkf xf xd 每步为每步为一维一维搜索搜索*()0 1 1）解析法解析法：2 2）数值解法数值解法的基本思想：确定的基本思想：确定 * *所在的搜索区间，所在的搜索区间， 然后根据区间消去原理不断缩小区间，然后根据区间消去原理不断缩小区间， 从而获得从而获得 * *的数值近似解。的数值近似解。函数在该区间只有函数在该区间只有一个极值点一个极值点。12xxx12()( )()f xf xf
2、 x“高高低低高高”（进退法（进退法/成功失败法）：成功失败法）：12x x x 12( )( )( )f xf xf x“高高低低高高”的基本步骤：的基本步骤：10210112212320332332123132300122312231.()()(),2hhyfyfyyhyfyyyyyyyyyhhyyyy 选定初始点，初始步长 ，计算点，然后比较函数值和的大小。2.若，则试探方向正确，计算点和，比较 和 的大小。如果，则形成，找到所需的区间，即；如果，则需要继续向前搜索，这时候令，同时令，开01231313 , min(,),max(,)hyyya b 始新一轮的试探（这时候的是原来的二倍，
3、步长加长了），直到找到时，新的搜索区间是。的基本步骤：的基本步骤：1200121233313112122323122320333.,()yyhhyyyyyyyyyhff 若，则试探方法错误，需要反向，即令，并且将和交换，同时交换 和 ，在程序中，如果用替换，则另一个函数值就没有了，所以加入和 做中间变量，即：；。然后得到新的和后，用新的向前推出（这里的已经反向了）。这时就得到了新的三个点，以及三个试探点的函数231231313 , min(,),max(,)yyyyya b 值，则继续前面的比较 与 ，直至找到时，新的搜索区间是。的程序流程图：的程序流程图：例：例：210( )710 , 01
4、f xxxa bh试用进退法确定函数的一维优化的初始搜索。其中，设初始点，初始搜索步长。通过通过外推法外推法，我们可以确定一个包含一元函数极值点的，我们可以确定一个包含一元函数极值点的搜索区间搜索区间，为了进一步找到极小点，我们需要不断的缩小，为了进一步找到极小点，我们需要不断的缩小搜索区间，消去不可能包含极小点的区间，使区间在缩小搜索区间，消去不可能包含极小点的区间，使区间在缩小的过程中逐步向极小点靠拢，最后缩小到极小点附近一个的过程中逐步向极小点靠拢，最后缩小到极小点附近一个极小的领域内。极小的领域内。 这个时候，如果我们规定一个足够小的正数这个时候，如果我们规定一个足够小的正数 ，称为收
5、敛，称为收敛精度。则当区间长度达到足够小，即精度。则当区间长度达到足够小，即 取该区间取该区间的中点的中点 作为极值点，这才能完成整个一维作为极值点，这才能完成整个一维搜索搜索 。kkba*1()2kkxab：不断缩小区间所用的原理。：不断缩小区间所用的原理。 包括：包括：1）直接法直接法：直接比较试选点的函数值；：直接比较试选点的函数值； 2）间接法间接法：利用函数导数值的变化信息。：利用函数导数值的变化信息。111111 , ()( )a bababf af b假定在搜索区间内任取两点 和 ，且，并计算和，可能出现三种情况：11111111111. ()( ) ,2. ()( ), 3.
6、()( ),f af ba bf af ba bf af ba b，由于函数的单峰性，极小点一定在内；，极小点一定在内；，极小点一定在内。111111 , ()( )a bababf af b假定在搜索区间内任取两点 和 ，且，并计算和，可能出现三种情况：1111111.()( ) ,2.()( ), f af ba bf af ba b若，则取为缩短后的搜索区间；若，则取为缩短后的搜索区间。 , ,( )a bxfx假定在搜索区间内取一点 并计算它的导数值，可能出现三种情况：*1. ( )0 , 2. ( )0 , 3. ( )0fxx bfxa xfxxx，则新区间是；，则新区间是；，则在
7、此点就是极小点。x fxabxx0 x fxabxx0 fxxabx0： 缩短后的新区间长度（0 1）缩短前的原区间长度：它是按照：它是按照某种给定的规律某种给定的规律来确定区间内插入点来确定区间内插入点的位置的。插入点位置的确定是为了使区间缩短的更快，的位置的。插入点位置的确定是为了使区间缩短的更快，而而不管函数值的分布规不管函数值的分布规律。它律。它包括包括：黄金分割法（：黄金分割法（0.6180.618法）、裴波纳契（法）、裴波纳契（FibonacciFibonacci）法等。）法等。：这种方法是根据某点处的某些：这种方法是根据某点处的某些信息（如信息（如函数值函数值、一阶导数一阶导数、
8、二阶导数二阶导数等）来构造一个等）来构造一个差值函数差值函数来逼近原来的函数，用来逼近原来的函数，用插值函数的极小点插值函数的极小点作为作为区间的插入点。它区间的插入点。它包括包括：二次差值法、三次插值法等。：二次差值法、三次插值法等。通过比较单峰区间内通过比较单峰区间内两个内分点两个内分点的的函数值函数值，不断舍弃，不断舍弃单峰区间的左端或者右端的一部分，使区间按照单峰区间的左端或者右端的一部分，使区间按照固定区间固定区间缩短率缩短率（=0.618=0.618）逐步缩短，直到极小点所在的区间缩）逐步缩短，直到极小点所在的区间缩短到短到给定的误差范围给定的误差范围内，而得到内，而得到近似最优解
9、近似最优解。 每次区间缩短都取每次区间缩短都取相等相等的的区间缩短率区间缩短率（ ），同时插入点距离两个端点有），同时插入点距离两个端点有对称性对称性。 0.61812()0.618()()0.618()bbabbaabaaba121211221 , 2 , ()0.618() ()0.618()()()a ba bbbabbaabaabayfyf）给定初始单峰区间和收敛精度 ，将 赋值为0.618；）在区间内，取两个内分点和，并计算其函数值： 和，12221221211111211211213 , ,()(), , ,yybyybbayfyybbay ）比较函数值大小，根据区间消去法原理缩短
10、区间：若，则极小点必在区间内，即为新区间,则为新区间内的第一个试验点，即令，而另一个试验点可按下式算出，它的函数值为；若，则极小点必在区间内，即为新区间，则为新区间内的第一个试验点，即令2222(),()yabayf，而另外一个试验点可以按下式给出。212*4315()()2yybabyxabyf x）进行迭代终止条件检验，检查区间是否缩短到足够小和函数值是否收敛到足够近，即和，如果不满足条件，则转到第 ）步；满足条件则继续执行下一步。）输出最优解和最优函数值。2*( )2 ,35f如图所示，对函数当给定搜索区间时，试用黄金分割法求极小点。 和黄金分割法和黄金分割法相似相似，都是在搜索区间内，
11、都是在搜索区间内对称的取点对称的取点，通过，通过比较两点函数值逐步缩小初始单峰区间来搜索出满意的极小比较两点函数值逐步缩小初始单峰区间来搜索出满意的极小点点x x* *。 与黄金分割法与黄金分割法不同不同的是：的是：黄金分割法黄金分割法每次迭代式按照同一每次迭代式按照同一区间缩短率区间缩短率=0.618=0.618来缩短区间，而来缩短区间，而斐波那契法斐波那契法每次迭代的区每次迭代的区间缩短率是不同的，它是按间缩短率是不同的，它是按斐波那契数列斐波那契数列FnFn产生的分数序产生的分数序列为缩短率来缩短区间的。列为缩短率来缩短区间的。， ，011FF12(2,3,)nnnFFFn斐波那契数：斐
12、波那契数： 凡是满足递推关系而产生的正数序列Fn，就称为斐波那契数。n n0 0 1 1 2 23 34 45 56 67 78 89 910101111121213131414FnFn1 1 1 1 2 23 35 58 813132121343455558989144144233233377377610610 ，n n0 0 1 1 2 23 34 45 56 67 78 89 910101111121213131414FnFn1 1 1 1 2 23 35 58 813132121343455558989144144233233377377610610 区间缩短率区间缩短率用相邻两数的用
13、相邻两数的前一数前一数与与后一数后一数之之比比产生，如计产生，如计算五个点的函数值（即迭代四次，每次区间缩短率分别为算五个点的函数值（即迭代四次，每次区间缩短率分别为123412514342134233253 8521 32nnnnnnnnFFFFFFFFFFFFFFFF11234518FF ，n n0 0 1 1 2 23 34 45 56 67 78 89 910101111121213131414FnFn1 1 1 1 2 23 35 58 813132121343455558989144144233233377377610610 推广到计算推广到计算n n个点的函数值，经过个点的函数值
14、，经过n-1n-1次迭代所获得的次迭代所获得的区间总缩短率区间总缩短率为为11211nnnFFF ，11(1)1/n21/0.61830.618nnnnFFF）斐波那契法开始计算第一个内点（即第一次缩短率）就要用到，也就是首先要确定计算函数的次数（即计算的总点数 ），否则无法确定缩短率）与黄金分割法相比，收敛效果好，即计算相同试点数，斐波那契法总区间缩短率。黄金分割法的区间总缩短率。）斐波那契法每次的区间缩短率是变化的，当计算函数值的点数较多时，其区间缩短率将逼近。 ，11111101121a,b2nn11|()()Fn1,(2,3,)nnnnnnnnnnnnbababababaFbaFFFF
15、FFn）由外推法（进退法）选定初始单峰区间。）确定所需计算的试点总数（即计算函数的次数） 。当给定区间缩短率的绝对精度 时，经过次迭代，最后获得的新区间长度（）必须满足。而，故。由即可从斐波那契数列表或按推算出相应的 。112111223a,b(), (), (), ()nnnnFFxabaxbbaff xff xFF）确定试点并计算相应的函数值，在区间内的两个试点： ，212221211211211112122122*114 ,() , ,()15(),()2nnffa xbx xxffxabxff xffx bax xxffxabxff xbaxabff x）比较函数值的大小后进行区间缩短
16、。若，即为新区间，并作如下置换：即令若时，得新区间，并作如下置换：）检查迭代终止条件：，若满足，则输出最优解，若不满足，则转入（4），继续进行迭代。 我们就可以根据我们就可以根据几个试验点的函数值几个试验点的函数值，利用插值方法建立，利用插值方法建立函数的某种函数的某种近似表达式近似表达式，进而求得函数的极小值，并用它作，进而求得函数的极小值，并用它作为为原函数极小点的近似值原函数极小点的近似值。这种方法称为插值法，或函数逼。这种方法称为插值法，或函数逼近法近法 。利用一点的函数值，一阶导数值和二利用一点的函数值，一阶导数值和二阶导数值来构造此二次函数。阶导数值来构造此二次函数。利用三点的函数
17、值形成一个抛利用三点的函数值形成一个抛物线来构造二次函数物线来构造二次函数 。 ，用用切线切线代替代替弧弧逐渐逼近函数极值的一种方法。逐渐逼近函数极值的一种方法。 ，1() (0,1,2,)()kkkkfkf ，01*11k01()()()2()3|4411kkkkkkkkkffffkk给定初始点，控制误差 ，令。）计算和；）求。）若，则求得近似解，停止计算，否则转到第（ ）步；）令转到第（ ）步。 ，： 1 1）每一次迭代都要计算函数的二阶导数，增加了计）每一次迭代都要计算函数的二阶导数，增加了计算工作量；算工作量； 2 2）对初始点的要求较高，如果选不好，可能使数列发）对初始点的要求较高，
18、如果选不好，可能使数列发散或收敛到一个不是极小点的点上。散或收敛到一个不是极小点的点上。 ，43212( )27843f例：试用牛顿法求的近似极小值，已知探索区间为a,b=3,4, =0.05。 ，在给定的单峰区间在给定的单峰区间a,ba,b内，利用函数上的内，利用函数上的三个点三个点来构来构造一个造一个二次插值函数二次插值函数p()p()，以近似地表达原目标函数，以近似地表达原目标函数f()f()，并求这个插值函数的极小点近似作为原目标函数的极小并求这个插值函数的极小点近似作为原目标函数的极小点。它是以点。它是以目标函数的二次插值函数目标函数的二次插值函数的的极小点极小点作为作为新的新的中间
19、插入点中间插入点，进行区间缩小的一维搜索方法。，进行区间缩小的一维搜索方法。 ， 2012Paaa210112111220122222230132333PaaayfPaaayfPaaayf123123fff113212pcc31131yyc21121223yycc12/ 2paa ， ，2()0paa h2pyy2pyy ，2pyy2()0paa h2pyy ，123132112233211312112312311321,1(),(),(),();22( ):,1(),2ppppababyfyfyfyycyyaapccaaaacaaayfc）给定初始搜索区间a,b和迭代精度 ，取点时令求）计算二次插值函数的极值点和第一次插值时转到第三步，否则转到第4步。 ，221222232232222122222,4|ppppppppppppppppyyyyyyyyyyyyyyy3）缩短搜索区间，形成新的区间a,b:当且时，,，转到第二步；当且时，转到第二步；当且时，转到第二步；当且时，转到第二步；）判断迭代是否终止：满足或或，迭代终止，输出，如果则得到极值*22ppyy点是；若极值点为；不满足，转第二步。 ， ( )sin45f例：试用二次插值法求的近似极小点及极小值，已知。 ，2( )(3) , 1,7,0.01f xxa b例：试用二次插值法求函数的最优解，已知初始单峰区间给定计算精度。
