搜索算法结构ppt课件

1、一、下降算法模型一、下降算法模型 思索思索NP 常用一种线性搜索的方式来求解：迭代中从一点出常用一种线性搜索的方式来求解：迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。发沿下降可行方向找一个新的、性质有改善的点。迭代计算：迭代计算：其中其中 为第为第 次迭代的搜索方向，次迭代的搜索方向， 为沿为沿 搜索的搜索的最正确步长因子通常也称作最正确步长。最正确步长因子通常也称作最正确步长。min f(x) s.t. xS第三章第三章 常用的一维搜索方法常用的一维搜索方法kd1k kkd1,0,1,2,kkkkxxdkkX1 kX2 kXk 1d kdk 2d kkd 可行方向：设可行方向：

2、设 S，dRn,d0,假设存在假设存在 ，使使 ，称，称d 为为 点的可点的可行方向。行方向。同时满足上述两个性质的方向称下降可行方向。同时满足上述两个性质的方向称下降可行方向。_x_x_x0),0(,_Sdx下降方向下降方向 ： 设设 S，d Rn,d0,假设存在假设存在 ，使使 ，称，称d 为为 在在 点的下点的下降方向。降方向。0), 0(),()(_xfdxf_xl模型算法模型算法线性搜索求线性搜索求 ，新点新点使使x(k+1)S初始初始x(1) S, k =1对对x(k)点选择下降点选择下降可行方向可行方向d(k)0k)()()()1(kkkkdxx能否满足停机条件？能否满足停机条件

3、？停停k=k+1yesno1x2x5310X1X2X)(0Xf)(1Xf )(2Xf 二、收敛性概念：二、收敛性概念： 思索思索NP设迭代算法产生点列设迭代算法产生点列x(k) S.1. 理想的收敛性：设理想的收敛性：设x*S是是g.opt(全局全局最优解最优解).当当x* x(k) 或或 x(k) x*， k，满足，满足 时，称算法收敛到最优解时，称算法收敛到最优解 x*。 *)(limxxkkmin f(x) s.t. xS 由于非线性规划问题的复杂性，适用中建立以下收由于非线性规划问题的复杂性，适用中建立以下收敛性概念敛性概念 ：2. 适用收敛性：定义解集适用收敛性：定义解集 S* =

4、x | x 具有某种性质具有某种性质 例：例：S*=x|x-g.opt S*=x|x-l.opt S*=x| f(x)=0 S*=x|f(x) (为给定的实数阈值为给定的实数阈值)2.适用收敛性续适用收敛性续收敛性：设解集收敛性：设解集S* ，x(k)为算法产为算法产生的点列。以下情况之一成立时，称算生的点列。以下情况之一成立时，称算法收敛：法收敛： 1x(k) S*; 2x(k) S*， k，x(k)的恣意极限点的恣意极限点x* S* 。 全局收敛：对恣意初始点全局收敛：对恣意初始点x(1),算法均收算法均收敛。敛。 部分收敛：当部分收敛：当x(1) 充分接近解充分接近解x*时，算时，算法收

5、敛。法收敛。有限步终止有限步终止三、收敛速度三、收敛速度 设算法产生点列设算法产生点列x(k) 收敛到解收敛到解x*，且，且x(k)x*, k，关于算法的收敛速度，有关于算法的收敛速度，有1.线性收敛：线性收敛： 当当k充分大时成立。充分大时成立。2.超线性收敛：超线性收敛： 3.二阶收敛：二阶收敛： 0，是，是 使当使当k充分大时有充分大时有0|lim*)(*)1(xxxxkkk2*)(*)1(|xxxxkk1|*)(*)1(xxxxkk三、收敛速度续三、收敛速度续定理：设算法点列定理：设算法点列x(k)超线性收敛于超线性收敛于x*,且且x(k)x*， k，那么，那么证明：只需留意证明：只需

6、留意| |x(k+1) x* | -| x(k) x* | | |x(k+1) x(k) | |x(k+1) x* | +| x(k) x* | ，除以，除以| x(k) x* | 并令并令k，利，利用超线性收敛定义可得结果。用超线性收敛定义可得结果。1|lim*)()1(xxxxk(k)kk该结论导出算法的停顿条件可用：该结论导出算法的停顿条件可用：1( )()|kkxx 1()()|()() |kkfxfx 或四、二次终结性四、二次终结性一个算法用于解正定二次函数的无约束极小一个算法用于解正定二次函数的无约束极小时，有限步迭代可达最优解，那么称该算法时，有限步迭代可达最优解，那么称该算法具

7、有二次终结性。具有二次终结性。知,kx并且求出了kx处的可行下降方向,kd从kx出发， 沿方向kd求如下目的函数的最优解，或者选取 minminkk00f xd 0k使得：min00Tkkkkf xdd 设其最优解为k叫准确步长因子，kk 1kkxxd 所以线性搜索是求解一元函数 的最优化问题也叫一维最优化问题或普通地，一维优化问题可描画为：于是得到一个新点： xfbxamin一维搜索。 =0()fxaxb 或解普通地，线性搜索算法分成两个阶段：第一阶段确定包含理想的步长因子或问题最优解的搜索区间；第二阶段采用某种分割技术或插值方法减少这个区间。 搜索区间确实定 黄金分割法(0.618法) 二

8、次插值法 Newton法要点：单峰函数的消去性质、进退算法根本思想、黄金分割要点：单峰函数的消去性质、进退算法根本思想、黄金分割法根本思想、重新开场、二次插值法要求、极小化框架、法根本思想、重新开场、二次插值法要求、极小化框架、Newton法根本思想、方法比较。法根本思想、方法比较。我们主要引见如下一些搜索方法：我们主要引见如下一些搜索方法：学习的重要性：学习的重要性：1、工程实际中有时需求直接运用；、工程实际中有时需求直接运用；2、多变量最优化的根底，迭代中经常要用到。、多变量最优化的根底，迭代中经常要用到。方法分类：方法分类：1、直接法：迭代过程中只需求计算函数值；、直接法：迭代过程中只需

9、求计算函数值；2、微分法：迭代过程中还需求计算目的函数的导数；、微分法：迭代过程中还需求计算目的函数的导数；f(x)xab3.2 3.2 搜索区间确实定搜索区间确实定 常用的一维直接法有消去法和近似法两类。它们都是从常用的一维直接法有消去法和近似法两类。它们都是从某个初始搜索区间出发，利用单峰函数的消去性质，逐渐减某个初始搜索区间出发，利用单峰函数的消去性质，逐渐减少搜索区间，直到满足精度要求为止。少搜索区间，直到满足精度要求为止。3.2.1 3.2.1 单峰函数单峰函数 延续单峰函数延续单峰函数f(x)xab不延续单峰函数不延续单峰函数f(x)xab离散单峰函数离散单峰函数f(x)xa b非

10、单峰函数非单峰函数定义：假设函数定义：假设函数f(x)f(x)在区间在区间a,ba,b上只需一个极值点上只需一个极值点, , 那么称那么称f(x)f(x)为为 a, b a, b上的单峰函数。上的单峰函数。 单峰函数具有一个重要的消去性质单峰函数具有一个重要的消去性质定理：设定理：设f(x)是区间是区间a,b上的一个单峰函数，上的一个单峰函数，x*a,b是其极小是其极小点，点， x1 和和x2是是a, b上的恣意两点，且上的恣意两点，且ax1 x2b，那么比较，那么比较f(x1)与与f(x2)的值后，可得出如下结论：的值后，可得出如下结论：f(x)xab(I) 消去消去a, x1 x*x1 x

11、2f(x)xab(II) 消去消去x2, bx*x2x1(II) (II) 假设假设f(x1) f(x2), xf(x1) f(x2), x* *a,x2a,x2在单峰函数的区间内，计算两个点的函数值，比较大小后，就在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间减少。在已减少的区间内，仍含有一个函数值，能把搜索区间减少。在已减少的区间内，仍含有一个函数值，假设再计算另一点的函数值，比较后就可进一步减少搜索区假设再计算另一点的函数值，比较后就可进一步减少搜索区间间 . .I 假设假设f(x1)f(x2)，x*x1,b3.2.2 3.2.2 进退算法进退算法 ( (或称胜利或称

12、胜利- -失败失败法法) )如何确定包含极小点在内的初始区间如何确定包含极小点在内的初始区间 ?一根本思想：一根本思想：由单峰函数的性质可知，函数值在极小点左边严厉下降，在右由单峰函数的性质可知，函数值在极小点左边严厉下降，在右边严厉上升。边严厉上升。f(x)xabx*x0 x1x2从某个初始点出发，沿函数值下降的方向前进，直至发现函从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。数值上升为止。由两边高，中间低的三点，可确定极小点所在的初始区间。由两边高，中间低的三点，可确定极小点所在的初始区间。二算法二算法1、选定初始点、选定初始点a 和步长和步长h;f(x) x2、计算并

13、比较、计算并比较f(a)和和f(a+h)；有前进；有前进(1)和后退和后退(2)两种情况：两种情况：(1) 前进运算：假设前进运算：假设f(a) f(a+h), (2) 后退运算：假设后退运算：假设f(a) f(a+h), a a+h 那么步长加倍，计算那么步长加倍，计算f(a+3h)。假设。假设f(a+h) f(a+3h)， 令令 a1=a, a2=a+3h, 停顿运算；否那么将步长加倍，并反复上述运算。停顿运算；否那么将步长加倍，并反复上述运算。a+3hf(x) xaa+ha+7ha1b1a-ha-3ha-7ha1b1 那么将步长改为那么将步长改为h。计算。计算f(ah), 假设假设f(a

14、h) f(a)， 令令 a1=ah, a2=a+h, 停顿运算；否那么将步长加倍，继续后退。停顿运算；否那么将步长加倍，继续后退。仅仅找区间！假设进一步仅仅找区间！假设进一步找最小点，参阅找最小点，参阅P44!(三三) 几点阐明几点阐明缺陷：效率低；缺陷：效率低；优点：可以求搜索区间；优点：可以求搜索区间；留意：留意：h 选择要适当，初始步长不能选得太小；选择要适当，初始步长不能选得太小； 3.3 3.3 区间消去法黄金分割法区间消去法黄金分割法 消去法的思想：反复运用单峰函数的消去性质，不断减少包含极小点的消去法的思想：反复运用单峰函数的消去性质，不断减少包含极小点的搜索区间，直到满足精度为

15、止。搜索区间，直到满足精度为止。 消去法的优点：只需计算函数值，通用性强。消去法的优点：只需计算函数值，通用性强。 消去法的设计原那么：消去法的设计原那么：1迭代公式简单；迭代公式简单；2消去效率高；消去效率高；3对称：对称： x1 a = b-x2 ；4坚持缩减比：坚持缩减比：=(保管的区间长度保管的区间长度原区间长度原区间长度) 不变。使每次保管下来的节点，不变。使每次保管下来的节点， x1或或 x2 ，在下一次的，在下一次的比较中成为一个相应比例位置的节点比较中成为一个相应比例位置的节点 。 一黄金分割一黄金分割 xabL L (1)Lbxxaxaba(1)LL152 取 “ ，=0.6

16、1803398874189 12 , ,a bx x21 , , , a ba xx b新或二黄金分割法的根本思想二黄金分割法的根本思想 黄金分割重要的消去性质黄金分割重要的消去性质: x2abL L (1)Lx1 L (1)L设设x1 ，x2 为为a, b 中对称的两个黄金分中对称的两个黄金分割点，割点，LLaxax)1 (21LLxbxb)1 (12x1为为a,x2的的黄金分割点黄金分割点x2为为x1,b的黄金分的黄金分割点割点 在进展区间消去时，不论是消去在进展区间消去时，不论是消去a, x1，还是消去，还是消去x2，b，留下来，留下来的区间中还含一个黄金分割点，只需在对称位置找另一个黄

17、金分割点，的区间中还含一个黄金分割点，只需在对称位置找另一个黄金分割点，又可以进展下一次区间消去。又可以进展下一次区间消去。 每次消去后，新区间的长度是原区间的每次消去后，新区间的长度是原区间的0.618倍，经过倍，经过n次消去后，保次消去后，保留下来的区间长度为留下来的区间长度为0.618nL，需计算函数值的次数仅为，需计算函数值的次数仅为n+1。 黄金分割比黄金分割比 0.618，所以此法也称为，所以此法也称为0.618法。法。 三算法三算法 开场开场b-x1 x2 a 给定给定a0 , b0 ,a=a0 ,b= b0 , =0.618034x2 =a+(b-a), x1 =a+bx2f2

18、 =f(x2), f1 =f(x1) f1 f2是是否否a=x1, x1= x2, f1 =f2 x2 =a+b- x1, f2 =f(x2) 否否b=x2, x2= x1, f2 =f1 x1 =a+b- x2, f1 =f(x1) 否否x*a, x2x*x1, bx*=x1, f*=f1终了终了是是x*=x2, f*=f2是是abx2x1x1 x2 = ab! 在迭代过程中，四个点的顺序一直应该是在迭代过程中，四个点的顺序一直应该是 ax1 x2 b但在计算第二个分割点时运用但在计算第二个分割点时运用x1 =a+bx2 或或 x2 =a+b x1, 由于舍入由于舍入误差的影响，能够破坏误差

19、的影响，能够破坏ax1 x2 b这一顺序，导致混乱。迭代中必需这一顺序，导致混乱。迭代中必需采取一些措施：采取一些措施：(1) 终止限终止限不要获得太小；不要获得太小；(2) 运用双精度运算；运用双精度运算；(3) 经过假设干次运算后，转到算法中的第经过假设干次运算后，转到算法中的第3步，重新开场。步，重新开场。(四四) 黄金分割法的优缺陷黄金分割法的优缺陷 2、缺陷：对解析性能好的单峰函数，与后面要引见的二次插值法、三次、缺陷：对解析性能好的单峰函数，与后面要引见的二次插值法、三次 插值法及牛顿拉夫森法等比较，计算量较大，收敛要慢。插值法及牛顿拉夫森法等比较，计算量较大，收敛要慢。1、优点：

20、算法简单，效率高，只计算函数值，对函数要求低，稳定性好，、优点：算法简单，效率高，只计算函数值，对函数要求低，稳定性好， 对多峰函数或强扭曲的，甚至不延续的，都有效对多峰函数或强扭曲的，甚至不延续的，都有效;2( )2f35 211f2f 迭代迭代 序号序号ab比较比较0-30.0561.94450.1157.6671-3-1.1110.0561.944-0.987-0.9873-1.832-1.111-0.6650.056-0.987-0.9875-1.386-1.111-0.940-0.66511()( 1.3860.665)1.025522ab f(x)=x2, a=-1.5, b=1;

21、精度10-5 a x1 x2 b-3.6034e-005 2.9804e-006 2.7093e-005 6.6107e-00522 0.618034 0.618034 (x1-a)/(x2-a) (b-x2)/(b-x1)-3.6034e-005 -1.1922e-005 2.9804e-006 2.7093e-00523 0.618034 0.618034-1.1922e-005 2.9804e-006 1.219e-005 2.7093e-00524 0.618035 0.618035-1.1922e-005 -2.7117e-006 2.9804e-006 1.219e-00525 0

22、.618032 0.618032-1.1922e-005 -6.2296e-006 -2.7117e-006 2.9804e-00626 0.618038 0.618038x*= -2.7117e-006-=5 12 假设用假设用0.618效果较差效果较差0.61803f(x)=x2, a=-1.5, b=1;精度10-10 a x1 x2 b-2.1976e-007 -9.7339e-008 -2.4483e-008 9.7933e-00834 0.626902 0.626902-9.7339e-008 -2.4483e-008 2.5078e-008 9.7933e-00835 0.595

23、145 0.595145-9.7339e-008 -4.7778e-008 -2.4483e-008 2.5078e-00836 0.680264 0.680264-4.7778e-008 -2.4483e-008 1.7832e-009 2.5078e-00837 0.470017 0.470017-2.4483e-008 1.7832e-009 -1.1888e-009 2.5078e-00838 1.12758 1.12758 (x1-a)/(x2-a) (b-x2)/(b-x1)1.7832e-009 -1.1888e-009 2.805e-008 2.5078e-00839 -0.1

24、13146 -0.1131461.7832e-009 3.1022e-008 -1.1888e-009 2.805e-008-9.83816 -9.83816x* = -1.1888e-009(不满足精度不满足精度)假设用假设用0.618效果更效果更差差f(x)=x2, a=-1.5, b=1;精度10-10重新开场 a x1 x2 b-7.8811e-010 1.9703e-010 8.0587e-010 1.791e-00944 0.618034 0.618034 (x1-a)/(x2-a) (b-x2)/(b-x1)-7.8811e-010 -1.7926e-010 1.9703e-01

25、0 8.0587e-01045 0.618034 0.618034-7.8811e-010 -4.1182e-010 -1.7926e-010 1.9703e-01046 0.618034 0.618034-4.1182e-010 -1.7926e-010 -3.5532e-011 1.9703e-01047 0.618034 0.618034-1.7926e-010 -3.5532e-011 5.3298e-011 1.9703e-01048 0.618034 0.618034-1.7926e-010 -9.0432e-011 -3.5532e-011 5.3298e-01149 0.618

26、034 0.618034-9.0432e-011 -3.5532e-011 -1.6019e-012 5.3298e-01150 0.618034 0.618034x* = -1.6019e-012(满足要求满足要求)-=5 12 设设 f (x)在在 a ,b上可微，且当导数为零时是解。上可微，且当导数为零时是解。 取取 x=(a+b) / 2, 那么那么 f (x) = 0 时时, x 为最小点为最小点, x= x* ; f (x) 0 时时, x 在上升段在上升段, x* x，去掉，去掉x ,b ; f (x) x，去掉，去掉a, x . (本人画算法框图本人画算法框图)a x btg

27、0f ( x )a x btg 0f ( x )3.4 二分法二分法a,b减少，当区间减少，当区间a,b的长度充分小时，或者当的长度充分小时，或者当 充分小时，即可将充分小时，即可将a,b的中点取做极小点的近似点，这的中点取做极小点的近似点，这时有估计：时有估计： *x*()0fx*xx( )f x( )0f x *xx( ) 0f x ( )0, ( )0f af b( )f x*x*()0fx*x02abx0()0fx0, a x0, a x0()fx*22abbax我们知道，在极小点我们知道，在极小点处，处，且，且时，时，递减，即递减，即，而当，而当，函数递增，即，函数递增，即假设找到一

28、个区间假设找到一个区间a, b, 满足性质满足性质。，那么，那么a,b内必有内必有的极小点的极小点，且，且，为找此，为找此，取取，假设，假设， 那么在那么在中有极小点，这时中有极小点，这时用用作为新的区间作为新的区间a,b，继续这个过程，逐渐将区间，继续这个过程，逐渐将区间假设假设 f(x) 是具有极小点的单峰函数，是具有极小点的单峰函数， 那么必存在区间那么必存在区间a, b，使，使f (a)0。由由f (x)的延续性可知，必有的延续性可知，必有x*(a, b)，使，使f (x)=0f (x)xaba1b1a2b2优点：计算量较少，总能找到最优点优点：计算量较少，总能找到最优点缺陷：要计算导

29、数值，收敛速度较慢，收敛速度为一阶缺陷：要计算导数值，收敛速度较慢，收敛速度为一阶其中区间其中区间a, b确实定确实定,普通可采用普通可采用“进退法。进退法。3.5 3.5 多项式近似法二次插值法多项式近似法二次插值法 一根本思想一根本思想对方式复杂的对方式复杂的函数，数学运函数，数学运算时不方便算时不方便找一个近似的、解析找一个近似的、解析性能好、便于计算的性能好、便于计算的简单函数来替代。简单函数来替代。用近似函数的极用近似函数的极小点作为原函数小点作为原函数极小点的近似极小点的近似复杂函数复杂函数 f(x) 极小点极小点x* 简单函数简单函数P(x) 极小点极小点x* 函数近似，函数近似

30、，最优点也应近最优点也应近似似一次多项式一次多项式二次多项式二次多项式三次多项式三次多项式? 如何构造符合要求的多项式如何构造符合要求的多项式 ?f(x)P2(x)二二次插值多项式近似法抛物线法的根本原理二二次插值多项式近似法抛物线法的根本原理设目的函数设目的函数 f(x)在三点在三点x1 x2 x3 上的函数值分别为上的函数值分别为f 1 , f2 , f3 x1x2x3相应的二次插值多项式为相应的二次插值多项式为 P2(x)=a0a1x + a2x2 令令P2(x) 和和f(x)在三点上的函数值相等在三点上的函数值相等三个待定系数三个待定系数 P2(x1)=a0+a1x1 + a2x12

31、f1 P2(x2)=a0+a1x2 + a2x22f2 P2(x3)=a0+a1x3 + a2x32f3a0, a1, a2 P2(x)的平稳点是的平稳点是 P2(x)a1 +2a2x =0 的解的解 21*2aax332211233222211*11111121fxfxfxxfxfxfx222222231312123231312123()()()12 ()()()xxfxxfxxfxxfxxfxxf 132123122ffxxfff等距情形f(x)P2(x)二二次插值多项式近似法抛物线法的根本原理二二次插值多项式近似法抛物线法的根本原理设目的函数设目的函数 f(x)在三点在三点x1 x2 x

32、3 上的函数值分别为上的函数值分别为f 1 , f2 , f3 x1x2x3相应的二次插值多项式为相应的二次插值多项式为 P2(x)=a0a1x + a2x2 三个待定系数三个待定系数P2(x)的平稳点是的平稳点是 P2(x)a1 +2a2x =0 的解的解 21*2aax332211233222211*11111121fxfxfxxfxfxfx222222231312123231312123()()()12 ()()()xxfxxfxxfxxfxxfxxf )x/(xc)x)/(xf(fc)x)/(xf(fc)/ccx(x21x12112122131312131*简化计算简化计算其他插值公式

33、参阅其他插值公式参阅P51-52 (2)-(4)!三点二次插值公式最三点二次插值公式最常用常用.22223121213121313121()()()()12 ()()()()xxffxxffxxffxxff ! 迭代过程要点迭代过程要点 ！f(x)P2(x)x1x2x3x1x2x3x*x*x*假设恣意取假设恣意取x1 x2 x3 三个点，三个点，那么求出的那么求出的x* 能够位于给定区间之外或误差太能够位于给定区间之外或误差太大大最初的三个点最初的三个点x1 x2 x3 应构成一个两边高，中间低的应构成一个两边高，中间低的“ 极小化框架极小化框架 ，即满足即满足f1f2，f3f2 ，且两个等号

34、不同时成立，且两个等号不同时成立极小化框架可由进退算法求得极小化框架可由进退算法求得在完成一次计算后，得到近似在完成一次计算后，得到近似x*，比较比较f(x*)与与f(x2)，以函数值较小的，以函数值较小的x为起点，缩短步长为起点，缩短步长近似近似x* 进退算法进退算法构造构造“ 极小化框架极小化框架x1 x2 x3比较比较f(x*)与与f(x2)，以函数值较小的，以函数值较小的小者小者x为中间点，加上左右两点为中间点，加上左右两点 要进展搜索区间的收缩，然后在新区间中要进展搜索区间的收缩，然后在新区间中重新构造三点组成的重新构造三点组成的“ 极小化框架极小化框架 ，有两种方法，有两种方法终止

35、准那么：采用目的函数值的相对误差或绝对误差来判终止准那么：采用目的函数值的相对误差或绝对误差来判别别 f(x) xx1 x2 x3f(x) xx1x2 x4前进胜利前进胜利 x5极小化框架极小化框架 x1 x2 x3前进失败前进失败x1x2x3x4x5x6极小化框架极小化框架 x3 x2 x1后退后退h0 2h04h0h0h02h04h0三进退算法用于求三进退算法用于求“ 极小化框架或初始搜索区间极小化框架或初始搜索区间四逐次二次插值近似法的算法四逐次二次插值近似法的算法初始点初始点x1，h0，精度，精度1，溢出下限，溢出下限2，步长缩短率，步长缩短率m进退算法即进退算法即“ 极小化框架极小化

36、框架 x1x2x3, 或或x3x2x1计算近似点计算近似点x*检验精度检验精度以以x2与与x* 函数值小者为函数值小者为x1h=mh以以x2与与x*函数值小者为函数值小者为x2,加加左右两点构成左右两点构成“极小化框架极小化框架二次插值法的优点：收敛速度较快，约为二次插值法的优点：收敛速度较快，约为1.32阶阶缺陷：对强扭曲或多峰的，收敛慢，甚至会失败，故要求函数具有较好缺陷：对强扭曲或多峰的，收敛慢，甚至会失败，故要求函数具有较好 的解析性能的解析性能 五五 二次插值法与黄金分割法的结合二次插值法与黄金分割法的结合 黄金分割法黄金分割法二次插值法二次插值法迭代收敛时迭代收敛时迭代不收敛时迭代

37、不收敛时00.20.40.60.811.21.41.61.820246810121416182用二次插值法逼近极小点用二次插值法逼近极小点相邻三点的函数值相邻三点的函数值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 代入公式：代入公式：222222*2313121232313121231 ()()()2 ()()()pxxfxxfxxfxxxfxxfxxfxp*0.555, fp=0.292l解解 l 1确定初始区间确定初始区间l初始区间初始区间a,b=0,2, 另有一中间点另有一中间点x2=1。00.20.40.60.811.21.41.61.82024681

38、012141618l在新区间，相邻三点的函数值在新区间，相邻三点的函数值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1.lxp*0.607, fp=0.243l由于由于fpx2, 新区间新区间a,b=x2, b=0.555,1l|x2-xp * |=|0.555-0.607|=0.0520.2, 迭代终止。迭代终止。lxp*0.607, f*=0.243由于由于fpf2, xp * 0.2, 应继续迭代。应继续迭代。此例黄金分割法需求此例黄金分割法需求5次收缩区间，例次收缩区间，例432( )46164f xxxxx13 1 6x x 0.05l例例

39、3-4用二次插值法求用二次插值法求 的极值点。初始搜的极值点。初始搜索区间索区间 ， 。2130.5 ()2.5xxx1.9545px*2()65.4648()96.9375pf xf x *1 ,px x*23,pxx x*2pxx20.03780.05pxx3.9501pxxl解：取解：取x2点为区间点为区间x1,x3的中点，的中点， , 计算计算x1,x2,x3 3点处的函数值点处的函数值f1=19，f2=-96.9375，f3=124。可见函数值满足。可见函数值满足“高低高形状。高低高形状。l以以x1,x2,x3为插值点构造二次曲线，为插值点构造二次曲线， l求第一次近似的二次曲线求第

40、一次近似的二次曲线p(x)的极小值点，由公式得。的极小值点，由公式得。l ， 比较函数值可知比较函数值可知ll这种情况应消去左边区段这种情况应消去左边区段 . 然后用然后用 作为作为x1,x2,x3新新3点点,重新构造二次曲线重新构造二次曲线p(x)，如此反复计算，直到，如此反复计算，直到 为止。整个迭为止。整个迭代过程的计算结果列于表代过程的计算结果列于表2-2.l从表中可见，经从表中可见，经7次迭代后，次迭代后， ，终止迭代。，终止迭代。故最优点故最优点 -10123456-150-100-5005010015020.03780.05pxx2()155.6850()155.8969pf x

41、f x 3.9501pxx0.618法法, 11次迭代次迭代, x*=3.9968; f*=-155.9996高精度时差别更大！高精度时差别更大！要求计算导数的插值法要求计算导数的插值法 假设目的函数假设目的函数f(x)可导，可经过解可导，可经过解f (x)0求平稳点，进而求出极值点。求平稳点，进而求出极值点。对高度非线性函数，要用逐次逼近求平稳点。对高度非线性函数，要用逐次逼近求平稳点。 一、一、 Newton Newton法法 要求目的函数要求目的函数f(x)在搜索区间内具有二阶延续导数，且知在搜索区间内具有二阶延续导数，且知f (x)和和f (x)的表的表达式达式 。一一 根本思想根本思

42、想 采用迭代法求采用迭代法求(x)=0的根的根 xk (x) xxk+1 xk+2 (xk)=(xk)/(xk1xk) xk+1=xk(xk)/ (xk) 用于求用于求(x) f (x)0的根的根 xK+1=xkf (xk)/ f (xk) 0一点二次插值一点二次插值-切线法切线法2( )f xaxbxc( )2,fxaxb( )2fxa2( )( )xbaxfxfx )a)b牛顿法程序流程：牛顿法程序流程：00100110011(1)()(2)()(3)|()|(4)(2)(5)xfxxxfxfxxxxxxx给定 、 、 ，计算判断是否或否，令,则转结束，结果为例题例题 用用Newton法求

