资源描述
,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。不能作为科学依据。,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。不能作为科学依据。,3.1 搜索算法结构,一、下降算法模型,考虑（,NP,）,惯用一个线性搜索方式来求解：迭代中从一点出发沿,下降可行方向,找一个新、性质有改进点。,迭代计算：,其中 为第 次迭代搜索方向，为沿 搜索最正确步长因子（通常也称作最正确步长）。,min,f(x),s.t.,xS,第三章 惯用一维搜索方法,1/66,可行方向：设 ,S,，,d,R,n,d,0,若存在 ，使 ，称,d 为 点可行方向。,同时满足上述两个性质方向称,下降可行方向,。,下降方向,：,设 ,S,，,d,R,n,d,0,若存在 ，使 ，称,d 为 在 点下降方向。,2/66,模型算法,线性搜索求 ，,新点,使x,(,k,+1),S,初始,x,(1),S,k=,1,对,x,(,k,),点选择下降,可行方向,d,(,k,),是否满足停机条件？,停,k,=,k,+1,yes,no,5,3,1,3/66,二、,收敛性,概念,：,考虑（,NP,）,设迭代算法产生点列,x,(,k,),S,.,1.理想收敛性：设,x,*,S,是,g.opt,(全局最优解).当,x,*,x,(,k,),或,x,(,k,),x,*，,k，,满足,时，称算法收敛到最优解,x,*。,min,f(x),s.t.,xS,4/66,因为非线性规划问题复杂性，实用中建立以下收敛性概念：,2,.实用收敛性：定义解集,S,*=,x|x 含有某种性质,例：,S,*=,x|x-g.opt,S,*=,x|x-l.opt,S,*=,x|,f(x)=0,S,*=,x|f(x),(,为给定实数阈值,),5/66,2.实用收敛性（续）,收敛性：设解集,S,*，,x,(,k,),为算法产生点列。以下情况之一成立时，称算法收敛：,1,x,(,k,),S,*;,2,x,(,k,),S,*，,k，,x,(,k,),任意极限点,x,*,S,*。,全局收敛,：对任意初始点,x,(1),算法均收敛。,局部收敛,：当,x,(1),充分靠近解,x,*时，算法收敛。,有限步终止,6/66,三、收敛速度,设算法产生点列,x,(,k,),收敛到解,x,*，且,x,(,k,),x,*,k，,关于算法收敛速度，有,1.线性收敛：当,k,充分大时成立。,2.超线性收敛：,3.二阶收敛：,0，,是 使当,k,充分大时有,7/66,三、收敛速度（续）,定理：设算法点列,x,(,k,),超线性收敛于,x,*,且,x,(,k,),x,*，,k，,那么,证实：,只需注意,|x,(,k+1,),x,*,|-|x,(,k,),x*|x,(,k+,1),x,(k),|x,(,k+,1),x,*,|+|x,(,k,),x*|，除以|x,(,k,),x*|并令k，利用超线性收敛定义可得结果。,该结论导出算法停顿条件可用：,8/66,四、二次终止性,一个算法用于解正定二次函数无约束极小时，有限步迭代可达最优解，则称该算法含有,二次终止性,。,9/66,10/66,问题描述：,已知,而且求出了,处可行下降方向,从,出发，,沿方向,求以下目标函数最优解，,或者选取,使得：,惯用一维搜索算法,11/66,设其最优解为,（叫准确步长因子），,所以线性搜索是,求解一元函数,最优化问,题,（也叫一维最优化问题或,普通地，一维优化问题可描述为：,于是得到一个新点：,一维搜索,）。,或解,12/66,普通地，线性搜索算法分成两个阶段：,第一阶段确定包含理想步长因子,（或问题最优解）搜索区间；,第二阶段采取某种分割技术或插值,方法缩小这个区间。,13/66,搜索区间确定,黄金分割法(0.618法),二次插值法,Newton法,关键点：,单峰函数消去性质、进退算法基本思想、黄金分割法基本思想、重新开始、二次插值法要求、极小化框架、Newton法基本思想、方法比较。,我们主要介绍以下一些搜索方法：,14/66,学习主要性：,1、,工程实践中有时需要直接使用；,2、,多变量最优化基础，迭代中经常要用到。,方法分类：,1、直接法：,迭代过程中只需要计算函数值；,2、微分法：,迭代过程中还需要计算目标函数导数；,15/66,f(x),x,a,b,3.2 搜索区间确定,惯用一维直接法有,消去法,和,近似法,两类。它们都是从某个初始搜索区间出发，利用,单峰函数消去性质,，逐步缩小搜索区间，直到满足精度要求为止。,3.2.1,单峰函数,连续单峰函数,f(x),x,a,b,不连续单峰函数,f(x),x,a,b,离散单峰函数,f(x),x,a,b,非单峰函数,定义：,假如函数,f,(,x,),在区间,a,b,上只有一个极值点,则称,f,(,x,),为,a,b,上单峰函数。,16/66,单峰函数含有一个主要消去性质,定理：,设f(x)是区间a,b上一个单峰函数，x,*,a,b是其极小点，x,1,和x,2,是a,b上任意两点，且ax,1,x,2,b，那么比较f(x,1,)与f(x,2,)值后，可得出以下结论：,f(x),x,a,b,(I)消去a,x,1,x,*,x,1,x,2,f(x),x,a,b,(II)消去x,2,b,x,*,x,2,x,1,(II)若,f(x,1,)f(x,2,),x,*,a,x,2,在单峰函数区间内，计算两个点函数值，比较大小后，就能把搜索区间缩小。在已缩小区间内，仍含有一个函数值，若再计算另一点函数值，比较后就可深入缩小搜索区间,.,（I）若f(x,1,)f(x,2,)，x,*,x,1,b,17/66,3.2.2,进退算法,(或称成功-失败法),怎样确定包含极小点在内初始区间?,（一）,基本思想：,由单峰函数性质可知，函数值在极小点左边严格下降，在右边严格上升。,f(x),x,a,b,x,*,x,0,x,1,x,2,从某个初始点出发，沿函数值下降方向前进，直至发觉函数值上升为止。,由,两边高，中间低三点,，可确定极小点所在初始区间。,18/66,（二）,算法,1、,选定初始点a 和步长h;,f(,x,),x,2、,计算并比较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)，,令 a,1,=a,a,2,=a+3h,停顿运算；不然将步长加倍，并重复上述运算。,a+3h,f(,x,),x,a,a+h,a+7h,a,1,b,1,a-h,a-3h,a-7h,a,1,b,1,则将步长改为,h,。计算f(ah),若f(ah)f(a)，,令 a,1,=ah,a,2,=a+h,停顿运算；不然将步长加倍，继续后退。,仅仅找区间！若深入找最小点，参阅P44!,19/66,(三),几点说明,缺点：效率低；,优点：能够求搜索区间；,注意：,h,选择要适当，,初始步长不能选得太小,；,20/66,3.3,区间消去法黄金分割法,消去法思想：,重复使用单峰函数消去性质，不停缩小包含极小点搜索区间，直到满足精度为止。,消去法优点：,只需计算函数值，通用性强。,消去法设计标准：,（1）迭代公式简单；（2）消去效率高；,（3）对称：,x,1,a,=,b-,x,2,；,（4）保持缩减比：,=(保留区间长度原区间长度)不变。（使每次保留下来节点，,x,1,或,x,2,，在下一次比较中成为一个对应百分比位置节点）。,（一）,黄金分割,x,a,b,L,L,(,1,),L,取“”，,=0.618,03398874189,21/66,（二）,黄金分割法基本思想,黄金分割主要,消去性质,:,x,2,a,b,L,L,(,1,),L,x,1,L,(,1,),L,设,x,1,，x,2,为a,b 中对称两个黄金分割点，,x,1,为a,x,2,黄金分割点,x,2,为x,1,b黄金分割点,在进行区间消去时，不论是消去a,x,1,，还是消去x,2,，b，留下来区间中还含一个黄金分割点，只要在对称位置找另一个黄金分割点，又能够进行下一次区间消去。,每次消去后，新区间长度是原区间0.618倍，经过,n次消去后,，保,留下来,区间长度为0.618,n,L,，需,计算函数值次数仅为n+1,。,黄金分割比,0.618，所以此法也称为0.618法。,22/66,（三）,算法,开始,b-x,1,x,2,a,给定,a,0,b,0,a=a,0,b=,b,0,=0.618034,x,2,=a+,(b-a),x,1,=a+,b,x,2,f,2,=f(x,2,),f,1,=f(x,1,),f,1,f,2,是,否,a=x,1,x,1,=,x,2,f,1,=f,2,x,2,=a+,b-,x,1,f,2,=f(x,2,),否,b=x,2,x,2,=,x,1,f,2,=f,1,x,1,=a+,b-,x,2,f,1,=f(x,1,),否,x,*,a,x,2,x,*,x,1,b,x,*,=x,1,f,*,=f,1,结束,是,x,*,=x,2,f,*,=f,2,是,a,b,x,2,x,1,x,1,x,2,=a,b,23/66,!在迭代过程中，四个点次序一直应该是 a,x,1,x,2,b,但在计算第二个分割点时使用,x,1,=a+,b,x,2,或 x,2,=a+,b,x,1,因为舍入误差影响，可能破坏,a,x,1,x,2,b,这一次序，造成混乱。迭代中必须采取一些办法：,(1),终止限,不要取得太小；,(2),使用双精度运算,；,(3),经过若干次运算后，转到算法中第3步，,重新开始。,(四),黄金分割法优缺点,2、,缺点：对解析性能好单峰函数，与后面要介绍二次插值法、三次,插值法及牛顿拉夫森法等比较，计算量较大，收敛要慢。,1、,优点：算法简单，效率高，只计算函数值，对函数要求低，稳定性好，,对多峰函数或强扭曲，甚至不连续，都有效;,24/66,迭代,序号,a,b,比较,0,-3,0.056,1.944,5,0.115,7.667,1,-3,-1.111,0.056,1.944,-0.987,-0.987,3,-1.832,-1.111,-0.665,0.056,-0.987,-0.987,5,-1.386,-1.111,-0.940,-0.665,例3-2对函数 ，当给定搜索区间 时，试用黄金分割法求极小点。,25/66,f(x)=x,2,a,=-1.5,b,=1;精度10-5,a x,1,x,2,b,-3.6034e-005 2.9804e-006 2.7093e-005 6.6107e-005,22 0.618034 0.618034,(x,1,-a)/(x,2,-a),(b-x,2,)/(b-x,1,),-3.6034e-005-1.1922e-005 2.9804e-006 2.7093e-005,23 0.618034 0.618034,-1.1922e-005 2.9804e-006 1.219e-005 2.7093e-005,24 0.618035 0.618035,-1.1922e-005-2.7117e-006 2.9804e-006 1.219e-005,25 0.618032 0.618032,-1.1922e-005-6.2296e-006-2.7117e-006 2.9804e-006,26 0.618038 0.618038,x*=-2.7117e-006,若用0.618效果较差,0.61803,26/66,f(x)=x,2,a,=-1.5,b,=1;精度10,-10,a x,1,x,2,b,-2.1976e-007-9.7339e-008-2.4483e-008 9.7933e-008,34 0.626902 0.626902,-9.7339e-008-2.4483e-008 2.5078e-008 9.7933e-008,35 0.595145 0.595145,-9.7339e-008-4.7778e-008-2.4483e-008 2.5078e-008,36 0.680264 0.680264,-4.7778e-008-2.4483e-008 1.7832e-009 2.5078e-008,37 0.470017 0.470017,-2.4483e-008 1.7832e-009-1.1888e-009 2.5078e-008,38 1.12758 1.12758,(x1-a)/(x2-a),(b-x2)/(b-x1),1.7832e-009-1.1888e-009 2.805e-008 2.5078e-008,39 -0.113146 -0.113146,1.7832e-009 3.1022e-008-1.1888e-009 2.805e-008,-9.83816 -9.83816,x*=-1.1888e-009(不满足精度),若用0.618效果更差,27/66,f(x)=x,2,a,=-1.5,b,=1;精度10,-10,重新开始,a x,1,x,2,b,-7.8811e-010 1.9703e-010 8.0587e-010 1.791e-009,44 0.618034 0.618034,(x1-a)/(x2-a),(b-x2)/(b-x1),-7.8811e-010-1.7926e-010 1.9703e-010 8.0587e-010,45 0.618034 0.618034,-7.8811e-010-4.1182e-010-1.7926e-010 1.9703e-010,46 0.618034 0.618034,-4.1182e-010-1.7926e-010-3.5532e-011 1.9703e-010,47 0.618034 0.618034,-1.7926e-010-3.5532e-011 5.3298e-011 1.9703e-010,48 0.618034 0.618034,-1.7926e-010-9.0432e-011-3.5532e-011 5.3298e-011,49 0.618034 0.618034,-9.0432e-011-3.5532e-011-1.6019e-012 5.3298e-011,50 0.618034 0.618034,x*=-1.6019e-012(满足要求),28/66,设,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,b,tg,0,f(,x,),a,x,b,tg,0,f(,x,),3.4 二分法,29/66,a,b缩小，当区间a,b,长度充分小时，或者当,充分小时，即可将a,b中点取做极小点近似点，这,时有预计：,我们知道，在极小点,处，,，且,时，,递减，即,，而当,，函数递增，即,若找到一个区间,a,b,满足性质,。,，则,a,b,内必有,极小点,，且,，为找此,，,取,，若,，,则在,中有极小点，这时,用,作为新区间a,b，继续这个过程，逐步将区间,30/66,假设 f(x)是含有极小点单峰函数，,则必存在区间a,b，使f(a)0。,由f(x)连续性可知，必有x,*,(a,b)，使f(x)=0,f(x),x,a,b,a,1,b,1,a,2,b,2,优点：,计算量较少，总能找到最优点,缺点：,要计算导数值，收敛速度较慢，收敛速度为一阶,其中区间a,b确定,普通可采用“进退法”。,31/66,3.5 多项式近似法,二次插值法,（一）,基本思想,对形式复杂函数，数学运算时不方便,找一个近似、解析性能好、便于计算简单函数来代替。,用近似函数极小点作为原函数极小点近似,复杂函数 f(x),极小点,x,*,简单函数P(x),极小点,x,*,函数近似，,最优点也应近似,一次多项式,二次多项式,三次多项式,?,怎样结构符合要求多项式,?,32/66,f(x),P,2,(x),（二）,二次插值多项式近似法（抛物线法）基本原理,设目标函数 f(x)在三点x,1,x,2,x,3,上函数值分别为f,1,f,2,f,3,x,1,x,2,x,3,对应二次插值多项式为,P,2,(x)=a,0,a,1,x+a,2,x,2,令P,2,(x)和f(x)在三点上函数值相等,三个待定系数,P,2,(x,1,)=a,0,+a,1,x,1,+a,2,x,1,2,f,1,P,2,(x,2,)=a,0,+a,1,x,2,+a,2,x,2,2,f,2,P,2,(x,3,)=a,0,+a,1,x,3,+a,2,x,3,2,f,3,a,0,a,1,a,2,P,2,(x)平稳点是 P,2,(x)a,1,+2a,2,x=0 解,33/66,f(x),P,2,(x),（二）,二次插值多项式近似法（抛物线法）基本原理,设目标函数 f(x)在三点x,1,x,2,x,3,上函数值分别为f,1,f,2,f,3,x,1,x,2,x,3,对应二次插值多项式为,P,2,(x)=a,0,a,1,x+a,2,x,2,三个待定系数,P,2,(x)平稳点是 P,2,(x)a,1,+2a,2,x=0 解,简化计算,其它插值公式参阅P51-52(2)-(4)!,三点二次插值公式最惯用.,34/66,!,迭代过程关键点,！,f(x),P,2,(x),x,1,x,2,x,3,x,1,x,2,x,3,x,*,x,*,x,*,若任意取,x,1,x,2,x,3,三个点，,则求出x,*,可能位于给定区间之外或误差太大,最初三个点x,1,x,2,x,3,应组成一个两边高，中间低“极小化框架”，,即满足f,1,f,2,，f,3,f,2,，且两个等号不一样时成立,极小化框架,可由进退算法求得,35/66,在完成一次计算后，得到近似x,*,，,比较f(x,*,)与f(x,2,)，以函数值较小x为起点，缩短步长,近似x,*,进退算法,结构“极小化框架”,x,1,x,2,x,3,比较f(x,*,)与f(x,2,)，以函数值较小小者x为中间点，加上左右两点,要进行搜索区间收缩，然后在新区间中,重新结构三点组成“极小化框架”，有两种方法,终止准则：,采取目标函数值相对误差或绝对误差来判断,36/66,f(x),x,x,1,x,2,x,3,f(x),x,x,1,x,2,x,4,前进成功,x,5,极小化框架 x,1,x,2,x,3,前进失败,x,1,x,2,x,3,x,4,x,5,x,6,极小化框架 x,3,x,2,x,1,后退,h,0,2h,0,4h,0,h,0,h,0,2h,0,4h,0,（三）,进退算法（用于求“极小化框架”或初始搜索区间）,37/66,（四）,逐次二次插值近似法算法,初始点x,1,，,h,0,，精度,1,，溢出下限,2,，步长缩短率,m,进退算法即“极小化框架”x,1,x,2,x,3,或x,3,x,2,x,1,计算近似点x,*,检验精度,以x,2,与x,*,函数值小者为x,1,h,=,mh,以x,2,与x,*,函数值小者为x,2,加左右两点组成“极小化框架”,38/66,二次插值法优点：,收敛速度较快，约为,1.32,阶,缺点：,对强扭曲或多峰，收敛慢，甚至会失败，故要求函数含有很好,解析性能,（五）,二次插值法与黄金分割法结合,黄金分割法,二次插值法,迭代收敛时,迭代不收敛时,39/66,2）用二次插值法迫近极小点,相邻三点函数值:,x,1,=0,x,2,=1,x,3,=2;f,1,=2,f,2,=1,f,3,=18.代入公式：,x,p,*0.555,f,p,=0.292,例 3-3用二次插值法求函数f(,x,)=3,x,3,-4,x,+2极小点，给定,x,0,=0,h,=1,=0.2。,解,1）确定初始区间,初始区间a,b=0,2,另有一中间点,x,2,=1。,40/66,在新区间，相邻三点函数值:,x,1,=0,x,2,=0.555,x,3,=1;f,1,=2,f,2,=0.292,f,3,=1.,x,p,*0.607,f,p,=0.243,因为f,p,x,2,新区间a,b=,x,2,b=0.555,1,|,x,2,-,x,p,*,|=|0.555-0.607|=0.0520.2,迭代终止。,x,p,*0.607,f*=0.243,因为f,p,f,2,x,p,*,0.2,应继续迭代。,此例黄金分割法需要5次收缩区间，,例,41/66,例 3-4用二次插值法求 极值点。初始搜索区间 ，。,图,解：取,x,2,点为区间,x,1,x,3,中点，,计算,x,1,x,2,x,3,3点处函数值f,1,=19，f,2,=-96.9375，f,3,=124。可见函数值满足“高低高”形态。,以,x,1,x,2,x,3,为插值点结构二次曲线，,求第一次近似二次曲线,p,(,x,)极小值点，由公式得。,，比较函数值可知,这种情况应消去左边区段 .然后用 作为,x,1,x,2,x,3,新3点,重新结构二次曲线,p,(,x,)，如此重复计算，直到 为止。整个迭代过程计算结果列于表2-2.,从表中可见，经7次迭代后，终止迭代。故最优点,42/66,43/66,0.618法,11次迭代,x*=3.9968;f*=-155.9996,高精度时差异更大！,44/66,要求计算导数插值法,若目标函数,f,(,x,)可导，可经过解,f,(,x,)0求平稳点，进而求出极值点。,对高度非线性函数，要用逐次迫近求平稳点。,一、,Newton法,要求目标函数,f,(,x,)在搜索区间内含有二阶连续导数，且已知,f,(,x,)和,f,(,x,)表示式。,（一）,基本思想,采取迭代法求(x)=0根,x,k,(x),x,x,k+1,x,k+2,(x,k,)=(x,k,)/(x,k1,x,k,),x,k+1,=x,k,(x,k,)/,(x,k,),用于求(x)f,(x)0根,x,K+1,=x,k,f,(x,k,)/f,”,(x,k,),0,一点二次插值-切线法,45/66,46/66,牛顿法程序流程：,47/66,例题,用Newton法求解,初始点取 x,0,=1。（迭代三次）,解：,f(x)一阶和二阶导函数为,迭代公式为 x,K+1,=x,k,f,(x,k,)/f,”,(x,k,),第一次迭代：x,0,=1,f(x,0,)12,f”(x,0,)36,x,1,1(12)/361.33,第二次迭代：x,1,=1.33,f(x,1,)3.73,f”(x,1,)17.6,x,2,1.33(3.73)/17.61.54,(本例准确解为 x,*,),第三次迭代：x,2,=1.54,f(x,2,),0.5865,f”(x,2,),12.76,x,3,1.54(0.587)/12.761.586 f(x,2,)=15.1191,0.618法1，2上11次,x*=1.5795,f*=15.1194,48/66,例1：求 min,f,(,x,)=,arctan t d t,解,：f,(,x,)=arctan,x,f,(,x,)=1(1+,x,2,),迭代公式：,x,k,+1,=,x,k,-(1+,x,k,2,)arctan,x,k,取,x,0,=1，计算结果：,k,x,k,f(x,k,),1,f(x,k,),1 1 0.7854 2,2 -0.5708 -0.5187 1.3258,3 0.1169 -0.1164 1.0137,4 -0.001095 -0.001095,5,7.9631e-010,x,4,x,*,=0,取,x,0,=2，计算结果以下：,2,-3.5357,13.9510-279.3441 1.2202e+005,不收敛！,49/66,50/66,线性收敛,二次收敛,Ex1：,Ex2：,51/66,(二)优缺点,1、优点：收敛速度快；,在,f,(,x,)=0单根处，是2阶收敛；在f(,x,)=0重根,处，是线性收敛,。,例,2、缺点：,需要求二阶导数，若用,数值导数,代替，因为舍入误差将影响收敛,速度；收敛性还依赖于初始点及函数性质。,f(x),x,!,通常在计算程序中要求最大迭代次数，当次数到达K还不能满足精度时，则认为不收敛，要换一个初始点。,52/66,二、二点二次插值,a,f(x),x,b,x,*,1)割线法基本思想：用割线代替Newton法中切线，并与区间消去法相结合。,c,P52(3-14),P51(3-12),2)另一个二点二次插值(f(a)f(b)f(b)较割线法稍好,收敛速度都为1.618阶,经过检验区间两端导数来收缩区间,新区间两端点导数值异号,53/66,基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导数值）,结构一个三次多项式P,3,(x)，用P,3,(x)极小点近似目标函数极小点x,*,利用函数在两点函数值和导数值：,三、,三次插值,三次插值法收敛速度比二次插值法要快，到达2阶收敛速度。,54/66,求出：,55/66,极值条件,：,56/66,极值充分条件为：,将极值点方程带入上式,仅取正号,两种情形(A=0/A,0,)统一为:,57/66,58/66,其它形式,59/66,二点三次插值法普通流程：,编写程序应用时提议结合教材p55框图编写(嵌入进退法)，其更具普适性、鲁棒性。,60/66,教材P56-58 D.S.C.法、Powell法及其组正当是区间搜索与二次插值法结合！,P59-P64介绍了有理插值、连分式方法属特殊方法，含教材,作者,一些研究结果，大家参阅教材，注意其适应条件，必要时课选取.,61/66,方法综述,（1）,如目标函数能求二阶导数：用Newton法 收敛快,（2）,如目标函数能求一阶导数：首先考虑用三次插值法，收敛较快,对分法、收敛速度慢，但可靠,二次插值如割线法也可选择.,（3）,只需计算函数值方法：首先考虑用二次插值法,收敛快,黄金分割法收敛速度较慢，但可靠,62/66,作业,一、,用黄金分割法求函数f(,x,)=3,x,4,-4,x,2,+2极小点，给定,x,0,=-2,h,=1,=0.1(,x,0,=2,h,=1,=0.1)。,二、ch3 3.1 3.7-9,参考课件见,f1=f(,x,1,)=2,x,2,=,x,0,+h=0+1=1,f2=f(,x,2,)=1,因为f1f2,应加大步长继续向前探测。,x,3,=,x,0,+2h=0+2=2,f3=f(,x,3,)=18,因为f2f3,可知初始区间已经找到，即a,b=,x,1,x,2,=0,2,2)用黄金分割法缩小区间,第一次缩小区间：,x,1,=0+0.382X(2-0)=0.764,f1=0.282,x,2,=0+0.618 X(2-0)=1.236,f2=2.72,f10.2,例 3-1用黄金分割法求函数f(,x,)=3,x,3,-4,x,+2极小点，给定,x,0,=0,h,=1,=0.2。,64/66,第三次缩小区间：,令,x,1,=,x,2,=0.764,f1=f2=0.282,x,2,=0.472+0.618X(1.236-0.472)=0.944,f2=0.747,因为f10.2,应继续缩小区间。,第二次缩小区间：,令,x,2,=,x,1,=0.764,f2=f1=0.282,x,1,=0+0.382X(1.236-0)=0.472,f1=0.317,因为f1f2,故新区间a,b=,x,1,b=0.472,1.236,因为 b-a=1.236-0.472=0.7640.2,应继续缩小区间。,65/66,第四次缩小区间：,令,x,2,=,x,1,=0.764,f2=f1=0.282,x,1,=0.472+0.382X(0.944-0.472)=0.652,f1=0.223,因为f10.2,应继续缩小区间。,第五次缩小区间：,令,x,2,=,x,1,=0.652,f2=f1=0.223,x,1,=0.472+0.382X(0.764-0.472)=0.584,f1=0.262,因为f1f2,故新区间a,b=,x,1,b=0.584,0.764,因为 b-a=0.764-0.584=0.180.2,停顿迭代。,极小点与极小值：,x,*=0.5X(0.584+0.764)=0.674,f(,x,*)=0.222,返回,66/66,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
