第4章 计算函数零点和极值点的迭代法
本章讨论非线性方程（组）的求解问题
4.1 不动点迭代法及其收敛性
1．不动点
设非线性方程组f (x ) = 0 (4.1-1) 等价： x = Φ(x ) (4.1-2)
则有迭代格式：x (k +1) = Φ(x (k ) ) ，k = 0，1，2，…
若Φ连续，且迭代序列{x (k ) }收敛到x *，则两边取极限得x * = Φ(x *) ，即x *满足(4.1-2)，从而满足(4.1-1)，即x *为f 零点。 称x *为Φ(x ) 的不动点。
注：(1) 求零点⇔求不动点
(2) Φ(.)称为迭代函数，{x (k ) }称为迭代序列
(3) 不同方法构造迭代函数，得不同的迭代序列
2．迭代法的基本问题
(1) 如何构造适当的迭代函数Φ(.)使迭代序列{x (k ) }收敛 (2) 收敛的速度和误差 (3) 如何加速
4.1.1 解一元方程的迭代法
1. 根的隔离
设一元方程f (x ) = 0，f 连续，其实根可能有很多，需将各根隔离，即f 在[a ，b ]内有且仅有一根。
方法：设f ∈C[a ，b ]，f (a ) f (b )
2. 迭代序列的收敛性
因为可以有多种迭代函数，所产生的迭代序列{x (k ) }有可能： (1) 收敛快 (2) 收敛慢 (3) 不收敛
例1 f (x ) = x 3 – x – 1 = 0，求f 在x = 1.5附近的根，初值取x (0) = 1.5。(p328) 取ϕ(x ) =
3
1+x ——收敛
取ϕ(x ) = x 3 – 1——不收敛
定理4.1-1 (1) 设ϕ(x ) ∈ C[a ，b ]，且对于任意x ∈ [a ，b ]有ϕ (x ) ∈ [a ，b ]，则ϕ在[a ，b ]上必有不动点。 (2) 进一步，若ϕ(x ) ∈ C1[a ，b ]，且存在L
x x
(k )
-x -x
*
≤≤
L 1-L L
k
x x
(k )
-x -x
(k -1)
(4.1-5)
(1)
(0)
(k ) *
1-L
证明：(1) 若ϕ(a ) = a 或ϕ(b ) = b ，则结论显然成立
现设a 0，ψ(b ) = ϕ(b ) – b
(2) 设ϕ(x ) ∈ C1[a ，b ]，且满足(4.1-4)，若有x 1*，x 2* ∈ [a ，b ]，x 1* ≠ x 2*，ϕ(x i *) = x i * i = 1，2 由微分中值定理，|x 1* – x 2*| = |ϕ(x 1*) – ϕ (x 2*)| = |ϕ'(ξ)| |x 1* – x 2*| ≤ L|x 1* – x 2*|
由|x (k ) – x *| = |ϕ( x(k -1) ) – ϕ (x *)| ≤ L |x (k -1) – x *| ≤ … ≤ L k|x (0) – x *| 及0
k →∞
(k )
-x |=0
*
即x (k ) 收敛于x *。
并且由|x (k ) – x *| ≤ L |x (k -1) – x *|得 |x (k ) – x *| ≤ L |x (k -1) – x (k ) + x(k ) – x *| ≤ L |x (k -1) – x (k ) | + L|x(k ) – x *| 从而有x
(k )
-x
*
≤
L 1-L
x
(k )
-x
(k -1)
又因
|x (k ) – x (k -1) | = |ϕ(x (k -1) ) – ϕ (x (k -2) )| ≤ L | x (k -1) – x (k -2) | ≤ …≤ L k-1| x (1) – x (0)|，代入上式的右边，即得 x
(k )
-x
*
≤
L
k
1-L
x
(1)
-x
(0)
注：(1) 若L ≈ 1，则收敛很慢，须考虑加速问题 (2) (4.1-5)中第一式为后验公式—迭代停止准则 第二式为先验公式—预测迭代次数
(3) 定理是以[a ，b ]中任一点作初值，迭代都收敛，称为全局收敛。 （此要求较难满足，故考虑在） x *的某一邻域内—局部收敛性
定理4.1-2 设x *为ϕ的不动点，ϕ ' 在x *的某邻域内连续，且|ϕ '(x *)| 0，只要x (0) ∈ [x * –δ，x * + δ]，迭代法x (k +1) = ϕ(x (k ) ) 收敛。
证明：∵|ϕ'(x *)| 0，使[x * –δ，x * + δ] ⊂ U (x *) ，且 ∀ x ∈ [x * –δ，x * + δ]有|ϕ '(x )| ≤ q
注：只要x (0)充分接近x *，且|ϕ '(x (0))| 明显小于1，则{x (k ) }收敛于x *。 例2 求方程x = e–x 在0.5附近的根。
由于|ϕ '(0.5)| = e–0.5 ≈ 0.61明显小于1，故收敛
3. 收敛阶
定义4.1-1 设x (k ) → x *，记e k = x(k ) - x * 若存在p ≥ 1，及c ≠0，使lim
|e k +1||e k |
p
k →∞
=c 则称{x (k ) }是p 阶收敛的，或称收敛阶为p （p
越高收敛越快） 注：
(1) p = 1，0 1，称超线性收敛 (3) p = 2，称平方收敛
因为| x (k +1) –x *| = |ϕ(x (k ) ) – ϕ(x *)| = |ϕ'(ξ)| |x (k ) – x *|，其中ξ在x (k ) 和x *之间。 则lim
|e k +1||e k |
p
k →∞
=|ϕ' (x ) |
*
所以若ϕ '(x *) ≠ 0，则为线性收敛
想得到更高阶的收敛性，须ϕ '(x *) = 0，通常可考虑麦克劳林展式。
定理4.1-3 设x *为ϕ的不动点，正整数p ≥ 2，若ϕ(p ) 在x *的某邻域内连续，且满足
⎧ϕ(k ) (x *) =0, ⎨(p ) *
⎩ϕ(x ) ≠0
k =1, 2,..., p -1
(4.1.6)
则{x (k ) }p 阶局部收敛。
证明：∵ϕ '(x *) = 0(
x +
(k +1)
=ϕ(x (x )
*
(k )
) =ϕ(x ) +ϕ' (x )(x
(k )
**(k )
-x ) +
(k )
*
ϕ" (x )
2!
*
p
*
(x
(k )
-x ) +...
*2
ϕ
(p -1)
(p -1)!
(x -x )
*p -1
+
ϕ
(p )
(ξ)
p !
(x -x )
由(4.1-6)知，
x
(k +1)
-x =ϕ(x
*(k )
) -ϕ(x ) =
*
ϕ
(p )
(ξ)
p !
(x
(k )
-x )
*p
所以
x (x
(k +1) (k )
-x
*
*p
-x )
=
ϕ
(p )
(ξ)
p !
→
ϕ
(p )
(x )
*
p !
≠0
即{x (k ) }p 阶局部收敛。
例3 设f ∈ C2[a ，b ]，ϕ (x ) = x – r 1(x ) f (x ) – r 2(x ) f 2(x ) ，x *为f 的单重零点。试确定未知函数r 1(x ) 、r 2(x ) ，使迭代法x (k +1) = ϕ(x (k ) ) 至少是三阶局部收敛的。解：由定理4.1-3知，应有ϕ '(x *) = ϕ "(x *) = 0因为ϕ '(x ) = 1 – r 1'(x ) f (x ) – r 1(x ) f '(x ) – r 2'(x ) f 2(x ) – 2r 2(x ) f (x ) f '(x ) 而f (x *) = 0，f '(x *) ≠ 0（单重零点），令ϕ '(x *) = 0，有1 – r 1'(x *) f '(x *) = 0即取r 1(x ) =
1f ' (x )
，则有ϕ '(x *) = 0
此时有ϕ '(x ) = – r 1'(x ) f (x ) – r 2'(x ) f 2(x ) – 2r 2(x ) f (x ) f '(x )
⇒ ϕ "(x ) = – r 1"(x ) f (x ) – r 1'(x ) f '(x ) – r 2"(x ) f 2(x ) – 4r 2'(x ) f (x ) f '(x ) – 2r 2(x )[f '(x )]2– 2r 2'(x ) f (x ) f "(x ) 其中r 1' (x ) =
-f " (x ) [f ' (x )]
2
*
令ϕ"(x ) = 0，有
*
f " (x ) f ' (x )
*
-2r 2(x )[f ' (x )]=0，即取
**2
r 2(x ) =
f " (x ) 2[f ' (x )]
3
，则有ϕ"(x *) = 0从而只要同时取r 1' (x ) =
-f " (x ) [f ' (x )]
2
，r 2(x ) =
f " (x ) 2[f ' (x )]
3
，
迭代法至少具有三阶局部收敛性。
4. 加速
幂法中曾有Aitken 加速，这里使用相同的思想 若x → x ，由中值定理， x
(k )
*
(k +1)
– x = ϕ (x ) –ϕ (x ) = ϕ'(ξ1)(x – x ) ⇒
*(k ) *(k ) *
x
(k +1) (k )
-x -x
*
*
*
x
=ϕ(ξ1)
'
ξ1在x 和x 之间x
(k ) *(k +2)
– x = ϕ (x
*(k +1)
) –ϕ (x ) = ϕ'(ξ2)(x
*(k +1)
– x ) ⇒
*
x x
(k +2) (k +1)
-x -x
*
=ϕ(ξ2) ξ2
'
在x (k +1)和x *之间因为x (k ) → x *，所以当k 充分大时，ϕ '(ξ1) ≈ ϕ '(ξ2) 即
x x
(k +2) (k +1)
-x -x
**
≈
x
(k +1) (k )
-x -x
*
*
x
⇒x ≈x
*(k +2)
-
(x x
(k +2)
-x
(k +1)
)
2(k )
(k +2)
-2x
(k +1)
+x
(4.1-7)
ˆ记x
(k +2)
=x
(k +2)
-
(x x
(k +2)
-x
(k +1)
)
2(k )
(k +2)
-2x
(k +1)
+x
ˆ，则{x
(k )
}比{x (k ) }收敛得快。
e k +1e k
定理4.1-4 设{x (k ) }线性收敛于x *，且∀k ≥ 0，e k = x (k ) – x * ≠ 0 lim (线性收敛) 则lim
ˆ(k ) -x *x x
(k )
k →∞
=λ 0
k →∞
-x
*
=0
证明：因为lim
e k +1e k
k →∞
=λ
所以e k +1 = (λ +εk ) e k ，其中εk → 0
⇒ x (k +1) – x (k ) = x (k +1) – x * – (x (k ) – x *) = e k +1 – e k = [(λ – 1) + εk ]e k 又
x (k +2) – 2x (k +1) + x (k ) = (x (k +2) – x (k +1)) – (x (k +1) – x (k ) ) = [(λ – 1) + εk +1]e k +1 – [(λ – 1) + εk ]e k
= [(λ – 1) + εk +1](λ + εk ) e k – [(λ – 1) + εk ]e k = [(λ – 1)2 + μ k ]e k .
其中μ k = λεk +1 +(λ – 2 )εk +εk +1εk → 0
ˆx
(k +2)
=x =x
(k +2)
-
(x x (x
(k +2)
-x
(k +1)
)
2(k )
(k +2)
-2x
(k +1) (k )
+x
2
=
x x
(k +2) (k +2)
⋅x
(k )
-(x
(k +1)
(k +1)
)
2
-2x +x
(k )
(k +1)
(k )
-
-x )
x
(k +2)
-2x
(k +1)
+x
(k )
所以
ˆx
(k +2)
-x =x
*(k )
-x -
*
(x x
(k +1)
-x
2
(k )
)
2(k )
(k +2)
-2
2
(k +1)
-x
=e k -
[(λ-1) +εk ]e k
2
[(λ-1) +μk ]e k
[(λ-1) +εk ]
2
2
=e k -e k
[(λ-1) +μk ]
⇒ lim
ˆ(k +2) -x *x x
(k +2)
k →∞
-x
*
=lim
e k e k +1
k →∞
(1-
[(λ-1) +εk ]
2
[(λ-1) +μk ]
) =0
注：(1) (4.1-7)成为Aitken 加速
⎧(k ) (k )
y =ϕ(x ) ⎪⎪⎪(k ) (k )
(2) ⎨z =ϕ(y ) k = 1，2，…
⎪
(k ) (k ) 2(z -y ) ⎪(k +1) (k )
x =z -(k )
(k ) (k ) ⎪z -2y +x ⎩
称为史蒂文生迭代法。
例4 用迭代法和Steffensen 迭代法求函数f (x ) = x – lnx – 2在区间(2，+∞) 内的零点，取x (0) = 3. 解：将f (x ) = 0化为等价的方程x = lnx + 2 = ϕ (x ) ，由于ϕ '(x ) = 1/x 在[2，+∞) 上满足|ϕ '(x )| ≤ 1/2
⎧(k ) (k )
y =ln x +2⎪⎪⎪(k ) (k )
=ln y +2 ⎨z
⎪
(k ) (k ) 2(z -y ) ⎪(k +1) (k )
x =z -(k )
(k ) (k ) ⎪z -2y +x ⎩
取初值x (0) = 3作迭代，结果见p336
迭代法x (k +1) = ln x(k ) + 2： x0=3 k=1
x1=log(x0)+2
while (abs(x1-x0)>0.0000001)
x0=x1;k=k+1 x1=log(x0)+2 end
Steffensen 迭代法 x0=3 k=1
y=log(x0)+2 z=log(y)+2
x1=z-(z-y)^2/(z-2*y+x0)
while (abs(x1-x0)>0.0000001) x0=x1;k=k+1 y=log(x0)+2 z=log(y)+2
x1=z-(z-y)^2/(z-2*y+x0) end
4.1.2 解非线性方程组的迭代法
设非线性方程组f (x ) = 0 (4.1-1)
⎧f 1(x 1, x 2,..., x n ) =0⎪
⎪f 2(x 1, x 2,..., x n ) =0
⎨
⎪
⎪⎩f n (x 1, x 2,..., x n ) =0
考虑等价形式
x = Φ(x ) (4.1-2)
迭代公式x (k +1) = Φ(x (k ) ) k = 0，1，2，… (4.1-3) 其收敛性有下述压缩映射（不动点）原理
Th4.1-5 设Φ在闭区域G =R n 上满足条件
(1) 存在q ，0
(1) 存在唯一不动点x *∈G ，且∀ x(0)∈G ，迭代向量列收敛于x *。 (2)
x
(k )
-x
*
≤
q 1-q q
k
x
(k )
-x
(k -1)
x
(1)
x
(k )
-x
*
≤
1-q
-x
(0)
证明与Th2.4-3相似 注：
(1) Φ(G ) ⊆G 保证序列{x (k ) }⊆G
(2) 若ϕi (x ) 在G 上可微，Φ(x ) = (ϕ1(x ) ，ϕ2(x ) ，…，ϕn (x )) T
⎡∂ϕ1⎢∂x ⎢1
记D Φ(x ) =⎢
∂ϕn ⎢⎢∂x 1⎣
∂ϕ1⎤∂x n ⎥
⎥
，则压缩条件可用下式替代 ⎥∂ϕn
⎥∂x n ⎥
⎦
∀x ∈G ⇒D Φ(x ) ≤q
例5
4.2 Newton 迭代法及其变形
4.2.1 一元非线性方程
f (x ) = 0
1. 牛顿迭代方法
线性化： 设f (x ) 在点x (k ) 处可微，则展开
f (x ) =f (x
(k )
(k ) (k )
) +f '(x )(x -x ) +
f ''(ξ) 2!
(x -x
(k )
)
2
用线性部分近似表示
f (x ) ≈ f (x (k ) ) + f '(x (k ) )( x – x (k ) )
即考虑方程f (x (k ) ) + f '(x (k ) )( x – x (k ) ) = 0 若f '(x ) ≠ 0，则有x =x
(k )
(k )
-
f (x
(k )
)
(k )
f '(x )
令：x
(k +1)
=x
(k )
-
f (x f '(x
(k ) (k )
) )
k = 0，1，2，… (4.2-4)
称为Newton 迭代公式，其迭代函数为
ϕ(x ) =x -
f (x ) f '(x )
(4.2-5)
2. 收敛性
(1) 若x *是f (x ) 的单重根： f (x *) = 0，f '(x *) ≠ 0 因为ϕ'(x ) =
*
**f (x ) f ''(x ) *2
[f '(x )]
=0, ϕ''(x ) =
*
*
f ''(x ) *
f '(x )
一般不为0
所以，牛顿法是局部二阶收敛的 ——由定理4.1-3
例1 用Newton 法求非线性方程f (x ) = x e x – 1 = 0在(0，1) 内的根，取x (0) = 0.5。 解：因为f (x ) = (1 + x )e x ，故其Newton 迭代公式为
x
(k +1)
=x
(k )
-
x
(k )
e
x
(k )
-1
x
(k )
(1+x
(k )
，k = 0，1，2，…
) e
从x (0) = 0.5出发，计算结果见p342表4.2-1。
(2) 若x *是f (x ) 的重根，即有f (x ) = (x – x *) m g (x ) ，其中g (x *) ≠ 0，m ≥ 2 因为f '(x ) = m (x – x *) m -1g (x ) + (x – x *) m g '(x ) 记x = x + h ，则ϕ(x +h ) =(x +h ) -
*
***
h g (x +h )
mh
m -1
*
g (x +h ) +h g '(x +h )
*
m
m *
=ϕ(x ) +h -
*
hg (x +h )
mg (x +h ) +h g '(x +h )
*
*
⇒ϕ'(x ) =lim
*
ϕ(x +h ) -ϕ(x )
h
**
h →0
=lim (1-
h →0
g (x +h )
mg (x +h ) +h g '(x +h )
*
*
*
) =1-
1m
当m ≥ 2时，ϕ '(x *) ≠ 0，由|ϕ '(x *)|
x
(k +1)
f (x ) f '(x )
，易知有ϕ '(x *) = 0所以，若事先知道x *的重数，则
=x
(k )
-m
f (x
(k )
)
(k )
f '(x )
(4.2-6)
此时，迭代序列{x (k ) }是二阶收敛的。 或令u (x ) =
f (x ) f '(x )
，则x *是u (x ) 的单重零点，应用Newdon 法于u (x ) ，有
x
(k +1)
=x
(k )
-
u (x
(k )
)
(k )
u '(x )
=x
(k )
-
f (x
(k )
(k )
) f '(x )
(k ) 2(k ) (k )
[f '(x )]-f (x ) f ''(x )
(4.2-7)
迭代序列也是二阶收敛的
例2 2是方程x – 4x + 4 = 0的二重根
42
(1) 采用Newdon 法 ϕ(x ) =x -
x -4x +44x -8x
34
2
=x -
(x -2)
2
22
4x (x -2)
=x -
x -24x
2
即x
(k +1)
=x
(k )
-
(x
(k )
) -2
(k )
2
4x
(2) 采用(4.2-6)
x
(k +1)
=x
(k )
-
(x
(k )
) -2
(k )
2
2x
(3) 采用(4.2-7)
u (x ) =
x -24x
2
2
1x +2
，u '(x ) =() 2
4x
2
2
u (x ) u '(x )
=
(x -2) x
2
x (x +2)
(k )
=
x (x -2) x +2
(k ) 2
22
2
即x
(k +1)
=x -
x
(k )
[(x
(k )
) -2]
[x ]+2
计算结果见343页表4.2-2
4.2.2 多元非线性方程组
f (x ) = 0 (4.1-1)
⎧f 1(x 1, x 2,..., x n ) =0
⎪
⎪f 2(x 1, x 2,..., x n ) =0
⎨
⎪
⎪⎩f n (x 1, x 2,..., x n ) =0
1. Newdon迭代公式
线性化 设f (x ) = [f 1(x ) ，f 2(x ) ，…，f n (x )]T 在点x (k ) 处可微，将f i (x ) 在点x (k ) 处展开
n
f i (x ) =f i (x
(k )
) +
∑
j =1
∂f i (x
(k )
)
∂x j
(x j -x j ) +
(k )
用线性函数近似表示，即有
n
f i (x
(k )
) +
∑
j =1
∂f i (x
(k )
)
∂x j
(x j -x j ) =0 (i = 1，2，…，n )
(k )
其矩阵形式：f (x (k ) ) + Df (x (k ) )( x – x (k ) ) = 0 (4.2-1)
⎡∂f 1⎢∂x ⎢1(k )
其中Df (x ) =⎢
∂f ⎢n ⎢∂x 1⎣
∂f 1⎤∂x n ⎥
⎥(k )
是f (x ) 在点x 处的Jacobi 矩阵 ⎥∂f n
⎥
∂x n ⎥(k )
⎦x =x
若Df (x (k ) ) 可逆，则由(4.2-1)解出x = x (k ) – [Df (x (k ) )]-1f (x (k ) ) 令x (k +1) = x (k ) – [Df (x (k ) )]-1f (x (k ) ) (4.2-2)
称(4.2-2)为解方程组(4.2-1)的Newdon 迭代公式，其迭代函数为 x – [Df (x )]-1f (x )
注：由于求逆较难，一般可解方程组： Df (x (k ) ) Δx (k ) = – f (x (k ) )
求得Δx (k ) = x (k +1) – x (k ) 即得迭代公式：
⎧Df (x (k ) ) ∆x (k ) =-f (x (k ) )
k = 0，1，2，… (4.2-3) ⎨(k +1)
(k ) (k ) =x +∆x ⎩x
2. 收敛性
定理4.2-1 设x *是f (x ) 的零点，f (x ) 在x *的某一领域N 内二次连续可微，且Df (x *) 可逆，则
存在闭球S = {x | ||x – x *|| ≤ δ} ⊆ N，由S 内任一点x (0)出发，按公式(4.2-2)产生的序列{x (k ) }被包含在S 内（x (0) ∈ S ⇒ {x (k ) } ⊆ S），且有||x (k +1) – x *|| ≤ C ||x (k ) – x *||2，其中C 与k 无关。
证明：因为Df (x ) 在x *处连续，且Df (x *) 可逆，故存在δ > 0，使在S = {x | ||x – x *|| ≤ δ} ⊆ N上Df (x ) 可逆，且f 二次连续可微于S 。又因为f (x *) = 0，所以若x (k ) ∈ S，就有 x (k +1) – x * = x (k ) – x * – [Df (x (k ) )]-1[f (x (k ) ) –f (x *)] （f (x *) = 0） = [Df (x (k ) )] -1[f (x (k ) ) –f (x *) + Df (x (k ) )(x (k ) – x *)]
⇒ ||x (k +1) – x *|| ≤ ||[Df (x (k ) )] -1|| || f(x (k ) ) –f (x *) + Df (x (k ) )(x (k ) – x *)|| ≤ ||[Df (x (k ) )] -1|| max{||D 2f (x * – t(x (k ) – x *))||：0 ≤ t ≤ 1} ||x (k ) – x *||2
因为f 在S 上二次连续可微，所以max{||D 2f (x * – t (x (k ) – x *))||：0 ≤ t ≤ 1} ≤ M [Df (x (k ) )] -1在S 上连续，所以||[Df (x (k ) )] -1|| ≤ D ，这里M 、D 与k 无关。 ⇒ ||x (k +1) – x *|| ≤ D M ||x (k ) – x *||2 = C ||x (k ) – x *||2 .
只要C δ
||x ||x
(k +1) (k )
-x ||
*
2
*
-x ||
→C ≠0知，Newton 法是局部二阶收敛的。
例3 用Newton 法求非线性方程组
⎧x 1+2x 2-3=0
⎨22
⎩2x 1+x 2-5=0
在点(1，5，1) 附近的根。
⎡x 1+2x 2-3⎤
解：f (x ) =⎢2
2⎥,
2x +x -52⎣1⎦
⎡1
Df (x ) =⎢
⎣4x 1
2⎤⎥ 2x 2⎦
由迭代公式
⎧Df (x (k ) ) ∆x (k ) =-f (x (k ) )
⎨(k +1)
(k ) (k ) =x +∆x ⎩x
有
(k )
⎧⎡12⎤(k ) ⎡x 1(k ) +2x 2⎤-3
∆x =-⎪⎢(k ) ⎢⎥(k ) ⎥(k ) 2(k ) 2
2x 2⎦2(x ) +(x ) -5⎨⎣4x 112⎣⎦
⎪(k +1) (k ) (k ) x =x +∆x ⎩
从x (0) = (1，5，1) T 出发，计算结果见p345表4.2-3。
注：虽然Newton 法收敛较快，但
(1) 要求x (0)充分靠近x *才能保证其收敛性
(2) 每一次迭代须解方程组Df (x (k ) ) Δx (k ) = – f (x (k ) ) 当Df (x (k ) ) 不可逆时无法继续
3. 改进——Newton 下山法
为改善对初始值的要求，在迭代公式中引入松弛因子ωk ： x (k +1) = x (k ) – ωk [Df (x (k ) )]-1f (x (k ) ) 或Df (x (k ) ) Δx (k ) = –ωk f(x (k ) )
其中ωk 的选取满足：||f (x (k +1))||
122, 1
2
,... 进行“试探”，直到(4.2-10)满足，再进行下一次迭代，若选
不到ωk ，则Newton 下山法失败 方法(2) 求m in ||f (x
ω>0
(k )
-ω(Df (x
(k )
)
-1
f (x
(k )
)) ||的最小值点ω
*
令x (k +1) = x (k ) – ω*[Df (x (k ) )]-1f (x (k ) )
这样迫使序列{|| f(x (k ) )||}严格单调下降，从而从某个x (k ) 开始进入x *的附近。
4.3 无约束优化问题的下降迭代法
问题：求函数F(x)的最小值，即确定x * ∈ R n 使 F (x ) =m in n F (x )
x ∈R
*
注：(1) 该问题为最优化理论中无约束化问题 (2) 上述最小值点记为 x =arg m in n F (x )
x ∈R
*
4.3.0 预备知识
(1) 设F(.)具二阶连续偏导数，记
⎡∂F (x ) ⎤⎢∂x ⎥
1
⎢⎥
g (x ) =∇F (x ) = F 的梯度 ⎢⎥
∂F (x ) ⎢⎥⎢∂x n ⎥⎣⎦
g 为多元向量值函数，故有Jacobi 阵：
⎡∂2F ⎢2
∂x 1⎢2⎢∂F
H (x ) =Dg (x ) =⎢∂x ∂x
⎢21⎢ 2⎢∂F ⎢∂x n ∂x 1⎣
∂F ∂x 1∂x 2∂F ∂x 2 2∂F
222
∂x n ∂x 2
2
∂F ⎤
⎥
∂x 1∂x n
⎥2
∂F ⎥∂x 2∂x n ⎥
⎥ ⎥2
∂F ⎥
2
∂x n ⎥⎦
称为F 的Hesse 矩阵
(2) 泰勒展开：
F (x ) =F (y ) +[g (y )](x -y ) +
T T
12
(x -y ) H (x )(x -y ) +... 12
T
(x -y ) H (x )(x -y ) +...
T
=F (y ) +[∇F (y )](x -y ) +d dt
n
(3) F (x +tp ) =
∑
i =1
∂F (x +tp )
∂x i
T
p i =[∇F (x +tp )]p
T
(4) 设F (x ) =
12
x Ax +b x +c ——二次函数，其中A 正定，b 为向量
T
则∇F (x ) = Ax + b 其中∇(
12
x Ax ) =Ax , ∇(b x ) =b
*
T
T
(5) 下降迭代法——求x =arg m in F (x )
x ∈R
n
目标：构造使F(x)逐步严格下降（递减）的迭代序列： F (x (k +1))
想法：设已有点x (k ) ，若从x (k ) 出发沿任何方向移动F(x)都不再严格减少，则x (k ) 为局部最小值点。若至少有一个方向，使F(x)严格减少，则从中任选一方向pk ，并在此方向上移动一步：
x (k +1) = x (k ) + t k p k (4.3-1) 其中t k > 0（称为步长因子）使
F (x (k +1)) = F (x (k ) + t k p k )
若此方法产生的序列{x (k ) }收敛于x *，则此方法有效，否则无效。 方法：不同规则对应不同的方法。
注：(1) 下降方向p k 的选取： 由泰勒展式知，当t 充分小时
F (x (k ) + tp k ) = F (x (k ) ) + t [∇F (x (k ) )]T p k +o(t ) = F (x (k ) ) + t g k T p k +o(t ) 其中o(t ) 为t 的高阶无穷小，g k = ∇F (x (k ) )
由(4.3-2)知，应有g k T p k
例如取p k = – g k （F(x)沿负梯度方向下降最快）称为最速下降 (2) 步长因子的选取：
t k 可沿射线x = x (k ) + tp k (t > 0) 进行一维搜索来确定
例如，取 t k = argminF(x (k ) + tp k ) (4.3-4) 称为最佳步长因子 实际计算不易求得，通常求不精确最佳步长因子 例如，使用“成功-失败”试探法
先取定一步长因子λ，若F(x (k ) + λp k )
4.3.1 最速下降法
1. 迭代公式
取p k = – g k ( = ∇F (x (k ) )) 即为最速下降法，其迭代公式（以选最佳步长因子为例）
(k )
⎧-tg k ) ⎪t k =arg min F (x
t >0 k = 0，1，2，... (4.3-5) ⎨(k +1) (k )
⎪x =x -t k g k ⎩
例1 设F (x ) =
12
x Ax +b x +c (4.3-6)
T T
——二次函数，其中A 正定，则
t k =
g k g k g k Ag
T
k T
——可以求出最佳步长因子t k
事实上：因为g (x ) = ∇F (x ) = Ax + b 所以g k = Ax (k ) + b
⇒ g k +1 = Ax (k +1) + b = A (x (k ) – t k g k ) + b = Ax (k ) + b – t k Ag k =g k – t k Ag k 另一方面： t k =arg m in F (x
t >0
(k )
-tg k )
所以而
d dt
d dt
F (x
(k )
-t k g k ) =0
T
F (x -tg ) =-[∇F (x -tg )]g
所以 – [∇F (x (k ) – t k g k )]T g k = – [∇F (x (k +1))]T g k = – g k +1T g k = 0 (4.3-7) 从而0 = [g k – t k Ag k ]T g k = g k T g k – t k g k T Ag k ⇒ t k =
g k g k g k Ag
T
k T
(4.3-8)
所以二次函数(4.3-6)最速下降法的迭代公式为
x
(k +1)
=x
(k )
-
g k g k g k Ag k
T
T
g k k = 0，1，2，... (4.3-9)
2. 算法流程图
求F(x)的最小值
注：因为最优因子t k 满足：g k +1T g k = 0 (4.3-7)
所以方向p k +1与p k 总是互相垂直的，称为锯齿状下降（图4.3-1）此方向在接近极小值点时收敛速度变慢。
例1 用最速下降法求解极值问题m in F (x 1, x 2) ，其中F (x 1，x 2) = 2x 12 + 2x 1x 2 + 5x 22，
x 1, x 2
取x (0) = [1，-1]T 出发。
解：F(x)是二次函数，且g (x ) =∇F (x ) =⎢⎥, A =⎢
⎣2⎣2x 1+10x 2⎦见p350
⎡4x 1+2x 2⎤
⎡4
2⎤⎥ 10⎦
4.3.2 变尺度法
1. 思想
为了改善收敛速度，考虑在x*处的泰勒展开：
F (x ) ≈F (x ) +[g (x )](x -x ) +
*
*
T
*
12
(x -x ) H (x )(x -x )
*T **
因为g (x *) = 0 所以 F (x ) ≈F (x ) +
*
12
(x -x ) H (x )(x -x )
12
x Ax ) =Ax >
T
*T **
⇒ ∇F (x ) = g (x ) ≈ H(x *)(x – x *)
设H 正定（从而可逆），设H(x *)(x – x *) = g (x )
⇒ x * = x – [H(x *)]-1g (x ) = x – Bg (x ) (4.3-10)
上式表明：用B = [H(x *)]-1作用于– g (x ) ，将使最速下降方向– g (x ) 变为直指x * 启示：用–Bg (x ) 作搜索方向。
2. 迭代公式
为了保证–Bg (x ) 是下降方向，由(4.3-3)知，只须g (x ) T (–Bg (x )) 0。 所以当B 正定时（g (x ) T Bg (x ) > 0），必有–Bg (x ) 为下降方向，从而迭代公式为 x (k +1) = x (k ) – t k B k g k k = 0，1，2，... (4.3-11) 其中t k 为步长因子，可通过一维搜索来确定
注：(1) 当 B k = I 时，(4.3-11)即为最速下降法的迭代公式 (2) 当B k = [H(x (k ) )]-1时，迭代公式为
x (k +1) = x (k ) – t k [H(x (k ) )] -1g k k = 0，1，2，... (4.3-12) = x (k ) – t k [Dg (x (k ) )] -1g k (Dg (x (k ) ) 为g 的Jacobi 矩阵) 即为Newdon 下山法
(3) 由于F(x)的Hesse 矩阵H(x ) = Dg (x ) 之逆可能在某些点不存在，即使存在，计算量也很大，所以考虑从[H(x (k ) )] -1的近似方阵出发，每次迭代进行修正（下述方法）。
3. DFP方法
考虑对B k = [H(x (k ) )] -1附加条件 (1) B k 应正定
(2) 从B k 到B k +1应简单：B k +1= B k + ΔB k
(3) B k 满足拟Newdon 条件：B k +1y k = s k ，其中y k = g k +1 – g k ，s k = x (k +1) – x (k ) 从而(ΔB k ) yk = s k –B k y k ，
设ΔB k = s k v k T –B k y k w k T ，(v k ，w k 待定) 解之得∆B k =
s k s k
T
T
s k y k
-
B k y k y k B k y k B k y k
T
T
(4.3-20)
(4.3-20)称为DFP 方法 注：(1) 通常取B 0 = I
(2) DFP方法很有效，但由于舍入误差的影响，可能破坏B k 的正定性，使计算失效。可采用重置措施：即当函数值不下降时取B k = I ，继续迭代，并且当迭代n + 1次后，令x(0) = x(n+1)，B n = I ，重新迭代
例2 用DFP 方法求解min F (x 1，x 2) ：F (x 1, x 2) =
⎛-2⎫= 4⎪⎪, ⎝⎭
⎛3
F (x 1, x 2) =(x 1, x 2) 2
1 - ⎝2
⎛3x 1-x 2-2⎫
⎪, ⎪
⎝x 2-x 1⎭
32
x 1+
2
12
x 2-x 1x 2-2x 1
2
-
取x
(0)
1⎫⎪x 1⎫2⎪-(2, 0) ⎛ x ⎪⎪ 1⎪
⎝2⎭⎪
2⎭
-1⎫⎪ ⎪1⎭
解：g (x ) =∇F (x ) =
⎛3
H (x ) = -1
⎝
4. BFGS方法
B k +1=B k +
1s k y k
T
[(1+
y k B k y k s k y k
T
T
) s k s k
T
-B k y k s k
T
-s k y k B k ] (4.3-21)
T
第4章 计算函数零点和极值点的迭代法
本章讨论非线性方程（组）的求解问题
4.1 不动点迭代法及其收敛性
1．不动点
设非线性方程组f (x ) = 0 (4.1-1) 等价： x = Φ(x ) (4.1-2)
则有迭代格式：x (k +1) = Φ(x (k ) ) ，k = 0，1，2，…
若Φ连续，且迭代序列{x (k ) }收敛到x *，则两边取极限得x * = Φ(x *) ，即x *满足(4.1-2)，从而满足(4.1-1)，即x *为f 零点。 称x *为Φ(x ) 的不动点。
注：(1) 求零点⇔求不动点
(2) Φ(.)称为迭代函数，{x (k ) }称为迭代序列
(3) 不同方法构造迭代函数，得不同的迭代序列
2．迭代法的基本问题
(1) 如何构造适当的迭代函数Φ(.)使迭代序列{x (k ) }收敛 (2) 收敛的速度和误差 (3) 如何加速
4.1.1 解一元方程的迭代法
1. 根的隔离
设一元方程f (x ) = 0，f 连续，其实根可能有很多，需将各根隔离，即f 在[a ，b ]内有且仅有一根。
方法：设f ∈C[a ，b ]，f (a ) f (b )
2. 迭代序列的收敛性
因为可以有多种迭代函数，所产生的迭代序列{x (k ) }有可能： (1) 收敛快 (2) 收敛慢 (3) 不收敛
例1 f (x ) = x 3 – x – 1 = 0，求f 在x = 1.5附近的根，初值取x (0) = 1.5。(p328) 取ϕ(x ) =
3
1+x ——收敛
取ϕ(x ) = x 3 – 1——不收敛
定理4.1-1 (1) 设ϕ(x ) ∈ C[a ，b ]，且对于任意x ∈ [a ，b ]有ϕ (x ) ∈ [a ，b ]，则ϕ在[a ，b ]上必有不动点。 (2) 进一步，若ϕ(x ) ∈ C1[a ，b ]，且存在L
x x
(k )
-x -x
*
≤≤
L 1-L L
k
x x
(k )
-x -x
(k -1)
(4.1-5)
(1)
(0)
(k ) *
1-L
证明：(1) 若ϕ(a ) = a 或ϕ(b ) = b ，则结论显然成立
现设a 0，ψ(b ) = ϕ(b ) – b
(2) 设ϕ(x ) ∈ C1[a ，b ]，且满足(4.1-4)，若有x 1*，x 2* ∈ [a ，b ]，x 1* ≠ x 2*，ϕ(x i *) = x i * i = 1，2 由微分中值定理，|x 1* – x 2*| = |ϕ(x 1*) – ϕ (x 2*)| = |ϕ'(ξ)| |x 1* – x 2*| ≤ L|x 1* – x 2*|
由|x (k ) – x *| = |ϕ( x(k -1) ) – ϕ (x *)| ≤ L |x (k -1) – x *| ≤ … ≤ L k|x (0) – x *| 及0
k →∞
(k )
-x |=0
*
即x (k ) 收敛于x *。
并且由|x (k ) – x *| ≤ L |x (k -1) – x *|得 |x (k ) – x *| ≤ L |x (k -1) – x (k ) + x(k ) – x *| ≤ L |x (k -1) – x (k ) | + L|x(k ) – x *| 从而有x
(k )
-x
*
≤
L 1-L
x
(k )
-x
(k -1)
又因
|x (k ) – x (k -1) | = |ϕ(x (k -1) ) – ϕ (x (k -2) )| ≤ L | x (k -1) – x (k -2) | ≤ …≤ L k-1| x (1) – x (0)|，代入上式的右边，即得 x
(k )
-x
*
≤
L
k
1-L
x
(1)
-x
(0)
注：(1) 若L ≈ 1，则收敛很慢，须考虑加速问题 (2) (4.1-5)中第一式为后验公式—迭代停止准则 第二式为先验公式—预测迭代次数
(3) 定理是以[a ，b ]中任一点作初值，迭代都收敛，称为全局收敛。 （此要求较难满足，故考虑在） x *的某一邻域内—局部收敛性
定理4.1-2 设x *为ϕ的不动点，ϕ ' 在x *的某邻域内连续，且|ϕ '(x *)| 0，只要x (0) ∈ [x * –δ，x * + δ]，迭代法x (k +1) = ϕ(x (k ) ) 收敛。
证明：∵|ϕ'(x *)| 0，使[x * –δ，x * + δ] ⊂ U (x *) ，且 ∀ x ∈ [x * –δ，x * + δ]有|ϕ '(x )| ≤ q
注：只要x (0)充分接近x *，且|ϕ '(x (0))| 明显小于1，则{x (k ) }收敛于x *。 例2 求方程x = e–x 在0.5附近的根。
由于|ϕ '(0.5)| = e–0.5 ≈ 0.61明显小于1，故收敛
3. 收敛阶
定义4.1-1 设x (k ) → x *，记e k = x(k ) - x * 若存在p ≥ 1，及c ≠0，使lim
|e k +1||e k |
p
k →∞
=c 则称{x (k ) }是p 阶收敛的，或称收敛阶为p （p
越高收敛越快） 注：
(1) p = 1，0 1，称超线性收敛 (3) p = 2，称平方收敛
因为| x (k +1) –x *| = |ϕ(x (k ) ) – ϕ(x *)| = |ϕ'(ξ)| |x (k ) – x *|，其中ξ在x (k ) 和x *之间。 则lim
|e k +1||e k |
p
k →∞
=|ϕ' (x ) |
*
所以若ϕ '(x *) ≠ 0，则为线性收敛
想得到更高阶的收敛性，须ϕ '(x *) = 0，通常可考虑麦克劳林展式。
定理4.1-3 设x *为ϕ的不动点，正整数p ≥ 2，若ϕ(p ) 在x *的某邻域内连续，且满足
⎧ϕ(k ) (x *) =0, ⎨(p ) *
⎩ϕ(x ) ≠0
k =1, 2,..., p -1
(4.1.6)
则{x (k ) }p 阶局部收敛。
证明：∵ϕ '(x *) = 0(
x +
(k +1)
=ϕ(x (x )
*
(k )
) =ϕ(x ) +ϕ' (x )(x
(k )
**(k )
-x ) +
(k )
*
ϕ" (x )
2!
*
p
*
(x
(k )
-x ) +...
*2
ϕ
(p -1)
(p -1)!
(x -x )
*p -1
+
ϕ
(p )
(ξ)
p !
(x -x )
由(4.1-6)知，
x
(k +1)
-x =ϕ(x
*(k )
) -ϕ(x ) =
*
ϕ
(p )
(ξ)
p !
(x
(k )
-x )
*p
所以
x (x
(k +1) (k )
-x
*
*p
-x )
=
ϕ
(p )
(ξ)
p !
→
ϕ
(p )
(x )
*
p !
≠0
即{x (k ) }p 阶局部收敛。
例3 设f ∈ C2[a ，b ]，ϕ (x ) = x – r 1(x ) f (x ) – r 2(x ) f 2(x ) ，x *为f 的单重零点。试确定未知函数r 1(x ) 、r 2(x ) ，使迭代法x (k +1) = ϕ(x (k ) ) 至少是三阶局部收敛的。解：由定理4.1-3知，应有ϕ '(x *) = ϕ "(x *) = 0因为ϕ '(x ) = 1 – r 1'(x ) f (x ) – r 1(x ) f '(x ) – r 2'(x ) f 2(x ) – 2r 2(x ) f (x ) f '(x ) 而f (x *) = 0，f '(x *) ≠ 0（单重零点），令ϕ '(x *) = 0，有1 – r 1'(x *) f '(x *) = 0即取r 1(x ) =
1f ' (x )
，则有ϕ '(x *) = 0
此时有ϕ '(x ) = – r 1'(x ) f (x ) – r 2'(x ) f 2(x ) – 2r 2(x ) f (x ) f '(x )
⇒ ϕ "(x ) = – r 1"(x ) f (x ) – r 1'(x ) f '(x ) – r 2"(x ) f 2(x ) – 4r 2'(x ) f (x ) f '(x ) – 2r 2(x )[f '(x )]2– 2r 2'(x ) f (x ) f "(x ) 其中r 1' (x ) =
-f " (x ) [f ' (x )]
2
*
令ϕ"(x ) = 0，有
*
f " (x ) f ' (x )
*
-2r 2(x )[f ' (x )]=0，即取
**2
r 2(x ) =
f " (x ) 2[f ' (x )]
3
，则有ϕ"(x *) = 0从而只要同时取r 1' (x ) =
-f " (x ) [f ' (x )]
2
，r 2(x ) =
f " (x ) 2[f ' (x )]
3
，
迭代法至少具有三阶局部收敛性。
4. 加速
幂法中曾有Aitken 加速，这里使用相同的思想 若x → x ，由中值定理， x
(k )
*
(k +1)
– x = ϕ (x ) –ϕ (x ) = ϕ'(ξ1)(x – x ) ⇒
*(k ) *(k ) *
x
(k +1) (k )
-x -x
*
*
*
x
=ϕ(ξ1)
'
ξ1在x 和x 之间x
(k ) *(k +2)
– x = ϕ (x
*(k +1)
) –ϕ (x ) = ϕ'(ξ2)(x
*(k +1)
– x ) ⇒
*
x x
(k +2) (k +1)
-x -x
*
=ϕ(ξ2) ξ2
'
在x (k +1)和x *之间因为x (k ) → x *，所以当k 充分大时，ϕ '(ξ1) ≈ ϕ '(ξ2) 即
x x
(k +2) (k +1)
-x -x
**
≈
x
(k +1) (k )
-x -x
*
*
x
⇒x ≈x
*(k +2)
-
(x x
(k +2)
-x
(k +1)
)
2(k )
(k +2)
-2x
(k +1)
+x
(4.1-7)
ˆ记x
(k +2)
=x
(k +2)
-
(x x
(k +2)
-x
(k +1)
)
2(k )
(k +2)
-2x
(k +1)
+x
ˆ，则{x
(k )
}比{x (k ) }收敛得快。
e k +1e k
定理4.1-4 设{x (k ) }线性收敛于x *，且∀k ≥ 0，e k = x (k ) – x * ≠ 0 lim (线性收敛) 则lim
ˆ(k ) -x *x x
(k )
k →∞
=λ 0
k →∞
-x
*
=0
证明：因为lim
e k +1e k
k →∞
=λ
所以e k +1 = (λ +εk ) e k ，其中εk → 0
⇒ x (k +1) – x (k ) = x (k +1) – x * – (x (k ) – x *) = e k +1 – e k = [(λ – 1) + εk ]e k 又
x (k +2) – 2x (k +1) + x (k ) = (x (k +2) – x (k +1)) – (x (k +1) – x (k ) ) = [(λ – 1) + εk +1]e k +1 – [(λ – 1) + εk ]e k
= [(λ – 1) + εk +1](λ + εk ) e k – [(λ – 1) + εk ]e k = [(λ – 1)2 + μ k ]e k .
其中μ k = λεk +1 +(λ – 2 )εk +εk +1εk → 0
ˆx
(k +2)
=x =x
(k +2)
-
(x x (x
(k +2)
-x
(k +1)
)
2(k )
(k +2)
-2x
(k +1) (k )
+x
2
=
x x
(k +2) (k +2)
⋅x
(k )
-(x
(k +1)
(k +1)
)
2
-2x +x
(k )
(k +1)
(k )
-
-x )
x
(k +2)
-2x
(k +1)
+x
(k )
所以
ˆx
(k +2)
-x =x
*(k )
-x -
*
(x x
(k +1)
-x
2
(k )
)
2(k )
(k +2)
-2
2
(k +1)
-x
=e k -
[(λ-1) +εk ]e k
2
[(λ-1) +μk ]e k
[(λ-1) +εk ]
2
2
=e k -e k
[(λ-1) +μk ]
⇒ lim
ˆ(k +2) -x *x x
(k +2)
k →∞
-x
*
=lim
e k e k +1
k →∞
(1-
[(λ-1) +εk ]
2
[(λ-1) +μk ]
) =0
注：(1) (4.1-7)成为Aitken 加速
⎧(k ) (k )
y =ϕ(x ) ⎪⎪⎪(k ) (k )
(2) ⎨z =ϕ(y ) k = 1，2，…
⎪
(k ) (k ) 2(z -y ) ⎪(k +1) (k )
x =z -(k )
(k ) (k ) ⎪z -2y +x ⎩
称为史蒂文生迭代法。
例4 用迭代法和Steffensen 迭代法求函数f (x ) = x – lnx – 2在区间(2，+∞) 内的零点，取x (0) = 3. 解：将f (x ) = 0化为等价的方程x = lnx + 2 = ϕ (x ) ，由于ϕ '(x ) = 1/x 在[2，+∞) 上满足|ϕ '(x )| ≤ 1/2
⎧(k ) (k )
y =ln x +2⎪⎪⎪(k ) (k )
=ln y +2 ⎨z
⎪
(k ) (k ) 2(z -y ) ⎪(k +1) (k )
x =z -(k )
(k ) (k ) ⎪z -2y +x ⎩
取初值x (0) = 3作迭代，结果见p336
迭代法x (k +1) = ln x(k ) + 2： x0=3 k=1
x1=log(x0)+2
while (abs(x1-x0)>0.0000001)
x0=x1;k=k+1 x1=log(x0)+2 end
Steffensen 迭代法 x0=3 k=1
y=log(x0)+2 z=log(y)+2
x1=z-(z-y)^2/(z-2*y+x0)
while (abs(x1-x0)>0.0000001) x0=x1;k=k+1 y=log(x0)+2 z=log(y)+2
x1=z-(z-y)^2/(z-2*y+x0) end
4.1.2 解非线性方程组的迭代法
设非线性方程组f (x ) = 0 (4.1-1)
⎧f 1(x 1, x 2,..., x n ) =0⎪
⎪f 2(x 1, x 2,..., x n ) =0
⎨
⎪
⎪⎩f n (x 1, x 2,..., x n ) =0
考虑等价形式
x = Φ(x ) (4.1-2)
迭代公式x (k +1) = Φ(x (k ) ) k = 0，1，2，… (4.1-3) 其收敛性有下述压缩映射（不动点）原理
Th4.1-5 设Φ在闭区域G =R n 上满足条件
(1) 存在q ，0
(1) 存在唯一不动点x *∈G ，且∀ x(0)∈G ，迭代向量列收敛于x *。 (2)
x
(k )
-x
*
≤
q 1-q q
k
x
(k )
-x
(k -1)
x
(1)
x
(k )
-x
*
≤
1-q
-x
(0)
证明与Th2.4-3相似 注：
(1) Φ(G ) ⊆G 保证序列{x (k ) }⊆G
(2) 若ϕi (x ) 在G 上可微，Φ(x ) = (ϕ1(x ) ，ϕ2(x ) ，…，ϕn (x )) T
⎡∂ϕ1⎢∂x ⎢1
记D Φ(x ) =⎢
∂ϕn ⎢⎢∂x 1⎣
∂ϕ1⎤∂x n ⎥
⎥
，则压缩条件可用下式替代 ⎥∂ϕn
⎥∂x n ⎥
⎦
∀x ∈G ⇒D Φ(x ) ≤q
例5
4.2 Newton 迭代法及其变形
4.2.1 一元非线性方程
f (x ) = 0
1. 牛顿迭代方法
线性化： 设f (x ) 在点x (k ) 处可微，则展开
f (x ) =f (x
(k )
(k ) (k )
) +f '(x )(x -x ) +
f ''(ξ) 2!
(x -x
(k )
)
2
用线性部分近似表示
f (x ) ≈ f (x (k ) ) + f '(x (k ) )( x – x (k ) )
即考虑方程f (x (k ) ) + f '(x (k ) )( x – x (k ) ) = 0 若f '(x ) ≠ 0，则有x =x
(k )
(k )
-
f (x
(k )
)
(k )
f '(x )
令：x
(k +1)
=x
(k )
-
f (x f '(x
(k ) (k )
) )
k = 0，1，2，… (4.2-4)
称为Newton 迭代公式，其迭代函数为
ϕ(x ) =x -
f (x ) f '(x )
(4.2-5)
2. 收敛性
(1) 若x *是f (x ) 的单重根： f (x *) = 0，f '(x *) ≠ 0 因为ϕ'(x ) =
*
**f (x ) f ''(x ) *2
[f '(x )]
=0, ϕ''(x ) =
*
*
f ''(x ) *
f '(x )
一般不为0
所以，牛顿法是局部二阶收敛的 ——由定理4.1-3
例1 用Newton 法求非线性方程f (x ) = x e x – 1 = 0在(0，1) 内的根，取x (0) = 0.5。 解：因为f (x ) = (1 + x )e x ，故其Newton 迭代公式为
x
(k +1)
=x
(k )
-
x
(k )
e
x
(k )
-1
x
(k )
(1+x
(k )
，k = 0，1，2，…
) e
从x (0) = 0.5出发，计算结果见p342表4.2-1。
(2) 若x *是f (x ) 的重根，即有f (x ) = (x – x *) m g (x ) ，其中g (x *) ≠ 0，m ≥ 2 因为f '(x ) = m (x – x *) m -1g (x ) + (x – x *) m g '(x ) 记x = x + h ，则ϕ(x +h ) =(x +h ) -
*
***
h g (x +h )
mh
m -1
*
g (x +h ) +h g '(x +h )
*
m
m *
=ϕ(x ) +h -
*
hg (x +h )
mg (x +h ) +h g '(x +h )
*
*
⇒ϕ'(x ) =lim
*
ϕ(x +h ) -ϕ(x )
h
**
h →0
=lim (1-
h →0
g (x +h )
mg (x +h ) +h g '(x +h )
*
*
*
) =1-
1m
当m ≥ 2时，ϕ '(x *) ≠ 0，由|ϕ '(x *)|
x
(k +1)
f (x ) f '(x )
，易知有ϕ '(x *) = 0所以，若事先知道x *的重数，则
=x
(k )
-m
f (x
(k )
)
(k )
f '(x )
(4.2-6)
此时，迭代序列{x (k ) }是二阶收敛的。 或令u (x ) =
f (x ) f '(x )
，则x *是u (x ) 的单重零点，应用Newdon 法于u (x ) ，有
x
(k +1)
=x
(k )
-
u (x
(k )
)
(k )
u '(x )
=x
(k )
-
f (x
(k )
(k )
) f '(x )
(k ) 2(k ) (k )
[f '(x )]-f (x ) f ''(x )
(4.2-7)
迭代序列也是二阶收敛的
例2 2是方程x – 4x + 4 = 0的二重根
42
(1) 采用Newdon 法 ϕ(x ) =x -
x -4x +44x -8x
34
2
=x -
(x -2)
2
22
4x (x -2)
=x -
x -24x
2
即x
(k +1)
=x
(k )
-
(x
(k )
) -2
(k )
2
4x
(2) 采用(4.2-6)
x
(k +1)
=x
(k )
-
(x
(k )
) -2
(k )
2
2x
(3) 采用(4.2-7)
u (x ) =
x -24x
2
2
1x +2
，u '(x ) =() 2
4x
2
2
u (x ) u '(x )
=
(x -2) x
2
x (x +2)
(k )
=
x (x -2) x +2
(k ) 2
22
2
即x
(k +1)
=x -
x
(k )
[(x
(k )
) -2]
[x ]+2
计算结果见343页表4.2-2
4.2.2 多元非线性方程组
f (x ) = 0 (4.1-1)
⎧f 1(x 1, x 2,..., x n ) =0
⎪
⎪f 2(x 1, x 2,..., x n ) =0
⎨
⎪
⎪⎩f n (x 1, x 2,..., x n ) =0
1. Newdon迭代公式
线性化 设f (x ) = [f 1(x ) ，f 2(x ) ，…，f n (x )]T 在点x (k ) 处可微，将f i (x ) 在点x (k ) 处展开
n
f i (x ) =f i (x
(k )
) +
∑
j =1
∂f i (x
(k )
)
∂x j
(x j -x j ) +
(k )
用线性函数近似表示，即有
n
f i (x
(k )
) +
∑
j =1
∂f i (x
(k )
)
∂x j
(x j -x j ) =0 (i = 1，2，…，n )
(k )
其矩阵形式：f (x (k ) ) + Df (x (k ) )( x – x (k ) ) = 0 (4.2-1)
⎡∂f 1⎢∂x ⎢1(k )
其中Df (x ) =⎢
∂f ⎢n ⎢∂x 1⎣
∂f 1⎤∂x n ⎥
⎥(k )
是f (x ) 在点x 处的Jacobi 矩阵 ⎥∂f n
⎥
∂x n ⎥(k )
⎦x =x
若Df (x (k ) ) 可逆，则由(4.2-1)解出x = x (k ) – [Df (x (k ) )]-1f (x (k ) ) 令x (k +1) = x (k ) – [Df (x (k ) )]-1f (x (k ) ) (4.2-2)
称(4.2-2)为解方程组(4.2-1)的Newdon 迭代公式，其迭代函数为 x – [Df (x )]-1f (x )
注：由于求逆较难，一般可解方程组： Df (x (k ) ) Δx (k ) = – f (x (k ) )
求得Δx (k ) = x (k +1) – x (k ) 即得迭代公式：
⎧Df (x (k ) ) ∆x (k ) =-f (x (k ) )
k = 0，1，2，… (4.2-3) ⎨(k +1)
(k ) (k ) =x +∆x ⎩x
2. 收敛性
定理4.2-1 设x *是f (x ) 的零点，f (x ) 在x *的某一领域N 内二次连续可微，且Df (x *) 可逆，则
存在闭球S = {x | ||x – x *|| ≤ δ} ⊆ N，由S 内任一点x (0)出发，按公式(4.2-2)产生的序列{x (k ) }被包含在S 内（x (0) ∈ S ⇒ {x (k ) } ⊆ S），且有||x (k +1) – x *|| ≤ C ||x (k ) – x *||2，其中C 与k 无关。
证明：因为Df (x ) 在x *处连续，且Df (x *) 可逆，故存在δ > 0，使在S = {x | ||x – x *|| ≤ δ} ⊆ N上Df (x ) 可逆，且f 二次连续可微于S 。又因为f (x *) = 0，所以若x (k ) ∈ S，就有 x (k +1) – x * = x (k ) – x * – [Df (x (k ) )]-1[f (x (k ) ) –f (x *)] （f (x *) = 0） = [Df (x (k ) )] -1[f (x (k ) ) –f (x *) + Df (x (k ) )(x (k ) – x *)]
⇒ ||x (k +1) – x *|| ≤ ||[Df (x (k ) )] -1|| || f(x (k ) ) –f (x *) + Df (x (k ) )(x (k ) – x *)|| ≤ ||[Df (x (k ) )] -1|| max{||D 2f (x * – t(x (k ) – x *))||：0 ≤ t ≤ 1} ||x (k ) – x *||2
因为f 在S 上二次连续可微，所以max{||D 2f (x * – t (x (k ) – x *))||：0 ≤ t ≤ 1} ≤ M [Df (x (k ) )] -1在S 上连续，所以||[Df (x (k ) )] -1|| ≤ D ，这里M 、D 与k 无关。 ⇒ ||x (k +1) – x *|| ≤ D M ||x (k ) – x *||2 = C ||x (k ) – x *||2 .
只要C δ
||x ||x
(k +1) (k )
-x ||
*
2
*
-x ||
→C ≠0知，Newton 法是局部二阶收敛的。
例3 用Newton 法求非线性方程组
⎧x 1+2x 2-3=0
⎨22
⎩2x 1+x 2-5=0
在点(1，5，1) 附近的根。
⎡x 1+2x 2-3⎤
解：f (x ) =⎢2
2⎥,
2x +x -52⎣1⎦
⎡1
Df (x ) =⎢
⎣4x 1
2⎤⎥ 2x 2⎦
由迭代公式
⎧Df (x (k ) ) ∆x (k ) =-f (x (k ) )
⎨(k +1)
(k ) (k ) =x +∆x ⎩x
有
(k )
⎧⎡12⎤(k ) ⎡x 1(k ) +2x 2⎤-3
∆x =-⎪⎢(k ) ⎢⎥(k ) ⎥(k ) 2(k ) 2
2x 2⎦2(x ) +(x ) -5⎨⎣4x 112⎣⎦
⎪(k +1) (k ) (k ) x =x +∆x ⎩
从x (0) = (1，5，1) T 出发，计算结果见p345表4.2-3。
注：虽然Newton 法收敛较快，但
(1) 要求x (0)充分靠近x *才能保证其收敛性
(2) 每一次迭代须解方程组Df (x (k ) ) Δx (k ) = – f (x (k ) ) 当Df (x (k ) ) 不可逆时无法继续
3. 改进——Newton 下山法
为改善对初始值的要求，在迭代公式中引入松弛因子ωk ： x (k +1) = x (k ) – ωk [Df (x (k ) )]-1f (x (k ) ) 或Df (x (k ) ) Δx (k ) = –ωk f(x (k ) )
其中ωk 的选取满足：||f (x (k +1))||
122, 1
2
,... 进行“试探”，直到(4.2-10)满足，再进行下一次迭代，若选
不到ωk ，则Newton 下山法失败 方法(2) 求m in ||f (x
ω>0
(k )
-ω(Df (x
(k )
)
-1
f (x
(k )
)) ||的最小值点ω
*
令x (k +1) = x (k ) – ω*[Df (x (k ) )]-1f (x (k ) )
这样迫使序列{|| f(x (k ) )||}严格单调下降，从而从某个x (k ) 开始进入x *的附近。
4.3 无约束优化问题的下降迭代法
问题：求函数F(x)的最小值，即确定x * ∈ R n 使 F (x ) =m in n F (x )
x ∈R
*
注：(1) 该问题为最优化理论中无约束化问题 (2) 上述最小值点记为 x =arg m in n F (x )
x ∈R
*
4.3.0 预备知识
(1) 设F(.)具二阶连续偏导数，记
⎡∂F (x ) ⎤⎢∂x ⎥
1
⎢⎥
g (x ) =∇F (x ) = F 的梯度 ⎢⎥
∂F (x ) ⎢⎥⎢∂x n ⎥⎣⎦
g 为多元向量值函数，故有Jacobi 阵：
⎡∂2F ⎢2
∂x 1⎢2⎢∂F
H (x ) =Dg (x ) =⎢∂x ∂x
⎢21⎢ 2⎢∂F ⎢∂x n ∂x 1⎣
∂F ∂x 1∂x 2∂F ∂x 2 2∂F
222
∂x n ∂x 2
2
∂F ⎤
⎥
∂x 1∂x n
⎥2
∂F ⎥∂x 2∂x n ⎥
⎥ ⎥2
∂F ⎥
2
∂x n ⎥⎦
称为F 的Hesse 矩阵
(2) 泰勒展开：
F (x ) =F (y ) +[g (y )](x -y ) +
T T
12
(x -y ) H (x )(x -y ) +... 12
T
(x -y ) H (x )(x -y ) +...
T
=F (y ) +[∇F (y )](x -y ) +d dt
n
(3) F (x +tp ) =
∑
i =1
∂F (x +tp )
∂x i
T
p i =[∇F (x +tp )]p
T
(4) 设F (x ) =
12
x Ax +b x +c ——二次函数，其中A 正定，b 为向量
T
则∇F (x ) = Ax + b 其中∇(
12
x Ax ) =Ax , ∇(b x ) =b
*
T
T
(5) 下降迭代法——求x =arg m in F (x )
x ∈R
n
目标：构造使F(x)逐步严格下降（递减）的迭代序列： F (x (k +1))
想法：设已有点x (k ) ，若从x (k ) 出发沿任何方向移动F(x)都不再严格减少，则x (k ) 为局部最小值点。若至少有一个方向，使F(x)严格减少，则从中任选一方向pk ，并在此方向上移动一步：
x (k +1) = x (k ) + t k p k (4.3-1) 其中t k > 0（称为步长因子）使
F (x (k +1)) = F (x (k ) + t k p k )
若此方法产生的序列{x (k ) }收敛于x *，则此方法有效，否则无效。 方法：不同规则对应不同的方法。
注：(1) 下降方向p k 的选取： 由泰勒展式知，当t 充分小时
F (x (k ) + tp k ) = F (x (k ) ) + t [∇F (x (k ) )]T p k +o(t ) = F (x (k ) ) + t g k T p k +o(t ) 其中o(t ) 为t 的高阶无穷小，g k = ∇F (x (k ) )
由(4.3-2)知，应有g k T p k
例如取p k = – g k （F(x)沿负梯度方向下降最快）称为最速下降 (2) 步长因子的选取：
t k 可沿射线x = x (k ) + tp k (t > 0) 进行一维搜索来确定
例如，取 t k = argminF(x (k ) + tp k ) (4.3-4) 称为最佳步长因子 实际计算不易求得，通常求不精确最佳步长因子 例如，使用“成功-失败”试探法
先取定一步长因子λ，若F(x (k ) + λp k )
4.3.1 最速下降法
1. 迭代公式
取p k = – g k ( = ∇F (x (k ) )) 即为最速下降法，其迭代公式（以选最佳步长因子为例）
(k )
⎧-tg k ) ⎪t k =arg min F (x
t >0 k = 0，1，2，... (4.3-5) ⎨(k +1) (k )
⎪x =x -t k g k ⎩
例1 设F (x ) =
12
x Ax +b x +c (4.3-6)
T T
——二次函数，其中A 正定，则
t k =
g k g k g k Ag
T
k T
——可以求出最佳步长因子t k
事实上：因为g (x ) = ∇F (x ) = Ax + b 所以g k = Ax (k ) + b
⇒ g k +1 = Ax (k +1) + b = A (x (k ) – t k g k ) + b = Ax (k ) + b – t k Ag k =g k – t k Ag k 另一方面： t k =arg m in F (x
t >0
(k )
-tg k )
所以而
d dt
d dt
F (x
(k )
-t k g k ) =0
T
F (x -tg ) =-[∇F (x -tg )]g
所以 – [∇F (x (k ) – t k g k )]T g k = – [∇F (x (k +1))]T g k = – g k +1T g k = 0 (4.3-7) 从而0 = [g k – t k Ag k ]T g k = g k T g k – t k g k T Ag k ⇒ t k =
g k g k g k Ag
T
k T
(4.3-8)
所以二次函数(4.3-6)最速下降法的迭代公式为
x
(k +1)
=x
(k )
-
g k g k g k Ag k
T
T
g k k = 0，1，2，... (4.3-9)
2. 算法流程图
求F(x)的最小值
注：因为最优因子t k 满足：g k +1T g k = 0 (4.3-7)
所以方向p k +1与p k 总是互相垂直的，称为锯齿状下降（图4.3-1）此方向在接近极小值点时收敛速度变慢。
例1 用最速下降法求解极值问题m in F (x 1, x 2) ，其中F (x 1，x 2) = 2x 12 + 2x 1x 2 + 5x 22，
x 1, x 2
取x (0) = [1，-1]T 出发。
解：F(x)是二次函数，且g (x ) =∇F (x ) =⎢⎥, A =⎢
⎣2⎣2x 1+10x 2⎦见p350
⎡4x 1+2x 2⎤
⎡4
2⎤⎥ 10⎦
4.3.2 变尺度法
1. 思想
为了改善收敛速度，考虑在x*处的泰勒展开：
F (x ) ≈F (x ) +[g (x )](x -x ) +
*
*
T
*
12
(x -x ) H (x )(x -x )
*T **
因为g (x *) = 0 所以 F (x ) ≈F (x ) +
*
12
(x -x ) H (x )(x -x )
12
x Ax ) =Ax >
T
*T **
⇒ ∇F (x ) = g (x ) ≈ H(x *)(x – x *)
设H 正定（从而可逆），设H(x *)(x – x *) = g (x )
⇒ x * = x – [H(x *)]-1g (x ) = x – Bg (x ) (4.3-10)
上式表明：用B = [H(x *)]-1作用于– g (x ) ，将使最速下降方向– g (x ) 变为直指x * 启示：用–Bg (x ) 作搜索方向。
2. 迭代公式
为了保证–Bg (x ) 是下降方向，由(4.3-3)知，只须g (x ) T (–Bg (x )) 0。 所以当B 正定时（g (x ) T Bg (x ) > 0），必有–Bg (x ) 为下降方向，从而迭代公式为 x (k +1) = x (k ) – t k B k g k k = 0，1，2，... (4.3-11) 其中t k 为步长因子，可通过一维搜索来确定
注：(1) 当 B k = I 时，(4.3-11)即为最速下降法的迭代公式 (2) 当B k = [H(x (k ) )]-1时，迭代公式为
x (k +1) = x (k ) – t k [H(x (k ) )] -1g k k = 0，1，2，... (4.3-12) = x (k ) – t k [Dg (x (k ) )] -1g k (Dg (x (k ) ) 为g 的Jacobi 矩阵) 即为Newdon 下山法
(3) 由于F(x)的Hesse 矩阵H(x ) = Dg (x ) 之逆可能在某些点不存在，即使存在，计算量也很大，所以考虑从[H(x (k ) )] -1的近似方阵出发，每次迭代进行修正（下述方法）。
3. DFP方法
考虑对B k = [H(x (k ) )] -1附加条件 (1) B k 应正定
(2) 从B k 到B k +1应简单：B k +1= B k + ΔB k
(3) B k 满足拟Newdon 条件：B k +1y k = s k ，其中y k = g k +1 – g k ，s k = x (k +1) – x (k ) 从而(ΔB k ) yk = s k –B k y k ，
设ΔB k = s k v k T –B k y k w k T ，(v k ，w k 待定) 解之得∆B k =
s k s k
T
T
s k y k
-
B k y k y k B k y k B k y k
T
T
(4.3-20)
(4.3-20)称为DFP 方法 注：(1) 通常取B 0 = I
(2) DFP方法很有效，但由于舍入误差的影响，可能破坏B k 的正定性，使计算失效。可采用重置措施：即当函数值不下降时取B k = I ，继续迭代，并且当迭代n + 1次后，令x(0) = x(n+1)，B n = I ，重新迭代
例2 用DFP 方法求解min F (x 1，x 2) ：F (x 1, x 2) =
⎛-2⎫= 4⎪⎪, ⎝⎭
⎛3
F (x 1, x 2) =(x 1, x 2) 2
1 - ⎝2
⎛3x 1-x 2-2⎫
⎪, ⎪
⎝x 2-x 1⎭
32
x 1+
2
12
x 2-x 1x 2-2x 1
2
-
取x
(0)
1⎫⎪x 1⎫2⎪-(2, 0) ⎛ x ⎪⎪ 1⎪
⎝2⎭⎪
2⎭
-1⎫⎪ ⎪1⎭
解：g (x ) =∇F (x ) =
⎛3
H (x ) = -1
⎝
4. BFGS方法
B k +1=B k +
1s k y k
T
[(1+
y k B k y k s k y k
T
T
) s k s k
T
-B k y k s k
T
-s k y k B k ] (4.3-21)
T