浙江大学研究生学位课程
《实用数值计算方法,1
第四章 非线性方程和非性方程组的解法
4.1 非线性方程的解法
4.2 非线性方程组的 线性化解法
4.3 非线性方程组的 极值求解法
4.4 最速下降法
4.5 共轭梯度法
4.6 牛顿过程及变度量法
4.7 直接法
4.8 方法的选择与总结浙江大学研究生学位课程
《实用数值计算方法,2
１,非线性方程的解法
２,非线性方程组的 线性化解法
－－牛顿迭代法
３,非线性方程组的 极值求解法
－－最速下降法 | 单纯形法
－－共轭梯度法 | Powell 方法
－－变尺度法 |
（可变矩阵方法） | 直接法
DFP 方法 |
浙江大学研究生学位课程
《实用数值计算方法,3
４,1 引言在科学研究中，常常会遇到非线性方程或非线性方程组的问题。例如解方程或一般的，我们记非线性方程为
14024503510 234 xxxx
240
2
s i n
xe x?
340xf
浙江大学研究生学位课程
《实用数值计算方法,4
4.1
非线性方程组的一般形式是：
0,,,
0,,,
0,,,
21
212
211
nn
n
n
xxxf
xxxf
xxxf
其中 fi（ i=1,2,…,n ） 是 n维实空间Ｒ n 上的实值函数。用向量形式表示：
这里 均是 n维向量。为了方便计，还是用 分别表示上述向量。
简记为：
440xf
0,,xf
0,,xf
0?xf
浙江大学研究生学位课程
《实用数值计算方法,5
4.1
c a
d
c a
d
b
3axy
dcxy 3
2axy
dcxy 2
图 4.1 非线性方程求根示意图浙江大学研究生学位课程
《实用数值计算方法,6
4.1
方程的解亦称方程的根或函数的零点。
根可能是实数或复数。
若 则 称为单根；
若而,则 称为 k 重根。
常见的求解问题有两种,
(1) 要求定出在给定范围内的 某个解 。
(2) 要求定出在给定范围内的 全部解 。
非线性问题，除少数情况外，一般不能不利用公式求解。而 要采用某种迭代解法 。
即构造出一近似值序列逼近真解 。
,0,0 ' ff?
01' kfff?
0kf
n,,,10
浙江大学研究生学位课程
《实用数值计算方法,7
4.1
迭代过程的 收敛性 一般 与初值 的选取和 方程的性态 有关，某些解法仅与初值有关。
收敛速度 一般由 迭代方法 所决定，方程的性态也会起一些作用。
本章主要介绍非线性方程组的解法,
而方程的解法用较少的篇幅在 4.2中扼要介绍。
解非线性方程和方程组有很大区别 。后者要 困难得多 。主要的区别在于一维情形可以找到一个根的范围，然后缩小，最终找到根。而 多维情况则很难确定根的存在 。
直到你求得它的解。
浙江大学研究生学位课程
《实用数值计算方法,8
4.2 非线性方程的解法
4.2.1 二分法对于连续函数,如果在和 处异号：
则 在 内至少有一个根。
xf
ax? bx 0 bfaf
xfba,
同号与否。与取决于代替前一步的或的方法，称二分法。用减小一倍，即二分每步使长度的解。近似作为用足够小时，。当区间当＝０时已找到解
，并保持逐步缩小区间
2
,
2
,
,
2
,
,
02
,
0,
ba
f
afba
ba
a
b
ba
ba
ba
xfba
ba
bfafba
浙江大学研究生学位课程
《实用数值计算方法,9
4.2.1
用图来表示这个过程：
０
y
x
a ba b
a b
时零点。
、只能求实函数的一个
、方法稳定，只要求
、收敛速度慢，线性。
3
,
2
1
0
bacxf?
确定根所在的范围［ a,b］ 对有的函数也是一件困难的事。所幸的是，在实际应用中，根据其物理或工程的背景，在绝大部分场合是不困难的。对给定的函数也有确定范围的方法。
图 4.2 二分法方程求根浙江大学研究生学位课程
《实用数值计算方法,10
a
b
ba
x1
x1 x2 x3dcfc
a
b
4.2.1
图 4.3 寻找隔根区间示意 1
浙江大学研究生学位课程
《实用数值计算方法,11
xc 1sin
cxd?1
a c
b
4.2.1
图 4.4 寻找隔根区间示意 2
图 4.5 寻找隔根区间示意 3
浙江大学研究生学位课程
《实用数值计算方法,12
例如，在［ a,b］ 之间寻找 f(x) 可能有的根可以用等分试探法：
a b
4.2.1
图 4.6 等分试探法寻找隔根区间示意浙江大学研究生学位课程
《实用数值计算方法,13
用二分法求函数 FUNC位于（ x1,x2） 之间的根，准确性为?XACC。
FUNCTION RTBIS (FUNC,X1,X2,XACC)
PARAMETER (JMAX=40)
FMID=FUNC(X2)
F=FUNC(X1)
IF (F*FMID.GE.0.) PAUSE '函数 FUNC在 x1,x2处不异号 '
IF (F.LT.0.) THEN
RTIBIS=X1
DX=X2-X1
ELSE
RTBIS=X2
DX=X1-X2
ENDIF
DO 11 J=1,JMAX
DX=DX*0.5
XMID=RTBIS+DX
FMID=FUNC(XMID)
IF (FMID.LE.0.) RTBIS=XMID
IF (ABS(DX),LT,XACC,OR,FMID,EQ,0.) RETURN
11 CONTINUE
PAUSE '迭代次数越界 '
END
4.2.1
浙江大学研究生学位课程
《实用数值计算方法,14
FUNCTION FF(X)
FF = X*X + 2.5*X + 0.5+SIN(X)
END
PROGRAM ROOTFIND
EXTERNAL FF
X1=-1.0
X2=0.0
ROOT=RTBIS(FF,X1,X2,1.0E-5)
PRINT *,'方程在（ -1,0）区间内有一个根,X=',ROOT
STOP
END
内的一个根解题示例。，在区间求
01
)s i n (5.05.2,2
xxxxf
4.2.1
浙江大学研究生学位课程
《实用数值计算方法,15
4.2.2 线性插值法 （又称弦位法）
为止。逼近解如此反复，直到充分
，重复上述过程得到
，代替似值。用的一个新的近为
：的零点，并记为求构造一线性函数，通过且
。，的两个近似解的解设
４
１３
３
３
１
２１
3
12
12
22
2
12
12
2
221
2211
,,
,
0
ff
f
xL
x
ff
fxL
ff
ffff
xf
x
f(x)
2?
4?
1?
3?
图 4.7 Secant Method
浙江大学研究生学位课程
《实用数值计算方法,16
4.2.2
c
c
3
3
23
323
设迭代控制：
21
2
3
3
3
,
0
1
，则当附近在零点如果程是发散的。当超过这个数时认为过
，迭代次数故一般提供一个最多的收敛的，由于有时这个过程是不
。作为解时认为过程收敛，或满足。则迭代过程如果一般取数。为绝对或相对误差控制其中
Cxf
k
f
C
浙江大学研究生学位课程
《实用数值计算方法,17
4.2.2
降低了收敛速度。
，但是却法增加了收敛的可能性
。简称个修改后的方法叫做
。。这定包含了解最近得到的。但它们一不一定是，解使它所保留的两个近似修正一下这个算法，的原因之一。我们如果敛。。这也是不能保证收不总是包含解之间并，的近似值解两个最近的是所保留的线性插值法的一个缺点阶。即超线性收敛。其收敛速度为的。时，线性插值法是收敛充分接近于
F P M
F P MM e ht odP os it ionF al s e,
618.1
21
21
浙江大学研究生学位课程
《实用数值计算方法,18
4.2.2
收敛还要慢。
插值法比二分法可以举出例子说明线性
。。根必须包含，值法的初始所示。图解的迭代过程如法及近似
21
8.4
FPM
FPM
f(x)
x
1
4
3
2
图 4.8 线性插值法求根示意浙江大学研究生学位课程
《实用数值计算方法,19
4.2.2
f(x)
x
1
3 4 5
图 4.9 线性插值法发散示例浙江大学研究生学位课程
《实用数值计算方法,20
4.2.3 Newton 法
'
1112
1
'
1
1
''
1
11
'
0
0
ff
xL
fxfxL
ff
ff
xfxf
得令作记：
存在。附近在解设
F(x)
x
2? 1?
11,fx
图 4.10 Newton 法示意浙江大学研究生学位课程
《实用数值计算方法,21
4.2.3
。故求弦位法每迭代一次只需求值。必须对存在
：法的收敛阶为
k
kk
k
k
k
k
fa
ff
fkf
c
e
e
N e w t o n
.
,3
,2,102
0lim
21
'
''
1
F(x)
2? 1?
x
11,f?0'2?f
图 4.11 导数变化对算法的影响浙江大学研究生学位课程
《实用数值计算方法,22
每次函数求值相当的收敛阶为：
b,求 fk' 有时工作量大，甚至不可能。
(4) 选用收敛域较大的方法（如二分法）
先进行迭代，然后再用 Newton法。
－－组合方法。
4.2.4 二次插值法设 f(x)=0 的三个近似解及函数值构造二次函数 g(y)使得：
。332211,,,,,fff
414.12? 618.1?
浙江大学研究生学位课程
《实用数值计算方法,23
4.2.4
PQX
y
ffff
fyfy
ffff
fyfy
ffff
fyfy
ygx
L agr ang e
ifgx
ii
则求新的近似根，令插值：利用
,0
3,2,1
1232
213
3121
132
2313
311
浙江大学研究生学位课程
《实用数值计算方法,24
4.2.4
1
3
3
2
2
1
21
3
3
13
2
2
32
1
1
111
f
f
T
f
f
S
f
f
R
ff
f
ff
f
ff
f
Q
TSRP
其中：
F(x)
x
g(x)
f(x)
1?
4?
3? 2?
图 4.12 二次插值法求根示意浙江大学研究生学位课程
《实用数值计算方法,25
4.2.4
(1) 要有三个初始值
(2) 当 。且收敛速度是 1.84 阶。（单根）
二重根的收敛阶是 1.23。
(3)
(4) 发生超射、越界。
21111,,,,且
时收敛,03Cxf?
不同值。
不同值。
3,2,1
3,2,1
if
i
i
i?
方法名称 收敛速度 有效指数 重根情况二分法 1 1 1,偶重失败线性插值法 1,6 1 8 1,6 1 8 1
牛顿法 2 1,4 1 4 1
二次插值法 1,8 4 1,8 4 二重时 1,2 3
表 4.1 各种插值方法的比较浙江大学研究生学位课程
《实用数值计算方法,26
4.2.5 组合方法 （ Brent Method）
能否有一种方法综合上述方法的优点呢？ Brent 做了一些工作。
Brent 把二分法和二次插值法结合起来 。
（１）一定收敛。
（２）收敛速度至少线性。
（３）在解附近足够光滑时，收敛速度将是 1.84 或 1.23。
有关多项式的求根还有一些特殊方法。
浙江大学研究生学位课程
《实用数值计算方法,27
4.3 非线性方程组及牛顿法非线性方程组的向量形式可表示为
Tn
T
n
x
ffff
xf
,,,
,,,
540
21
21
其中解法：
1,几乎不可能用直接法
2,线性化，迭代逼近。 牛顿法
3,最优化，求函数极小值。下降法。
例如，
求 的极小值点。
最速下降法,共轭梯度法,变尺度方法 。
2xfx i
浙江大学研究生学位课程
《实用数值计算方法,28
4.3.1 牛顿法为方便计，用二维情形来讨论。
640,
0,
212
211?
f
f
假定（ 4-6）的解,0,,0
21 xCffx
。且存在一阶偏导数。设?,0 xx k
kkkxx 2121,,,这里，
作线性函数 （ Taylor 展开，取一阶精度 ）
74
22
2
2
11
1
2
22
22
2
1
11
1
1
11
k
x
k
x
k
k
x
k
x
k
kk
kk
ff
xfxl
ff
xfxl
浙江大学研究生学位课程
《实用数值计算方法,29
4.3.1
在 内用线性函数（ 4-7）代替非线性方程组 (4-6)中的 f1,f2,从而
,0?x
kkkk
kkk
x
kkk
x
xf
ff
xf
ff
k
x
k
k
x
k
222111
22
2
2
1
2
2
12
2
1
1
1
1
,
这里，
如果在 中矩阵 （称 Jacobi矩阵 ）,0?x
84
2
2
1
2
2
1
1
1
kx
k
ff
ff
xDf
非奇异，则可解出。
浙江大学研究生学位课程
《实用数值计算方法,30
4.3.1
94
2
11
2
1?
k
k
k
xk
k
xf
xfDf
矩阵。从而称为向量函数的 J a c o b ixDf
kkk
kkk
22
1
2
11
1
1
10411 kk
x
kk xfDfxx
于是
k
x
n
nnn
n
n
k
fff
fff
fff
xDf
n
21
2
2
2
1
2
1
2
1
1
1
64
维情形：
的牛顿迭代公式非线性方程组浙江大学研究生学位课程
《实用数值计算方法,31
4.3.1
79.0
73.0
0.53.4
6.10.3
12.8
1
79.0
73.0
0.33.4
6.10.5
0.33.4
6.10.5
23,34
122,28
79.0,
73.0,
9.0,4.0
0332,
0224,
1
1
2
1
1
'
2
'
2
'
1
'
10
21
'
221
'
2
21
'
121
'
1
0
2
0
12
0
2
0
11
0
2
221
2
1212
221
2
2
2
1211
0
21
21
21
21
因此故再算解：设初始近似解为的近似解例：用牛顿法求方程组
x
T
ff
ff
xDf
ff
ff
f
f
x
f
f
浙江大学研究生学位课程
《实用数值计算方法,32
4.3.1
0.0
00000 0.1,50000 0.0
00013 8.0,00017 4.0
99986 2.0,50017 4.0
00013 8.0
01382 6.0
07039 2.0
08478 4.0
524.3056.5
028.2112.6
524.3056.5
028.2112.6
07039 2.0,08478 4.0,
000.1,514.0
100.0,114.0
3
2
3
1
223
2
112
1
1
2
1
1
1
11
1
1
2
1
1
001
0
xfxf
xxx
x
xxx
xf
xf
xDfx
xDf
xfxf
xxx
x
T
T
T
T
T
T
T
且故再重复做一次，得故重复上述过程，
故得：
浙江大学研究生学位课程
《实用数值计算方法,33
迭代式。
的改进为克服上述三个缺点，
的逆矩阵工作量大。计算可能出现病态。
很小。初始要求高，即
。收敛。且收敛速度阶为迭代式充分小，则且初值非奇。矩阵当
104
3
2
2104
,,0
,1,01
0
k
k
k
xDf
xDf
xx
kxDfJ ac obi
4.3.2 牛顿法的改进改进１ 带松弛因子的牛顿迭代格式 改善了对初始值近似程度的要求。
浙江大学研究生学位课程
《实用数值计算方法,34
4.3.2
(4-10) 中引入了松弛因子,有k?
二次插值法求解。它可以用黄金分割法或极值问题。
是一维的求取时，按即是牛顿法。收敛最快收敛。时当或的选取满足而
1241243
,12
114021
124m i n
114,2,1,0
1
1
1
1
k
k
k
kkk
kk
k
kkkkk
xfxDfxf
xfxf
k
xfxDfxx
浙江大学研究生学位课程
《实用数值计算方法,35
4.3.2
满足以上条件。
上的凸函数，则是显然，若
，当
，当内满足：在设内的极小值。在法（优选法）求函数
bax
xxxaxx
bxxxxx
bax
xba
x
,
,
,,
618.01
2112
2121
a b a?x?x b
图 4.13 凸函数示例浙江大学研究生学位课程
《实用数值计算方法,36
4.3.2
继续进行。否则，令若成立，则判别：
显然，
否则取取则若计算两个实验点
11
11
11
11
11
11
11
,
2
1
618.0
,
618.0
382.0
bbaa
abx
ab
abab
bax
bbca
dbaa
dc
abad
abac
浙江大学研究生学位课程
《实用数值计算方法,37
4.3.2
1
54
3
2
a c d b
x
2
15
61803.0
,1
1
,1
2
ww
ww
w
ab
ad
w
w
w
ad
ac
w
ab
ac
解得故从而则若根据等比收缩原则；
1a 1c 1d 1b
图 4.14 0.618法搜索极小点过程浙江大学研究生学位课程
《实用数值计算方法,38
4.3.2
(2) 二次插值法求一维函数极小值：
1
3
2
4
5
a cb
3,2,1
2,4,1
afbfcbcfbfab
afbfcbcfbfab
bx
x
cfcbfbafa
22
2
1
,,,,,
坐标：抛物线的极小点的通过图 4.15 二次插值法进行一维极小点搜索浙江大学研究生学位课程
《实用数值计算方法,39
4.3.2
改进２,带阻尼因子的牛顿迭代格式克服了矩阵 的奇异或病态。 (4-10)中引入阻尼因子,
kxDf
k?
,2,1,0
13411
k
xfIxDfxx kkkkk?
的选取可以在满足 (4-12)的前提下取很大值。
（１）改善对初值的要求
（２）当 ＝０时为牛顿法，收敛最快。
（３）为满足 (4-12)，实际上需要多次试算，
工作量大。
改进 3,修正牛顿法尽可能减少矩阵求逆次数。
k?
k?
浙江大学研究生学位课程
《实用数值计算方法,40
4.3.2
一种简单的办法 是每次使用同一个 Jacobi
矩阵的逆。
2,1,0101 kxDfxDf k令但大大影响收敛速度。
另一种办法是若干次迭代后求一个矩阵逆：
144,1,0
,,1
,1
1,
1
1,,
0,
kxx
mixfxDfxx
xx
mkk
ikkikik
kk
令它减少了矩阵求逆，又保证了收敛。
换一个角度看，如果说它的求逆次数与牛顿法相同 (k次 )，则它的收敛阶为 m+1。
浙江大学研究生学位课程
《实用数值计算方法,41
4.3.2
1,
1
1,2,1
0,
1
0,1,
0,
kkkkk
kkkk
kk
xfxDfxxx
xfxDfxx
xx
或
154,1,0
11
1
k
xfxDfxfxfxDfxx kkkkkkk
迭代格式 (4-15)具有 ３ 阶收敛速度。
对一维情况,Newton法在几何上表现为 m步迭代过程保持斜率 f'(xk) 不变。
如图 4.16：
f(x)
x0
0,kx
kx
1,kx2,kx
1?kx
1,1?kx
2,1?kx
2?kx
图 4.16 m=2的迭代效果作为特例，取 m=2:
浙江大学研究生学位课程
《实用数值计算方法,42
4.3.2
非线性代数方程组求解问题
1,Newton--Raphson 迭代法
2,极值化求解。
问题的转化,
xfxfxf
xxxf
nixxxf
i
n
x
ni
0
,,,m i n
,,2,10,,,
21
21
是一个非负函数，且设无约束最优化问题?
nibxaDx
xxxx
xxxfxf
xxxfxf
iii
T
n
n
i
ni
n
i
ni
,,2,1,
,,,
,,,
,,,
21
1
2
21
1
21
这里，
例：
浙江大学研究生学位课程
《实用数值计算方法,43
4.4 最速下降法
方程组的主要方法。
方法是解非线性最优化极值化
4.4.1 极值化求解
164
,,2,10,,,
1
2
21
n
i
i
ni
xfxf
nixxxf
等价于求解
的 零极值点 。
求解 (4-16)的极值点也是一个无约束的最优化问题。
浙江大学研究生学位课程
《实用数值计算方法,44
4.4.1
求解最优化问题，通常采用下降法 。 下降法一般描述如下：
增加最快的方向。显然：梯度方向是函数的梯度。称为其中：
有即的初始估计。是点。是无约束问题局部极小设
xf
x
xf
x
xf
xf
xf
xfxf
xx
x
T
n
Dx
,,
0
1
0
m i n
浙江大学研究生学位课程
《实用数值计算方法,45
4.4.1
下降法的迭代步骤
，迭代结束。置
，转置则转且若计算
，以保证选择步长因子
，使确定下降的搜索方向
1
21
11
1
:.6
11:.5
6
.4
.3
0.2
0),(
.1
k
kk
k
kkkk
kkkk
k
kk
k
xx
kk
xfxf
xf
hxx
xfhxf
hxf
h
浙江大学研究生学位课程
《实用数值计算方法,46
4.4.1
最速下降法 取因此
,kk xfh
,2,1,0
1
k
xfxx kkkk?
kkk
k
kk
kkkk
k
k
xfxf
ii
xfxfxf
i
0
m i n:
2
1
0
通过一维搜索确定
，再检验。不成立时，让检验
，为给定常数取有为步长因子。它的取法其中浙江大学研究生学位课程
《实用数值计算方法,47
4.4.1
等高线图：
f(x)=Ci
f(x1,x2)=Ci
x
0x
1x
0h
kx
1h
1?kx
kh
k?
k
k
kkk
k
k
kk
kkk
h
hxx
h
hxf
hh
1
m i n其大小应满足方向步长，为沿为反梯度方向，
xf
x
kxxx
f
kx
xf
1?
2?
kkkx 21,
kxf?
kxx
f
1?
kxx
f
2?
图 4.17 等高线图 4.18 偏导数示意浙江大学研究生学位课程
《实用数值计算方法,48
xfxf
xf
k
k
k
0lim
单调下降这样，
4.4.2 讨论与改进优点：
１,程序简单，每步迭代计算量少，存储省。
２,对于不太好的初始点 x0，往往也能收敛。
缺点,
最速下降法是名不符实的，一般来说，
它只有线性的收敛速度。
浙江大学研究生学位课程
《实用数值计算方法,49
4.4.2
收敛很慢。
出现锯齿形。对于一族扁椭圆，迭代则可以证明：若好。
这个方向并非最最快的方向，从整体看只是局部下降得究其原因，
ii
xfxfi
xfxfxf
xf
k
T
k
kkk
k
0
,min
1
1
0x
1x
2x kx
1?kx
x?
图 4.19 锯齿形搜索路径情况浙江大学研究生学位课程
《实用数值计算方法,50
4.4.2
成立。序列速下降法生成的使用精确一维搜索的最对正定二次函数或从而故而所以则证明：令
k
TT
k
T
k
k
T
k
k
T
k
k
T
k
kxx
n
kxxkxxxx
xx
kkk
kk
x
cxbAxxxf
xfxf
xfxf
hxf
hxf
h
f
h
f
h
f
d
xdf
d
xdf
hxfxf
hxf
nk
kkk
k
2
1
0
0
0
0
min
1
1
1
1
21
0
1
1
21111
1
浙江大学研究生学位课程
《实用数值计算方法,51
4.4.2
法收敛慢。严重。故此时最速下降偏离指向极小点方向椭圆扁长，负梯度方向时，的椭圆。当离心率很大等高线是离心率为为例：
中的正定二次函数以偏长的情形。几何上可解释为等高线
，收敛速度越慢。越接近于时，当的接近程度。和可见，收敛速度依赖于的最小、最大特征值。分别为这里其中：
b
a
ba
ba
q
b
a
A
ba
xf
R
cxf
qMm
mM
AMm
xfxf
m
c
mM
mM
q
cqxx
xfxfqxfxf
k
k
k
k
2
22
22
2
2
2
2
2
2
2
1
2
2
0
2
2
0
1
0
0
1
2
1
:
1
,
1
浙江大学研究生学位课程
《实用数值计算方法,52
4.4.2
一般来说，开始几步下降速度较快，但越靠近极小值点越慢。
改进,
e ls exf
iikifxx
h
khxx
P ar
N e w t on
k
kk
k
kkkk
,2,1,3
{
,2,1,0
t a n.2
.1
2
1
其中法法。后改用前几步用最速下降法，
浙江大学研究生学位课程
《实用数值计算方法,53
4.4.2
最速下降法算法框图,
0,0误差控制取初值 nRx
00 xfg
00,0 ghk
kkk
kkkk
hxfxf
hxx
01
1
min
:求一维极值得
11 kk xfg
11 kk gh
1kk
停yes
0xx解停yes
1 kxx解图 4.20 最速下降法算法框图浙江大学研究生学位课程
《实用数值计算方法,54
4.4.2
表数据：重复以上过程，可得下故求一维极值得设解：
用最速下降法求取例：设
T
Rx
T
xfxx
xfxfx
xfxf
xfx
xf
17
38
,
17
26
17
5
261 8 03 0 6
6
12
,
23
m i n,4,2
2
2
1
2
3
0001
0
2
00
0
12
21
0
121
2
2
2
1
2
k
0 -2 4
1 1,5 2 9 4 1 2,2 3 5 2 9
2 0,9 4 1 7 7 0 1,0 5 8 8 2
3 1,0 1 0 3 8 1,0 2 4 2 2
4 0,9 9 8 8 4 7 1,0 0 1 1 5
5 1,0 0 0 2 0 1,0 0 0 4 8
6 0,9 9 9 9 7 7 1,0 0 0 0 2
7 1,0 0 0 0 0 1,0 0 0 0 1
8 1,0 0 0 0 0 1,0 0 0 0 0
1? 2? 2
1?
0x
1x
2x
3x
x
图 4.21 搜索路径示意浙江大学研究生学位课程
《实用数值计算方法,55
4.5 共轭梯度法
（ Conjugate Gradient Methods）
4.5.1 共轭方向
A
B
D
C
O
0h
0h
0
0
||
,
hCDOCD
hBA
D
点且过的两个切点给定方向椭圆中心
为共轭方向。与为共轭直径。与则
CDAB
CDAB
图 4.22 共轭方向浙江大学研究生学位课程
《实用数值计算方法,56
4.5.1
共轭。关于这种关系称则有那么若令方向由下式决定并且及两个初始点给定方向其中维二次函数引理：
对称正定为凸函数
：时的二次函数可表示为
“共轭”关系：对二次函数来讨论这种
Ahh
Ahhxxh
hxfxf
hxfxf
hxxhxx
xxh
AA
cxbAxxxfn
AxxAxf
cxbAxx
cbb
aa
aa
cbb
aaaxf
n
T
T
TT
T
TT
,,
0,
m i n
m i n
,
,,
0
2
1
0
2
1
2
1
2
1
2
1
2
10
01111
00
0
1
00
0
1
01010001
000
2
1
21
2
1
2212
1211
21
2211
2
2222112
2
111
浙江大学研究生学位课程
《实用数值计算方法,57
4.5.1
0
0
0
0
0
2
1
2
1
2
1
01011
011
011
01
01
11
1
111
2211
2211
2
22
2
222
112112
2
111
AhhAhxx
hxxA
hxfxf
hxf
hxf
bAx
b
b
aa
aa
xf
baaa
f
cbbb
a
aa
aaaxf
T
T
T
T
T
T
nnnnn
n
inniii
i
nn
nnn
nn
nn
所以故又故所以证明：
浙江大学研究生学位课程
《实用数值计算方法,58
4.5.1
0h 0h
1x
1x
1h
0x
0x
cbxAxxxf TT 21
0,?x
xf
2?
1?
图 4.23 二次函数的共轭方向图 4.24 二次函数浙江大学研究生学位课程
《实用数值计算方法,59
4.5.1
0)(
0
,,2,11
,,2,1,
,,2,1,
,,,
,,1,;02
,01
,
,,,
2211
2211
21
21
21
21
mm
T
i
mm
i
i
i
m
j
T
i
T
nn
n
m
hhhAh
hhh
mih
mih
mihIA
Ahhh
mjijiAhh
Ahh
Ahh
ARRA
Rhhh
得事实上，由线性无关。：共轭向量组性质具有以下性质：共轭向量组是共轭的特殊情况。交的向量。因此，正交是一组正时，显然，当共轭的向量组。是则称若共轭的；是和则称向量若为对称正定。
定义：
浙江大学研究生学位课程
《实用数值计算方法,60
4.5.1
bAxxf
nkhxf
fxxxf
hxfxf
hhh
nih
mi
miAhhA
miAhh
mih
k
T
k
nn
kkk
ni
i
i
i
T
i
i
T
ii
i
2
,,2,10
1
0
m i n
,,,
,,2,1.2
,,2,10
,,2,10
,,2,10
,,2,1,
1
11
0
1
2
一维搜索满足：证明：
为凸若和有为搜索方向的搜索方法向量共轭，则相继以设性质可知的正定性。即由共轭，故有因为
浙江大学研究生学位课程
《实用数值计算方法,61
4.5.1
毕为凸函数，故又设
，得由性质的共轭性。得及，由
.
01
,,2,10
3
,,2,121
1
1
111
111
1
1
111
xxf
xf
nj
hAhAhxf
hAhAhxf
hAhxf
hxf
nih
Ahxf
xxAxf
AxxfAxxf
n
n
j
T
jj
T
nn
T
j
j
T
nn
T
nn
T
n
j
T
nn
T
n
j
T
n
i
kkk
kkk
kkkk
浙江大学研究生学位课程
《实用数值计算方法,62
4.5.2 共轭梯度法 Conjugate Gradient Method
利用共轭方向，对二次型求极值问题可以得到 n步收敛的结果。
现在的问题是：
1.如何构造 n个共轭方向？
2.对一般的非线性函数 f(x)怎么办？
3.由于舍入误差等影响,n次迭代不收敛时怎么办？
如下：和定义向量序列为任意向量阶对称正定矩阵是设
ii
T
hg
g
bxAxxxf
nnA
0
2
1
浙江大学研究生学位课程
《实用数值计算方法,63
4.5.2
双正交化方法。
一般称其为共轭向量序列的方法。
和一是构造一正交向量序列故可以证明：
因此一共轭正交使选择
Sc hm idtG r am
nji
jihAh
jigg
hAh
Ahg
hAhAhg
Ahg
gg
Ahggg
AhAh
gg
hgh
Ahgg
hg
j
T
i
j
T
i
i
T
i
i
T
i
ii
T
iii
T
i
i
T
i
i
T
i
ii
T
iii
T
i
i
T
i
i
T
i
ii
iiii
iiii
184,174
194,0
0
0
184
0
0
0
,,
174
1
1
1
1
11
1
00
浙江大学研究生学位课程
《实用数值计算方法,64
4.5.2
毕而
，由事实上，
引理：
证明：
改写，把公式为尽可能不使用矩阵
i
T
i
i
T
i
i
T
i
iii
T
i
i
T
i
i
T
i
i
T
i
i
T
i
i
T
i
i
T
i
i
i
T
iii
T
iiiii
T
ii
T
i
i
T
iii
T
i
T
ii
T
i
iii
T
iii
T
i
iii
T
ii
T
i
i
T
ii
T
iii
T
i
i
T
iiii
T
i
i
T
i
i
T
ii
T
i
i
T
i
i
T
i
i
i
T
i
i
T
ii
i
T
i
i
T
i
i
Ahh
hg
Ahh
hhg
Ahg
gg
gg
gg
Ahh
Ahg
AhhAhgAhgggg
Ahggg
gghg
hghg
hgghg
AhgAhhAhg
AhhgAhh
hg
AhhAhg
Ahh
hg
gg
ggg
gg
gg
A
11
111
1
111
010101
2121111
1111
11
11
1
1111
174
0
0
204
184
浙江大学研究生学位课程
《实用数值计算方法,65
4.5.10
k
T
k
k
T
kk
k
T
k
k
T
k
k
kkkk
k
T
k
k
T
k
k
kkkk
ii
i
i
T
i
i
T
i
i
i
T
i
i
T
ii
i
T
i
i
T
i
i
gg
ggg
gg
gg
ghhgh
Ahh
hg
hxx
k
xfg
h
Ahh
hg
gg
ggg
gg
gg
1111
0011
1
1111
234
2,1,0
184174
224
214
共轭梯度法：
为时，下面的极值算法称当令是共轭的，并且构成的向量，由浙江大学研究生学位课程
《实用数值计算方法,66
4.5.2
kkk
kkkk
i
Ahg
bhxAg
g
xfghx
1
0000
1184
,
式：的第满足容易说明：这样定义的其中，初始近似为
0
0
min
min
1
1
1
k
T
k
k
T
k
kk
k
k
gg
xfxf
hxf
xf
即时，
的选取用一维极值当
方法。
式子时，叫做个取第方法，而方法或称为一个等式时，叫做取第中的当共轭梯度法
RPR ibi e r eP ol ak
RF
e v e sF le t c he r
k
k
2
Re
234
浙江大学研究生学位课程
《实用数值计算方法,67
4.5.2
共轭梯度法是从梯度向量出发构造共轭向量。
* 由于误差积累等因素，对二次型，迭代
n次也未能达到极小点。
* F-R方法和 P-R方法的区别在于它们对二次型是一样的。而对一般函数用 P-R方法可能更合适。
* 共轭梯度法具有二次收敛速度 。
那么对一般的函数的共轭梯度法又是怎样的呢？
浙江大学研究生学位课程
《实用数值计算方法,68
4.5.2
在极小值点附近进行二次逼近：
Axxbxc
xx
xx
f
x
x
f
Pfxf
T
ji
jiP
jii
iP
i
i
2
1
2
1
,
2
kkkkk
kxx
k
P
ji
ij
hxfhxf
f
xf
A
xx
f
A
PfbPfc
ji
0
''
2
min
:,
.234
244
我们采用一维搜索求避免求的二阶偏导数。为因此需要计算时要用到知，求由共轭梯度法其中浙江大学研究生学位课程
《实用数值计算方法,69
4.5.2
但是求导数?f(xk)是必须的。
另外，我们总假定 f(x)在极值点附近性质足够好，满足各种要求。
对一般函数 f(x)，共轭梯度法 (4-23)有限步收敛几乎是不可能的。如果迭代 k 步达到精度（ k?n）,则 xk就作为 x*的近似。
当经过 n步迭代仍不可能满足要求时，令再进行第二次循环。
但是，实际计算中，不一定迭代
k=n 步才进行“重置”。
nn xfgkxx 000 而浙江大学研究生学位课程
《实用数值计算方法,70
4.5.2
(1) 在极小点附近是一个高度偏心的二次函数。
则进行 （ m+n） 次迭代 （１?m<n） 就收敛了。而进行 k 次迭代 （ k? n） 就重置的话，有可能会不收敛。
(2) 在极小点附近或稍远处不是二次函数。
此时称“扭曲”现象。
则 留有非二次函数的痕迹，故可能对收敛很有害。此时最好重置。
kkh?
浙江大学研究生学位课程
《实用数值计算方法,71
4.5.2
共轭梯度法 Conjugate Gradient Methods
算法框图
0,0误差控制取初值 nRx
00 xfg
00,0 ghk
kkk kkkk hxfxf
hxx
01
1
min
:求一维极值得
00 xfg
nk?
kkkk
k
T
k
k
T
kk
k
T
k
k
T
k
k
hgh
gg
ggg
gg
gg
11
1111
1kk
10
10
k
kgg xx
停yes
0xx解
no
停
1 kxx解
yes
no
no
yes
图 4.25 共轭梯度法算法框图浙江大学研究生学位课程
《实用数值计算方法,72
(3) 如何判别是高度偏心的二次函数还是扭曲的函数 呢？
启发性的办法是：
对一般非二次函数，若 x0离 x*较远，
则迭代 n次不收敛时，就重置。但以后不再重置。
对既高度偏心，又严重扭曲的函数，
则经常性的重置是有好处的。
52102010
4110
1
2
1
2
2
2
12
4
1
2
1
22
12
xxxxxxxf
xxxxf
即：
函数例如：
浙江大学研究生学位课程
《实用数值计算方法,73
4.5.2
它在点（ 1,1）处有极小值 4.
其图象为：
1x
2x
图 4.26 函数等高线图浙江大学研究生学位课程
《实用数值计算方法,74
4.5.2
表 4.3 最速下降法计算结果
X
1
X
2
f X
1
X
2
f
-1,2 0 0
-0,9 9 3
-0,7 9 3
-0,6 6 3
-0,5 5 2
-0,3 8 8
-0,3 0 6
0,6 3 3
0,6 2 5
0,6 5 4
0,6 4 8
1,0 0 0
1,0 7 1
0,4 9 3
0,5 3 8
0,2 1 8
0,2 7 5
0,0 3 7
0,3 6 1
0,3 8 2
0,3 9 2
0,4 1 1
1 0,7 7 6
8,0 4 5
7,4 0 3
6,8 6 2
6,4 8 3
6,0 8 1
5,7 3 9
4,1 5 1
4,1 4 1
4,1 3 2
4,1 2 5
0,6 7 2
0,6 6 7
0,6 8 9
0,6 8 3
0,7 0 3
0,6 9 8
0,7 1 6
0,7 1 1
0,7 2 8
0,7 2 4
…
0,4 2 0
0,4 3 7
0,4 4 4
0,4 6 0
0,4 6 6
0,4 8 1
0,4 8 7
0,5 0 0
0,5 0 5
0,5 1 7
…
4,1 1 8
4,1 1 2
4,1 0 6
4,1 0 1
4,0 9 6
4,0 9 1
4,0 8 7
4,0 8 3
4,0 8 0
4,0 7 7
…
浙江大学研究生学位课程
《实用数值计算方法,75
4.5.2
表 4.4 各种重置循环的共轭梯度法计算结果
A B C
x
1
x
2
f x
1
x
2
f x
1
x
2
f
- 1,2 0 0
G -,9 9 3
-,6 5 7
-,4 0 9
-,2 4 1
-,1 1 2
-,0 0 3
0,0 1 0
,1 9 1
,2 8 7
,3 9 0
,5 0 4
,6 3 6
,7 9 2
,9 8 6
1,2 4 9
1,4 1 8
1,0 0 0
1,0 7 1
,2 7 5
-,0 7 3
-,2 2 7
-,3 0 2
-,3 3 5
-,3 4 2
-,3 2 7
-,2 9 0
-,2 2 6
-,1 2 5
,0 2 9
,2 6 7
,6 4 9
1,3 0 1
1,9 4 3
1 0,7 7 6
8,0 4 5
6,9 9 2
6,5 6 4
6,3 5 5
6,2 2 4
6,1 2 9
6,0 4 8
5,9 7 3
5,8 9 3
5,8 0 2
5,6 8 9
5,5 4 2
5,3 4 0
5,0 4 5
4,6 0 2
4,1 8 6
- 1,2 0 0
G -,9 9 3
-,6 5 7
-,4 0 9
-,2 4 1
G,0 5 9
,2 8 9
,5 8 2
,7 6 7
G,7 9 2
,9 2 8
,9 6 5
,9 6 9
G,9 6 9
1,0 0 0
1,0 0 0
1,0 0 0
1,0 7 1
,2 7 5
-,0 7 3
-,2 2 7
-,1 0 0
,0 0 8
,2 3 5
,6 2 8
,6 1 6
,8 3 4
,9 3 5
,9 3 7
,9 3 8
,9 9 8
,9 9 9
1 0,7 7 6
8,0 4 5
6,9 9 2
6,5 6 4
6,3 5 5
4,9 7 9
4,5 6 5
4,2 8 3
4,0 7 0
4,0 4 4
4,0 1 3
4,0 0 1
4,0 0 1
4,0 0 1
4,0 0 0
4,0 0 0
- 1,2 0 0
G -,9 9 3
-,6 5 7
G -,4 9
-,1 3 2
G,8 3 7
,8 3 3
G,8 4 2
,9 7 2
G,9 6 5
1,0 0 0
G 1,0 0 0
1,0 0 0
1,0 7 1
,2 7 5
,3 4 6
-,0 9 8
,6 8 1
,6 8 8
,6 9 4
,9 2 6
,9 3 0
,9 9 9
,9 9 9
1 0,7 7 6
8,0 4 5
6,9 9 2
6,3 3 2
5,4 1 6
4,0 3 0
4,0 2 8
4,0 2 7
4,0 0 4
4,0 0 1
4,0 0 0
4,0 0 0
浙江大学研究生学位课程
《实用数值计算方法,76
4.6 牛顿过程及变度量法
4.6.1 Newton--Raphson 迭代把函数 f(x)在第 k次近似解 xk 附近进行
Taylor展开：
xxf
xf
xxJxx
xxxfxfxf
kk
T
k
k
T
kk
之极小点：求记
2
1
浙江大学研究生学位课程
《实用数值计算方法,77
4.6.1
考查下例可能奇异。
收敛到鞍点。有些问题可能发散，或敛。是二次函数，则一步收若收敛阶为收敛快。
迭代格式。这就是即
k
kkkk
kkkk
kkkk
x
i
i
Jiv
iii
xfii
i
r aphs onN e w t on
xfJxx
xfxJxJ
xxJxfxf
ni
f
xf
.2
0
,,2,10
1
1
浙江大学研究生学位课程
《实用数值计算方法,78
4.6.1
稍有增加。出发的第一步，函数值从极小点支配。
的二次函数受到极小点，因为其附近敛更接近鞍点，但它却收虽比小点；受极小点影响收敛到极鞍点；在鞍点的影响下收敛到所示。见图出发的几条极小化路径方法分别从应用设
Civ
ACiii
Bii
Ai
CBAR aphoonN e w t on
xxxx
xxxxxxf
27.4
,,
44
2
9
2
22
2121
2
2
2
12
2
1
4
1
浙江大学研究生学位课程
《实用数值计算方法,79
4.6.1
A
C
B
1x
2x
图 4.27 初值对 Newton-Raphson 方法的影响浙江大学研究生学位课程
《实用数值计算方法,80
4.6.1
下降法避免收敛到极大点。
敛可能性。加快收敛速度和增加收其优点有：
极小化。使这里进是：这个方法一个有效的改一个鞍点是该函数的极值点为：
ii
i
xf
f
f
kk 1
493.1,611 7.0
513 4.0028.1,053.1
985 5.0854.3,941.1
kkkkk xfJxx 11?
浙江大学研究生学位课程
《实用数值计算方法,81
然而这个方法的致命弱点是要计算
Jk-1。 4.2提供的办法，即迭代若干次修改一次 Jk-1，是一种方案。但不是最好的。
4.6.2 变量的尺度变换为改变函数的偏心程度，从而改变极小化方法的收敛性质，采用变量替换是个很好的措施。
2
1
2
1
21
2
2
2
1
44
414 4
8414 4
x
x
x
x
xxxxxf
T
例：
浙江大学研究生学位课程
《实用数值计算方法,82
4.6.2
多。的极小化方法要稳定得求此的偏心程度小得多。因比的等高线图，显然和比较得：
作变换
xf
xfxf
xfxf
x
x
x
x
xxxx
xxfxf
x
x
x
x
T
~
~
~
~
~
1
6
1
6
1
1
~
~
~~
3
1
~~
~
,
~
~
~
~
2
1
0
0
12
1
2
1
2
1
21
2
2
2
1
21
2
1
2
1
浙江大学研究生学位课程
《实用数值计算方法,83
4.6.2
1x
2x
2~x
1~x图 4.28 函数进行尺度变换的效果浙江大学研究生学位课程
《实用数值计算方法,84
4.6.2
尺度变换 目的是把函数的偏心程度降到最低限度（它放大或缩小各个坐标），
但并不能完全消除偏心问题。
把尺度变换应用于各种算法，都有一定效果。
一般地
IATTT
A
xATTx
cBxAxx
nnT
xTx
T
TT
T
使是正定的，则若则二次项为考虑极小化二次函数阶矩阵。是非奇异的这里
~~
2
1
2
1
~
浙江大学研究生学位课程
《实用数值计算方法,85
4.6.2
即变换后的二次函数偏心率为０，它是圆。
它用最速下降法一步可以达到极小点。
现在希望直接处理原来的函数，而定义一个 算子。 用它产生通过极小点的向量。
考虑这样的Ｔ：
1
1
ATT
IATT
TAT
IATT
T
T
T
T
从 Newton--Raphson 过程
kkkkk xfJxx 11?
浙江大学研究生学位课程
《实用数值计算方法,86
4.6.2
变尺度法的基础。
的方法思想将是一种收敛很好量变换的不过由此引出的有关度甚至是奇异的。这是困难的。有时是正定的。实际上但是我们要求
。就可以显著减小偏心率或如果得到近似的因此我们不用求
，这个向量就是可知，对二次函数来说
k
k
T
k
k
T
kk
J
J
TTT
J
xfTTxfAh
1
1
1
,
,
浙江大学研究生学位课程
《实用数值计算方法,87
4.6.3 变尺度法
—— DFP方法
—— BFGS方法常用的度量是
通过极小点。对于正定二次函数，它记方法的搜索方向是：而方向用这种度量得最速下降
kkkk
kk
n
i
i
T
xfAxfJh
R aphs onN e w t on
xfh
xxxx
11
1
2
2
浙江大学研究生学位课程
《实用数值计算方法,88
kk
T
k
k
T
k
k
T
kkk
T
xfh
xxx
xf
xfxf
Oxfxf
xfxfxf
xOxxfxfxxf
而下降方向是量是故最速下降法采用的度对充分小的量最速下降法所采用的度
,
,
'''
2
2
2
2
2
2
4.6.3
浙江大学研究生学位课程
《实用数值计算方法,89
4.6.3
下的最速下降法。
就是在新度量意义因此，
由于是正定的，引进度量设
kk
k
k
T
k
k
T
k
k
T
k
k
T
kkkk
T
xfAh
xfA
xfAAxfA
xfAAxfA
xfAAxfA
xfAxfxfxfAxf
Axxx
A
1
2
1
11
11
11
11
2
2
1
2
1
2
1
的最速下降法。牛顿法就是在新度量下
浙江大学研究生学位课程
《实用数值计算方法,90
4.6.3
度和性质。
速，并且保持一定的收敛来代替近似度量简单的说，我们用一个
）
它也叫变矩阵法（
变化的。另外，是随的度量矩阵度量变度量法的名称是因为
。度，又不要计算顿法的收敛速而变度量法既保持了牛
。及其逆要计算二阶偏导数矩阵速度，但是它牛顿法具有很好的收敛
1
1
1
2
1
1
kk
kk
kk
T
kk
k
k
JH
M e t hods
M at r ixV ar iabl e
xJ
xJxx
J
J
浙江大学研究生学位课程
《实用数值计算方法,91
4.6.3
iikk
v
HHH
Hiv
hxx
hxfhxfiii
gHxfHhii
kHRxi
HHH
H
kkk
k
kkkk
kkkkkk
kkkkk
n
kkk
k
转：
不满足结束条件时令计算令求记正定矩阵取算法的步骤：
修正值的产生又比较方便：而
1
,
,
m i n:;0,,
1
1
1
0
00
1
浙江大学研究生学位课程
《实用数值计算方法,92
4.6.3
使之满足上面等式。构造
，故其中由中值定理，
记拟牛顿性质性，稳定性。拟牛顿性质，二次收敛的原则构造
1
1
1
2
1
1
0
,
,
2
k
kk
kk
kkkk
kkkkkkk
k
ji
kkk
kkkkk
k
H
xgA
xhxA
xghxgggg
J
xx
f
Axxx
gggxfg
i
H
浙江大学研究生学位课程
《实用数值计算方法,93
4.6.3
k
kkk
kk
T
kkkk
kk
n
n
kkk
xfxfH
gHgxfxf
kxfxf
iii
AH
Ahhh
n
ii
D F P
xgH
对适当小的正定时，总有故当事实上，
即稳定性：
轭的向量组，且共构成到极小点，这就要求步达法至多用于凸二次函数时，算二次收敛性条件此式称为拟牛顿方程
1
1
1
1
1
21
1
2
1
,2,1,0
,,,
浙江大学研究生学位课程
《实用数值计算方法,94
4.6.3
kkk
kk
T
k
k
T
k
T
k
T
k
kk
k
T
kk
T
k
k
T
kkkk
T
kkkk
T
kkk
T
kkk
kkkkk
kkkk
kkk
k
k
gHg
Hg
q
gx
x
q
gqg
gqgHgxgH
qgHxH
gHxgH
xgHH
D F PHHH
D F P
H
H
,
,
1
:3
1
可取为：这样的即可。只要求令故条件：满足要求方法。变度量方法。这里介绍种方法的不同，形成了各构造具体构造浙江大学研究生学位课程
《实用数值计算方法,95
4.6.3
谢如彪，姜培庆《非线性数值分析》，
陈开周《最优化计算方法》，
详细证明可参考：
正定二次收敛性可以证明：
变度量算法迭代公式。这就是得代入
2
1
,3,2
1
kHii
i
D F P
gHg
HggH
gx
xx
HH
k
kk
T
k
T
k
T
kkk
k
T
k
T
kk
kk
浙江大学研究生学位课程
《实用数值计算方法,96
4.6.3
变尺度法 Variable Matrix Methods
算法框图：
0,0误差控制取初值 nRx
00 xfg yes 停
0xx解
no
IHk 0,0:
kkk kkkk hxfxf
hxx
01
1
min
:求一维极值得
kkk gHh
11 kk xfg yes 停
1 kxx解
nk?
no
yes
10
10
n
ngg xx
no
k
T
k
T
kk
k
T
k
T
kk
kk
kkk
kkkkkk
ggx
xx
HH
gH
gggxxx
1
11,,
1kk
图 4.29 变尺度法算法框图浙江大学研究生学位课程
《实用数值计算方法,97
4.6.3
891241
241385
986
1
921
2149
58
1
12
24
17
1
10
01
1790
17210
61712
12176
1730
1760
41738
21726
1712
176
1738
1726
17
5
212264212
64
2
1
212
2
3
6,12
6,12
,4,2,
2
2
1
2
3
1
0000
0
0
111
0
22
00
000
00
00
121
2
2
2
1
H
ggH
g
x
xfgx
hxf
gHh
gxf
xfxIH
xf
T
T
T
故故得按精确一维搜索法不难而记首先计算之极小点。求取例：设
浙江大学研究生学位课程
《实用数值计算方法,98
4.6.3
1
12
111
11
1
2
1
111
31
11
2
1
833357
357153
986
441189
18981
306
1
744
366
986
1
1712
176
891241
241385
986
1
1712
176
,
1721
179
17381
17261
1
1
0
2
31
11
2
1
0
0
,
0
2
,
01
13
,
2
1
1
1
2921
299
17
29
1738
1726
17
29
2921
299
1712
176
891241
241385
986
1
A
HH
gH
gx
bA
cbA
cxbAxxxfxf
xf
x
gHh
TT
继续计算下去，则其极小点为则写成事实上，将的极小点。不难验证此即故作一维搜索，得再循环一次：
浙江大学研究生学位课程
《实用数值计算方法,99
4.6.3
,,,,
5
1
4
1
kkkk
k
T
k
k
T
k
k
T
kkkkk
k
T
kkkkk
T
kkk
T
kkkk
dcba
gv
gu
gHdxcv
gHbxau
vgHuxHH
H uang
个参数这个公式含有且满足：
其中：
公式：
族是一般的变度量算法主要变度量算法的校正公式
浙江大学研究生学位课程
《实用数值计算方法,100
4.6.3
数值稳定性最好的。它是当前变度量方法中公式：
即得重要的，，令族公式。即，令公式。即，令较重要的三种公式是：
个独立参数个关系式，故有但有
k
T
k
kk
T
k
k
k
T
k
k
T
kk
T
kkk
T
kkk
kk
kkk
kk
kk
gx
gHg
gx
HgxxgHxx
HH
B F G S
dcbiii
B r oy de ncbii
D F Pbci
1
,01
,1
,01
32
1
浙江大学研究生学位课程
《实用数值计算方法,101
4.6.3
方性 法质牛顿法 D F P （拟牛顿法）
共轭梯度法
（重置初值）
二次终止性质一步终止
（? =1 ）
n 步 ( 精确一维搜索 )
终止
n 步 ( 精确一维搜索 )
终止收 敛
f? C
( 3 )
且有界凸,x
0
充分接近 x
*
,?
k
1
f? C
( 3 )
在 L ( x
0
) 上有界凸,L ( x
0
) 有界
（精确一维搜索）
f? C
( 3 )
在 L ( x
0
) 上有界凸,L ( x
0
) 有界
（精确一维搜索）
局部收敛性同上二阶收敛同上，且? f(x ) 是
L i p s c h i t z 连续。
超线性收敛。
同上，
超线性收敛优缺点要计算二阶偏导数计算量大。 n 大时存贮量亦大计算量少，程序简单；
n 大时存贮量也大计算程序简单，
存贮量相对较小
称水平集。注：,00 xfxfRxxL n
表 4.5 各种方法比较浙江大学研究生学位课程
《实用数值计算方法,102
4.7 直接法 （ Simplex,Powell）
大量的目标函数是很复杂的，有时连解析式都没有，因而它的导数
f(x)
很难求，有时甚至不存在。
4.7.1 单纯形法 Simplex Method
Nelder--Mead (1965)提出这种简单的方法。它不需要求导数（梯度）
对变元不多的情况是有效的。
程序简单。
浙江大学研究生学位课程
《实用数值计算方法,103
4.7.1
单纯形的思想 是在 n维空间的 (n+1)个点
(它们构成单纯形 )上引进函数值比较。丢弃最坏的点并代之以新点。它们仍然构成单纯形。以此逐步逼近极小点。
下：则单纯形法迭代过程如它满足的一个排列是设个单位向量为定义初点选取单纯形的选取：
1,,1,0
,,,1,0
,,2,1
,
,,1,0
1
0
0
nixfxf
niPx
nu
niuPP
P
niP
ii
ii
i
iii
i
浙江大学研究生学位课程
《实用数值计算方法,104
4.7.1
）几何意义：（
是反射系数，一般
）（
的反射点关于求形心，令排列按
2
10
1
1
,,,
1
1
1
0
110
n
xxxxxP
Pxx
x
n
xii
xfxfxxxi
nnn
nn
n
i
i
iin
1x
x
0x2x
3P
图 4.30 单纯形法中的反射浙江大学研究生学位课程
《实用数值计算方法,105
1x
2x
x
0x
3P
4P
4.7.1
）几何意义：（
是延伸系数，一般
：方向的延伸点求沿则延伸。
的大小满足接和若
2
21
)1(;,,,,)
,,,
111
21
101
1110
n
xPxPxP
PP
xxxPa
PfPxxx
nnn
nn
nn
nnn
图 4.31 单纯形法中的延伸浙江大学研究生学位课程
《实用数值计算方法,106
4.7.1
);;,
5.010
5.0
:;,,,,,);;,,,,);
22
112
2
1110
1110
1
212
e
iPxxfPf
PxxPxP
Px
xPxxxc
iPxxxxxb
i
Px
PxPfPf
nnnn
nnn
n
nnn
nnnn
nn
nnnn
转否则转则若
。为收缩系数，一般方向的收缩点求沿则收缩。；转则转否则则若
1?nP
浙江大学研究生学位课程
《实用数值计算方法,107
4.7.1
2x
3P
x
1x
0x
4P
'4P
图 4.32 单纯形法中的收缩
e
iPxxfPf
xxxxxP
Px
Pxxxd
nnnn
nnn
nn
nn
否则转转则若如图方向的收缩点求沿则收缩;,
2
1
32.4,;,,,,)
'
2
'
2
'
2
'
2
110
浙江大学研究生学位课程
《实用数值计算方法,108
4.7.1
e) 缩小边长
i
ni
xxxxxx
xxnix
iii
ii
转令缩小一半：沿
,,2,1
2
1
2
1
,,1
000
0
1x
2x 0x
'1x
'2x
1?nP
图 4.33 单纯形法中的缩小边长浙江大学研究生学位课程
《实用数值计算方法,109
4.7.1
单纯形法（ Simplex）框图：
0,,1,0,0 ；任取 niP i?
niuuPP Tiiii,1,0,,1,,0,0,0
0xfxf n
nixfxfPx iiii,1,,1并排列：
nnn
i i
xxxPnxx
1
1
0; 反射
1?nPf判别
2?nP延伸得 2?nP收缩得 2?nP收缩得
12 nn PfPfnn xfPf2nn xfPf2
1 nn Px ix缩小边长，求
2 nn Px
解 x*?x0y
n
b
dca
n
yyy
n
图 4.34 单纯形法计算框图浙江大学研究生学位课程
《实用数值计算方法,110
以上的迭代过程直到满足精度为止。
精度：
则 x0作为所求的近似解。
4.7.2 Powelll 方法
Powelll 方法是一种不依赖于目标函数梯度的直接搜索法。
它 逐步构造共轭方向并作为搜索方向,
因此 Powell方法也是一种共轭方向法。
它的基本过程如下：
n
i i
xfxf
0
2
0
浙江大学研究生学位课程
《实用数值计算方法,111
4.7.2
则作为搜索方向，取取两单位标准向量例，设
,2,2
1
0
0
1
,2
0
21
21
2
2
2
1
T
x
ee
xf
k H
k
T
k
x
T
k + 1
F ( x
k + 1
)
0
1
2
( 0,1 )
( 1,0 )
( 0,1 )
-1
- 1,7 5
- 0,8 7 5
( 2,1 )
( 0,2 5,1 )
( 0,2 5,0,1 2 5 )
7
0,8 7 5
0,1 0 9
0,8 75
它必然指向极小点。
作为搜索方向故若取
，
即：
共轭的，是与可以发现，
13
213
0
1
0
21
14
112 5.0225.0
xxh
A
exx
5.0 0.1 5.1 0.25.0?0.1?5.1?
1.0
0.1
1x
0x
2x
3x
1?
2?
图 4.35 Powell搜索路径表 4.6 Powell 方法解题过程
5.0
2.5
浙江大学研究生学位课程
《实用数值计算方法,112
4.7.2
nn
nn
nn
ii
iiii
iiii
i
ii
i
uPfPf
uPP
PPu
niuu
uPfPf
uPP
P
uPni
ni
un
P
0
0
0
0
1
1
0
1
1
0
m i n
,3
1,,2,1,2
m i n
:
,,,2,11
,,2,1
0,,0,1,0,,0
使得求令值搜索，令极值点为方向作一维极小沿对个单位方向并且令给定一点
浙江大学研究生学位课程
《实用数值计算方法,113
4.7.2
Powell方法过程图示：
00P nu
0P
1u
1P
2u
2P
3u
3P
4u?
1?iP
iu
iP
3?nP
3?nu
2?nP
2?nu
1?nP
1?nu
nP
nu
10P
01 PPu nn
11u
11P
12u
12P
13u
13P
14u?
11?iP
1iu
1iP
13?nu
13?nP12?nP
1 2?nu
11?nP
11?nu
1nP
1nu
1012 PPu nn
1nP
101 nnnnn PPu
nP0
nu1
nP1
nu2
nP2
nu3
nP3
nu4?
niP1?
niu
niP
nnu3?
nnP3?
nnu 2?
nnP2?
nnu1?
nnP1?
nnu
nnP
,2,1 ;1,,2,1,11 j niuu jiji
图 4.36 Powell 方法计算过程图示浙江大学研究生学位课程
《实用数值计算方法,114
4.7.2
循环上面 (1)--(3)，直至 P0点函数值不再减小为止 。
当循环 k次 (k?n)以后,un与它前面的 k-1个向量 un-k+1,?,un-1共轭。因此对于二次函数，
理论上只要循环 n次即可求得极小值。即具有 二次收敛性 。事实上，因为
P0和 Pn是沿相同方向 un求得 的 极小值，
所以 Pn?P0与 un方向共轭。
nP
11?nP
10P
1nP
nu nu
图 4.37 共轭方向浙江大学研究生学位课程
《实用数值计算方法,115
4.7.2
方法Po w ell
n 2?
20P
12P
2212u?
1212u?
11P
1111u?
10P
212?u12P
2P
22?u
0P
11?u
00P
2u
图 4.38 Powell 方法计算过程示意浙江大学研究生学位课程
《实用数值计算方法,116
4.7.2
果为：方法计算的第一循环结用
，搜索方向取极小点为它是一正定函数，整体例：设
P ow e lleu
eueuP
P
xf
T
T
,
,,
2
1
,1,
2
1
0,0,0
3
0
3
2
0
21
0
10
2
321
2
132
2
321
k u
k
0
P
k
0
f(P
k
0
)
0
1
2
3
e
1
e
2
e
3
T
T
T
T
18
5
,
3
1
,
2
1
2
1
,
3
1
,
2
1
2
1
,1,
2
1
2
1
,1,
2
1
8142
32
2
2
。不能替换进行。故的平面上以后的搜索肯定在线性相关。，，显然索方向应是据算法，第二循环的搜于是
103
1
1
3
1
2
1
1
1
3
1
2
1
1
03
2
1
,
9
2
,
3
2
,0,1,0,0,0,1,0
9
2
3
2
0
ePP
uuu
uuu
PP
T
TT
T
表 4.7 Powell方法第一次循环计算结果浙江大学研究生学位课程
《实用数值计算方法,117
xf
x0P 1P
1x 0x 2P 3P
0x 1x
1x 0x 3P 2P
0x 1x
3P 2P1x 0x
1x 0x
图 4.39 单纯形法求一维极值示意图（ 1）
a
d
c
4.7.2
浙江大学研究生学位课程
《实用数值计算方法,118
xf
x
a
d
d
d
e
a
0P 1P
1x 0x 2P 3P
0x 1x
1x 0x 2P 3P
0x 1x
1x 0x3P 2P
0x1x
1x 3P 0x 2P
1x 0x
1x 3P 0x 2P
1x 0x
图 4.40 单纯形法求一维极值示意图（ 2）
4.7.2
浙江大学研究生学位课程
《实用数值计算方法,119
4.7.2
但是，实际计算中对二次函数也不能保证
n步内达到极小值点。
因为每一循环都用 Pn--P0“挤掉” u1,所以新的向量系 ui(I=1,…,n) 有可能线性相关，
例如，某一循环中，如果?1?０则这样,u2,u3,…,Pn--P0是线性相关的 。
当发生这种情况时，以后的搜索就在
n 维的子空间中进行。最后的解就不正确。
解决的办法是 Pn--P0不是挤掉 u1。而是挤掉
ur,而?r?０。 一般取 最大下降方向 （ the
Direction of the Largest Decrease)
0
2
0 PPuPP n
n
i
iin
平均方向?
浙江大学研究生学位课程
《实用数值计算方法,120
4.7.2
这是因为最大下降方向 ur已经在平均方向
Pn-P0中得到最充分的体现 。
这一简单的思想有两种例外情况：此时并不修改方向。
0m a x,0
2
1
1
1
0
00
ii
ni
rr
n
nn
ffffff
PPff
Pff
Pff
令：
fff
ffffff
PP
nff
E
nEn
n
E
2
0
2
00
0
0
222
,1
已不是好的方向。
个方向，因为保持原来的如果：
浙江大学研究生学位课程
《实用数值计算方法,121
4.7.2
因为下列两个原因之一成立：
a) Pn-P0方向的下降主要不是因为?f.
b) Pn-P0方向上二阶导数很大，这表明在
Pn附近有可能有极小点。
xf
0f
f? nf1f
Ef0P
nP
EP
1P
图 4.41 函数变化的影响浙江大学研究生学位课程
《实用数值计算方法,122
4.7.2
图 4.42 修正 Powell算法框图：
000000,0,,PffkeuP ii及置初值
k
i
k
i
k
i
k
i
k
i
k
i
k
i
k
i
k
i
k
i
k
i
uPP
uPfuPf
Pni
1
11 m in
,,2,1
使：
和进行一维搜索，确定对?
knEknnkknkn PffPffPPP 101,2 及计算
kikinikrkr PfPfPfPfffr 111 m a x,使和求
fE?f0
fffffffff EnEn 20200 22
kiki uunrinr 11,, 置时，对当?
k
n
k
n
k
n
k
k
n
k
n
k
n
k
n
k
n
k
i
kk
n
kk
n
k
n
uPP
uPfuPf
PPPPu
10
1
100
m in
,
并置使：
并确定置
kPff 00?求收敛准则 1kk
P*= Pkn,计算结束 Y
N
Y
Y N
N
浙江大学研究生学位课程
《实用数值计算方法,123
4.7.2
010.0
205.0
000.1
200.1
99.0
995.0
1
0
1
21
872.152.2421.20
)21.20980.22.24(872.15980.322.242
2.24872.15
1
21.2099.31.24
872.15
980.0
790.0
000.1
200.1
990.0
995.0
22
980.3,990.0,99951.0
990.3,000.1,995.0
,
2.24,0.1,2.1
1100
0
0
0
2
1
2
0
2
1
1
2
2
0
0
10
0
3
0
0
2
0
3
0
2
0
2
0
2
0
1
0
1
0
1
2
0
21
0
1
00
2
1
2
2
12
PPu
uu
r
nr
ff
r
PfPff
Pff
PPP
PfP
u
PfP
u
eueu
PfP
xf
R os e nbr oc k
E
E
T
T
T
计算前移一位：搜索方向自因且因所以而一维搜索得：沿一维搜索得：沿取搜索方向此时取函数例，对
浙江大学研究生学位课程
《实用数值计算方法,124
4.7.2
计算结果表作一维搜索得沿所以
8.4
990.0,990.0
04 88.0
999.0
206.01021.4
1
0
1
2
1
2
20
0
0
2
T
Pu
u
PP
k (u
1
k
)
T
(U
2
k
)
T
P
k
T
f( P
k
)
1 ( 0,1) ( 0.9 99,- 0.0 48 8)
P
0
1
( - 0.9 90,0,99 0)
P
1
1
( - 0.9 90,0,99 0)
P
2
1
( - 0.9 84,0,97 9)
3.9 69
3.9 59
3.9 48
2 ( 0,1) ( 0.4 53,- 0.8 92 )
P
0
2
( - 0.7 61,0,54 0)
P
0
1
( - 0.7 61,0,57 9)
P
0
1
( - 0.7 02,0,46 2)
3.2 57
3.1 01
2.9 86
3 ( 0.4 53,- 0.8 92 ) ( 0.6 08,- 0.7 44 )
P
0
3
( - 0.5 03,0,20 3)
P
1
3
( - 0.5 38,0,27 3)
P
2
3
( - 0.4 66,0,17 8)
2.5 10
2.3 96
2.3 01
2,39 6
5.05.0? 0.1
0.1
1?
2?
图 4.43 计算结果图示
P*
浙江大学研究生学位课程
《实用数值计算方法,125
4.8 方法的选择与总结
4.8.1 方法的选择
1,原则：
（ 1） 有效性
（２） 运算量
（３） 存储量
2,非线性代数方程
（１） 二分法具有良好的有效性
（２） 二次插值和有理插值运算量少
（３） 一般采用组合方法浙江大学研究生学位课程
《实用数值计算方法,126
4.8.1
3,非线性方程组
（１） 一般采用最优化方法
（２） 对于无梯度（或不易求梯度）问题，
一般不用ＣＧ方法，因为稳定性太差。
用有限差商近似导数不是好的选择。
但是当问题很大时（ n?200）由于存贮的限制，ＰＯＷ方法和ＶＭ方法不能用时，只能考虑ＣＧ方法。
对小问题（ 2? n? 10）,选择
ＰＯＷ方法或ＶＭ方法（差商近似导数）均可考虑。有效性依赖于问题。
浙江大学研究生学位课程
《实用数值计算方法,127
4.8.1
更要使用精确的梯度。时病态而梯度时，要利用梯度。
精确在计算量不太大能得到对于有梯度问题方法较合适。
没有连续的梯度，则若比较可靠。
方法一般大问题方法更好。对于性态差则选对于中等问题
,
3
,20050
,5010
xf
P O W
xf
VMn
VM
n
浙江大学研究生学位课程
《实用数值计算方法,128
4.8.1
艺术。
它也是一种方法强烈依赖于问题，
用，选择有几种组合方法可以利
。方法要求梯度，存储
。方法不用求导数，存储存贮量大度，并且而且稳定。但它要求梯方法最有效就方法本身来说，
方法。时，选当或时，当较好。时，当
5
.
4
150
15050
502
2
2
nOCG
nOP O W
nO
VM
CGn
VMCGn
VMn
浙江大学研究生学位课程
《实用数值计算方法,129
4.8.2 算法思想小结
1.迭代法，而不是解析法
2.线性化，极值化方法
3.降维法
4.下降法
5.插值逼近法
6.组合法
7.梯度方向共轭方向改变度量浙江大学研究生学位课程
《实用数值计算方法,130
第四章 习 题
.0,
,,2,1
);
)
,,2,1.3
,
2
1
,
,.2
10)),
10)),
)
,)
)
,)
,126.1
21
21
21
4
3
2
21
2
21
2
3
1
x
Anihx
iiDD
iA
nihnnA
x
xxJxxFxxFxF
T ay lor
F
iviii
iii
fB r e ntiv
ffN e w t oniii
fii
ffi
exxfxxxf
i
i
TT
x
则共轭与是正定的，且Ａ
如果为对角阵ＡＰ使得Ｐ
试找一个矩阵Ｐ，共轭的向量组，是阶对称矩阵，是设试证明之。
处的值。这里上横线表示在点展开式为的点关于两个变量的非线性函数取
，取精度控制问题的根；方法来求用的一个实根；法分别计算用的根；求线性插值法用割线法的一个实根；用二分法分别计算设
Ｔ
浙江大学研究生学位课程
《实用数值计算方法,131
T
kk
T
k
k
T
kkkk
kk
PxfP ow e l l
y
zx
yz
yx
xf
xFD F P
xxxxfxfxF
xxf
xxxf
gHg
HggHx
HH
D F P
xfxfx
xf
xfxfxxLx
c
ccxfxf
xf
0.2,0.1,0.0
2e x p
2
1
s i n
1
1
.7
2
1
2
1
m i n
0
0.6
)(.5
0)4(
)3(
,0)2(;04.0,02.0,01.0,0,01.0,02.0,04.0,2.0,1
,)1(
2
1
3
1
.4
0
2
2
2
1
2
21
2
2
2
1
12
211
1
000
2
2
3
1
的极大点值，取方法求试用设的极小值点。方法分别求试用共轭梯度法和问题的求解可化为以下极值方程组条件下式满足拟牛顿方程在变尺度法中，试证明的极值点。的稳定点，是否为是否为区域中不为有界凸；
为有界凸，那些举例说明在哪些区域中试绘出水平集设取以下值：的等高线试绘出设
《实用数值计算方法,1
第四章 非线性方程和非性方程组的解法
4.1 非线性方程的解法
4.2 非线性方程组的 线性化解法
4.3 非线性方程组的 极值求解法
4.4 最速下降法
4.5 共轭梯度法
4.6 牛顿过程及变度量法
4.7 直接法
4.8 方法的选择与总结浙江大学研究生学位课程
《实用数值计算方法,2
１,非线性方程的解法
２,非线性方程组的 线性化解法
－－牛顿迭代法
３,非线性方程组的 极值求解法
－－最速下降法 | 单纯形法
－－共轭梯度法 | Powell 方法
－－变尺度法 |
（可变矩阵方法） | 直接法
DFP 方法 |
浙江大学研究生学位课程
《实用数值计算方法,3
４,1 引言在科学研究中，常常会遇到非线性方程或非线性方程组的问题。例如解方程或一般的，我们记非线性方程为
14024503510 234 xxxx
240
2
s i n
xe x?
340xf
浙江大学研究生学位课程
《实用数值计算方法,4
4.1
非线性方程组的一般形式是：
0,,,
0,,,
0,,,
21
212
211
nn
n
n
xxxf
xxxf
xxxf
其中 fi（ i=1,2,…,n ） 是 n维实空间Ｒ n 上的实值函数。用向量形式表示：
这里 均是 n维向量。为了方便计，还是用 分别表示上述向量。
简记为：
440xf
0,,xf
0,,xf
0?xf
浙江大学研究生学位课程
《实用数值计算方法,5
4.1
c a
d
c a
d
b
3axy
dcxy 3
2axy
dcxy 2
图 4.1 非线性方程求根示意图浙江大学研究生学位课程
《实用数值计算方法,6
4.1
方程的解亦称方程的根或函数的零点。
根可能是实数或复数。
若 则 称为单根；
若而,则 称为 k 重根。
常见的求解问题有两种,
(1) 要求定出在给定范围内的 某个解 。
(2) 要求定出在给定范围内的 全部解 。
非线性问题，除少数情况外，一般不能不利用公式求解。而 要采用某种迭代解法 。
即构造出一近似值序列逼近真解 。
,0,0 ' ff?
01' kfff?
0kf
n,,,10
浙江大学研究生学位课程
《实用数值计算方法,7
4.1
迭代过程的 收敛性 一般 与初值 的选取和 方程的性态 有关，某些解法仅与初值有关。
收敛速度 一般由 迭代方法 所决定，方程的性态也会起一些作用。
本章主要介绍非线性方程组的解法,
而方程的解法用较少的篇幅在 4.2中扼要介绍。
解非线性方程和方程组有很大区别 。后者要 困难得多 。主要的区别在于一维情形可以找到一个根的范围，然后缩小，最终找到根。而 多维情况则很难确定根的存在 。
直到你求得它的解。
浙江大学研究生学位课程
《实用数值计算方法,8
4.2 非线性方程的解法
4.2.1 二分法对于连续函数,如果在和 处异号：
则 在 内至少有一个根。
xf
ax? bx 0 bfaf
xfba,
同号与否。与取决于代替前一步的或的方法，称二分法。用减小一倍，即二分每步使长度的解。近似作为用足够小时，。当区间当＝０时已找到解
，并保持逐步缩小区间
2
,
2
,
,
2
,
,
02
,
0,
ba
f
afba
ba
a
b
ba
ba
ba
xfba
ba
bfafba
浙江大学研究生学位课程
《实用数值计算方法,9
4.2.1
用图来表示这个过程：
０
y
x
a ba b
a b
时零点。
、只能求实函数的一个
、方法稳定，只要求
、收敛速度慢，线性。
3
,
2
1
0
bacxf?
确定根所在的范围［ a,b］ 对有的函数也是一件困难的事。所幸的是，在实际应用中，根据其物理或工程的背景，在绝大部分场合是不困难的。对给定的函数也有确定范围的方法。
图 4.2 二分法方程求根浙江大学研究生学位课程
《实用数值计算方法,10
a
b
ba
x1
x1 x2 x3dcfc
a
b
4.2.1
图 4.3 寻找隔根区间示意 1
浙江大学研究生学位课程
《实用数值计算方法,11
xc 1sin
cxd?1
a c
b
4.2.1
图 4.4 寻找隔根区间示意 2
图 4.5 寻找隔根区间示意 3
浙江大学研究生学位课程
《实用数值计算方法,12
例如，在［ a,b］ 之间寻找 f(x) 可能有的根可以用等分试探法：
a b
4.2.1
图 4.6 等分试探法寻找隔根区间示意浙江大学研究生学位课程
《实用数值计算方法,13
用二分法求函数 FUNC位于（ x1,x2） 之间的根，准确性为?XACC。
FUNCTION RTBIS (FUNC,X1,X2,XACC)
PARAMETER (JMAX=40)
FMID=FUNC(X2)
F=FUNC(X1)
IF (F*FMID.GE.0.) PAUSE '函数 FUNC在 x1,x2处不异号 '
IF (F.LT.0.) THEN
RTIBIS=X1
DX=X2-X1
ELSE
RTBIS=X2
DX=X1-X2
ENDIF
DO 11 J=1,JMAX
DX=DX*0.5
XMID=RTBIS+DX
FMID=FUNC(XMID)
IF (FMID.LE.0.) RTBIS=XMID
IF (ABS(DX),LT,XACC,OR,FMID,EQ,0.) RETURN
11 CONTINUE
PAUSE '迭代次数越界 '
END
4.2.1
浙江大学研究生学位课程
《实用数值计算方法,14
FUNCTION FF(X)
FF = X*X + 2.5*X + 0.5+SIN(X)
END
PROGRAM ROOTFIND
EXTERNAL FF
X1=-1.0
X2=0.0
ROOT=RTBIS(FF,X1,X2,1.0E-5)
PRINT *,'方程在（ -1,0）区间内有一个根,X=',ROOT
STOP
END
内的一个根解题示例。，在区间求
01
)s i n (5.05.2,2
xxxxf
4.2.1
浙江大学研究生学位课程
《实用数值计算方法,15
4.2.2 线性插值法 （又称弦位法）
为止。逼近解如此反复，直到充分
，重复上述过程得到
，代替似值。用的一个新的近为
：的零点，并记为求构造一线性函数，通过且
。，的两个近似解的解设
４
１３
３
３
１
２１
3
12
12
22
2
12
12
2
221
2211
,,
,
0
ff
f
xL
x
ff
fxL
ff
ffff
xf
x
f(x)
2?
4?
1?
3?
图 4.7 Secant Method
浙江大学研究生学位课程
《实用数值计算方法,16
4.2.2
c
c
3
3
23
323
设迭代控制：
21
2
3
3
3
,
0
1
，则当附近在零点如果程是发散的。当超过这个数时认为过
，迭代次数故一般提供一个最多的收敛的，由于有时这个过程是不
。作为解时认为过程收敛，或满足。则迭代过程如果一般取数。为绝对或相对误差控制其中
Cxf
k
f
C
浙江大学研究生学位课程
《实用数值计算方法,17
4.2.2
降低了收敛速度。
，但是却法增加了收敛的可能性
。简称个修改后的方法叫做
。。这定包含了解最近得到的。但它们一不一定是，解使它所保留的两个近似修正一下这个算法，的原因之一。我们如果敛。。这也是不能保证收不总是包含解之间并，的近似值解两个最近的是所保留的线性插值法的一个缺点阶。即超线性收敛。其收敛速度为的。时，线性插值法是收敛充分接近于
F P M
F P MM e ht odP os it ionF al s e,
618.1
21
21
浙江大学研究生学位课程
《实用数值计算方法,18
4.2.2
收敛还要慢。
插值法比二分法可以举出例子说明线性
。。根必须包含，值法的初始所示。图解的迭代过程如法及近似
21
8.4
FPM
FPM
f(x)
x
1
4
3
2
图 4.8 线性插值法求根示意浙江大学研究生学位课程
《实用数值计算方法,19
4.2.2
f(x)
x
1
3 4 5
图 4.9 线性插值法发散示例浙江大学研究生学位课程
《实用数值计算方法,20
4.2.3 Newton 法
'
1112
1
'
1
1
''
1
11
'
0
0
ff
xL
fxfxL
ff
ff
xfxf
得令作记：
存在。附近在解设
F(x)
x
2? 1?
11,fx
图 4.10 Newton 法示意浙江大学研究生学位课程
《实用数值计算方法,21
4.2.3
。故求弦位法每迭代一次只需求值。必须对存在
：法的收敛阶为
k
kk
k
k
k
k
fa
ff
fkf
c
e
e
N e w t o n
.
,3
,2,102
0lim
21
'
''
1
F(x)
2? 1?
x
11,f?0'2?f
图 4.11 导数变化对算法的影响浙江大学研究生学位课程
《实用数值计算方法,22
每次函数求值相当的收敛阶为：
b,求 fk' 有时工作量大，甚至不可能。
(4) 选用收敛域较大的方法（如二分法）
先进行迭代，然后再用 Newton法。
－－组合方法。
4.2.4 二次插值法设 f(x)=0 的三个近似解及函数值构造二次函数 g(y)使得：
。332211,,,,,fff
414.12? 618.1?
浙江大学研究生学位课程
《实用数值计算方法,23
4.2.4
PQX
y
ffff
fyfy
ffff
fyfy
ffff
fyfy
ygx
L agr ang e
ifgx
ii
则求新的近似根，令插值：利用
,0
3,2,1
1232
213
3121
132
2313
311
浙江大学研究生学位课程
《实用数值计算方法,24
4.2.4
1
3
3
2
2
1
21
3
3
13
2
2
32
1
1
111
f
f
T
f
f
S
f
f
R
ff
f
ff
f
ff
f
Q
TSRP
其中：
F(x)
x
g(x)
f(x)
1?
4?
3? 2?
图 4.12 二次插值法求根示意浙江大学研究生学位课程
《实用数值计算方法,25
4.2.4
(1) 要有三个初始值
(2) 当 。且收敛速度是 1.84 阶。（单根）
二重根的收敛阶是 1.23。
(3)
(4) 发生超射、越界。
21111,,,,且
时收敛,03Cxf?
不同值。
不同值。
3,2,1
3,2,1
if
i
i
i?
方法名称 收敛速度 有效指数 重根情况二分法 1 1 1,偶重失败线性插值法 1,6 1 8 1,6 1 8 1
牛顿法 2 1,4 1 4 1
二次插值法 1,8 4 1,8 4 二重时 1,2 3
表 4.1 各种插值方法的比较浙江大学研究生学位课程
《实用数值计算方法,26
4.2.5 组合方法 （ Brent Method）
能否有一种方法综合上述方法的优点呢？ Brent 做了一些工作。
Brent 把二分法和二次插值法结合起来 。
（１）一定收敛。
（２）收敛速度至少线性。
（３）在解附近足够光滑时，收敛速度将是 1.84 或 1.23。
有关多项式的求根还有一些特殊方法。
浙江大学研究生学位课程
《实用数值计算方法,27
4.3 非线性方程组及牛顿法非线性方程组的向量形式可表示为
Tn
T
n
x
ffff
xf
,,,
,,,
540
21
21
其中解法：
1,几乎不可能用直接法
2,线性化，迭代逼近。 牛顿法
3,最优化，求函数极小值。下降法。
例如，
求 的极小值点。
最速下降法,共轭梯度法,变尺度方法 。
2xfx i
浙江大学研究生学位课程
《实用数值计算方法,28
4.3.1 牛顿法为方便计，用二维情形来讨论。
640,
0,
212
211?
f
f
假定（ 4-6）的解,0,,0
21 xCffx
。且存在一阶偏导数。设?,0 xx k
kkkxx 2121,,,这里，
作线性函数 （ Taylor 展开，取一阶精度 ）
74
22
2
2
11
1
2
22
22
2
1
11
1
1
11
k
x
k
x
k
k
x
k
x
k
kk
kk
ff
xfxl
ff
xfxl
浙江大学研究生学位课程
《实用数值计算方法,29
4.3.1
在 内用线性函数（ 4-7）代替非线性方程组 (4-6)中的 f1,f2,从而
,0?x
kkkk
kkk
x
kkk
x
xf
ff
xf
ff
k
x
k
k
x
k
222111
22
2
2
1
2
2
12
2
1
1
1
1
,
这里，
如果在 中矩阵 （称 Jacobi矩阵 ）,0?x
84
2
2
1
2
2
1
1
1
kx
k
ff
ff
xDf
非奇异，则可解出。
浙江大学研究生学位课程
《实用数值计算方法,30
4.3.1
94
2
11
2
1?
k
k
k
xk
k
xf
xfDf
矩阵。从而称为向量函数的 J a c o b ixDf
kkk
kkk
22
1
2
11
1
1
10411 kk
x
kk xfDfxx
于是
k
x
n
nnn
n
n
k
fff
fff
fff
xDf
n
21
2
2
2
1
2
1
2
1
1
1
64
维情形：
的牛顿迭代公式非线性方程组浙江大学研究生学位课程
《实用数值计算方法,31
4.3.1
79.0
73.0
0.53.4
6.10.3
12.8
1
79.0
73.0
0.33.4
6.10.5
0.33.4
6.10.5
23,34
122,28
79.0,
73.0,
9.0,4.0
0332,
0224,
1
1
2
1
1
'
2
'
2
'
1
'
10
21
'
221
'
2
21
'
121
'
1
0
2
0
12
0
2
0
11
0
2
221
2
1212
221
2
2
2
1211
0
21
21
21
21
因此故再算解：设初始近似解为的近似解例：用牛顿法求方程组
x
T
ff
ff
xDf
ff
ff
f
f
x
f
f
浙江大学研究生学位课程
《实用数值计算方法,32
4.3.1
0.0
00000 0.1,50000 0.0
00013 8.0,00017 4.0
99986 2.0,50017 4.0
00013 8.0
01382 6.0
07039 2.0
08478 4.0
524.3056.5
028.2112.6
524.3056.5
028.2112.6
07039 2.0,08478 4.0,
000.1,514.0
100.0,114.0
3
2
3
1
223
2
112
1
1
2
1
1
1
11
1
1
2
1
1
001
0
xfxf
xxx
x
xxx
xf
xf
xDfx
xDf
xfxf
xxx
x
T
T
T
T
T
T
T
且故再重复做一次，得故重复上述过程，
故得：
浙江大学研究生学位课程
《实用数值计算方法,33
迭代式。
的改进为克服上述三个缺点，
的逆矩阵工作量大。计算可能出现病态。
很小。初始要求高，即
。收敛。且收敛速度阶为迭代式充分小，则且初值非奇。矩阵当
104
3
2
2104
,,0
,1,01
0
k
k
k
xDf
xDf
xx
kxDfJ ac obi
4.3.2 牛顿法的改进改进１ 带松弛因子的牛顿迭代格式 改善了对初始值近似程度的要求。
浙江大学研究生学位课程
《实用数值计算方法,34
4.3.2
(4-10) 中引入了松弛因子,有k?
二次插值法求解。它可以用黄金分割法或极值问题。
是一维的求取时，按即是牛顿法。收敛最快收敛。时当或的选取满足而
1241243
,12
114021
124m i n
114,2,1,0
1
1
1
1
k
k
k
kkk
kk
k
kkkkk
xfxDfxf
xfxf
k
xfxDfxx
浙江大学研究生学位课程
《实用数值计算方法,35
4.3.2
满足以上条件。
上的凸函数，则是显然，若
，当
，当内满足：在设内的极小值。在法（优选法）求函数
bax
xxxaxx
bxxxxx
bax
xba
x
,
,
,,
618.01
2112
2121
a b a?x?x b
图 4.13 凸函数示例浙江大学研究生学位课程
《实用数值计算方法,36
4.3.2
继续进行。否则，令若成立，则判别：
显然，
否则取取则若计算两个实验点
11
11
11
11
11
11
11
,
2
1
618.0
,
618.0
382.0
bbaa
abx
ab
abab
bax
bbca
dbaa
dc
abad
abac
浙江大学研究生学位课程
《实用数值计算方法,37
4.3.2
1
54
3
2
a c d b
x
2
15
61803.0
,1
1
,1
2
ww
ww
w
ab
ad
w
w
w
ad
ac
w
ab
ac
解得故从而则若根据等比收缩原则；
1a 1c 1d 1b
图 4.14 0.618法搜索极小点过程浙江大学研究生学位课程
《实用数值计算方法,38
4.3.2
(2) 二次插值法求一维函数极小值：
1
3
2
4
5
a cb
3,2,1
2,4,1
afbfcbcfbfab
afbfcbcfbfab
bx
x
cfcbfbafa
22
2
1
,,,,,
坐标：抛物线的极小点的通过图 4.15 二次插值法进行一维极小点搜索浙江大学研究生学位课程
《实用数值计算方法,39
4.3.2
改进２,带阻尼因子的牛顿迭代格式克服了矩阵 的奇异或病态。 (4-10)中引入阻尼因子,
kxDf
k?
,2,1,0
13411
k
xfIxDfxx kkkkk?
的选取可以在满足 (4-12)的前提下取很大值。
（１）改善对初值的要求
（２）当 ＝０时为牛顿法，收敛最快。
（３）为满足 (4-12)，实际上需要多次试算，
工作量大。
改进 3,修正牛顿法尽可能减少矩阵求逆次数。
k?
k?
浙江大学研究生学位课程
《实用数值计算方法,40
4.3.2
一种简单的办法 是每次使用同一个 Jacobi
矩阵的逆。
2,1,0101 kxDfxDf k令但大大影响收敛速度。
另一种办法是若干次迭代后求一个矩阵逆：
144,1,0
,,1
,1
1,
1
1,,
0,
kxx
mixfxDfxx
xx
mkk
ikkikik
kk
令它减少了矩阵求逆，又保证了收敛。
换一个角度看，如果说它的求逆次数与牛顿法相同 (k次 )，则它的收敛阶为 m+1。
浙江大学研究生学位课程
《实用数值计算方法,41
4.3.2
1,
1
1,2,1
0,
1
0,1,
0,
kkkkk
kkkk
kk
xfxDfxxx
xfxDfxx
xx
或
154,1,0
11
1
k
xfxDfxfxfxDfxx kkkkkkk
迭代格式 (4-15)具有 ３ 阶收敛速度。
对一维情况,Newton法在几何上表现为 m步迭代过程保持斜率 f'(xk) 不变。
如图 4.16：
f(x)
x0
0,kx
kx
1,kx2,kx
1?kx
1,1?kx
2,1?kx
2?kx
图 4.16 m=2的迭代效果作为特例，取 m=2:
浙江大学研究生学位课程
《实用数值计算方法,42
4.3.2
非线性代数方程组求解问题
1,Newton--Raphson 迭代法
2,极值化求解。
问题的转化,
xfxfxf
xxxf
nixxxf
i
n
x
ni
0
,,,m i n
,,2,10,,,
21
21
是一个非负函数，且设无约束最优化问题?
nibxaDx
xxxx
xxxfxf
xxxfxf
iii
T
n
n
i
ni
n
i
ni
,,2,1,
,,,
,,,
,,,
21
1
2
21
1
21
这里，
例：
浙江大学研究生学位课程
《实用数值计算方法,43
4.4 最速下降法
方程组的主要方法。
方法是解非线性最优化极值化
4.4.1 极值化求解
164
,,2,10,,,
1
2
21
n
i
i
ni
xfxf
nixxxf
等价于求解
的 零极值点 。
求解 (4-16)的极值点也是一个无约束的最优化问题。
浙江大学研究生学位课程
《实用数值计算方法,44
4.4.1
求解最优化问题，通常采用下降法 。 下降法一般描述如下：
增加最快的方向。显然：梯度方向是函数的梯度。称为其中：
有即的初始估计。是点。是无约束问题局部极小设
xf
x
xf
x
xf
xf
xf
xfxf
xx
x
T
n
Dx
,,
0
1
0
m i n
浙江大学研究生学位课程
《实用数值计算方法,45
4.4.1
下降法的迭代步骤
，迭代结束。置
，转置则转且若计算
，以保证选择步长因子
，使确定下降的搜索方向
1
21
11
1
:.6
11:.5
6
.4
.3
0.2
0),(
.1
k
kk
k
kkkk
kkkk
k
kk
k
xx
kk
xfxf
xf
hxx
xfhxf
hxf
h
浙江大学研究生学位课程
《实用数值计算方法,46
4.4.1
最速下降法 取因此
,kk xfh
,2,1,0
1
k
xfxx kkkk?
kkk
k
kk
kkkk
k
k
xfxf
ii
xfxfxf
i
0
m i n:
2
1
0
通过一维搜索确定
，再检验。不成立时，让检验
，为给定常数取有为步长因子。它的取法其中浙江大学研究生学位课程
《实用数值计算方法,47
4.4.1
等高线图：
f(x)=Ci
f(x1,x2)=Ci
x
0x
1x
0h
kx
1h
1?kx
kh
k?
k
k
kkk
k
k
kk
kkk
h
hxx
h
hxf
hh
1
m i n其大小应满足方向步长，为沿为反梯度方向，
xf
x
kxxx
f
kx
xf
1?
2?
kkkx 21,
kxf?
kxx
f
1?
kxx
f
2?
图 4.17 等高线图 4.18 偏导数示意浙江大学研究生学位课程
《实用数值计算方法,48
xfxf
xf
k
k
k
0lim
单调下降这样，
4.4.2 讨论与改进优点：
１,程序简单，每步迭代计算量少，存储省。
２,对于不太好的初始点 x0，往往也能收敛。
缺点,
最速下降法是名不符实的，一般来说，
它只有线性的收敛速度。
浙江大学研究生学位课程
《实用数值计算方法,49
4.4.2
收敛很慢。
出现锯齿形。对于一族扁椭圆，迭代则可以证明：若好。
这个方向并非最最快的方向，从整体看只是局部下降得究其原因，
ii
xfxfi
xfxfxf
xf
k
T
k
kkk
k
0
,min
1
1
0x
1x
2x kx
1?kx
x?
图 4.19 锯齿形搜索路径情况浙江大学研究生学位课程
《实用数值计算方法,50
4.4.2
成立。序列速下降法生成的使用精确一维搜索的最对正定二次函数或从而故而所以则证明：令
k
TT
k
T
k
k
T
k
k
T
k
k
T
k
kxx
n
kxxkxxxx
xx
kkk
kk
x
cxbAxxxf
xfxf
xfxf
hxf
hxf
h
f
h
f
h
f
d
xdf
d
xdf
hxfxf
hxf
nk
kkk
k
2
1
0
0
0
0
min
1
1
1
1
21
0
1
1
21111
1
浙江大学研究生学位课程
《实用数值计算方法,51
4.4.2
法收敛慢。严重。故此时最速下降偏离指向极小点方向椭圆扁长，负梯度方向时，的椭圆。当离心率很大等高线是离心率为为例：
中的正定二次函数以偏长的情形。几何上可解释为等高线
，收敛速度越慢。越接近于时，当的接近程度。和可见，收敛速度依赖于的最小、最大特征值。分别为这里其中：
b
a
ba
ba
q
b
a
A
ba
xf
R
cxf
qMm
mM
AMm
xfxf
m
c
mM
mM
q
cqxx
xfxfqxfxf
k
k
k
k
2
22
22
2
2
2
2
2
2
2
1
2
2
0
2
2
0
1
0
0
1
2
1
:
1
,
1
浙江大学研究生学位课程
《实用数值计算方法,52
4.4.2
一般来说，开始几步下降速度较快，但越靠近极小值点越慢。
改进,
e ls exf
iikifxx
h
khxx
P ar
N e w t on
k
kk
k
kkkk
,2,1,3
{
,2,1,0
t a n.2
.1
2
1
其中法法。后改用前几步用最速下降法，
浙江大学研究生学位课程
《实用数值计算方法,53
4.4.2
最速下降法算法框图,
0,0误差控制取初值 nRx
00 xfg
00,0 ghk
kkk
kkkk
hxfxf
hxx
01
1
min
:求一维极值得
11 kk xfg
11 kk gh
1kk
停yes
0xx解停yes
1 kxx解图 4.20 最速下降法算法框图浙江大学研究生学位课程
《实用数值计算方法,54
4.4.2
表数据：重复以上过程，可得下故求一维极值得设解：
用最速下降法求取例：设
T
Rx
T
xfxx
xfxfx
xfxf
xfx
xf
17
38
,
17
26
17
5
261 8 03 0 6
6
12
,
23
m i n,4,2
2
2
1
2
3
0001
0
2
00
0
12
21
0
121
2
2
2
1
2
k
0 -2 4
1 1,5 2 9 4 1 2,2 3 5 2 9
2 0,9 4 1 7 7 0 1,0 5 8 8 2
3 1,0 1 0 3 8 1,0 2 4 2 2
4 0,9 9 8 8 4 7 1,0 0 1 1 5
5 1,0 0 0 2 0 1,0 0 0 4 8
6 0,9 9 9 9 7 7 1,0 0 0 0 2
7 1,0 0 0 0 0 1,0 0 0 0 1
8 1,0 0 0 0 0 1,0 0 0 0 0
1? 2? 2
1?
0x
1x
2x
3x
x
图 4.21 搜索路径示意浙江大学研究生学位课程
《实用数值计算方法,55
4.5 共轭梯度法
（ Conjugate Gradient Methods）
4.5.1 共轭方向
A
B
D
C
O
0h
0h
0
0
||
,
hCDOCD
hBA
D
点且过的两个切点给定方向椭圆中心
为共轭方向。与为共轭直径。与则
CDAB
CDAB
图 4.22 共轭方向浙江大学研究生学位课程
《实用数值计算方法,56
4.5.1
共轭。关于这种关系称则有那么若令方向由下式决定并且及两个初始点给定方向其中维二次函数引理：
对称正定为凸函数
：时的二次函数可表示为
“共轭”关系：对二次函数来讨论这种
Ahh
Ahhxxh
hxfxf
hxfxf
hxxhxx
xxh
AA
cxbAxxxfn
AxxAxf
cxbAxx
cbb
aa
aa
cbb
aaaxf
n
T
T
TT
T
TT
,,
0,
m i n
m i n
,
,,
0
2
1
0
2
1
2
1
2
1
2
1
2
10
01111
00
0
1
00
0
1
01010001
000
2
1
21
2
1
2212
1211
21
2211
2
2222112
2
111
浙江大学研究生学位课程
《实用数值计算方法,57
4.5.1
0
0
0
0
0
2
1
2
1
2
1
01011
011
011
01
01
11
1
111
2211
2211
2
22
2
222
112112
2
111
AhhAhxx
hxxA
hxfxf
hxf
hxf
bAx
b
b
aa
aa
xf
baaa
f
cbbb
a
aa
aaaxf
T
T
T
T
T
T
nnnnn
n
inniii
i
nn
nnn
nn
nn
所以故又故所以证明：
浙江大学研究生学位课程
《实用数值计算方法,58
4.5.1
0h 0h
1x
1x
1h
0x
0x
cbxAxxxf TT 21
0,?x
xf
2?
1?
图 4.23 二次函数的共轭方向图 4.24 二次函数浙江大学研究生学位课程
《实用数值计算方法,59
4.5.1
0)(
0
,,2,11
,,2,1,
,,2,1,
,,,
,,1,;02
,01
,
,,,
2211
2211
21
21
21
21
mm
T
i
mm
i
i
i
m
j
T
i
T
nn
n
m
hhhAh
hhh
mih
mih
mihIA
Ahhh
mjijiAhh
Ahh
Ahh
ARRA
Rhhh
得事实上，由线性无关。：共轭向量组性质具有以下性质：共轭向量组是共轭的特殊情况。交的向量。因此，正交是一组正时，显然，当共轭的向量组。是则称若共轭的；是和则称向量若为对称正定。
定义：
浙江大学研究生学位课程
《实用数值计算方法,60
4.5.1
bAxxf
nkhxf
fxxxf
hxfxf
hhh
nih
mi
miAhhA
miAhh
mih
k
T
k
nn
kkk
ni
i
i
i
T
i
i
T
ii
i
2
,,2,10
1
0
m i n
,,,
,,2,1.2
,,2,10
,,2,10
,,2,10
,,2,1,
1
11
0
1
2
一维搜索满足：证明：
为凸若和有为搜索方向的搜索方法向量共轭，则相继以设性质可知的正定性。即由共轭，故有因为
浙江大学研究生学位课程
《实用数值计算方法,61
4.5.1
毕为凸函数，故又设
，得由性质的共轭性。得及，由
.
01
,,2,10
3
,,2,121
1
1
111
111
1
1
111
xxf
xf
nj
hAhAhxf
hAhAhxf
hAhxf
hxf
nih
Ahxf
xxAxf
AxxfAxxf
n
n
j
T
jj
T
nn
T
j
j
T
nn
T
nn
T
n
j
T
nn
T
n
j
T
n
i
kkk
kkk
kkkk
浙江大学研究生学位课程
《实用数值计算方法,62
4.5.2 共轭梯度法 Conjugate Gradient Method
利用共轭方向，对二次型求极值问题可以得到 n步收敛的结果。
现在的问题是：
1.如何构造 n个共轭方向？
2.对一般的非线性函数 f(x)怎么办？
3.由于舍入误差等影响,n次迭代不收敛时怎么办？
如下：和定义向量序列为任意向量阶对称正定矩阵是设
ii
T
hg
g
bxAxxxf
nnA
0
2
1
浙江大学研究生学位课程
《实用数值计算方法,63
4.5.2
双正交化方法。
一般称其为共轭向量序列的方法。
和一是构造一正交向量序列故可以证明：
因此一共轭正交使选择
Sc hm idtG r am
nji
jihAh
jigg
hAh
Ahg
hAhAhg
Ahg
gg
Ahggg
AhAh
gg
hgh
Ahgg
hg
j
T
i
j
T
i
i
T
i
i
T
i
ii
T
iii
T
i
i
T
i
i
T
i
ii
T
iii
T
i
i
T
i
i
T
i
ii
iiii
iiii
184,174
194,0
0
0
184
0
0
0
,,
174
1
1
1
1
11
1
00
浙江大学研究生学位课程
《实用数值计算方法,64
4.5.2
毕而
，由事实上，
引理：
证明：
改写，把公式为尽可能不使用矩阵
i
T
i
i
T
i
i
T
i
iii
T
i
i
T
i
i
T
i
i
T
i
i
T
i
i
T
i
i
T
i
i
i
T
iii
T
iiiii
T
ii
T
i
i
T
iii
T
i
T
ii
T
i
iii
T
iii
T
i
iii
T
ii
T
i
i
T
ii
T
iii
T
i
i
T
iiii
T
i
i
T
i
i
T
ii
T
i
i
T
i
i
T
i
i
i
T
i
i
T
ii
i
T
i
i
T
i
i
Ahh
hg
Ahh
hhg
Ahg
gg
gg
gg
Ahh
Ahg
AhhAhgAhgggg
Ahggg
gghg
hghg
hgghg
AhgAhhAhg
AhhgAhh
hg
AhhAhg
Ahh
hg
gg
ggg
gg
gg
A
11
111
1
111
010101
2121111
1111
11
11
1
1111
174
0
0
204
184
浙江大学研究生学位课程
《实用数值计算方法,65
4.5.10
k
T
k
k
T
kk
k
T
k
k
T
k
k
kkkk
k
T
k
k
T
k
k
kkkk
ii
i
i
T
i
i
T
i
i
i
T
i
i
T
ii
i
T
i
i
T
i
i
gg
ggg
gg
gg
ghhgh
Ahh
hg
hxx
k
xfg
h
Ahh
hg
gg
ggg
gg
gg
1111
0011
1
1111
234
2,1,0
184174
224
214
共轭梯度法：
为时，下面的极值算法称当令是共轭的，并且构成的向量，由浙江大学研究生学位课程
《实用数值计算方法,66
4.5.2
kkk
kkkk
i
Ahg
bhxAg
g
xfghx
1
0000
1184
,
式：的第满足容易说明：这样定义的其中，初始近似为
0
0
min
min
1
1
1
k
T
k
k
T
k
kk
k
k
gg
xfxf
hxf
xf
即时，
的选取用一维极值当
方法。
式子时，叫做个取第方法，而方法或称为一个等式时，叫做取第中的当共轭梯度法
RPR ibi e r eP ol ak
RF
e v e sF le t c he r
k
k
2
Re
234
浙江大学研究生学位课程
《实用数值计算方法,67
4.5.2
共轭梯度法是从梯度向量出发构造共轭向量。
* 由于误差积累等因素，对二次型，迭代
n次也未能达到极小点。
* F-R方法和 P-R方法的区别在于它们对二次型是一样的。而对一般函数用 P-R方法可能更合适。
* 共轭梯度法具有二次收敛速度 。
那么对一般的函数的共轭梯度法又是怎样的呢？
浙江大学研究生学位课程
《实用数值计算方法,68
4.5.2
在极小值点附近进行二次逼近：
Axxbxc
xx
xx
f
x
x
f
Pfxf
T
ji
jiP
jii
iP
i
i
2
1
2
1
,
2
kkkkk
kxx
k
P
ji
ij
hxfhxf
f
xf
A
xx
f
A
PfbPfc
ji
0
''
2
min
:,
.234
244
我们采用一维搜索求避免求的二阶偏导数。为因此需要计算时要用到知，求由共轭梯度法其中浙江大学研究生学位课程
《实用数值计算方法,69
4.5.2
但是求导数?f(xk)是必须的。
另外，我们总假定 f(x)在极值点附近性质足够好，满足各种要求。
对一般函数 f(x)，共轭梯度法 (4-23)有限步收敛几乎是不可能的。如果迭代 k 步达到精度（ k?n）,则 xk就作为 x*的近似。
当经过 n步迭代仍不可能满足要求时，令再进行第二次循环。
但是，实际计算中，不一定迭代
k=n 步才进行“重置”。
nn xfgkxx 000 而浙江大学研究生学位课程
《实用数值计算方法,70
4.5.2
(1) 在极小点附近是一个高度偏心的二次函数。
则进行 （ m+n） 次迭代 （１?m<n） 就收敛了。而进行 k 次迭代 （ k? n） 就重置的话，有可能会不收敛。
(2) 在极小点附近或稍远处不是二次函数。
此时称“扭曲”现象。
则 留有非二次函数的痕迹，故可能对收敛很有害。此时最好重置。
kkh?
浙江大学研究生学位课程
《实用数值计算方法,71
4.5.2
共轭梯度法 Conjugate Gradient Methods
算法框图
0,0误差控制取初值 nRx
00 xfg
00,0 ghk
kkk kkkk hxfxf
hxx
01
1
min
:求一维极值得
00 xfg
nk?
kkkk
k
T
k
k
T
kk
k
T
k
k
T
k
k
hgh
gg
ggg
gg
gg
11
1111
1kk
10
10
k
kgg xx
停yes
0xx解
no
停
1 kxx解
yes
no
no
yes
图 4.25 共轭梯度法算法框图浙江大学研究生学位课程
《实用数值计算方法,72
(3) 如何判别是高度偏心的二次函数还是扭曲的函数 呢？
启发性的办法是：
对一般非二次函数，若 x0离 x*较远，
则迭代 n次不收敛时，就重置。但以后不再重置。
对既高度偏心，又严重扭曲的函数，
则经常性的重置是有好处的。
52102010
4110
1
2
1
2
2
2
12
4
1
2
1
22
12
xxxxxxxf
xxxxf
即：
函数例如：
浙江大学研究生学位课程
《实用数值计算方法,73
4.5.2
它在点（ 1,1）处有极小值 4.
其图象为：
1x
2x
图 4.26 函数等高线图浙江大学研究生学位课程
《实用数值计算方法,74
4.5.2
表 4.3 最速下降法计算结果
X
1
X
2
f X
1
X
2
f
-1,2 0 0
-0,9 9 3
-0,7 9 3
-0,6 6 3
-0,5 5 2
-0,3 8 8
-0,3 0 6
0,6 3 3
0,6 2 5
0,6 5 4
0,6 4 8
1,0 0 0
1,0 7 1
0,4 9 3
0,5 3 8
0,2 1 8
0,2 7 5
0,0 3 7
0,3 6 1
0,3 8 2
0,3 9 2
0,4 1 1
1 0,7 7 6
8,0 4 5
7,4 0 3
6,8 6 2
6,4 8 3
6,0 8 1
5,7 3 9
4,1 5 1
4,1 4 1
4,1 3 2
4,1 2 5
0,6 7 2
0,6 6 7
0,6 8 9
0,6 8 3
0,7 0 3
0,6 9 8
0,7 1 6
0,7 1 1
0,7 2 8
0,7 2 4
…
0,4 2 0
0,4 3 7
0,4 4 4
0,4 6 0
0,4 6 6
0,4 8 1
0,4 8 7
0,5 0 0
0,5 0 5
0,5 1 7
…
4,1 1 8
4,1 1 2
4,1 0 6
4,1 0 1
4,0 9 6
4,0 9 1
4,0 8 7
4,0 8 3
4,0 8 0
4,0 7 7
…
浙江大学研究生学位课程
《实用数值计算方法,75
4.5.2
表 4.4 各种重置循环的共轭梯度法计算结果
A B C
x
1
x
2
f x
1
x
2
f x
1
x
2
f
- 1,2 0 0
G -,9 9 3
-,6 5 7
-,4 0 9
-,2 4 1
-,1 1 2
-,0 0 3
0,0 1 0
,1 9 1
,2 8 7
,3 9 0
,5 0 4
,6 3 6
,7 9 2
,9 8 6
1,2 4 9
1,4 1 8
1,0 0 0
1,0 7 1
,2 7 5
-,0 7 3
-,2 2 7
-,3 0 2
-,3 3 5
-,3 4 2
-,3 2 7
-,2 9 0
-,2 2 6
-,1 2 5
,0 2 9
,2 6 7
,6 4 9
1,3 0 1
1,9 4 3
1 0,7 7 6
8,0 4 5
6,9 9 2
6,5 6 4
6,3 5 5
6,2 2 4
6,1 2 9
6,0 4 8
5,9 7 3
5,8 9 3
5,8 0 2
5,6 8 9
5,5 4 2
5,3 4 0
5,0 4 5
4,6 0 2
4,1 8 6
- 1,2 0 0
G -,9 9 3
-,6 5 7
-,4 0 9
-,2 4 1
G,0 5 9
,2 8 9
,5 8 2
,7 6 7
G,7 9 2
,9 2 8
,9 6 5
,9 6 9
G,9 6 9
1,0 0 0
1,0 0 0
1,0 0 0
1,0 7 1
,2 7 5
-,0 7 3
-,2 2 7
-,1 0 0
,0 0 8
,2 3 5
,6 2 8
,6 1 6
,8 3 4
,9 3 5
,9 3 7
,9 3 8
,9 9 8
,9 9 9
1 0,7 7 6
8,0 4 5
6,9 9 2
6,5 6 4
6,3 5 5
4,9 7 9
4,5 6 5
4,2 8 3
4,0 7 0
4,0 4 4
4,0 1 3
4,0 0 1
4,0 0 1
4,0 0 1
4,0 0 0
4,0 0 0
- 1,2 0 0
G -,9 9 3
-,6 5 7
G -,4 9
-,1 3 2
G,8 3 7
,8 3 3
G,8 4 2
,9 7 2
G,9 6 5
1,0 0 0
G 1,0 0 0
1,0 0 0
1,0 7 1
,2 7 5
,3 4 6
-,0 9 8
,6 8 1
,6 8 8
,6 9 4
,9 2 6
,9 3 0
,9 9 9
,9 9 9
1 0,7 7 6
8,0 4 5
6,9 9 2
6,3 3 2
5,4 1 6
4,0 3 0
4,0 2 8
4,0 2 7
4,0 0 4
4,0 0 1
4,0 0 0
4,0 0 0
浙江大学研究生学位课程
《实用数值计算方法,76
4.6 牛顿过程及变度量法
4.6.1 Newton--Raphson 迭代把函数 f(x)在第 k次近似解 xk 附近进行
Taylor展开：
xxf
xf
xxJxx
xxxfxfxf
kk
T
k
k
T
kk
之极小点：求记
2
1
浙江大学研究生学位课程
《实用数值计算方法,77
4.6.1
考查下例可能奇异。
收敛到鞍点。有些问题可能发散，或敛。是二次函数，则一步收若收敛阶为收敛快。
迭代格式。这就是即
k
kkkk
kkkk
kkkk
x
i
i
Jiv
iii
xfii
i
r aphs onN e w t on
xfJxx
xfxJxJ
xxJxfxf
ni
f
xf
.2
0
,,2,10
1
1
浙江大学研究生学位课程
《实用数值计算方法,78
4.6.1
稍有增加。出发的第一步，函数值从极小点支配。
的二次函数受到极小点，因为其附近敛更接近鞍点，但它却收虽比小点；受极小点影响收敛到极鞍点；在鞍点的影响下收敛到所示。见图出发的几条极小化路径方法分别从应用设
Civ
ACiii
Bii
Ai
CBAR aphoonN e w t on
xxxx
xxxxxxf
27.4
,,
44
2
9
2
22
2121
2
2
2
12
2
1
4
1
浙江大学研究生学位课程
《实用数值计算方法,79
4.6.1
A
C
B
1x
2x
图 4.27 初值对 Newton-Raphson 方法的影响浙江大学研究生学位课程
《实用数值计算方法,80
4.6.1
下降法避免收敛到极大点。
敛可能性。加快收敛速度和增加收其优点有：
极小化。使这里进是：这个方法一个有效的改一个鞍点是该函数的极值点为：
ii
i
xf
f
f
kk 1
493.1,611 7.0
513 4.0028.1,053.1
985 5.0854.3,941.1
kkkkk xfJxx 11?
浙江大学研究生学位课程
《实用数值计算方法,81
然而这个方法的致命弱点是要计算
Jk-1。 4.2提供的办法，即迭代若干次修改一次 Jk-1，是一种方案。但不是最好的。
4.6.2 变量的尺度变换为改变函数的偏心程度，从而改变极小化方法的收敛性质，采用变量替换是个很好的措施。
2
1
2
1
21
2
2
2
1
44
414 4
8414 4
x
x
x
x
xxxxxf
T
例：
浙江大学研究生学位课程
《实用数值计算方法,82
4.6.2
多。的极小化方法要稳定得求此的偏心程度小得多。因比的等高线图，显然和比较得：
作变换
xf
xfxf
xfxf
x
x
x
x
xxxx
xxfxf
x
x
x
x
T
~
~
~
~
~
1
6
1
6
1
1
~
~
~~
3
1
~~
~
,
~
~
~
~
2
1
0
0
12
1
2
1
2
1
21
2
2
2
1
21
2
1
2
1
浙江大学研究生学位课程
《实用数值计算方法,83
4.6.2
1x
2x
2~x
1~x图 4.28 函数进行尺度变换的效果浙江大学研究生学位课程
《实用数值计算方法,84
4.6.2
尺度变换 目的是把函数的偏心程度降到最低限度（它放大或缩小各个坐标），
但并不能完全消除偏心问题。
把尺度变换应用于各种算法，都有一定效果。
一般地
IATTT
A
xATTx
cBxAxx
nnT
xTx
T
TT
T
使是正定的，则若则二次项为考虑极小化二次函数阶矩阵。是非奇异的这里
~~
2
1
2
1
~
浙江大学研究生学位课程
《实用数值计算方法,85
4.6.2
即变换后的二次函数偏心率为０，它是圆。
它用最速下降法一步可以达到极小点。
现在希望直接处理原来的函数，而定义一个 算子。 用它产生通过极小点的向量。
考虑这样的Ｔ：
1
1
ATT
IATT
TAT
IATT
T
T
T
T
从 Newton--Raphson 过程
kkkkk xfJxx 11?
浙江大学研究生学位课程
《实用数值计算方法,86
4.6.2
变尺度法的基础。
的方法思想将是一种收敛很好量变换的不过由此引出的有关度甚至是奇异的。这是困难的。有时是正定的。实际上但是我们要求
。就可以显著减小偏心率或如果得到近似的因此我们不用求
，这个向量就是可知，对二次函数来说
k
k
T
k
k
T
kk
J
J
TTT
J
xfTTxfAh
1
1
1
,
,
浙江大学研究生学位课程
《实用数值计算方法,87
4.6.3 变尺度法
—— DFP方法
—— BFGS方法常用的度量是
通过极小点。对于正定二次函数，它记方法的搜索方向是：而方向用这种度量得最速下降
kkkk
kk
n
i
i
T
xfAxfJh
R aphs onN e w t on
xfh
xxxx
11
1
2
2
浙江大学研究生学位课程
《实用数值计算方法,88
kk
T
k
k
T
k
k
T
kkk
T
xfh
xxx
xf
xfxf
Oxfxf
xfxfxf
xOxxfxfxxf
而下降方向是量是故最速下降法采用的度对充分小的量最速下降法所采用的度
,
,
'''
2
2
2
2
2
2
4.6.3
浙江大学研究生学位课程
《实用数值计算方法,89
4.6.3
下的最速下降法。
就是在新度量意义因此，
由于是正定的，引进度量设
kk
k
k
T
k
k
T
k
k
T
k
k
T
kkkk
T
xfAh
xfA
xfAAxfA
xfAAxfA
xfAAxfA
xfAxfxfxfAxf
Axxx
A
1
2
1
11
11
11
11
2
2
1
2
1
2
1
的最速下降法。牛顿法就是在新度量下
浙江大学研究生学位课程
《实用数值计算方法,90
4.6.3
度和性质。
速，并且保持一定的收敛来代替近似度量简单的说，我们用一个
）
它也叫变矩阵法（
变化的。另外，是随的度量矩阵度量变度量法的名称是因为
。度，又不要计算顿法的收敛速而变度量法既保持了牛
。及其逆要计算二阶偏导数矩阵速度，但是它牛顿法具有很好的收敛
1
1
1
2
1
1
kk
kk
kk
T
kk
k
k
JH
M e t hods
M at r ixV ar iabl e
xJ
xJxx
J
J
浙江大学研究生学位课程
《实用数值计算方法,91
4.6.3
iikk
v
HHH
Hiv
hxx
hxfhxfiii
gHxfHhii
kHRxi
HHH
H
kkk
k
kkkk
kkkkkk
kkkkk
n
kkk
k
转：
不满足结束条件时令计算令求记正定矩阵取算法的步骤：
修正值的产生又比较方便：而
1
,
,
m i n:;0,,
1
1
1
0
00
1
浙江大学研究生学位课程
《实用数值计算方法,92
4.6.3
使之满足上面等式。构造
，故其中由中值定理，
记拟牛顿性质性，稳定性。拟牛顿性质，二次收敛的原则构造
1
1
1
2
1
1
0
,
,
2
k
kk
kk
kkkk
kkkkkkk
k
ji
kkk
kkkkk
k
H
xgA
xhxA
xghxgggg
J
xx
f
Axxx
gggxfg
i
H
浙江大学研究生学位课程
《实用数值计算方法,93
4.6.3
k
kkk
kk
T
kkkk
kk
n
n
kkk
xfxfH
gHgxfxf
kxfxf
iii
AH
Ahhh
n
ii
D F P
xgH
对适当小的正定时，总有故当事实上，
即稳定性：
轭的向量组，且共构成到极小点，这就要求步达法至多用于凸二次函数时，算二次收敛性条件此式称为拟牛顿方程
1
1
1
1
1
21
1
2
1
,2,1,0
,,,
浙江大学研究生学位课程
《实用数值计算方法,94
4.6.3
kkk
kk
T
k
k
T
k
T
k
T
k
kk
k
T
kk
T
k
k
T
kkkk
T
kkkk
T
kkk
T
kkk
kkkkk
kkkk
kkk
k
k
gHg
Hg
q
gx
x
q
gqg
gqgHgxgH
qgHxH
gHxgH
xgHH
D F PHHH
D F P
H
H
,
,
1
:3
1
可取为：这样的即可。只要求令故条件：满足要求方法。变度量方法。这里介绍种方法的不同，形成了各构造具体构造浙江大学研究生学位课程
《实用数值计算方法,95
4.6.3
谢如彪，姜培庆《非线性数值分析》，
陈开周《最优化计算方法》，
详细证明可参考：
正定二次收敛性可以证明：
变度量算法迭代公式。这就是得代入
2
1
,3,2
1
kHii
i
D F P
gHg
HggH
gx
xx
HH
k
kk
T
k
T
k
T
kkk
k
T
k
T
kk
kk
浙江大学研究生学位课程
《实用数值计算方法,96
4.6.3
变尺度法 Variable Matrix Methods
算法框图：
0,0误差控制取初值 nRx
00 xfg yes 停
0xx解
no
IHk 0,0:
kkk kkkk hxfxf
hxx
01
1
min
:求一维极值得
kkk gHh
11 kk xfg yes 停
1 kxx解
nk?
no
yes
10
10
n
ngg xx
no
k
T
k
T
kk
k
T
k
T
kk
kk
kkk
kkkkkk
ggx
xx
HH
gH
gggxxx
1
11,,
1kk
图 4.29 变尺度法算法框图浙江大学研究生学位课程
《实用数值计算方法,97
4.6.3
891241
241385
986
1
921
2149
58
1
12
24
17
1
10
01
1790
17210
61712
12176
1730
1760
41738
21726
1712
176
1738
1726
17
5
212264212
64
2
1
212
2
3
6,12
6,12
,4,2,
2
2
1
2
3
1
0000
0
0
111
0
22
00
000
00
00
121
2
2
2
1
H
ggH
g
x
xfgx
hxf
gHh
gxf
xfxIH
xf
T
T
T
故故得按精确一维搜索法不难而记首先计算之极小点。求取例：设
浙江大学研究生学位课程
《实用数值计算方法,98
4.6.3
1
12
111
11
1
2
1
111
31
11
2
1
833357
357153
986
441189
18981
306
1
744
366
986
1
1712
176
891241
241385
986
1
1712
176
,
1721
179
17381
17261
1
1
0
2
31
11
2
1
0
0
,
0
2
,
01
13
,
2
1
1
1
2921
299
17
29
1738
1726
17
29
2921
299
1712
176
891241
241385
986
1
A
HH
gH
gx
bA
cbA
cxbAxxxfxf
xf
x
gHh
TT
继续计算下去，则其极小点为则写成事实上，将的极小点。不难验证此即故作一维搜索，得再循环一次：
浙江大学研究生学位课程
《实用数值计算方法,99
4.6.3
,,,,
5
1
4
1
kkkk
k
T
k
k
T
k
k
T
kkkkk
k
T
kkkkk
T
kkk
T
kkkk
dcba
gv
gu
gHdxcv
gHbxau
vgHuxHH
H uang
个参数这个公式含有且满足：
其中：
公式：
族是一般的变度量算法主要变度量算法的校正公式
浙江大学研究生学位课程
《实用数值计算方法,100
4.6.3
数值稳定性最好的。它是当前变度量方法中公式：
即得重要的，，令族公式。即，令公式。即，令较重要的三种公式是：
个独立参数个关系式，故有但有
k
T
k
kk
T
k
k
k
T
k
k
T
kk
T
kkk
T
kkk
kk
kkk
kk
kk
gx
gHg
gx
HgxxgHxx
HH
B F G S
dcbiii
B r oy de ncbii
D F Pbci
1
,01
,1
,01
32
1
浙江大学研究生学位课程
《实用数值计算方法,101
4.6.3
方性 法质牛顿法 D F P （拟牛顿法）
共轭梯度法
（重置初值）
二次终止性质一步终止
（? =1 ）
n 步 ( 精确一维搜索 )
终止
n 步 ( 精确一维搜索 )
终止收 敛
f? C
( 3 )
且有界凸,x
0
充分接近 x
*
,?
k
1
f? C
( 3 )
在 L ( x
0
) 上有界凸,L ( x
0
) 有界
（精确一维搜索）
f? C
( 3 )
在 L ( x
0
) 上有界凸,L ( x
0
) 有界
（精确一维搜索）
局部收敛性同上二阶收敛同上，且? f(x ) 是
L i p s c h i t z 连续。
超线性收敛。
同上，
超线性收敛优缺点要计算二阶偏导数计算量大。 n 大时存贮量亦大计算量少，程序简单；
n 大时存贮量也大计算程序简单，
存贮量相对较小
称水平集。注：,00 xfxfRxxL n
表 4.5 各种方法比较浙江大学研究生学位课程
《实用数值计算方法,102
4.7 直接法 （ Simplex,Powell）
大量的目标函数是很复杂的，有时连解析式都没有，因而它的导数
f(x)
很难求，有时甚至不存在。
4.7.1 单纯形法 Simplex Method
Nelder--Mead (1965)提出这种简单的方法。它不需要求导数（梯度）
对变元不多的情况是有效的。
程序简单。
浙江大学研究生学位课程
《实用数值计算方法,103
4.7.1
单纯形的思想 是在 n维空间的 (n+1)个点
(它们构成单纯形 )上引进函数值比较。丢弃最坏的点并代之以新点。它们仍然构成单纯形。以此逐步逼近极小点。
下：则单纯形法迭代过程如它满足的一个排列是设个单位向量为定义初点选取单纯形的选取：
1,,1,0
,,,1,0
,,2,1
,
,,1,0
1
0
0
nixfxf
niPx
nu
niuPP
P
niP
ii
ii
i
iii
i
浙江大学研究生学位课程
《实用数值计算方法,104
4.7.1
）几何意义：（
是反射系数，一般
）（
的反射点关于求形心，令排列按
2
10
1
1
,,,
1
1
1
0
110
n
xxxxxP
Pxx
x
n
xii
xfxfxxxi
nnn
nn
n
i
i
iin
1x
x
0x2x
3P
图 4.30 单纯形法中的反射浙江大学研究生学位课程
《实用数值计算方法,105
1x
2x
x
0x
3P
4P
4.7.1
）几何意义：（
是延伸系数，一般
：方向的延伸点求沿则延伸。
的大小满足接和若
2
21
)1(;,,,,)
,,,
111
21
101
1110
n
xPxPxP
PP
xxxPa
PfPxxx
nnn
nn
nn
nnn
图 4.31 单纯形法中的延伸浙江大学研究生学位课程
《实用数值计算方法,106
4.7.1
);;,
5.010
5.0
:;,,,,,);;,,,,);
22
112
2
1110
1110
1
212
e
iPxxfPf
PxxPxP
Px
xPxxxc
iPxxxxxb
i
Px
PxPfPf
nnnn
nnn
n
nnn
nnnn
nn
nnnn
转否则转则若
。为收缩系数，一般方向的收缩点求沿则收缩。；转则转否则则若
1?nP
浙江大学研究生学位课程
《实用数值计算方法,107
4.7.1
2x
3P
x
1x
0x
4P
'4P
图 4.32 单纯形法中的收缩
e
iPxxfPf
xxxxxP
Px
Pxxxd
nnnn
nnn
nn
nn
否则转转则若如图方向的收缩点求沿则收缩;,
2
1
32.4,;,,,,)
'
2
'
2
'
2
'
2
110
浙江大学研究生学位课程
《实用数值计算方法,108
4.7.1
e) 缩小边长
i
ni
xxxxxx
xxnix
iii
ii
转令缩小一半：沿
,,2,1
2
1
2
1
,,1
000
0
1x
2x 0x
'1x
'2x
1?nP
图 4.33 单纯形法中的缩小边长浙江大学研究生学位课程
《实用数值计算方法,109
4.7.1
单纯形法（ Simplex）框图：
0,,1,0,0 ；任取 niP i?
niuuPP Tiiii,1,0,,1,,0,0,0
0xfxf n
nixfxfPx iiii,1,,1并排列：
nnn
i i
xxxPnxx
1
1
0; 反射
1?nPf判别
2?nP延伸得 2?nP收缩得 2?nP收缩得
12 nn PfPfnn xfPf2nn xfPf2
1 nn Px ix缩小边长，求
2 nn Px
解 x*?x0y
n
b
dca
n
yyy
n
图 4.34 单纯形法计算框图浙江大学研究生学位课程
《实用数值计算方法,110
以上的迭代过程直到满足精度为止。
精度：
则 x0作为所求的近似解。
4.7.2 Powelll 方法
Powelll 方法是一种不依赖于目标函数梯度的直接搜索法。
它 逐步构造共轭方向并作为搜索方向,
因此 Powell方法也是一种共轭方向法。
它的基本过程如下：
n
i i
xfxf
0
2
0
浙江大学研究生学位课程
《实用数值计算方法,111
4.7.2
则作为搜索方向，取取两单位标准向量例，设
,2,2
1
0
0
1
,2
0
21
21
2
2
2
1
T
x
ee
xf
k H
k
T
k
x
T
k + 1
F ( x
k + 1
)
0
1
2
( 0,1 )
( 1,0 )
( 0,1 )
-1
- 1,7 5
- 0,8 7 5
( 2,1 )
( 0,2 5,1 )
( 0,2 5,0,1 2 5 )
7
0,8 7 5
0,1 0 9
0,8 75
它必然指向极小点。
作为搜索方向故若取
，
即：
共轭的，是与可以发现，
13
213
0
1
0
21
14
112 5.0225.0
xxh
A
exx
5.0 0.1 5.1 0.25.0?0.1?5.1?
1.0
0.1
1x
0x
2x
3x
1?
2?
图 4.35 Powell搜索路径表 4.6 Powell 方法解题过程
5.0
2.5
浙江大学研究生学位课程
《实用数值计算方法,112
4.7.2
nn
nn
nn
ii
iiii
iiii
i
ii
i
uPfPf
uPP
PPu
niuu
uPfPf
uPP
P
uPni
ni
un
P
0
0
0
0
1
1
0
1
1
0
m i n
,3
1,,2,1,2
m i n
:
,,,2,11
,,2,1
0,,0,1,0,,0
使得求令值搜索，令极值点为方向作一维极小沿对个单位方向并且令给定一点
浙江大学研究生学位课程
《实用数值计算方法,113
4.7.2
Powell方法过程图示：
00P nu
0P
1u
1P
2u
2P
3u
3P
4u?
1?iP
iu
iP
3?nP
3?nu
2?nP
2?nu
1?nP
1?nu
nP
nu
10P
01 PPu nn
11u
11P
12u
12P
13u
13P
14u?
11?iP
1iu
1iP
13?nu
13?nP12?nP
1 2?nu
11?nP
11?nu
1nP
1nu
1012 PPu nn
1nP
101 nnnnn PPu
nP0
nu1
nP1
nu2
nP2
nu3
nP3
nu4?
niP1?
niu
niP
nnu3?
nnP3?
nnu 2?
nnP2?
nnu1?
nnP1?
nnu
nnP
,2,1 ;1,,2,1,11 j niuu jiji
图 4.36 Powell 方法计算过程图示浙江大学研究生学位课程
《实用数值计算方法,114
4.7.2
循环上面 (1)--(3)，直至 P0点函数值不再减小为止 。
当循环 k次 (k?n)以后,un与它前面的 k-1个向量 un-k+1,?,un-1共轭。因此对于二次函数，
理论上只要循环 n次即可求得极小值。即具有 二次收敛性 。事实上，因为
P0和 Pn是沿相同方向 un求得 的 极小值，
所以 Pn?P0与 un方向共轭。
nP
11?nP
10P
1nP
nu nu
图 4.37 共轭方向浙江大学研究生学位课程
《实用数值计算方法,115
4.7.2
方法Po w ell
n 2?
20P
12P
2212u?
1212u?
11P
1111u?
10P
212?u12P
2P
22?u
0P
11?u
00P
2u
图 4.38 Powell 方法计算过程示意浙江大学研究生学位课程
《实用数值计算方法,116
4.7.2
果为：方法计算的第一循环结用
，搜索方向取极小点为它是一正定函数，整体例：设
P ow e lleu
eueuP
P
xf
T
T
,
,,
2
1
,1,
2
1
0,0,0
3
0
3
2
0
21
0
10
2
321
2
132
2
321
k u
k
0
P
k
0
f(P
k
0
)
0
1
2
3
e
1
e
2
e
3
T
T
T
T
18
5
,
3
1
,
2
1
2
1
,
3
1
,
2
1
2
1
,1,
2
1
2
1
,1,
2
1
8142
32
2
2
。不能替换进行。故的平面上以后的搜索肯定在线性相关。，，显然索方向应是据算法，第二循环的搜于是
103
1
1
3
1
2
1
1
1
3
1
2
1
1
03
2
1
,
9
2
,
3
2
,0,1,0,0,0,1,0
9
2
3
2
0
ePP
uuu
uuu
PP
T
TT
T
表 4.7 Powell方法第一次循环计算结果浙江大学研究生学位课程
《实用数值计算方法,117
xf
x0P 1P
1x 0x 2P 3P
0x 1x
1x 0x 3P 2P
0x 1x
3P 2P1x 0x
1x 0x
图 4.39 单纯形法求一维极值示意图（ 1）
a
d
c
4.7.2
浙江大学研究生学位课程
《实用数值计算方法,118
xf
x
a
d
d
d
e
a
0P 1P
1x 0x 2P 3P
0x 1x
1x 0x 2P 3P
0x 1x
1x 0x3P 2P
0x1x
1x 3P 0x 2P
1x 0x
1x 3P 0x 2P
1x 0x
图 4.40 单纯形法求一维极值示意图（ 2）
4.7.2
浙江大学研究生学位课程
《实用数值计算方法,119
4.7.2
但是，实际计算中对二次函数也不能保证
n步内达到极小值点。
因为每一循环都用 Pn--P0“挤掉” u1,所以新的向量系 ui(I=1,…,n) 有可能线性相关，
例如，某一循环中，如果?1?０则这样,u2,u3,…,Pn--P0是线性相关的 。
当发生这种情况时，以后的搜索就在
n 维的子空间中进行。最后的解就不正确。
解决的办法是 Pn--P0不是挤掉 u1。而是挤掉
ur,而?r?０。 一般取 最大下降方向 （ the
Direction of the Largest Decrease)
0
2
0 PPuPP n
n
i
iin
平均方向?
浙江大学研究生学位课程
《实用数值计算方法,120
4.7.2
这是因为最大下降方向 ur已经在平均方向
Pn-P0中得到最充分的体现 。
这一简单的思想有两种例外情况：此时并不修改方向。
0m a x,0
2
1
1
1
0
00
ii
ni
rr
n
nn
ffffff
PPff
Pff
Pff
令：
fff
ffffff
PP
nff
E
nEn
n
E
2
0
2
00
0
0
222
,1
已不是好的方向。
个方向，因为保持原来的如果：
浙江大学研究生学位课程
《实用数值计算方法,121
4.7.2
因为下列两个原因之一成立：
a) Pn-P0方向的下降主要不是因为?f.
b) Pn-P0方向上二阶导数很大，这表明在
Pn附近有可能有极小点。
xf
0f
f? nf1f
Ef0P
nP
EP
1P
图 4.41 函数变化的影响浙江大学研究生学位课程
《实用数值计算方法,122
4.7.2
图 4.42 修正 Powell算法框图：
000000,0,,PffkeuP ii及置初值
k
i
k
i
k
i
k
i
k
i
k
i
k
i
k
i
k
i
k
i
k
i
uPP
uPfuPf
Pni
1
11 m in
,,2,1
使：
和进行一维搜索，确定对?
knEknnkknkn PffPffPPP 101,2 及计算
kikinikrkr PfPfPfPfffr 111 m a x,使和求
fE?f0
fffffffff EnEn 20200 22
kiki uunrinr 11,, 置时，对当?
k
n
k
n
k
n
k
k
n
k
n
k
n
k
n
k
n
k
i
kk
n
kk
n
k
n
uPP
uPfuPf
PPPPu
10
1
100
m in
,
并置使：
并确定置
kPff 00?求收敛准则 1kk
P*= Pkn,计算结束 Y
N
Y
Y N
N
浙江大学研究生学位课程
《实用数值计算方法,123
4.7.2
010.0
205.0
000.1
200.1
99.0
995.0
1
0
1
21
872.152.2421.20
)21.20980.22.24(872.15980.322.242
2.24872.15
1
21.2099.31.24
872.15
980.0
790.0
000.1
200.1
990.0
995.0
22
980.3,990.0,99951.0
990.3,000.1,995.0
,
2.24,0.1,2.1
1100
0
0
0
2
1
2
0
2
1
1
2
2
0
0
10
0
3
0
0
2
0
3
0
2
0
2
0
2
0
1
0
1
0
1
2
0
21
0
1
00
2
1
2
2
12
PPu
uu
r
nr
ff
r
PfPff
Pff
PPP
PfP
u
PfP
u
eueu
PfP
xf
R os e nbr oc k
E
E
T
T
T
计算前移一位：搜索方向自因且因所以而一维搜索得：沿一维搜索得：沿取搜索方向此时取函数例，对
浙江大学研究生学位课程
《实用数值计算方法,124
4.7.2
计算结果表作一维搜索得沿所以
8.4
990.0,990.0
04 88.0
999.0
206.01021.4
1
0
1
2
1
2
20
0
0
2
T
Pu
u
PP
k (u
1
k
)
T
(U
2
k
)
T
P
k
T
f( P
k
)
1 ( 0,1) ( 0.9 99,- 0.0 48 8)
P
0
1
( - 0.9 90,0,99 0)
P
1
1
( - 0.9 90,0,99 0)
P
2
1
( - 0.9 84,0,97 9)
3.9 69
3.9 59
3.9 48
2 ( 0,1) ( 0.4 53,- 0.8 92 )
P
0
2
( - 0.7 61,0,54 0)
P
0
1
( - 0.7 61,0,57 9)
P
0
1
( - 0.7 02,0,46 2)
3.2 57
3.1 01
2.9 86
3 ( 0.4 53,- 0.8 92 ) ( 0.6 08,- 0.7 44 )
P
0
3
( - 0.5 03,0,20 3)
P
1
3
( - 0.5 38,0,27 3)
P
2
3
( - 0.4 66,0,17 8)
2.5 10
2.3 96
2.3 01
2,39 6
5.05.0? 0.1
0.1
1?
2?
图 4.43 计算结果图示
P*
浙江大学研究生学位课程
《实用数值计算方法,125
4.8 方法的选择与总结
4.8.1 方法的选择
1,原则：
（ 1） 有效性
（２） 运算量
（３） 存储量
2,非线性代数方程
（１） 二分法具有良好的有效性
（２） 二次插值和有理插值运算量少
（３） 一般采用组合方法浙江大学研究生学位课程
《实用数值计算方法,126
4.8.1
3,非线性方程组
（１） 一般采用最优化方法
（２） 对于无梯度（或不易求梯度）问题，
一般不用ＣＧ方法，因为稳定性太差。
用有限差商近似导数不是好的选择。
但是当问题很大时（ n?200）由于存贮的限制，ＰＯＷ方法和ＶＭ方法不能用时，只能考虑ＣＧ方法。
对小问题（ 2? n? 10）,选择
ＰＯＷ方法或ＶＭ方法（差商近似导数）均可考虑。有效性依赖于问题。
浙江大学研究生学位课程
《实用数值计算方法,127
4.8.1
更要使用精确的梯度。时病态而梯度时，要利用梯度。
精确在计算量不太大能得到对于有梯度问题方法较合适。
没有连续的梯度，则若比较可靠。
方法一般大问题方法更好。对于性态差则选对于中等问题
,
3
,20050
,5010
xf
P O W
xf
VMn
VM
n
浙江大学研究生学位课程
《实用数值计算方法,128
4.8.1
艺术。
它也是一种方法强烈依赖于问题，
用，选择有几种组合方法可以利
。方法要求梯度，存储
。方法不用求导数，存储存贮量大度，并且而且稳定。但它要求梯方法最有效就方法本身来说，
方法。时，选当或时，当较好。时，当
5
.
4
150
15050
502
2
2
nOCG
nOP O W
nO
VM
CGn
VMCGn
VMn
浙江大学研究生学位课程
《实用数值计算方法,129
4.8.2 算法思想小结
1.迭代法，而不是解析法
2.线性化，极值化方法
3.降维法
4.下降法
5.插值逼近法
6.组合法
7.梯度方向共轭方向改变度量浙江大学研究生学位课程
《实用数值计算方法,130
第四章 习 题
.0,
,,2,1
);
)
,,2,1.3
,
2
1
,
,.2
10)),
10)),
)
,)
)
,)
,126.1
21
21
21
4
3
2
21
2
21
2
3
1
x
Anihx
iiDD
iA
nihnnA
x
xxJxxFxxFxF
T ay lor
F
iviii
iii
fB r e ntiv
ffN e w t oniii
fii
ffi
exxfxxxf
i
i
TT
x
则共轭与是正定的，且Ａ
如果为对角阵ＡＰ使得Ｐ
试找一个矩阵Ｐ，共轭的向量组，是阶对称矩阵，是设试证明之。
处的值。这里上横线表示在点展开式为的点关于两个变量的非线性函数取
，取精度控制问题的根；方法来求用的一个实根；法分别计算用的根；求线性插值法用割线法的一个实根；用二分法分别计算设
Ｔ
浙江大学研究生学位课程
《实用数值计算方法,131
T
kk
T
k
k
T
kkkk
kk
PxfP ow e l l
y
zx
yz
yx
xf
xFD F P
xxxxfxfxF
xxf
xxxf
gHg
HggHx
HH
D F P
xfxfx
xf
xfxfxxLx
c
ccxfxf
xf
0.2,0.1,0.0
2e x p
2
1
s i n
1
1
.7
2
1
2
1
m i n
0
0.6
)(.5
0)4(
)3(
,0)2(;04.0,02.0,01.0,0,01.0,02.0,04.0,2.0,1
,)1(
2
1
3
1
.4
0
2
2
2
1
2
21
2
2
2
1
12
211
1
000
2
2
3
1
的极大点值，取方法求试用设的极小值点。方法分别求试用共轭梯度法和问题的求解可化为以下极值方程组条件下式满足拟牛顿方程在变尺度法中，试证明的极值点。的稳定点，是否为是否为区域中不为有界凸；
为有界凸，那些举例说明在哪些区域中试绘出水平集设取以下值：的等高线试绘出设
