2015/5/8 西电数学与统计学院 穆学文 1 2015/5/8 西电数学与统计学院 穆学文 2
对问题
a x b
min
f ( x)
我们主要介绍如下一些搜索方法：

令：
f ( x), a x b F ( x) , others
则：
a x b
min f ( x) min F ( x)
Y
xk +1= xk - f′ (xk ) ／ f″(xk )
西电数学与统计学院
穆学文
22
例1： 求 min f (x)=
arctan t d t
0
x
解： f ′ (x) =arctan x , f ″(x)=1／(1+ x2) 迭代公式： xk +1= xk - (1+ xk 2) arctan xk 取 x1= 1，计算结果： k 1 2 3 4 x4≈ x* =0
2015/5/8
西电数学与统计学院
穆学文
17
2015/5/8
西电数学与统计学院
穆学文
18
3
§4 牛顿法（Newton）和插值法
§4 .1、Newton法： 对 f (x) 在 x k 点展开： f (x )= f (xk )+ f ′(xk )( x-x x xk ) +(1/2) f ″(xk )(x-x x x k )2 2 + o( ||(x- xk) ||) 取二次式（略去高阶项） g(x) = f (xk) +f ′(xk)(x-xk) + (1/2)f ″(xk)(x-xk)2
tgபைடு நூலகம்α>0 α
2015/5/8 西电数学与统计学院 穆学文 15 2015/5/8
tg α<0 α
f′ ( x )
α x
f′ ( x )
b
α
x
穆学文
b
16
西电数学与统计学院
* * 我们知道，在极小点 x 处，f ' x 0，且 x x 时， * * f x 递减，即 f ' x 0 ，而当 x x ，函数递增，即 f ' x 0 。若找到一个区间[a, b], 满足性质 f ' a 0, f ' b 0 * 则[a,b]内必有 f x 的极小点 x * ，且 f ' x 0 ，为找此 x* ab 取 x0 ，若 f ' x0 0 则在 x0 , b 中有极小点，这时 2 用 x0 , b 作新的区间 作 的 间[a,b]，继续这个过程，逐步将区间 续 个过 步将 间 [a,b]缩小，当区间[a,b]的长度充分小时，或者当 f ' x0 充分小时，即可将[a,b]的中点取做极小点的近似点，这 时有估计： ab ba x* 2 2
2015/5/8
x2
b
西电数学与统计学院
t
x2 x1 (2) b x2
12
2015/5/8
西电数学与统计学院
穆学文
11
穆学文
2
黄金分割法（0.618 法）（算法） 整理② ： x 2 = a + t ( b -α ) x1 = a + t ( x2 -α)
2015/5/8 西电数学与统计学院 穆学文 9
定理1：设 f：R→R 在[a, b ]上是单峰函数， a≤ x1 < x2 ≤b 。那么 1°若 f (x1)≥ f (x2)，则 x* ∈[x1 , b] ,如左下图 2°若 f (x1)< f (x2) ，则 x* ∈[a, x2 ], 如右下图
α
x1
x2
b
α
x1
x2
b
2015/5/8
西电数学与统计学院
穆学文
10
Proof. 1°反证法：设 x* ∈[a, b]为最小点， 若x* ∈[a, x1]，由定义 知 f (x1)< f (x2 )，矛盾 （假设）； 2 °若 若x* ∈[x2 , b ]，由定义知 f (x1 ) > f (x2 ), 矛盾（条件）； 结论成立。 注：上述定理为缩短区间的算法提供了理论根据。
*
至于区间[a, b]的确定,一般可采用下述方法： 首先取初始点 x0 ，若 f ' x0 0 ，则在 x0 右方取点 x1 x0 x, ( x 也是事先给定的步长）；若 f ' x1 0 , 则 令 a x0, b x1 ；若仍然有 f ' x1 0 ，则取 x2 x1 x （或将 x 放大一倍，再取 x2 x1 x）,若 f ' x2 0 , 则以 x 1 , x 2 作区间[ [a,b] , ]；否则继续下去 ；否则继续下去。 对于 f ' x0 0的情况，可类似于上面在 x0 左侧取点，此 时 x 0 . 优点：计算量较少，而且总能收敛到一个局部极小点。 缺点：收敛速度较慢。
通过上述定理，选二点 x1 < x2 , 比较 f (x1 ) 与 f (x2 ) ,可去掉 [a , x1 ] 或者[x2 , b]. 考虑条件： 1°对称： x1 – a = b- x2 ……① （使“坏”的情况去掉，区间长度不小于“好”的情况） 2°保持缩减比 t =(保留的区间长度／原区间长度) 不变。 （使每次保留下来的节点， 使每次保留 来的节点 x1或 x2 ，在下一次的比较中成 在 次的比较中成 为一个相应比例位置的节点 ）。 推导缩减比 t : 如图设第一次保留[a, x2 ] (去掉[x2 , b]), 那么第 二次保留的长度为[α, x1 ], 则 α x1
5 2015/5/8 西电数学与统计学院 穆学文 6
2015/5/8
西电数学与统计学院
穆学文
1
例1：设给定初始点为 a 及初始步长为 h, 求搜索区 间[c, d] 1. 前进运算 (1) 首先计算 f (a), f (a+h), ) (2) 如果 f (a)> f (a+h), 则步长加倍, 计算f (a+3h). (3) 若 f (a+h)<= f (a+3h), 则c=a, d=a+3h; (4) 否则将步长再加倍，并重复上面运算.
“成功—失败”法（进退法）： 步骤1：选取初始点 x∈R , 初始步长 h > 0 及精度ε> 0， 1 f ( x). 步骤2：计算 2 f ( x h). 步骤3：若 2 1 , 搜索成功, 转步骤4；否则，搜索失败， 转步骤5. 5 步骤4：令 x:= x + h, 1 : 2 , h : 2h (点更新)，转步骤 2. 步骤5：判断 h ? 若 h , 停止迭代， x* x ； 否则令 h h , （点没更新）， 转步骤 2。 4 缺点：效率低。优点：可以求搜索区间 注意：初始步长不能选得太小
yes
α
b= x2 , x2 = x1 x1 = α + （1-t）( b -α )
x1 x2 x2
b b
No
f（ x1 ）-f（ x2 ）>0?
STOP; x* =(α+b)/2
No
yes
（算法框图见下页）
2015/5/8 西电数学与统计学院 穆学文 13 2015/5/8
α= x1 , x1 = x2 x2 =α +t ( b –α)
2015/5/8
西电数学与统计学院
穆学文
19
2015/5/8
西电数学与统计学院
穆学文
20
x 定理：设函数 f ( x) 存在连续的三阶导数，
满足 于 x
f '( x* ) 0, f ''( x* ) 0
*
Newton法算法框图：
初始 x1 ,ε1, ε2 >0 k=1
x* ，则牛顿法产生的序列 xk 2阶收敛
西电数学与统计学院 穆学文
α
x1
x2 x1
b
14
α
§3
黄金分割法（0.618 法）的优缺点 优点：不要求函数可微，且每次迭代只需计算一 个函数值，计算量小，程序简单 缺点：收敛速度慢。
二分法
设 f (x)在 [a ,b]上可微，且当导数为零时是解。 取 x=(a+b) / 2, 那么 f ′(x) = 0 时, x 为最小点, x= x* ; f ′(x) > 0 时, x 在上升段, x* < x，去掉[x ,b] ; f′ (x) < 0 时, x 在下降段, x* > x，去掉 去掉[a, x] .
2. 后退运算 (1)首先计算 f (a), f (a+h), (2)如果 f (a)< f (a+h), 则将步长缩为原来的1/4并改 变符号，即将步长改为-h/4, (3)如果 f (a)< f (a-h/4),则c=a-h /4,d=a+h; (4)否则将步长加倍，并继续后退。 否则将步长加倍 并继续后退
2015/5/8 西电数学与统计学院 穆学文 23
取 x1=2，计算结果如下： k 1 2 3 xk 2 -3.5357 13.95 f′ (xk) 1.1071 1 1071 -1.2952 不收敛。 1／f″( xk ) 5 13.50
xk 1 -0.5708 0.1169 -0.001095
f′ ( (xk) 0.7854 -0.5187 -0.1164 -0.001095
用 g(x)作为f (x)的近似，当 f ″(xk) > 0时，其驻点为极 小点： g′ (x)= f ′(xk) +f ″(xk)(x - xk )=0 得到极小点 x = xk –f ′(xk) /f ″(xk) 令下一个迭代点 xk +1=x= xk –f ′(xk) /f ″(xk). 取 xk +1为新的迭代点。以上过程即Newton法。