43、解法求解 初始点取初始点取 x0 = 1。迭代三次。迭代三次 x162xf(x) min2解：解：f(x) 的一阶和二阶导函数为的一阶和二阶导函数为 2x164x(x) f3x324(x) f迭代公式为迭代公式为 xK+1=xkf (xk)/ f (xk) 第一次迭代：第一次迭代： x0 = 1, f (x0)12, f (x0)36 x11(12)/361.33 第二次迭代：第二次迭代： x1 = 1.33, f (x1)3.73, f (x1)17.6 x21.33(3.73)/17.61.54 (本例准确解为本例准确解为 x* )58740105. 143第三次迭代：第三次迭代： x2

44、= 1.54, f (x2)0.5865, f (x2) 12.76 x31.54(0.587)/12.761.586 f(x2)=15.11910.618法法1，2上上11次次 x*=1.5795, f*=15.1194例例1： 求求 min f (x)= arctan t d t 解：解： f (x) =arctan x , f (x)=1(1+ x2) 迭代公式：迭代公式： xk +1= xk - (1+ xk 2) arctan xk 取取 x0= 1，计算结果：，计算结果： k xk f (xk) 1f(xk ) 1 1 0.7854 2 2 -0.5708 -0.5187 1.32

45、58 3 0.1169 -0.1164 1.0 4 -0.001095 -0.001095 5 7.9631e-010 x4 x* =0 取取 x0=2，计算结果如下：，计算结果如下：2 -3.535713.9510 -279.3441 1.2202e+005 不收敛！不收敛！ 0 x-3-2-10123-1.5-1-0.500.511.5-3-2-101230.10.20.30.40.50.60.70.80.91)(xf ( )fx,)(2xxf( )2 ,fxx02x 1,22kkkkxxxx10120kkxx2( )1,fxx( )2 ,fxx02x 22111,22kkkkkkxxxx

46、xx2212221121111221121kkkkkkkkkxxxxxxxxx线性收敛线性收敛二次收敛二次收敛11x 212x 314x 154x 2411.02540 x 31.0003,x 41.00000005x Ex1：Ex2：(二二) 优缺陷优缺陷1、优点：收敛速度快；在、优点：收敛速度快；在f(x)=0的单根处，是的单根处，是2阶收敛；在阶收敛；在f(x)=0的重根的重根 处，是线性收敛。例处，是线性收敛。例2、缺陷：需求求二阶导数，假设用数值导数替代，由于舍入误差将影响收敛、缺陷：需求求二阶导数，假设用数值导数替代，由于舍入误差将影响收敛 速度；速度； 收敛性还依赖于初始点及函数

47、性质。收敛性还依赖于初始点及函数性质。f (x) x! 通常在计算程序中规定最大迭代次数，当次数到达通常在计算程序中规定最大迭代次数，当次数到达K还不能满足精还不能满足精度时，度时， 那么以为不收敛，要换一个初始点。那么以为不收敛，要换一个初始点。二、二点二次插值二、二点二次插值a f (x)x bx*1) 割线法割线法根本思想：用割线替根本思想：用割线替代代Newton法中的切线，并与区间消法中的切线，并与区间消去法相结合。去法相结合。c()( )( )( )bacbfbfbfa()( )( )( )2( )ba fbcbf bf afbbaP52 (3-14)P51 (3-12)2) 另一

