第三章 一维搜索方法
概述
– 搜索区间的确定
一维搜索的试探方法
– 黄金分割法
一维搜索的插值方法
– 牛顿法 (切线法 )
– 二次插值法
2
概述
直接搜索法更适合于工程实践
对于单个变量（一维问题）的直接搜索，
通常称为 一维搜索 或线性搜索
多维问题转化为一维问题求解
3
多维和一维间的转换
多维目标函数的极值问题，通常采用数值迭代的方法求解
每一步的格式都是从某一定点 xk出发沿着某一使函数值下降的规定方向 dk，找出在此方向的极值点 xk+1。
在任何一次迭代计算过程中，当起步点和方向确定之后，就把求多维问题的目标函数的极小值这个多维问题，转变成求一个变量即步长 ak的最优值的一维问题
沿着规定方向求 ak的最优值以使 f(xk+akdk)得到极小值的过程，就是 一维搜索或一维最优化问题,而 ak则称为一维搜索的最优化步长
多维问题就转换为 一系列 的一维搜索问题
( )1 0,1,2,k k kkx x a d k+ = + = L
( ) ( ) ( )1 m i n m i nk k kkkf x f x a d f a+ = + =
5
一维搜索方法
采用数值解法代替解析解法
– 第一步是确定搜索区间，即最优步长 ak所在的区间 [a,b]，搜索区间应为单峰区间，区间内目标函数应只有一个极小值
– 第二步是在此区间内求最优步长 ak，使目标函数 f(xk+ak)达到极小，即通过某种原理不断缩小搜索区间,从而获得最优步长 a*的数值近似解。
6
确定初始搜索区间的进退算法
3x
f
2x1x x
1x 2x 3x
1x2x3x
f
x1x 2x
3x
前进计算 后退计算
— 试探后作前进或后退计算 。
一）基本思路
1x2x
7
h=h0
y1=f(x1),x2=x1+h,y2=f(x2)
给定 x1,h0
y1≥y 2
y2≥ y3
是
h=2h
x3=x2+h,y3=f(x3)
结束否
h= -h
x3=x1
y3=y1
a=x1,b=x3
是
x1=x2
y1=y2
x2=x3
y2=y3
是
a=x3,b=x1 否 h>0
否二 ) 迭代步骤 初始进退距
3x
f
2x1x x
1x 2x 3x
前进计算
1x2x3x
f
x1x 2x
3x
后退计算
1x2x
1y
2y
3y
8
.1.0,0
,983)(.13
01
3
hx
xxxf
初始进退距初始点给定的一维优化初始区间用进退法确定函数
：解
k h x1 y1 x2 y2 x3 y3
1 0.10.2 0 9 0.1 8.203 0.3 6.681
2 0.4 0.1 8.203 0.3 6.681 0.7 4.429
3 0.8 0.3 6.681 0.7 4.429 1.5 7.125
.5.1,3.0,?ba可得初始搜索区间
9
.1.0,8.1
,983)(.23
01
3
hx
xxxf
初始进退距初始点给定的一维优化初始区间用进退法确定函数
：解 k h x
1 y1 x2 y2 x3 y3
1 0.1-0.2 1.8 12.096 1.9 14.377 1.9 14.3771.8 12.096 1.6 8.488
2 -0.4 1.8 12.096 1.6 8.488 1.2 4.584
3 -0.8 1.6 8.488 1.2 4.584 0.4 5.992
.6.1,4.0,?ba可得初始搜索区间
10
进退法的计算机程序框图
t0,h
t1=t0; t2=t0+h
f1=f(t1); f2=f(t2)
f2<f1
h=2h
t2=t2+h
f1=f2; f2=f(t2)
h=-h/4
是否
f2<f1t1=t2-h
t1=t1+h
f2=f1
f1=f(t1)
f2<f1
t2=t1-h
h=2h
否
a=t1
b=t2
是是否结束
11
一维搜索方法的分类
为了每次缩短区间，只需要在区间内再插入一点并计算其函数值。然而，对于插入点的位置，是可以用不同的方法来确定的。
一类称作 试探法,区间内插入点位置的确定仅仅按照区间缩短如何加快，而不顾及函数值的分布关系
– 黄金分割法等
一类称作 插值法或函数逼近法,构造一个插值函数来逼近原来函数，用插值函数的极小点作为区间的插入点
– 牛顿法、二次插值法等
12
一维搜索的试探方法黄金分割法
是最常用的一维搜索试探方法，又称作 0.618法
适用于区间上的任何单谷函数求极小值问题
– 对函数除要求“单谷”外不作其他要求，甚至可以不连续
基本思路：在搜索区间内适当插入两点，并计算其函数值。将区间分成三段。应用函数的单谷性质，通过函数值大小的比较，删去其中一段，使搜索区间得以缩短。然后再在保留下来的区间上作同样的处置，如此迭代下去，使搜索区间无限缩小，从而得到极小点的数值近似解。
13
黄金分割法
黄金分割法要求插入点?1,?2的位置相对于原区间 [a,b]
的两端点具有对称性，即
黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布
1 －?
(1 －? )
2
1
a a
1
a
2
b
a a
2
a
1
a
3
图 黄金分割法
( )
( )
1
2
b b a
a b a
al l
al
= - -ì
í? = + -?
其 中 为 待 定 系 数
2 511 0,6 1 82l l l -- = =
14
黄金分割法的搜索过程
⑴ 给出初始搜索区间 [a,b]及收敛精度?，将?赋以 0.618
⑵ 按前页中坐标点比例公式计算?1和?2,并计算其对应的函数值 f(?1)和 f(?2)。
⑶比较函数值，利用进退法缩短搜索区间
⑷检查区间是否缩短到足够小和函数值是否收敛到足够近，如果条件不满足则返回到步骤⑵
⑸如果条件满足则取最后两试验点的平均值作为极小点的数值近似值
15
黄金分割法程序框图给定 a,b,?
＝ 0.618
a1=b-?(b-a); y1=f(a1);
a2=a+?(b-a); y2=f(a2);
y1≥y2
a=a1; a1=a2;
y1=y2;
a2=a+?(b-a);
y2=f(a2)
b=a2; a2=a1;
y2=y1;
a1=b-?(b-a);
y1=f(a1)
b - a y 2 - y 1<<b y 2ee和a*=(a+b)/2
结束是 否是 否
16
一维搜索的插值方法
假定我们的问题是在某一确定区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干试验点处的函数值。我们可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的近似值。
这种方法称作插值法，又称作函数逼近法 。
17
插值方法与试探方法的对比
相同之处 在于都是利用区间消去法原理将初始搜索区间不断缩短，从而求得极小点的数值近似解。
不同之处 在于试验点位置的确定方法不同。
– 在试探法中试验点位置是由某种给定的规律确定。
– 在插值法中试验点位置是按函数值近似分布的极小点确定。
– 试探法仅仅利用了试验点函数值的大小的比较，
– 而插值法还要利用函数值的本身或者其导数信息。
– 由于试探法仅对试验点数值的大小进行比较，而函数值本身的特性没有得到充分利用
– 插值法则是利用函数在已知试验点的值（或导数值）来确定新试验点的位置。当函数具有比较好的性质时 (例如连续可微性 )，插值方法比试探法效果更好。
18
一维搜索的插值方法
多项式是函数逼近的一种常用工具。在搜索区间内我们可以利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，
并用这个多项式的极小点作为原函数极小点的近似。
常用的插值多项式为二次多项式。
– 牛顿法（切线法）：利用一点的函数值、一阶导数值和二阶导数值来构造此二次函数
– 抛物线法（二次插值法）：它利用三个点的函数值形成一个抛物线来构造此二次函数
19
牛顿法
对于一维搜索函数，假定已给出极小点的一个较好的近似点 a0，
因为一个连续可微的函数在极小点附近与一个二次函数很接近，
所以可以在 a0点附近用一个二次函数来逼近函数，即在点 a0将 f(a)
进行泰勒展开，并保留到二次项，有
然后以二次函数的极小点作为极小点的一个新近似点，根据极值必要条件
( ) ( ) ( ) ( ) ( ) 20 0 0 0 01( ) ( ) 2f x a f a f a a a f a a af ⅱ? + - + -
1( ) 0af ￠ = ( ) ( ) ( )0 0 1 0 0f a f a a aⅱ + - =对 a求偏导
( )
( )
010
0
faaa
fa
￠=-
ⅱ
( )
( )1 0,1,2,
kkk
k
faa a k
fa+
￠= - =
ⅱ L
依此继续可得牛顿法迭代公式
20
牛顿法的计算步骤
⑴ 给定初始点 a0，控制误差?，令 k=0
⑵ 计算 f(x)在 ak点的一阶和二阶导数
⑶利用牛顿法迭代公式求 ak+1
⑷ 若 |ak+1-ak|≤?，则求得近似解 a*=ak+1，
停止计算，否则作第⑸步
⑸令 k=k+1，然后转第 ⑵步
21
牛顿法
最大优点是收敛速度快
缺点
– 每一点处都要计算函数的导数和二阶导数，因而增加了每次迭代的工作量
– 用数值微分代替二阶导数时，舍入误差会影响牛顿法的收敛速度，当二阶导数很小时问题更严重
– 牛顿法要求初始点选得比较好，即不能离极小点太远，否则在可能使极小化序列发散或收敛到非极小点
22
上机实验
进退法确定搜索区间上机编程
黄金分割法上机编程
二次插值法上机编程
汽车转向梯形优化设计
23
二次插值法（一）
又称抛物线法。利用 y=f(x)在单谷区间中的三点
x1<x2<x3的相应函数值,f(x1)>f(x2)<f(x3)，作出如下的二次插值多项式
多项式的极值点可以从极值的必要条件求得
( ) 20 1 2P a a a x a x= + +
( ) ( )21 0 1 1 2 1 1 1P x a a x a x y f x= + + = =
( ) ( )22 0 1 2 2 2 2 2P x a a x a x y f x= + + = =
( ) ( )23 0 1 3 2 3 3 3P x a a x a x y f x= + + = =
( ) 1220P x a a x**￠ = + = 1
22
ax a* =-
24
二次插值法（二）
P(x)的系数确定与极小点的计算
( ) ( )
( ) ( )
221 1 2 2 1 2 1 2
221 2 3 2 2 3 2 3
a x x a x x y y
a x x a x x y y
- + - = -
- + - = -
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
2 2 2 2 2 2
2 3 1 3 1 2 1 2 3
1
1 2 2 3 3 1
2 3 1 3 1 2 1 2 3
2
1 2 2 3 3 1
x x y x x y x x y
a
x x x x x x
x x y x x y x x y
a
x x x x x x
- + - + -
=
- - -
- + - + -
=-
- - -
( ) ( ) ( )
( ) ( ) ( )
2 2 2 2 2 22 3 1 3 1 2 1 2 31
2 2 3 1 3 1 2 1 2 3
1
22
x x y x x y x x yax
a x x y x x y x x y*
- + - + -= - =
- + - + -
令
21 1
31 2112
3 1 2 3
,
yy c
yy xxcc
x x x x
- -
- -==
--
112
2
1
2
cx x x
c*
骣 ÷?= + - ÷?桫
25
二次插值法（三）
缩短搜索区间
(1)如果搜索区间足够小，则可用 P(x)的极小点 x4作为 f(x)的极小值
x*的近似解
(2)否则，必须缩短搜索区间（利用单谷函数的性质）重复进行二次插值法
– (1)当 x2<x4时，
如果 f(x2)<f(x4)，则取 [x1,x2,x4]为新的搜索区间；
如果 f(x2)>f(x4)则取 [x2,x4,x3]。
– (2)当 x2>x4时，
如果 f(x2)<f(x4)，则取 [x4,x2,x3]为新的搜索区间；
如果 f(x2)>f(x4)则取 [x1,x4,x2]。
x1 x2 x3x4 x1 x2 x3x4 x1 x2 x3x4x1 x2 x3x4
26
二次插值法（四）
计算步骤
(1)确定搜索区间 [x1,x2,x3]，给定计算精度?>0
(2)计算 f(xk)，置 fk=f(xk),k=1,2,3
(3)按公式计算 x4，并计算 f4=f(x4)
(4)检验 |x4-x2|<?否。如果满足，则停止计算，取 x*=x4，
否则转 (5)
(5)如果 x2<x4，转 (6)，否则当 f2<f4时,x1=x4,f1=f4，
转 (3)；当 f2≥f4时,x3=x2,f3=f2,x2=x4,f2=f4，转
(3)
(6)当 x2<x4，当 f2<f4时,x3=x4,f3=f4，转 (3)；当
f2≥f4时,x1=x2,f1=f2,x2=x4,f2=f4，转 (3)
27
二次插值法（四）
计算机流程图给定 x1,x2,x3,?
计算 f1,f2,f3
c1=(y2-y1)/(x3-x1);
C2=((y2-y1)/x2-x1)-c1)/(x2-x3)
x4=0.5*(x1+x3-c1/c2);
f4=f(x4)
|(f4-f2)/f2|<?
x*=x4 x2<x4
f2<f4
x3=x4;
f3=f4
x1=x2;
f1=f2;
x2=x4
f2=f4
f2<f4
x1=x4;
f1=f4
x3=x2;
f3=f2;
x2=x4
f2=f4
结束是 否是是是否否否
28
例题：黄金分割法（一）
对函数 f(x)＝ x2+2x，给定搜索区间 -3≤x≤5时，用黄金分割法求极小点 x*
此时 a=-3,b=5，按公式计算两插入点
( ) ( )1 5 0,6 1 8 5 3 0,0 5 6a b b al= - - = -? =
( ) ( )2 3 0,6 1 8 5 3 1,9 4 4a a b al= + - = - +? =
计算两插入点的函数值
( )11 0,1 5 5y f a==
( )22 7,6 7 7y f a==
21yy>
消去区间 [a2,b]，新的搜索区间 [a,b]的端点
a=-3不变，而 b=a2=1.944
29
例题：黄金分割法（二）
依次重复黄金分割法的迭代过程，前五次迭代的结果
假定，经过 5次迭代后已满足收敛精度要求，则得
该问题的精确解为迭代序号 a a1 a2 b y1 比较 y2
0 -3 0.056 1.944 5 0.115 ＜ 7.667
1 -3 -1.111 0.056 1.944 -0.987 ＜ 0.115
2 -3 -1.832 -1.111 0.056 -0.306 ＞ -0.987
3 -1.832 -1.111 -0.665 0.056 -0.987 ＜ -0.888
4 -1.832 -1.386 -1.111 -0.665 -0.851 ＞ -0.987
5 -1.386 -1.111 -0.940 -0.665
( ) ( )11 1,3 8 6 0,6 6 5 1,0 2 5 522x a b* = + = - - = -
( ) 1,0 0 0 7fx * =-
( )11x f x**= - = -
30
例题：牛顿法
给定 f(x)=x4-4x3-6x2-16x+4，用牛顿法求其最小点首先求出函数的一阶、二阶导函数
( ) ( )
( ) ( )
32
2
4 3 3 4
1 2 2 1
f x x x x
f x x x
￠ = - - -
ⅱ = - -
给定起始点 a0=3，控制误差?＝ 0.001
k 0 1 2 3 4
ak 3 5.16667 4.33474 4.03960 4.00066
f`(ak) -52 153.35183 32.30199 3.38299 0.00551
f``(ak) 24 184.33332 109.44586 86.86992 84.04720
ak+1 5.16667 4.33474 4.03960 4.00066 4.00059
( )
( )1 0,1,2,kkk k
faa a kfa+ ￠= - =ⅱ L
31
例题：二次插值法
用二次插值法示 f(x)=sin(x)在 4≤x≤5上的最小值此时的搜索区间为 [4,5]
121 3 24,5,4,52aaa a a += = = =
迭代两次的计算过程及结果见下表
1 2
a1 4 4.5
a2 4.5 4.705120
a3 5 5
f1 -0.756802 -0.977590
f2 -0.977590 -0.999974
f3 -0.968924 -0.958924
a4 4.705120 4.710594
f4 -0.999974 -0.999998
概述
– 搜索区间的确定
一维搜索的试探方法
– 黄金分割法
一维搜索的插值方法
– 牛顿法 (切线法 )
– 二次插值法
2
概述
直接搜索法更适合于工程实践
对于单个变量（一维问题）的直接搜索，
通常称为 一维搜索 或线性搜索
多维问题转化为一维问题求解
3
多维和一维间的转换
多维目标函数的极值问题，通常采用数值迭代的方法求解
每一步的格式都是从某一定点 xk出发沿着某一使函数值下降的规定方向 dk，找出在此方向的极值点 xk+1。
在任何一次迭代计算过程中，当起步点和方向确定之后，就把求多维问题的目标函数的极小值这个多维问题，转变成求一个变量即步长 ak的最优值的一维问题
沿着规定方向求 ak的最优值以使 f(xk+akdk)得到极小值的过程，就是 一维搜索或一维最优化问题,而 ak则称为一维搜索的最优化步长
多维问题就转换为 一系列 的一维搜索问题
( )1 0,1,2,k k kkx x a d k+ = + = L
( ) ( ) ( )1 m i n m i nk k kkkf x f x a d f a+ = + =
5
一维搜索方法
采用数值解法代替解析解法
– 第一步是确定搜索区间，即最优步长 ak所在的区间 [a,b]，搜索区间应为单峰区间，区间内目标函数应只有一个极小值
– 第二步是在此区间内求最优步长 ak，使目标函数 f(xk+ak)达到极小，即通过某种原理不断缩小搜索区间,从而获得最优步长 a*的数值近似解。
6
确定初始搜索区间的进退算法
3x
f
2x1x x
1x 2x 3x
1x2x3x
f
x1x 2x
3x
前进计算 后退计算
— 试探后作前进或后退计算 。
一）基本思路
1x2x
7
h=h0
y1=f(x1),x2=x1+h,y2=f(x2)
给定 x1,h0
y1≥y 2
y2≥ y3
是
h=2h
x3=x2+h,y3=f(x3)
结束否
h= -h
x3=x1
y3=y1
a=x1,b=x3
是
x1=x2
y1=y2
x2=x3
y2=y3
是
a=x3,b=x1 否 h>0
否二 ) 迭代步骤 初始进退距
3x
f
2x1x x
1x 2x 3x
前进计算
1x2x3x
f
x1x 2x
3x
后退计算
1x2x
1y
2y
3y
8
.1.0,0
,983)(.13
01
3
hx
xxxf
初始进退距初始点给定的一维优化初始区间用进退法确定函数
：解
k h x1 y1 x2 y2 x3 y3
1 0.10.2 0 9 0.1 8.203 0.3 6.681
2 0.4 0.1 8.203 0.3 6.681 0.7 4.429
3 0.8 0.3 6.681 0.7 4.429 1.5 7.125
.5.1,3.0,?ba可得初始搜索区间
9
.1.0,8.1
,983)(.23
01
3
hx
xxxf
初始进退距初始点给定的一维优化初始区间用进退法确定函数
：解 k h x
1 y1 x2 y2 x3 y3
1 0.1-0.2 1.8 12.096 1.9 14.377 1.9 14.3771.8 12.096 1.6 8.488
2 -0.4 1.8 12.096 1.6 8.488 1.2 4.584
3 -0.8 1.6 8.488 1.2 4.584 0.4 5.992
.6.1,4.0,?ba可得初始搜索区间
10
进退法的计算机程序框图
t0,h
t1=t0; t2=t0+h
f1=f(t1); f2=f(t2)
f2<f1
h=2h
t2=t2+h
f1=f2; f2=f(t2)
h=-h/4
是否
f2<f1t1=t2-h
t1=t1+h
f2=f1
f1=f(t1)
f2<f1
t2=t1-h
h=2h
否
a=t1
b=t2
是是否结束
11
一维搜索方法的分类
为了每次缩短区间，只需要在区间内再插入一点并计算其函数值。然而，对于插入点的位置，是可以用不同的方法来确定的。
一类称作 试探法,区间内插入点位置的确定仅仅按照区间缩短如何加快，而不顾及函数值的分布关系
– 黄金分割法等
一类称作 插值法或函数逼近法,构造一个插值函数来逼近原来函数，用插值函数的极小点作为区间的插入点
– 牛顿法、二次插值法等
12
一维搜索的试探方法黄金分割法
是最常用的一维搜索试探方法，又称作 0.618法
适用于区间上的任何单谷函数求极小值问题
– 对函数除要求“单谷”外不作其他要求，甚至可以不连续
基本思路：在搜索区间内适当插入两点，并计算其函数值。将区间分成三段。应用函数的单谷性质，通过函数值大小的比较，删去其中一段，使搜索区间得以缩短。然后再在保留下来的区间上作同样的处置，如此迭代下去，使搜索区间无限缩小，从而得到极小点的数值近似解。
13
黄金分割法
黄金分割法要求插入点?1,?2的位置相对于原区间 [a,b]
的两端点具有对称性，即
黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布
1 －?
(1 －? )
2
1
a a
1
a
2
b
a a
2
a
1
a
3
图 黄金分割法
( )
( )
1
2
b b a
a b a
al l
al
= - -ì
í? = + -?
其 中 为 待 定 系 数
2 511 0,6 1 82l l l -- = =
14
黄金分割法的搜索过程
⑴ 给出初始搜索区间 [a,b]及收敛精度?，将?赋以 0.618
⑵ 按前页中坐标点比例公式计算?1和?2,并计算其对应的函数值 f(?1)和 f(?2)。
⑶比较函数值，利用进退法缩短搜索区间
⑷检查区间是否缩短到足够小和函数值是否收敛到足够近，如果条件不满足则返回到步骤⑵
⑸如果条件满足则取最后两试验点的平均值作为极小点的数值近似值
15
黄金分割法程序框图给定 a,b,?
＝ 0.618
a1=b-?(b-a); y1=f(a1);
a2=a+?(b-a); y2=f(a2);
y1≥y2
a=a1; a1=a2;
y1=y2;
a2=a+?(b-a);
y2=f(a2)
b=a2; a2=a1;
y2=y1;
a1=b-?(b-a);
y1=f(a1)
b - a y 2 - y 1<<b y 2ee和a*=(a+b)/2
结束是 否是 否
16
一维搜索的插值方法
假定我们的问题是在某一确定区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干试验点处的函数值。我们可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的近似值。
这种方法称作插值法，又称作函数逼近法 。
17
插值方法与试探方法的对比
相同之处 在于都是利用区间消去法原理将初始搜索区间不断缩短，从而求得极小点的数值近似解。
不同之处 在于试验点位置的确定方法不同。
– 在试探法中试验点位置是由某种给定的规律确定。
– 在插值法中试验点位置是按函数值近似分布的极小点确定。
– 试探法仅仅利用了试验点函数值的大小的比较，
– 而插值法还要利用函数值的本身或者其导数信息。
– 由于试探法仅对试验点数值的大小进行比较，而函数值本身的特性没有得到充分利用
– 插值法则是利用函数在已知试验点的值（或导数值）来确定新试验点的位置。当函数具有比较好的性质时 (例如连续可微性 )，插值方法比试探法效果更好。
18
一维搜索的插值方法
多项式是函数逼近的一种常用工具。在搜索区间内我们可以利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，
并用这个多项式的极小点作为原函数极小点的近似。
常用的插值多项式为二次多项式。
– 牛顿法（切线法）：利用一点的函数值、一阶导数值和二阶导数值来构造此二次函数
– 抛物线法（二次插值法）：它利用三个点的函数值形成一个抛物线来构造此二次函数
19
牛顿法
对于一维搜索函数，假定已给出极小点的一个较好的近似点 a0，
因为一个连续可微的函数在极小点附近与一个二次函数很接近，
所以可以在 a0点附近用一个二次函数来逼近函数，即在点 a0将 f(a)
进行泰勒展开，并保留到二次项，有
然后以二次函数的极小点作为极小点的一个新近似点，根据极值必要条件
( ) ( ) ( ) ( ) ( ) 20 0 0 0 01( ) ( ) 2f x a f a f a a a f a a af ⅱ? + - + -
1( ) 0af ￠ = ( ) ( ) ( )0 0 1 0 0f a f a a aⅱ + - =对 a求偏导
( )
( )
010
0
faaa
fa
￠=-
ⅱ
( )
( )1 0,1,2,
kkk
k
faa a k
fa+
￠= - =
ⅱ L
依此继续可得牛顿法迭代公式
20
牛顿法的计算步骤
⑴ 给定初始点 a0，控制误差?，令 k=0
⑵ 计算 f(x)在 ak点的一阶和二阶导数
⑶利用牛顿法迭代公式求 ak+1
⑷ 若 |ak+1-ak|≤?，则求得近似解 a*=ak+1，
停止计算，否则作第⑸步
⑸令 k=k+1，然后转第 ⑵步
21
牛顿法
最大优点是收敛速度快
缺点
– 每一点处都要计算函数的导数和二阶导数，因而增加了每次迭代的工作量
– 用数值微分代替二阶导数时，舍入误差会影响牛顿法的收敛速度，当二阶导数很小时问题更严重
– 牛顿法要求初始点选得比较好，即不能离极小点太远，否则在可能使极小化序列发散或收敛到非极小点
22
上机实验
进退法确定搜索区间上机编程
黄金分割法上机编程
二次插值法上机编程
汽车转向梯形优化设计
23
二次插值法（一）
又称抛物线法。利用 y=f(x)在单谷区间中的三点
x1<x2<x3的相应函数值,f(x1)>f(x2)<f(x3)，作出如下的二次插值多项式
多项式的极值点可以从极值的必要条件求得
( ) 20 1 2P a a a x a x= + +
( ) ( )21 0 1 1 2 1 1 1P x a a x a x y f x= + + = =
( ) ( )22 0 1 2 2 2 2 2P x a a x a x y f x= + + = =
( ) ( )23 0 1 3 2 3 3 3P x a a x a x y f x= + + = =
( ) 1220P x a a x**￠ = + = 1
22
ax a* =-
24
二次插值法（二）
P(x)的系数确定与极小点的计算
( ) ( )
( ) ( )
221 1 2 2 1 2 1 2
221 2 3 2 2 3 2 3
a x x a x x y y
a x x a x x y y
- + - = -
- + - = -
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
2 2 2 2 2 2
2 3 1 3 1 2 1 2 3
1
1 2 2 3 3 1
2 3 1 3 1 2 1 2 3
2
1 2 2 3 3 1
x x y x x y x x y
a
x x x x x x
x x y x x y x x y
a
x x x x x x
- + - + -
=
- - -
- + - + -
=-
- - -
( ) ( ) ( )
( ) ( ) ( )
2 2 2 2 2 22 3 1 3 1 2 1 2 31
2 2 3 1 3 1 2 1 2 3
1
22
x x y x x y x x yax
a x x y x x y x x y*
- + - + -= - =
- + - + -
令
21 1
31 2112
3 1 2 3
,
yy c
yy xxcc
x x x x
- -
- -==
--
112
2
1
2
cx x x
c*
骣 ÷?= + - ÷?桫
25
二次插值法（三）
缩短搜索区间
(1)如果搜索区间足够小，则可用 P(x)的极小点 x4作为 f(x)的极小值
x*的近似解
(2)否则，必须缩短搜索区间（利用单谷函数的性质）重复进行二次插值法
– (1)当 x2<x4时，
如果 f(x2)<f(x4)，则取 [x1,x2,x4]为新的搜索区间；
如果 f(x2)>f(x4)则取 [x2,x4,x3]。
– (2)当 x2>x4时，
如果 f(x2)<f(x4)，则取 [x4,x2,x3]为新的搜索区间；
如果 f(x2)>f(x4)则取 [x1,x4,x2]。
x1 x2 x3x4 x1 x2 x3x4 x1 x2 x3x4x1 x2 x3x4
26
二次插值法（四）
计算步骤
(1)确定搜索区间 [x1,x2,x3]，给定计算精度?>0
(2)计算 f(xk)，置 fk=f(xk),k=1,2,3
(3)按公式计算 x4，并计算 f4=f(x4)
(4)检验 |x4-x2|<?否。如果满足，则停止计算，取 x*=x4，
否则转 (5)
(5)如果 x2<x4，转 (6)，否则当 f2<f4时,x1=x4,f1=f4，
转 (3)；当 f2≥f4时,x3=x2,f3=f2,x2=x4,f2=f4，转
(3)
(6)当 x2<x4，当 f2<f4时,x3=x4,f3=f4，转 (3)；当
f2≥f4时,x1=x2,f1=f2,x2=x4,f2=f4，转 (3)
27
二次插值法（四）
计算机流程图给定 x1,x2,x3,?
计算 f1,f2,f3
c1=(y2-y1)/(x3-x1);
C2=((y2-y1)/x2-x1)-c1)/(x2-x3)
x4=0.5*(x1+x3-c1/c2);
f4=f(x4)
|(f4-f2)/f2|<?
x*=x4 x2<x4
f2<f4
x3=x4;
f3=f4
x1=x2;
f1=f2;
x2=x4
f2=f4
f2<f4
x1=x4;
f1=f4
x3=x2;
f3=f2;
x2=x4
f2=f4
结束是 否是是是否否否
28
例题：黄金分割法（一）
对函数 f(x)＝ x2+2x，给定搜索区间 -3≤x≤5时，用黄金分割法求极小点 x*
此时 a=-3,b=5，按公式计算两插入点
( ) ( )1 5 0,6 1 8 5 3 0,0 5 6a b b al= - - = -? =
( ) ( )2 3 0,6 1 8 5 3 1,9 4 4a a b al= + - = - +? =
计算两插入点的函数值
( )11 0,1 5 5y f a==
( )22 7,6 7 7y f a==
21yy>
消去区间 [a2,b]，新的搜索区间 [a,b]的端点
a=-3不变，而 b=a2=1.944
29
例题：黄金分割法（二）
依次重复黄金分割法的迭代过程，前五次迭代的结果
假定，经过 5次迭代后已满足收敛精度要求，则得
该问题的精确解为迭代序号 a a1 a2 b y1 比较 y2
0 -3 0.056 1.944 5 0.115 ＜ 7.667
1 -3 -1.111 0.056 1.944 -0.987 ＜ 0.115
2 -3 -1.832 -1.111 0.056 -0.306 ＞ -0.987
3 -1.832 -1.111 -0.665 0.056 -0.987 ＜ -0.888
4 -1.832 -1.386 -1.111 -0.665 -0.851 ＞ -0.987
5 -1.386 -1.111 -0.940 -0.665
( ) ( )11 1,3 8 6 0,6 6 5 1,0 2 5 522x a b* = + = - - = -
( ) 1,0 0 0 7fx * =-
( )11x f x**= - = -
30
例题：牛顿法
给定 f(x)=x4-4x3-6x2-16x+4，用牛顿法求其最小点首先求出函数的一阶、二阶导函数
( ) ( )
( ) ( )
32
2
4 3 3 4
1 2 2 1
f x x x x
f x x x
￠ = - - -
ⅱ = - -
给定起始点 a0=3，控制误差?＝ 0.001
k 0 1 2 3 4
ak 3 5.16667 4.33474 4.03960 4.00066
f`(ak) -52 153.35183 32.30199 3.38299 0.00551
f``(ak) 24 184.33332 109.44586 86.86992 84.04720
ak+1 5.16667 4.33474 4.03960 4.00066 4.00059
( )
( )1 0,1,2,kkk k
faa a kfa+ ￠= - =ⅱ L
31
例题：二次插值法
用二次插值法示 f(x)=sin(x)在 4≤x≤5上的最小值此时的搜索区间为 [4,5]
121 3 24,5,4,52aaa a a += = = =
迭代两次的计算过程及结果见下表
1 2
a1 4 4.5
a2 4.5 4.705120
a3 5 5
f1 -0.756802 -0.977590
f2 -0.977590 -0.999974
f3 -0.968924 -0.958924
a4 4.705120 4.710594
f4 -0.999974 -0.999998
