搜索算法结构教学课件市公开课一等奖百校联赛特等奖课件.pptx

3.1 3.1 3.1 3.1 搜索算法结构搜索算法结构搜索算法结构搜索算法结构一、下降算法模型一、下降算法模型 考虑（考虑（NP）惯用一个线性搜索方式来求解：迭代中从一惯用一个线性搜索方式来求解：迭代中从一点出发沿点出发沿下降可行方向下降可行方向找一个新、性质有找一个新、性质有改进点。改进点。迭代计算：其中 为第 次迭代搜索方向，为沿 搜索最正确步长因子（通常也称作最正确步长）。min f(x)s.t.xS第三章第三章 惯用一维搜索方法惯用一维搜索方法第1页可行方向：设可行方向：设 S，dRn,d0,若存在若存在 ，使，使 ，称，称d 为为 点可点可行方向。行方向。同时满足上述两个性质方向称同时满足上述两个性质方向称下降可行方向下降可行方向。下降方向下降方向 ：设设 S，d Rn,d0,若存在若存在 ，使，使 ，称，称d 为为 在在 点下降方向。点下降方向。第2页l模型算法模型算法线性搜索求线性搜索求 ，新点新点使使x(k+1)S初始初始x(1)S,k=1对对x(k)点选择下降点选择下降可行方向可行方向d(k)是否满足停机条件？是否满足停机条件？停停k=k+1yesno531第3页二、二、收敛性收敛性概念概念：考虑（考虑（NP）设迭代算法产生点列设迭代算法产生点列x(k)S.1.理想收敛性：设理想收敛性：设x*S是是g.opt(全局最优解全局最优解).当当x*x(k)或或 x(k)x*，k，满足满足 时，称算法收敛到最优解时，称算法收敛到最优解 x*。min f(x)s.t.xS第4页 因为非线性规划问题复杂性，实用中建立以下收敛因为非线性规划问题复杂性，实用中建立以下收敛性概念性概念：2.实用收敛性：定义解集实用收敛性：定义解集 S*=x|x 含有某种性质含有某种性质 例：例：S*=x|x-g.opt S*=x|x-l.opt S*=x|f(x)=0 S*=x|f(x)(为给定实数阈值为给定实数阈值)第5页2.实用收敛性（续）实用收敛性（续）收敛性：设解集收敛性：设解集S*，x(k)为算法产生点列。为算法产生点列。以下情况之一成立时，称算法收敛：以下情况之一成立时，称算法收敛：1 x(k)S*;2x(k)S*，k，x(k)任意极限点任意极限点x*S*。全局收敛全局收敛：对任意初始点：对任意初始点x(1),算法均收敛。算法均收敛。局部收敛局部收敛：当：当x(1)充分靠近解充分靠近解x*时，算法收敛。时，算法收敛。有限步终止有限步终止第6页三、收敛速度三、收敛速度 设算法产生点列设算法产生点列x(k)收敛到解收敛到解x*，且，且x(k)x*,k，关于算法收敛速度，有关于算法收敛速度，有1.线性收敛：线性收敛：当当k充分大时成立。充分大时成立。2.超线性收敛：超线性收敛：3.二阶收敛：二阶收敛：0，是是 使当使当k充分大时有充分大时有第7页三、收敛速度（续）三、收敛速度（续）定理：设算法点列定理：设算法点列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页四、二次终止性四、二次终止性一个算法用于解正定二次函数无约束极小时，一个算法用于解正定二次函数无约束极小时，有限步迭代可达最优解，则称该算法含有有限步迭代可达最优解，则称该算法含有二二次终止性次终止性。第9页第10页问题描述：问题描述：问题描述：问题描述：已知而且求出了处可行下降方向从出发，沿方向求以下目标函数最优解，或者选取使得：惯用一维搜索算法惯用一维搜索算法惯用一维搜索算法惯用一维搜索算法第11页设其最优解为（叫准确步长因子），所以线性搜索是求解一元函数最优化问题（也叫一维最优化问题或普通地，一维优化问题可描述为：于是得到一个新点：一维搜索）。或解第12页普通地，线性搜索算法分成两个阶段：第一阶段确定包含理想步长因子（或问题最优解）搜索区间；第二阶段采取某种分割技术或插值方法缩小这个区间。第13页 搜索区间确定 黄金分割法(0.618法)二次插值法 Newton法关键点：关键点：单峰函数消去性质、进退算法基本思想、黄金分割单峰函数消去性质、进退算法基本思想、黄金分割法基本思想、重新开始、二次插值法要求、极小化框架、法基本思想、重新开始、二次插值法要求、极小化框架、Newton法基本思想、方法比较。法基本思想、方法比较。我们主要介绍以下一些搜索方法：我们主要介绍以下一些搜索方法：第14页学习主要性：学习主要性：1、工程实践中有时需要直接使用；工程实践中有时需要直接使用；2、多变量最优化基础，迭代中经常要用到。多变量最优化基础，迭代中经常要用到。方法分类：方法分类：1、直接法：、直接法：迭代过程中只需要计算函数值；迭代过程中只需要计算函数值；2、微分法：、微分法：迭代过程中还需要计算目标函数导数；迭代过程中还需要计算目标函数导数；第15页f(x)xab3.2 搜索区间确定 惯用一维直接法有惯用一维直接法有消去法消去法和和近似法近似法两类。它们都是从某两类。它们都是从某个初始搜索区间出发，利用个初始搜索区间出发，利用单峰函数消去性质单峰函数消去性质，逐步缩小搜，逐步缩小搜索区间，直到满足精度要求为止。索区间，直到满足精度要求为止。3.2.1 单峰函数单峰函数 连续单峰函数连续单峰函数f(x)xab不连续单峰函数不连续单峰函数f(x)xab离散单峰函数离散单峰函数f(x)xa b非单峰函数非单峰函数定义：定义：假如函数假如函数f(x)在区间在区间a,b上只有一个极值点上只有一个极值点,则称则称f(x)为为 a,b上单峰函数。上单峰函数。第16页单峰函数含有一个主要消去性质单峰函数含有一个主要消去性质定理：定理：设设f(x)是区间是区间a,b上一个单峰函数，上一个单峰函数，x*a,b是其极小点，是其极小点，x1 和和x2是是a,b上任意两点，且上任意两点，且ax1 x2b，那么比较，那么比较f(x1)与与f(x2)值后，可得出以下结论：值后，可得出以下结论：f(x)xab(I)消去消去a,x1 x*x1x2f(x)xab(II)消去消去x2,bx*x2x1(II)(II)若若f(x1)f(x2),x*a,x2在单峰函数区间内，计算两个点函数值，比较大小后，就能把在单峰函数区间内，计算两个点函数值，比较大小后，就能把搜索区间缩小。在已缩小区间内，仍含有一个函数值，若再计搜索区间缩小。在已缩小区间内，仍含有一个函数值，若再计算另一点函数值，比较后就可深入缩小搜索区间算另一点函数值，比较后就可深入缩小搜索区间.（I）若若f(x1)f(x2)，x*x1,b第17页3.2.2 进退算法进退算法(或称成功或称成功-失败失败法法)怎样确定包含极小点在内初始区间怎样确定包含极小点在内初始区间?（一）（一）基本思想：基本思想：由单峰函数性质可知，函数值在极小点左边严格下降，在右边由单峰函数性质可知，函数值在极小点左边严格下降，在右边严格上升。严格上升。f(x)xabx*x0 x1x2从某个初始点出发，沿函数值下降方向前进，直至发觉函数值从某个初始点出发，沿函数值下降方向前进，直至发觉函数值上升为止。上升为止。由由两边高，中间低三点两边高，中间低三点，可确定极小点所在初始区间。，可确定极小点所在初始区间。第18页（二）（二）算法算法1、选定初始点选定初始点a 和步长和步长h;f(x)x2、计算并比较计算并比较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(ah)f(a)，令令 a1=ah,a2=a+h,停顿运算；不然将步长加倍，继续后退。停顿运算；不然将步长加倍，继续后退。仅仅找区间！若深入找最仅仅找区间！若深入找最小点，参阅小点，参阅P44!第19页(三三)几点说明几点说明缺点：效率低；缺点：效率低；优点：能够求搜索区间；优点：能够求搜索区间；注意：注意：h 选择要适当，选择要适当，初始步长不能选得太小初始步长不能选得太小；第20页3.3 区间消去法黄金分割法区间消去法黄金分割法 消去法思想：消去法思想：重复使用单峰函数消去性质，不停缩小包含极小点搜索区重复使用单峰函数消去性质，不停缩小包含极小点搜索区间，直到满足精度为止。间，直到满足精度为止。消去法优点：消去法优点：只需计算函数值，通用性强。只需计算函数值，通用性强。消去法设计标准：消去法设计标准：（1）迭代公式简单；（）迭代公式简单；（2）消去效率高；）消去效率高；（3）对称：）对称：x1 a=b-x2；（4）保持缩减比：）保持缩减比：=(保留区间长度原保留区间长度原区间长度区间长度)不变。（使每次保留下来节点，不变。（使每次保留下来节点，x1或或 x2，在下一次比较中，在下一次比较中成为一个对应百分比位置节点成为一个对应百分比位置节点）。）。（一）（一）黄金分割黄金分割 xabL LL (1 1)L L取“”，=0.61803398874189 第21页（二）（二）黄金分割法基本思想黄金分割法基本思想 黄金分割主要黄金分割主要消去性质消去性质:x2abL LL (1 1)L Lx1 LL (1 1)L L设设x1，x2 为为a,b 中对称两个黄金分割点，中对称两个黄金分割点，x1为为a,x2黄黄金分割点金分割点x2为为x1,b黄金分割黄金分割点点 在在进进行行区区间间消消去去时时，不不论论是是消消去去a,x1，还还是是消消去去x2，b，留留下下来来区区间间中中还还含含一一个个黄黄金金分分割割点点，只只要要在在对对称称位位置置找找另另一一个个黄黄金金分分割割点点，又又能够进行下一次区间消去。能够进行下一次区间消去。每次消去后，新区间长度是原区间每次消去后，新区间长度是原区间0.618倍，经过倍，经过n次消去后次消去后，保，保留下来留下来区间长度为区间长度为0.618nL，需，需计算函数值次数仅为计算函数值次数仅为n+1。黄金分割比黄金分割比 0.618，所以此法也称为，所以此法也称为0.618法。法。第22页（三）（三）算法算法 开始开始b-x1 x2 a 给定给定a0,b0,a=a0,b=b0,=0.618034x2=a+(b-a),x1=a+bx2f2=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第23页!在迭代过程中，四个点次序一直应该是在迭代过程中，四个点次序一直应该是 ax1 x2 b但在计算第二个分割点时使用但在计算第二个分割点时使用x1=a+bx2 或或 x2=a+b x1,因为舍入误差影因为舍入误差影响，可能破坏响，可能破坏ax1 x2 b这一次序，造成混乱。迭代中必须采取一些办法：这一次序，造成混乱。迭代中必须采取一些办法：(1)终止限终止限 不要取得太小；不要取得太小；(2)使用双精度运算使用双精度运算；(3)经过若干次运算后，转到算法中第经过若干次运算后，转到算法中第3步，步，重新开始。重新开始。(四四)黄金分割法优缺点黄金分割法优缺点 2、缺点：对解析性能好单峰函数，与后面要介绍二次插值法、三次缺点：对解析性能好单峰函数，与后面要介绍二次插值法、三次 插值法及牛顿拉夫森法等比较，计算量较大，收敛要慢。插值法及牛顿拉夫森法等比较，计算量较大，收敛要慢。1、优点：算法简单，效率高，只计算函数值，对函数要求低，稳定性好，优点：算法简单，效率高，只计算函数值，对函数要求低，稳定性好，对多峰函数或强扭曲，甚至不连续，都有效对多峰函数或强扭曲，甚至不连续，都有效;第24页 迭代迭代 序号序号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.665例例例例3-23-2对函数对函数对函数对函数 ，当给定搜索区间，当给定搜索区间，当给定搜索区间，当给定搜索区间 时，时，时，时，试用黄金分割法求极小点。试用黄金分割法求极小点。试用黄金分割法求极小点。试用黄金分割法求极小点。第25页f(x)=x2,a=-1.5,b=1;精度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.618032 0.618032-1.1922e-005-6.2296e-006-2.7117e-006 2.9804e-00626 0.618038 0.618038x*=-2.7117e-006若用若用0.618效果较差效果较差0.61803第26页f(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.595145 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.113146 -0.1131461.7832e-009 3.1022e-008-1.1888e-009 2.805e-00840-9.83816 -9.83816x*=-1.1888e-009(不满足精度不满足精度)若用若用0.618效果更差效果更差第27页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-010 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.618034 0.618034-9.0432e-011-3.5532e-011-1.6019e-012 5.3298e-01150 0.618034 0.618034x*=-1.6019e-012(满足要求满足要求)第28页 设设 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 0f(x)a x btg 0f(x)3.4 二分法二分法第29页a,b缩小，当区间缩小，当区间a,b长度充分小时，或者当长度充分小时，或者当 充分小时，即可将充分小时，即可将a,b中点取做极小点近似点，这中点取做极小点近似点，这时有预计：时有预计：我们知道，在极小点我们知道，在极小点处，处，且，且时，时，递减，即递减，即，而当，而当，函数递增，即，函数递增，即若找到一个区间若找到一个区间a,b,满足性质满足性质。，则，则a,b内必有内必有极小点极小点，且，且，为找此，为找此，取取，若，若，则在则在中有极小点，这时中有极小点，这时用用作为新区间作为新区间a,b，继续这个过程，逐步将区间，继续这个过程，逐步将区间第30页假设假设 f(x)是含有极小点单峰函数，是含有极小点单峰函数，则必存在区间则必存在区间a,b，使，使f(a)0。由由f(x)连续性可知，必有连续性可知，必有x*(a,b)，使，使f(x)=0f(x)xaba1b1a2b2优点：优点：计算量较少，总能找到最优点计算量较少，总能找到最优点缺点：缺点：要计算导数值，收敛速度较慢，收敛速度为一阶要计算导数值，收敛速度较慢，收敛速度为一阶其中区间a,b确定,普通可采用“进退法”。第31页3.5 多项式近似法多项式近似法二次插值法二次插值法 （一）（一）基本思想基本思想对形式复杂函对形式复杂函数，数学运算数，数学运算时不方便时不方便找一个近似、解析性找一个近似、解析性能好、便于计算简单能好、便于计算简单函数来代替。函数来代替。用近似函数极小用近似函数极小点作为原函数极点作为原函数极小点近似小点近似复杂函数复杂函数 f(x)极小点极小点x*简单函数简单函数P(x)极小点极小点x*函数近似，函数近似，最优点也应近最优点也应近似似一次多项式一次多项式二次多项式二次多项式三次多项式三次多项式?怎样结构符合要求多项式怎样结构符合要求多项式?第32页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 f1 P2(x2)=a0+a1x2+a2x22f2 P2(x3)=a0+a1x3+a2x32f3a0,a1,a2 P2(x)平稳点是平稳点是 P2(x)a1+2a2x=0 解解 第33页f(x)P2(x)（二）（二）二次插值多项式近似法（抛物线法）基本原理二次插值多项式近似法（抛物线法）基本原理设目标函数设目标函数 f(x)在三点在三点x1 x2 x3 上函数值分别为上函数值分别为f 1,f2,f3 x1x2x3对应二次插值多项式为对应二次插值多项式为 P2(x)=a0a1x+a2x2 三个待定系数三个待定系数P2(x)平稳点是平稳点是 P2(x)a1+2a2x=0 解解 简化计算简化计算其它插值公式参阅其它插值公式参阅P51-52(2)-(4)!三点二次插值公式最三点二次插值公式最惯用惯用.第34页!迭代过程关键点迭代过程关键点！f(x)P2(x)x1x2x3x1x2x3x*x*x*若任意取若任意取x1 x2 x3 三个点，三个点，则求出则求出x*可能位于给定区间之外或误差太大可能位于给定区间之外或误差太大最初三个点最初三个点x1 x2 x3 应组成一个两边高，中间低应组成一个两边高，中间低“极小化框架极小化框架”，即满足即满足f1f2，f3f2，且两个等号不一样时成立，且两个等号不一样时成立极小化框架极小化框架可由进退算法求得可由进退算法求得第35页在完成一次计算后，得到近似在完成一次计算后，得到近似x*，比较比较f(x*)与与f(x2)，以函数值较小，以函数值较小x为起点，缩短步长为起点，缩短步长近似近似x*进退算法进退算法结构结构“极小化框架极小化框架”x1 x2 x3比比较较f(x*)与与f(x2)，以以函函数数值值较较小小小小者者x为中间点，加上左右两点为中间点，加上左右两点 要进行搜索区间收缩，然后在新区间中要进行搜索区间收缩，然后在新区间中重新结构三点组成重新结构三点组成“极小化框架极小化框架”，有两种方法，有两种方法终止准则：终止准则：采取目标函数值相对误差或绝对误差来判断采取目标函数值相对误差或绝对误差来判断 第36页f(x)xx1x2 x3f(x)xx1x2 x4前进成功前进成功 x5极小化框架极小化框架 x1 x2 x3前进失败前进失败x1x2x3x4x5x6极小化框架极小化框架 x3 x2 x1后退后退h02h04h0h0h02h04h0（三）（三）进退算法（用于求进退算法（用于求“极小化框架极小化框架”或初始搜索区间）或初始搜索区间）第37页（四）（四）逐次二次插值近似法算法逐次二次插值近似法算法初始点初始点x1，h0，精度，精度1，溢出下限，溢出下限2，步长缩短率，步长缩短率m进退算法即进退算法即“极小化框架极小化框架”x1x2x3,或或x3x2x1计算近似点计算近似点x*检验精度检验精度以以x2与与x*函数值小者为函数值小者为x1h=mh以以x2与与x*函函数数值值小小者者为为x2,加加左左右右两两点点组组成成“极极小小化化框框架架”第38页二次插值法优点：二次插值法优点：收敛速度较快，约为收敛速度较快，约为1.32阶阶缺点：缺点：对强扭曲或多峰，收敛慢，甚至会失败，故要求函数含有很好对强扭曲或多峰，收敛慢，甚至会失败，故要求函数含有很好 解析性能解析性能（五）（五）二次插值法与黄金分割法结合二次插值法与黄金分割法结合 黄金分割法黄金分割法二次插值法二次插值法迭代收敛时迭代收敛时迭代不收敛时迭代不收敛时第39页2）用二次插值法迫近极小点）用二次插值法迫近极小点相邻三点函数值相邻三点函数值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.代入代入公式：公式：xp*0.555,fp=0.292例例例例 3-3 3-3用二次插值法求函数用二次插值法求函数用二次插值法求函数用二次插值法求函数f(f(x x)=3)=3x x3 3-4-4x x+2+2极小点，极小点，极小点，极小点，给定给定给定给定 x x0 0=0,=0,h h=1,=0.2=1,=0.2。l解解 1）确定初始区间）确定初始区间初始区间初始区间a,b=0,2,另有一中间点另有一中间点x2=1。第40页l在新区间，相邻三点函数值在新区间，相邻三点函数值:x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1.lxp*0.607,fp=0.243因为因为fpx2,新区间新区间a,b=x2,b=0.555,1|x2-xp*|=|0.555-0.607|=0.0520.2,迭代终止。迭代终止。lxp*0.607,f*=0.243因为因为fpf2,xp*0.2,应继续迭代。应继续迭代。此例黄金分割法需要此例黄金分割法需要5次收缩区间，次收缩区间，例例第41页l例例 3-4用二次插值法求用二次插值法求 极值点。初始搜索极值点。初始搜索区间区间 ，。图图l解：取解：取x2点为区间点为区间x1,x3中点，中点，,计算计算x1,x2,x3 3点处函数值点处函数值f1=19，f2=-96.9375，f3=124。可见函数值满足。可见函数值满足“高高低高低高”形态。形态。l以以x1,x2,x3为插值点结构二次曲线，为插值点结构二次曲线，l求第一次近似二次曲线求第一次近似二次曲线p(x)极小值点，由公式得。极小值点，由公式得。l ，比较函数值可知比较函数值可知ll这种情况应消去左边区段这种情况应消去左边区段 .然后用然后用 作为作为x1,x2,x3新新3点点,重新结构二次曲线重新结构二次曲线p(x)，如此重复计算，直到，如此重复计算，直到 为止。整个迭为止。整个迭代过程计算结果列于表代过程计算结果列于表2-2.l从表中可见，经从表中可见，经7次迭代后，次迭代后，终止迭代。，终止迭代。故最优点故最优点 第42页第43页0.618法法,11次迭代次迭代,x*=3.9968;f*=-155.9996高精度时差异更大！高精度时差异更大！第44页要求计算导数插值法要求计算导数插值法 若目标函数若目标函数f(x)可导，可经过解可导，可经过解f(x)0求平稳点，进而求出极值点。求平稳点，进而求出极值点。对高度非线性函数，要用逐次迫近求平稳点。对高度非线性函数，要用逐次迫近求平稳点。一、一、Newton法法 要求目标函数要求目标函数f(x)在搜索区间内含有二阶连续导数，且已知在搜索区间内含有二阶连续导数，且已知f(x)和和f(x)表示式表示式。（一）（一）基本思想基本思想 采取迭代法求采取迭代法求(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一点二次插值一点二次插值-切线法切线法第45页第46页牛顿法程序流程：牛顿法程序流程：第47页例题例题 用用Newton法求解法求解 初始点取初始点取 x0=1。（迭代三次）。（迭代三次）解：解：f(x)一阶和二阶导函数为一阶和二阶导函数为 迭代公式为迭代公式为 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*)第三次迭代：第三次迭代：x2=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第48页例例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.3258 3 0.1169 -0.1164 1.0137 4 -0.001095 -0.001095 5 7.9631e-010 x4 x*=0 取取 x0=2，计算结果以下：，计算结果以下：2 -3.535713.9510-279.3441 1.2202e+005 不收敛！不收敛！第49页第50页线性收敛线性收敛二次收敛二次收敛Ex1：Ex2：第51页(二二)优缺点优缺点1、优点：收敛速度快；、优点：收敛速度快；在在f(x)=0单根处，是单根处，是2阶收敛；在阶收敛；在f(x)=0重根重根 处，是线性收敛处，是线性收敛。例例2、缺点：、缺点：需要求二阶导数，若用需要求二阶导数，若用数值导数数值导数代替，因为舍入误差将影响收敛代替，因为舍入误差将影响收敛 速度；速度；收敛性还依赖于初始点及函数性质。收敛性还依赖于初始点及函数性质。f(x)x!通常在计算程序中要求最大迭代次数，当次数到达通常在计算程序中要求最大迭代次数，当次数到达K还不能满足还不能满足精度时，精度时，则认为不收敛，要换一个初始点。则认为不收敛，要换一个初始点。第52页二、二点二次插值二、二点二次插值a f(x)x bx*1)割线法割线法基本思想：用割线代基本思想：用割线代替替Newton法中切线，并与区间消去法中切线，并与区间消去法相结合。法相结合。cP52(3-14)P51(3-12)2)另一个二点二次插值另一个二点二次插值(f(a)f(b)f(b)较割线法稍好较割线法稍好收敛速度都为收敛速度都为1.618阶阶经过检验区间两端导数来经过检验区间两端导数来收缩区间收缩区间新区间两端点导数值异号新区间两端点导数值异号第53页基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导数值）基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导数值）结构一个三次多项式结构一个三次多项式P3(x)，用，用P3(x)极小点近似目标函数极小点极小点近似目标函数极小点x*利用函数在两点函数值和导数值：利用函数在两点函数值和导数值：三、三、三次插值三次插值三次插值法收敛速度比二次插值法要快，到达三次插值法收敛速度比二次插值法要快，到达2阶收敛速度。阶收敛速度。第54页求出：第55页极值条件极值条件：第56页极值充分条件为：极值充分条件为：将极值点方程带入上式将极值点方程带入上式仅取正号仅取正号两种情形两种情形(A=0/A0)统一为统一为:第57页第58页其它形式其它形式第59页二点三次插值法普通流程：二点三次插值法普通流程：编写程序应用时提议结合教材编写程序应用时提议结合教材p55p55框图编写框图编写(嵌入进嵌入进退法退法)，其更具普适性、鲁棒性。，其更具普适性、鲁棒性。第60页教材教材P56-58 D.S.C.法、法、Powell法及其组正当是区间法及其组正当是区间搜索与二次插值法结合！搜索与二次插值法结合！P59-P64介绍了有理插值、连分式方法属特殊方法，介绍了有理插值、连分式方法属特殊方法，含教材含教材作者作者一些研究结果，大家参阅教材，注意其适一些研究结果，大家参阅教材，注意其适应条件，必要时课选取应条件，必要时课选取.第61页方法综述方法综述（1）如目标函数能求二阶导数：如目标函数能求二阶导数：用用Newton法法 收敛快收敛快（2）如目标函数能求一阶导数如目标函数能求一阶导数：首先考虑用三次插值法，收敛较快：首先考虑用三次插值法，收敛较快 对分法、收敛速度慢，但可靠对分法、收敛速度慢，但可靠 二次插值如割线法也可选择二次插值如割线法也可选择.（3）只需计算函数值方法只需计算函数值方法：首先考虑用二次插值法首先考虑用二次插值法,收敛快收敛快 黄金分割法收敛速度较慢，但可靠黄金分割法收敛速度较慢，但可靠 第62页作业一、用黄金分割法求函数用黄金分割法求函数f(x)=3x4-4x2+2极小极小点，给定点，给定 x0=-2,h=1,=0.1(x0=2,h=1,=0.1)。二、ch3 3.1 3.7-9参考课件见http:/ 第一次缩小区间：第一次缩小区间：x1=0+0.382X(2-0)=0.764,f1=0.282 x2=0+0.618 X(2-0)=1.236,f2=2.72 f10.2例例例例 3-1 3-1用黄金分割法求函数用黄金分割法求函数用黄金分割法求函数用黄金分割法求函数f(f(x x)=3)=3x x3 3-4-4x x+2+2极小点，极小点，极小点，极小点，给定给定给定给定 x x0 0=0,=0,h h=1,=0.2=1,=0.2。第64页第三次缩小区间：第三次缩小区间：l令令 x1=x2=0.764,f1=f2=0.282lx2=0.472+0.618X(1.236-0.472)=0.944,f2=0.747l因为因为f10.2,应继续缩小区间。应继续缩小区间。第二次缩小区间：第二次缩小区间：l令令 x2=x1=0.764,f2=f1=0.282lx1=0+0.382X(1.236-0)=0.472,f1=0.317l因为因为f1f2,故新区间故新区间a,b=x1,b=0.472,1.236l因为因为 b-a=1.236-0.472=0.7640.2,应继续缩小区间。应继续缩小区间。第65页第四次缩小区间：第四次缩小区间：l令令 x2=x1=0.764,f2=f1=0.282lx1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223l因为因为f10.2,应继续缩小区间。应继续缩小区间。第五次缩小区间：第五次缩小区间：l令令 x2=x1=0.652,f2=f1=0.223lx1=0.472+0.382X(0.764-0.472)=0.584,f1=0.262l因为因为f1f2,故新区间故新区间a,b=x1,b=0.584,0.764l因为因为 b-a=0.764-0.584=0.180.2,停顿迭代。停顿迭代。极小点与极小值：极小点与极小值：x*=0.5X(0.584+0.764)=0.674,f(x*)=0.222返回返回第66页