48、个二点二次插值另一个二点二次插值(f(a)f(b)f(b)较割线法稍好较割线法稍好收敛速度都为收敛速度都为1.618阶阶经过检查区间两端导数来经过检查区间两端导数来收缩区间收缩区间新区间两端点的导数值异新区间两端点的导数值异号号 2p xA xbB xbC根本思想与二次插值法类似：用四个知值如两个点函数值及其导数值根本思想与二次插值法类似：用四个知值如两个点函数值及其导数值构造一个三次多项式构造一个三次多项式P3(x)，用，用P3(x)的极小点近似目的函数的极小点的极小点近似目的函数的极小点x* 利用函数在两点的函数值和导数值：利用函数在两点的函数值和导数值： 32pAaBaCaD三、三、 三

49、次插值三次插值三次插值法的收敛速度比二次插值法要快，到达三次插值法的收敛速度比二次插值法要快，到达2阶收敛速度。阶收敛速度。求出： 32232p aDfap bA baB baC baDf bpaCfap bA baB baCfb)()()()(2)()()()(3)()()(2)()()(23afDafCabafbfabafbfBabbfafafbfabA极值的条件：极值的条件： 2320dpAaBaCd/2aCB2303BBACaAA若0A若极值充分条件为：极值充分条件为：将极值点方程带入上式将极值点方程带入上式22620d pAaBd222223333333 BBACBBACBBACaAABBACCBBAC22232230BBACBBAC 仅取正号仅取正号23CaBBAC两种情形两种情形(A=0/A0)一致为一致为: 2222,0,()33 ufbfaabsf bf abazsuB baCwzubaBACbaazw ,0,()ufbfaabbaazw ,sgn( )ufbfabaazw wvuzwuabawvuzwuabwvuvzwabzuwvwzzwabvabzuwzwabwzuwzabwzwzuwzabuvwzvuabvwzvaba212122222其它方式其它方式二点三次插值法普通