数值模拟导论 -第十讲
改进的牛顿法
雅克比 ·怀特
感谢 Deepak Ramaswamy, Jaime Peraire,
MichalRewienski, and Karen Veroy
概要
阻尼牛顿定律
—若雅可比矩阵是非奇异矩阵，则全局收敛
—奇异雅可比矩阵收敛非常困难
介绍连续定律
—源 /载荷步问题
更通用的连续定律
牛顿算法求解 F(x)=0
多维牛顿法
牛顿算法
SMA-HPC ?2003 MIT
0
0xk= =初始给定值，
重复 {
( ) ( )
()( ) ()
()
11
11
,
lim
1
kk
F
kk k k k
F
kk k
Fx J x
Jx x x Fx x
xx x
kk
+ +
++
?=?
=+ ?
=+
计算
解方程 求得
}
直到 ( )
11kk
xfx
++
? 足够小
极限牛顿法
阻尼牛顿定律
SMA-HPC ?2003 MIT
一般阻尼定律
( ) ( )
11
11
kk k k
F
kkkk
J xx Fx x
xx xα
+ +
+
?=? ?
=+?
＋
解方程 求解
主要思想：线性搜索
()
()()()
2
1
2
2
111
2
kkk
T
kkk kkk kkk
Fx x
Fx x Fx x Fx x
αα
α
+
+++
+?
+? ≡ +? +?
找出 使得 取极小值
该法在牛顿收敛方向执行一维搜索
极限牛顿法
阻尼牛顿收敛定律
SMA-HPC ?2003 MIT
()
() ()
( ]
() ()()
1
11
a) ( )
) ( Lipschitz Cont)
0,1
1
k
F
FF
k
kkk k
Jx
bJxJy lxy
Fx Fx x Fx
β
α
αγ γ
?
++
≤
?≤?
∈
=+?< <
如果
反之不成立
导数为
那么
存在一些列 使得
其中
每进行一步迭代则减小了 F——全局收敛性
极限牛顿法
阻尼牛顿法
SMA-HPC ?2003 MIT
实例
1
0
10
10
d
t
rr
V
V
ds
IV
IIe
?=
??
? ?=
??
??
节点方程：
()
( )
()
2
0
2 16
0.025
2
1
10 1 0
10
v
v
fv e
?
?
?
??
=+ ?=
??
??
SMA-HPC ?2003 MIT
疑问解答续
方阵
极限牛顿法
阻尼牛顿法
实例继续
极限牛顿法
嵌套迭代
SMA-HPC ?2003 MIT
＝初始值，
0
x
0k =
重复 {
( ) ( )
() ()
()
11
1
11
,
1
kk
F
kk k k
F
kkk
kkkk
Fx J x
Jx x Fx x
Fx x
xx x
kk
αα
α
++
+
++
?=? ?
+?
=+?
=+
计算
解方程 求得
找出 使得 取极小值
}
( )
11
,
kk
xFx
++
?直到 足够小为止
如何求阻尼系数？
极限牛顿法
阻尼牛顿定律
SMA-HPC ?2003 MIT
定理证明
通过定义牛顿迭代
( ) ( )
1
1kkk k k
F
xx JxFxα
?
+
=?
牛顿方向
多维均值迭代
() () ()( )
2
2
F
l
F xFyJyxy xy?? ?≤?
综合以上
( ) () () () () () ()
2
11
1
2
kkkkkk kkk
FF F
l
Fx Fx J x J x Fx J x Fxαα
??
+
??
?? ≤
??
??
SMA-HPC ?2003 MIT
极限牛顿法
阻尼牛顿定律
定理进一步证明
由上述证明
( ) () () () () () ()
2
11
1
2
kkkkkk kkk
FF F
l
Fx Fx J x J x Fx J x Fxαα
??
+
??
?? ≤
??
??
化简上式，将 移到范数符号外得
()
2
k
α
()( )() () () ()
2
21
1
1
2
kkkkkkk
F
l
Fx Fx J x Fxααα
?
+
?? ≤
利用雅可比矩阵的极限并分解范数得
()()()() ()
2
2
2
1
1
2
kkkkk
l
Fx Fx Fx
β
αα
+
??
≤? +
??
??
得出关于阻尼系数的二次方程
牛顿极限法
阻尼定律
SMA-HPC ?2003 MIT
定理进一步证明II
由前面的证明简化二次方程式
() () ()
2
2
2
1
1
2
kkk k
l
Fx Fx
β
αα
+
? ?
≤? +
? ?
? ?
分两种情况讨论：
() ()
() ()
()
()
() ()
()
2
k
2
2
kk
2
2
2
2
kk
2
1
1) α 1
22
1
1 αα
22
11
2)
22
1
1 αα 1
2
2
k
k
kk
k
k
k
l
Fx
l
Fx
l
Fx
lFx
l
Fx
lFx
β
β
β
α
β
β
β
<=
??
??+ <
??
??
≥=
??
??+ <?
??
??
取 标准牛顿法
取
SMA-HPC ?2003 MIT
牛顿极限法
阻尼定律
定理进一步证明III
综合前面的证明
1
() ()
kkk
Fx Fxγ
+
≤
证明不充分， γ 大小由 κ 决定
上述结果意味着：
10
() ()
k
F xFx
+
≤
不是收敛定理
因为当 时
2
1
()
22
k
l
Fx
β
>
0
22
11
11
2()2()
kk
lFx lFx
γ
ββ
? ≤? ≤
注意证明技巧
首先 ——显示收敛性不是递增的
其次 ——利用非递增性证明收敛性
极限牛顿法
阻尼定律
SMA-HPC ?2003 MIT
嵌套迭代
＝初始值，
0
x
0k =
重复 {
( ) ( )
() ()
()
11
1
11
,
1
kk
F
kk k k
F
kkk
kkkk
Fx J x
Jx x Fx x
Fx x
xx x
kk
αα
α
++
+
++
?=? ?
+?
=+?
=+
计算
解方程 求得
找出 使得 取极小值
}
多种方法求解
k
α
极限牛顿法
阻尼牛顿法
SMA-HPC ?2003 MIT
奇异雅可比矩阵问题
阻尼牛顿法 “推动 ”迭代趋向局部极小值
找出雅可比矩阵的奇异点
连续定律
基本概念
SMA-HPC ?2003 MIT
加载源或载荷步
在给出恰当初始值的情况下牛顿法收敛
—产生一系列问题
—确保前一问题为后一问题提供初始值
导热棒实例
. 初始无热源， T＝ 0 较接近初始值
. 缓慢增热， T＝ 0 较接近初始值
SMA-HPC ?2003 MIT
连续定律
基本概念
常用设置
求解 其中()( )
,0Fxλλ=
易于求解 开始时连续()
0,0 0Fx =
终止时连续
( )( )
1,1 ( )F xFx=
充分光滑 难以确保！
()
x λ
SMA-HPC ?2003 MIT
连续定律
基本概念
模板算法
()( ) ( ) ( )
() ()
()
()()
0
0 , 0 0, 0
0.01,
1 {
,0
,
=+ , 2
1
=+
2
}
Fx x x
xx
Fx
xx
λ
δλ λ δλ
λ
λλ
λλ
λλ
λ λ δλ δλ δλ
δλ δλ λ λ δλ
==
==
<
=
=
=
=
前一个
前一个
前一个
前一个
求解
当
试用牛顿法求解
若牛顿收敛 ＝
否则 ，
SMA-HPC ?2003 MIT
连续定律
基本概念
载荷源 /载荷步实例
() () ()
() ()
1
,0
,
1
s
fv i v v V
R
ivfv
vvR
λλ λ
λ
λ
=+?=
??
=+←
? ?
二极管
二极管
非丛属
()
( )
()
,0
,
,0
x
yl
fxy
Fx
fxy f
λ
λ
=?
?
=
?
+ =
?
?
G
连续定律
雅克比迭代定律
定律描述步
问题易于求解且雅克比矩阵非奇异。
( )()( )( ) ( ) ( )
,1Fx x xλ λλλ λλ=+?
观察
() ( )
0 0 ,0 0 0
((0),0)
Fx x
Fx
I
x
λ ===
?
=
?
()( ) ( )( )
()()
1 1 ,1 1
1
((0),0)
Fx Fx
Fx
Fx
xx
λ ==
?
?
=
??
重新回到初始的问题和初始雅克比矩 阵
SMA-HPC ?2003 MIT
连续定律
雅克比迭代定律
基本算法
( )( ) ( ) ( )
() ()
()
()()
0
0 ,0 0, 0
0.01,
1 {
?
,0
, = + , 2
1
=+
2
}
Fx x x
xx
Fx
xx
λ
δλ λ δλ
λ
λλ
λλ
λ λ λλδλδλ δλ
δλ δλ λ λ δλ
==
==
<
=+
=
=
=
前一个
前一个
前一个
前一个
求解
当
试用牛顿法求解
若牛顿收敛 ＝
否则 ，
连续定律
雅克比迭代定律
为每一载荷步估计初始载荷值
SMA-HPC ?2003 MIT
连续定律
雅克比迭代定律
更新改进迭代
( )()( )( )
()
()()
()
()
()()
()
0
,,
,
,
,,
Fx Fx
Fx
xx
x
Fx
x
Fx Fx
xx
x
λδλλδλ λλ
λλ
λδλ λ
λλ
δλ
λλ λλ
λδλ λ
++≈ +
+? +
?
?
??
??
?+?=?
??
??
最好为下一步牛顿法
由上一步牛顿法得出的
估计初始值
x
δλ
SMA-HPC ?2003 MIT
连续定律
雅克比迭代定律
更新改进迭代续
如果
( )
( )
( )
( )
()( )
,1Fx Fx xλ λλ λ λλ+?
＝
那么
()
() ()
,Fx
Fx x
λ
λ
λ
+
?
易于计算
＝
连续定律
雅克比迭代定律
更新改进迭代续II
()()
()( ) ()( )
1
0
,,Fx Fx
xx
xx
λλ λλ
λ δλ λ δλ
??
+=
??
??
??
－
图形表示：
SMA-HPC ?2003 MIT
连续定律
雅克比迭代定律
迭代仍存在问题
连续定律
雅克比迭代定律
弧长步？
需求解λ
()()
2
2
2
2
(, ) 0
0
Fx
xx arc
λ
λλ λ
=
? +? ? =
前一个 前一个
SMA-HPC ?2003 MIT
连续定律
雅克比迭代定律
弧长步牛顿法
( )
()
()
( )
()
()
()()
1
1
22
2
2
,
,
2
2,
,
kk
kk
kk
kk
T
k
k
kk
kk
Fx
Fx
xx
x
xx
Fx
xx arc
λ
λ
λ
λλ
λλ
λ
λ
λλ λ
+
+
?
? ?
?
?
? ?
??
?
=
?
?
? ?
?
?
?
? ?
?
?
?
?
?
? ?
?
? ?
?
? ?
??? ?
? ?
前一个
前一个
前一个 前一个
SMA-HPC ?2003 MIT
连续定律
雅克比迭代定律
弧长转折点
( )
()
()
( )
()
,
,
2
2,
kk
kk
T
k
k
Fx
Fx
x
xx
λ
λ
λ
λλ
λ
?
? ?
?
?
?
?
??
?
?
?
?
? ?
?
前一个
前一个
矩阵左上角模块为奇数
小结
SMA-HPC ?2003 MIT
阻尼牛顿定律
—若雅可比矩阵非奇异则全局收敛
—奇异雅可比矩阵收敛困难
介绍连续定律
—载荷源 /载荷步问题
—更普遍的连续方案
