数值模拟导论 -第九讲 多维牛顿法 雅克比 ·怀特 感谢 Deepak Ramaswamy, Jaime Peraire, MichalRewienski, and Karen Veroy z 简单回顾一维牛顿法 ——收敛性检验 z 多维牛顿法 ——基本算法 ——雅可比矩阵的描述 ——方程式 z 多维收敛性 ——证明局部收敛性 ——收敛性的改善 摘要 问题： 找 出使得 一维问题回顾 牛顿法的思想 SMA-HPC ?2003 MIT ( ) * 0fx= * x 利用泰勒展开式： () () () ( ) () 2 2 ** 2 fx f fx fx x x x x xx ? ? ? =+ ?+ ? ? ?  若接近于精确解 x () () f xx fx x ? ? ?=? ? 一维回顾 牛顿算法 SMA-HPC ?2003 MIT 0 0xk= =初始给定值， 重复 { ()() 1 1 kk k f xx fx x kk + ? ?=? ? =+ } 直到？ () 11kk k xx fx ++ ?< <极限值？ 极限值？ 一维回顾 牛顿算法 SMA-HPC ?2003 MIT 牛顿算法图 一维回顾 牛顿算法 SMA-HPC ?2003 MIT 收敛性检验 需要一个 “”来检测是否产生错误的收敛 x? 一维回顾 牛顿算法 SMA-HPC ?2003 MIT 收敛性检验 同样需要一个 “”来检测是否产生错误的收敛 ( ) fx 一维回顾 牛顿算法 SMA-HPC ?2003 MIT 局部收敛 收敛性依赖于给定恰当的初始值 多维牛顿法 实例问题 SMA-HPC ?2003 MIT 杆件和节点问题 () () () () 22 0 0 0 0 0 c x y lxy ll F EA l l l xx fF ll ll yy fF ll ll ε ε ε =+ ? = =? == ? == ? () () () 0 0 0 0 0 0 x y x y xL yL L L fF Fx fF x llF l y llF l ε ε + = ?? = ?? + = ?? ?+ = ?+ = G 或 多维牛顿法 实例问题 SMA-HPC ?2003 MIT 非线性电阻器问题 节点分析 () ( ) () ( ) 12 112 32 312 0 0 0 0 ii gv gv v ii gv gv v + = ?+?= ?= ???= 在 节 点 1处 ： 在 节 点 2处 ： 在 两 个 非 线 性 方 程 式 中 有 两 个 未 知 数 多维牛顿法 一般设定 SMA-HPC ?2003 MIT 利用泰勒级数展开式 ( ) ( ) ( ) ( ) () () () ** * .. F F F xFxJxxxHOT Jxxx Fx =+ ?+ ?≈?  雅可比矩阵 若近似于精确解 则 问题：求解出使得 ( ) * 0Fx = : NNN xRFR R ? ∈→且 多维牛顿法 节点分析 SMA-HPC ?2003 MIT 杆件和节点问题 222 :xRFR R ? ∈→且 () () 0 0 0 0 x y L L x llF l y ll F l ε ε ? += ? += () ?? ?? F Jx ? ? = ? ? ? ? G 多维牛顿法 节点分析 SMA-HPC ?2003 MIT 非线性电阻器问题 222 :xRFR R ? ∈→且 () () ( ) () () ( ) () 12 1112 32 1312 0 0 0 0 ?? ?? F ii Fv gv gv v ii Fv gv gv v Jx + = ?=+?= ?= ?=??= ?? = ?? ?? G G G 在节点1处： 在节点2处： 多维牛顿法 雅可比矩阵 SMA-HPC ?2003 MIT ( ) ( ) ( ) () () () () () 11 N 11 F N F N JxxFx xFx FxFx xxx Jxx x Fx Fx xx ?≈ +? ? ? ??? ?? ??? ? ? ?? ? ? ?? ?= ? ? ?? ? ? ? ?? ?? ? ? ?? ? ? " #%# # " 多维牛顿法 雅可比矩阵 SMA-HPC ?2003 MIT 奇数实例 () () () () () () 11 N 11 0 F N F N Jx FxFx xxx Jxx x Fx Fx xx ? ??? ?? ??? ?? ?? ?? ?? ? == ?? ?? ?? ? ?? ?? ?? ?? ? ? " #%# # " 假设 为奇数？ 其含义是什么？ 多维牛顿法 牛顿算法 SMA-HPC ?2003 MIT 0k = ＝初始值， 0 x 重复 { ( ) ( ) ()( ) () 11 , 1 kk F kk k k k F Fx J x Jx x x Fx x kk + + ?=? =+ 计算 解方程 求得 ( ) 11 , kk k xxFx ++ ?直到 足够小为止} 多维牛顿法 计算雅可比矩阵和函数 SMA-HPC ?2003 MIT 考 虑节点之间的一个非线性电阻的作用 12 nn和 ( ) bb igv= 节点 上求和 ： 1 n ( ) ( ) 112 ... nnn Fv gv v= ?+ 节点 上求 和： 2 n ( ) ( ) 212 ... nnn Fv gv v=??+ () ( ) () ( ) 12 12 11 11 22 1 ... ... nn nn nn nn gg vv gv v gv v Fv Fv n vv vv ?? = +=+ ?? ??   对节点 求偏微分： 多维牛顿法 计算雅可比矩阵和函数 SMA-HPC ?2003 MIT 一个电阻器上受到的电压 1 2 n n () 12 12 nn nn gv v v ?? ? ## # ## ## # # () () () () 12 12 12 F nn nn nn Jv gv v v gv v gv v vv ?? ?? ?? ? ?? ?? ?? ?? ?? ## # ## ## ## # ##  () () () 12 12 nn nn Fv gv v gv v ?? ?? ? ?? ?? ? ?? ?? # # #  1 2 n n 多维牛顿法 进一步计算牛顿算法 ＝初始值 ， 0 x 0k = 重复 { () ( ) ()( ) () 11 , 1 kk F F F kk k k k F Fx J x JF FJ J xx x Fx x kk + + ?=? =+ 将和置零 对于每一单元，计算单元电流及其导数， 求电流的和 ，求导数的和 解方程 求得 ( ) 11 , kk k xxFx ++ ?直到 足够小为止 } 多维牛顿法 实例：直通棒中的热流 SMA-HPC ?2003 MIT 什么是雅可比行矩阵？ 多维牛顿法 多维收敛定理 定理陈述 主要定理 ( ) () () 1 a) ( ) ) ( Lipschitz Cont) k F FF Jx bJxJy lxy β ? ≤ ?≤? 反之不成立 导数为 给定的足够准确的初始值,牛顿法收敛 多维牛顿法 多维收敛定理 SMA-HPC ?2003 MIT 重要辅助定理 ( ) ( ) () () ()( ) 2 ( Lipschitz Cont) 2 FF F JxJy lxy l Fx Fy Jyxy xy ?≤? ?? ?≤? 如 果导数 为 那 么 这里没有多维的均值定理。 多维牛顿法 多维收敛方法 SMA-HPC ?2003 MIT 定理证明 通过牛顿迭代的定义和假定雅可比矩阵逆的极限值得： ( ) ( ) ( ) 11kk k k k F x x J x Fx Fxβ +? ?= ≤ 再次利用牛顿迭代的定义： () ( ) ( ) 111 0 kk k k kk F x x Fx Fx J x xβ +?? ?≤ ? ? ?  最后利用辅助定理： 2 11 2 kk kk l xx xx β +? ?≤ ? 多维牛顿法 多维收敛方法 等式重组 111 2 k k kk kk l x x xx xx β + ?? ?? ?≤ ? ? ?? ?? () 10 110 0 1 2 kkk kk k l xx xx xxx β γ γ ∞ ++ = ?? ?≤< ?? ?? ?≤? ?+ ∑ 若 则收敛 定理进一步证明 SMA-HPC ?2003 MIT 不收敛的情况 一维图 必须设法限定 X的变化范围 极限牛顿法 牛顿算法 用牛顿算法求解 F（ x）＝ 0 ＝初始值， 0 x 0k = 重复 { ( ) ( ) () () () 11 11 , lim 1 kk F kk k k F kk k Fx J x Jx x Fx x xx x kk + + ++ ?=? ? =+ ? =+ 计算 解方程 求得 } ( ) 11 , kk xFx ++ ?直到 足够小为止 SMA-HPC ?2003 MIT 极限牛顿法 极限算法 z迭代方向正确 () 11 1 1 lim( ) kk k ii i k i xx x x γ γ ++ + + ?=? ?< ? 若 否则用 表示 z迭代方向错误 ( ) 11 1 lim min 1, kk k xx x α γ α ++ + ?=? ?? ?? = ?? ? ?? 由此推断，牛顿迭代不能保证全局收敛 SMA-HPC ?2003 MIT 极限牛顿法 阻尼牛顿定律 一般阻尼定律 ( ) ( ) 11 11 kk k k F kkkk Jx x Fx x xx xα + + + ?=? ? =+? ＋ 解方程 求解 主要思想：线性搜索 () ()()() 2 1 2 2 111 2 kkk T kkk kkk kkk Fx x F xxFxxFxx αα α + +++ +? +? ≡ +? +? 找出 使得 取极小值 该法在牛顿收敛方向执行一维搜索 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——全局收敛性 极限牛顿法 阻尼牛顿收敛定律 嵌套迭代 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 极限牛顿法 阻尼牛顿法 奇异雅可比矩阵问题 阻尼牛顿法 “推动 ”迭代趋向局部极小值 找出雅可比矩阵的奇异点 总结 结： 简要回顾一维牛顿法 -——收敛性检验 多维牛顿法 —基本算法 —雅可比矩阵的描述 雅可比矩阵的构建