单峰函数具有一个重要的消去性质 定理:设f(x)是区间a,b上的一个单峰函数,x'∈|a,b是其极小 点,x1和x2是,b上的任意两点,且a<x1<x2<b,那么比较f(x1) 与x2的值后,可得出如下结论 (D)若(x)≥x),x'∈[x1,b(I)若r(x1)<f(x2),x'∈a,x2l f(x) f( (D消去a,x1 (I消去x2,b 在单峰函数的区间内,计算两个点的函数值,比较大小后,就 能把搜索区间缩小。在已缩小的区间内,仍含有一个函数值, 若再计算另一点的函数值,比较后就可进一步缩小搜索区间
单峰函数具有一个重要的消去性质 定理：设f(x)是区间[a,b]上的一个单峰函数，x *∈[a,b]是其极小 点， x1 和x2是[a, b]上的任意两点，且a<x1 <x2<b，那么比较f(x1 ) 与f(x2 )的值后，可得出如下结论： f(x) a b x (I) 消去[a, x1 ] x x * 1 x2 f(x) a b x (II) 消去[x2 , b] x * x1 x2 (II) 若f(x1 ) < f(x2 ), x*∈[a,x2 ] 在单峰函数的区间内，计算两个点的函数值，比较大小后，就 能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值， 若再计算另一点的函数值，比较后就可进一步缩小搜索区间. （I） 若f(x1 )≥f(x2 )，x *∈[x1 ,b]
如何确定包含极小点在内的初始区间? §322进退算法(或称成功失败法) (一)基本思想: 由单峰函数的性质可知,函数值在极小点左边严格下降,在右 边严格上升。 从某个初始点出发,沿函数值下降的方向前进,直至发现函 数值上升为止。 由两边高,中间低的三点,可确定极小点所在的初始区间
§3.2.2 进退算法 (或称成功-失败法) 如何确定包含极小点在内的初始区间 ? （一）基本思想： 由单峰函数的性质可知，函数值在极小点左边严格下降，在右 边严格上升。 f(x) a b x x x * 0 x1 x2 从某个初始点出发，沿函数值下降的方向前进，直至发现函 数值上升为止。 由两边高，中间低的三点，可确定极小点所在的初始区间
(二)算法 1、选定初始点a和步长h; 2、计算并比较fa)和f(a+h);有前进(1)和后退(2)两种情况: (1)前进运算:若fa)≥fa+h),则步长加倍,计算a+3h)。若a+b)≤f(a+3h, 令a1=a,a2=a+3h,停止运算;否则将步长加倍,并重复上述运算。 (2)后退运算:若a)<fa+h),则将步长改为一h。计算f(a-h,若fa-h)≥fa), 令a1=a-h,a2=a+h,停止运算;否则将步长加倍,继续后退。 仅仅找区间!若进一步找 最小点,参阅P44 f(x) f(r) a ath a+3h a+7h a-Th a-h a-h a thx
（二）算法 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)， 令 a1=a, a2=a+3h, 停止运算；否则将步长加倍，并重复上述运算。 a+3h f(x) x a+7h a a+h a1 b1 a-3h a-h a-7h a1 b1 则将步长改为－h。计算f(a－h), 若f(a－h) ≥ f(a)， 令 a1=a－h, a2=a+h, 停止运算；否则将步长加倍，继续后退。 ——仅仅找区间！若进一步找 最小点，参阅P44!
(三)几点说明 缺点:效率低; 优点:可以求搜索区间; 注意:h选择要适当,初始步长不能选得太小;
(三) 几点说明 缺点：效率低； 优点：可以求搜索区间； 注意：h选择要适当，初始步长不能选得太小；
§33区间消去法一黄金分割法 消去法的思想:反复使用单峰函数的消去性质,不断缩小包含极小点的 搜索区间,直到满足精度为止b]→x,x][a1=ax成x,b] 消去法的优点:只需计算函数值,通用性强。 消去法的设计原则:(1)迭代公式简单;(2)消去效率高 (3)对称:x1-a=bx2;(4)保持缩减比:=(保留的区间长度/原 区间长度)不变。(使每次保留下来的节点,x或x2,在下一次的比 较中成为一个相应比例位置的节点)。 (一)黄金分割 6-x x-a x-a IL (1-A)L 1-x)L L 1士 取“+”,=0.61803398874189
§3.3 区间消去法－黄金分割法 消去法的思想：反复使用单峰函数的消去性质，不断缩小包含极小点的 搜索区间，直到满足精度为止。 消去法的优点：只需计算函数值，通用性强。 消去法的设计原则：（1）迭代公式简单；（2）消去效率高； （3）对称：x1 – a = b-x2 ；（4）保持缩减比：λ=(保留的区间长度／原 区间长度) 不变。（使每次保留下来的节点，x1或 x2 ，在下一次的比 较中成为一个相应比例位置的节点）。 （一）黄金分割 x a b L λL (1－λ)L b x x a x a b a − − = = − − (1 )L L − = 1 5 2 − = 取 “ ＋”，λ=0.61803398874189 1 2 [ , ] [ , ] a b x x → 2 1 [ , ] [ , ] [ , ] a b a x x b 新 = 或