4__一维搜索

二、0.618法（黄金分割法）
令 a 2 = 1 . 146 , b 2 = 2 . 292 ′ x 3 = 1 . 146 + 0 . 382 ( 2 . 292 − 1 . 146 ) = 1 . 584 , x 3 = 1 . 854 ′ f ( x 3 ) = 0 . 927 > f ( x 3 ) = 0 . 792 , 故原区间缩短为 [1 . 584 , 2 . 292 ]
三、牛顿法（Newton）（切线法）
对f 在x k 点展开： f(x )= f(xk )+ f '(xk )(x- xk ) +f″ (xk )(x- xk )2 /2 + o (x- xk )2 取二次式（略去高阶项）： qk(x) = f(xk) + f '(xk)(x-xk) + (f ″(xk)(x-xk)2)/2 用qk(x)作为f(x)的近似。 首先求qk(x)的导数，并令其等于零。 q′k(x)= f′(xk) +f″(xk)(x- xk )=0 得 xk +1=xk –f′(xk) / f″(xk) 取xk +1为新的迭代点。 以上过程即Newton法。 特点：二阶、局部收敛。
一、分数法（斐波那契法）
因此，现在我们关心的是：进行n次搜索后，能把区间 [a,b]缩小到什么程度？或者说，计算n次函数值以后能把多 长的区间缩小成长度为1的区间？ 用Fn表示计算n个函数值能缩短为单位区间的最大原 区间长度，显然有
F0 = F1 = 1
这是因为至少要计算两次函数值才能缩短区间，只 计算零次或一次函数值是不能缩短区间长度的，故只有 区间长度本身等于1时才行。 现考虑计算函数值两次的情形。 我们把计算函数值的点称为试算点或试点。
Fibonacci_eg2.m
一、分数法（斐波那契法）
/ / f ( x2 ) = 1.0499, f ( x2 ) = 0.7504, f ( x2 ) > f ( x2 )
取a2 = −1.0476, b2 = b1 = 0.4762 这样一直进行下去，最后可得。
/ 由于x6 = −0.4762 = x6，因此取
以不变的区间缩短率0.618代替分数法每次不同的缩短率，就 得到黄金分割法（0.618法）。它可以看成是分数法的近似， 实现起来比较容易，效果也好。
二、0.618法（黄金分割法）
例：用黄金分割法求函数 ⎧ x / 2, f ( x) = ⎨ ⎩− x + 3,
长度的15％。 x≤2 x>2
在区间[0,3]上极大点，要求缩短后 的长度不大于原区间
a
X* a1
b1 b
a a1 X*
b1
b
一、分数法（斐波那契法）
a
a1 a2
a3
a4 a5 a6
b6 b5
b1 b b2 b3 b4
一、分数法（斐波那契法）
通过上面的讨论，我们知道，只要在区间[a,b]内取两个 不同的点，并算出这两点的函数值，加以比较，就能把搜索 区间[a,b]缩小成[a,b1]或[a1,b]。 如果继续缩小区间[a,b1](或[a1,b])，就需要在区间[a,b1](或 [a1,b])内取一点b2，并计算出f(b2)的值，并与f(a1)比较。 若 f(a1)< f(b2)， 则x*∈ [a,b2] f(a1)> f(b2)，则x*∈ [a1,b1]
/ / f ( xn −1 )的值以确定最后的区间[an −1 , bn −1 ]，在xn −1与xn −1
中其函数值较小者为近似极小点，相应的函数值为 近似的极小值。
一、分数法（斐波那契法）
例：试用分数法，求函 数 f ( x ) = x 2 + x + 1在区间 [ − 2, 2 ]上的 近似极小点和近似极小 值，并要求误差不超过 0 .2。 解：不难验证， f ( x ) = x 2 + x + 1在区间 [ − 2, 2 ]上是仅有唯一 的极小点的单峰函数， 极小点为 x* = − 0 .5, 极小值 f ( x*) = 0 .75。 下面利用分数法求解。 已知 δ＝0 .2， Fn ≥ 4 / 0 .2 = 20 , 故 n = 7 , 又已知 a = − 2, b = 2 ⎧ x1 = a + (b − a ) F5 / F7 = − 2 + 4 × 8 / 21 = − 0 .4762 ∴⎨ / ⎩ x1 = a + (b − a ) F6 / F7 = − 2 + 4 × 13 / 21 = 0 .4762 f ( x1 ) = 0 .7506 , f ( x1/ ) = 1 .7030 Q f ( x1 ) < f ( x1/ ),∴ 取 a1 = − 2, b1 = 0 .4762 ⎧ x 2 = a1 + (b1 − a1 ) F4 / F6 = − 1 .0476 ⎨ / x 2 = x1 = − 0 .4762 ⎩
极大值
三、牛顿法（Newton）（切线法）
上面我们所讨论的方法，只是对一些点的函数值的大小进 行比较，而函数本身并没有得到充分利用，至于函数的一些 解析性质，更是毫无利用，下面介绍的牛顿法当函数性质具 有较好的解析性质时，计算效果要比分数法、0.618法更好。 现在仍设f(x)在[a,b]上仅有一个极小点的单峰函数，且具 有二阶导数。 我们知道，如果函数f(x)在x*处取极小值，则必有 f′(x)=0，因此求此函数极小点，只需求出f′(x)在(a,b)内的 零点即可。
ÓÉ Foxit Reader ±à¼°æȨËùÓÐ (C) Foxit Software Company,2005-2006 ½öÓÃÓÚÆÀ¹À¡£
一、分数法（斐波那契法）
/ 这时无法比较函数值f ( xn −1 )与f ( xn −1 )来确定最后的区
间[an −1 , bn −1 ], 为此取 xn −1 = (an − 2 + bn − 2 ) / 2 ⎧ ⎨ / ⎩ xn −1 = an − 2 + (bn − 2 − an − 2 ) /(1 / 2 + ε ) 其中ε是一个很小的正数，这样就可以比较f ( xn −1 )与
ta tb
一、分数法ห้องสมุดไป่ตู้斐波那契法）
（1）给出精度Δ，求出使Fn=(b-a)/Δ的最小整数n，由 Fn=Fn-1+Fn-2,定出两个试点 x1=a+(b-a) Fn-2 / Fn-1，x1’=a+ (b-a) Fn-1 / Fn。 （2）计算f(x1)与f(x1’) 若f(x1)<f(x1’)，取a=a1, x1’=b1 并令x2=a1+ (b1-a1) Fn-3 / Fn-2 , x2’= x1 若f(x1)>f(x1’)，取x1 =a1, b=b1并令x2= x1’ 并令x2= x1’ , x2’=a1+ (b1-a1) Fn-2 / Fn-1 （3）计算f(x2)与f(x2’)，比较它们的大小,方法同（2）。 （4）当迭代到k=n-1时， xn-1= xn-1’=(an-2+bn-2)/2 这时无法比较函数值f(xn-1)与f( xn-1’)来确定最后的区 间[an-1 , an-1]
由上节讨论知，用分数法以n个试点来缩短某一区间时，区 间长度的第一次缩短率为Fn-1 / Fn，其后各次分别为：Fn-2 / Fn-1 ，Fn-3 / Fn-2 ，…，F1 / F2，现将以上数列分为奇数项和偶数 项，可以证明，这两个数量收敛于同一个极限
−1 + 5 = 0.6180339887418948 2
一、分数法（斐波那契法）
由此得： F2=2 根据同样的方法，可得 F3=3,F4=5,F5=8,F6=13…..
序列
{F n } 的递推公式为：
F n = F n −1 + F n − 2 (n ≥ 2)
一、分数法（斐波那契法）
利用公式可计算出Fn的值如下：
n Fn 0 1 1 1 2 2 3 3 4 5 5 6 8 13 7 21 8 34 9 55 10 89 11 144
这里的Fn就是通常所说的裴波那契数。 由以上讨论知，计算n次函数值所能获得的最大缩短率（缩 短后的长度与原区间长度的比）为1/Fn。 如F20＝10946
即计算20个函数值可以把原区间长度为L的区间缩短为 L = 0.00009 L的区间长度。 10946
一、分数法（斐波那契法）
现在对于寻找近似极小点来说，如果希望误差不超过 Δ，只需将原区间[a,b]缩短为包含极小点而区间长度不超 过Δ的区间就可以了。这时计算函数值的次数n只要满足： 1 Fn ≥ (b − a) 即可
迭代次数
0 1 2 3 4 5 6
an -2 -2 -1.0476 -1.0476 -0.6666 -0.6666 -0.6666
bn 2 0.4762 0.4762 -0.0952 -0.0952 -0.2857 -0.4723
= x = a5 + 0.5＋0.01 (b5 − a5） −0.4723 （ ）
/ 6
f ( x ) = 0.7508 > f ( x6 ) = 0.7506
/ 6
因此取a6 = −0.666, b6 = −0.4762 取x6＝ − 0.4723为近似极小点， 近似极小值f ( x6 ) = 0.7506 易看出 b6－a6 = 0.1943 < 0.2
二、0.618法（黄金分割法）
令 a 3 = 1 . 584 , b3 = 2 . 292 ′ x 4 = 1 . 854 , x 4 = 1 . 584 + 0 . 618 ( 2 . 292 − 1 . 584 ) = 2 . 022 ′ f ( x 4 ) = 0 . 978 > f ( x 4 ) = 0 . 927 , 故原区间缩短为 [1 . 854 , 2 . 292 ] 由于 2 . 292 －1 . 854 ＝14 . 6％ < 15 % 3 已达到精度要求，停止 迭代，得近似极大点和 x = ( 2 . 292 + 1 . 854 ) / 2 = 2 . 073 , f ( x ) = 0 . 927 此题的精确最优解为 x * = 2 , f ( x *) = 1。