数值模拟导论-第六讲 Krylov子空间矩阵求解方法 雅克比怀特 感谢 Deepak ramaswamy, Michal Rewienski. Karen Veroy and Jacob White
数值模拟导论 -第六讲 Krylov子空间矩阵求解方法 雅克比·怀特 感谢Deepak Ramaswamy, Michal Rewienski,Karen Veroy and Jacob White
概述 常规的子空间极小化算法 回顾学过的正交化和投射定理 GCR算法 krylov-子空间 一对称矩阵的简化 收敛条件 回顾特征值和特征向量 范数和谱半径 谱映射定理
常规的子空间极小化算法 ——回顾学过的正交化和投射定理 GCR算法 －krylov-子空间 －对称矩阵的简化 －收敛条件 回顾特征值和特征向量 －范数和谱半径 －谱映射定理 概述
任意的子空间方法 任意的子空间方法 近似的解MX=b 选择一个k维的子空间 可以近似为向量{的和 a 1 SMA-HPC C2003 MIT
任意的子空间方法 SMA-HPC ©2003 MIT 可以近似为向量 的和 任意的子空间方法 近似的解Mx ＝ b 选择一个 k维的子空间 1 0 k k i i i x α w − = ⇒ = ∑ G { } 0 1 , , − ⋅⋅⋅ w wk G G { } 0 1 , , − ⋅⋅⋅ w wk G G { } 0 1 , , − ⋅⋅⋅ w wk G G { } 0 1 , , − ⋅⋅⋅ w wk G G { } 0 1 , , − ⋅⋅⋅ w wk G G {w w 0 1 , , ⋅⋅⋅ k − } G G
任意子空间方法 最小残向量 残向量定义为r=b-M 如果=a两→r=b-M2=b-2aM i=0 残向量最小化的思路为:取αs,最小化式: t2上 SMA-HPC C2003 MIT
·残向量定义为 如果 残向量最小化的思路为：取 ，最小化式： 1 0 k k i i i x w α − = = ⇒ ∑ G k k r b Mx = − 1 0 k i i i b Mw α − = = −∑ G 任意子空间方法 SMA-HPC ©2003 MIT 最小残向量 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G k k r = b − Mx i α s ′ i α s ′ ( )( ) 1 1 2 2 0 0 T k k T k kk ii ii i i r r r b Mw b Mw α α − − = = ⎛ ⎞⎛ ⎞ ≡ =− − ⎜ ⎟⎜ ⎟ ⎝ ⎠⎝ ⎠ ∑ ∑ G G k k r b Mx = −
任意子空间方法 最小残向量 算法 如果(M)(M)=0或者M)正交于(M,那么我 们将很容易计算出=-24的最小值。 如果(4)()=0或者(5)于()非正交 那么要建立一组正交的向量{…}使向量空间 向量空间{并且()()=0,≠j SMA-HPC C2003 MIT
如果 或者 正交于 ，那么我 们将很容易计算出 的最小值。 如果 或者 于 非正交 那么要建立一组正交的向量 使向量 空间 ＝向量空间 并且 ， ( ) ( ) 0 Mw Mw i j = G G ( Mwi) G ( Mwj ) G 任意子空间方法 SMA-HPC ©2003 MIT 最小残向量 算法 2 2 2 2 k i i r b Mw = − ∑ α G { p p 0 1 , , ⋅⋅⋅ k − } G G { } 0 1 , , w wk − ⋅⋅⋅ G G ( ) ( ) 0 T Mp Mp i j = G G i ≠ j ( Mwi) G ( Mwj ) G ( ) ( ) 0 T Mp Mp i j = G G
任意子空间方法 最小残向量 运算步骤 给定M,b并且一组搜索方向{而…而 1)通过将Ms正交化生成p for j=0 to k-1 P=w 如)(M 2)解x计算r的最小值 ()=( ()(M)=(Mp)( SMA-HPC C2003 MIT
给定M，b并且一组搜索方向 1）通过将 正交化生成 for j＝0 to k－1 2）解 计算r 的最小值 { } 0 1 , , w wk− ⋅⋅⋅ G G Mw sj ′ j p s G ′ 任意子空间方法 SMA-HPC ©2003 MIT 最小残向量 运算步骤 ( ) ( ) ( )( ) 1 0 T k j i j j T i i i i Mw Mp p w p Mp Mp − = = −∑ ( ) ( ) ( )( ) ( ) ( ) ( )( ) 0 1 1 0 0 T T i k k i i k T T i i i i ii ii r Mp r Mp x p p Mp Mp Mp Mp − − = = = = ∑ ∑ k x
任意子空间方法 最小残向量 图示计算步骤 1)正交化M,s 2)解计算r的最小值 MpI 自000 SMA-HPC C2003 MIT
1）正交化 2）解计算r 的最小值 任意子空间方法 SMA-HPC ©2003 MIT 最小残向量 图示计算步骤 Mw sj ′
任意子空间方法 最小化算法 ro=b-Axo for j=0 to k-1 for i=0 to j-1 n←n()()2正交搜索方向 P P 标准化向量 柳p)(M )(4)n更新结果 =r+()()4更新残向量 SMA-HPC C2003 MIT
for j＝0 to k－1 for i＝0 to j-1 正交搜索方向 标准化向量 更新结果 更新残向量 0 0 r b Ax = − 任意子空间方法 SMA-HPC ©2003 MIT 最小化算法 j j p w= ( ) ( ) T j j j ii p ← − p Mp Mp p ( )( ) 1 j j T j j p p Mp Mp ← ( ) ( ) 1 T j jj j j x x r Mp p + = + ( ) ( ) 1 T j jj j j r r r Mp Mp + = +
任意子空间方法 子空间的选择 标准 选择而,而的标准 对所有在空间n…,中的 任意3,b-Mb->aM的值都很小 当k<N时b≈在向量空间{ 种选择,单位向量,x∈{2…向量空间 如果k=N进行QR分解 如果k<N情况会很糟糕 SMA-HPC C2003 MIT
选择 的标准 对所有在空间 中的 任意 ， 的值都很小 当 时 在向量空间 一种选择，单位向量， 向量空间 如果k＝N进行QR分解 如果k<N情况会很糟糕 0 1 {,, } w wk− ⋅⋅⋅ G G i α′s 1 0 k k i i i b Mx b Mw α − = = − −∑ G 任意子空间方法 SMA-HPC ©2003 MIT 子空间的选择 标准 k N ≺≺ 1 A b− ≈ { 1, } k k x ee ∈ ⋅⋅⋅ G G 0 1 , , w wk− ⋅⋅⋅ G G 0 1 {,, } w wk− ⋅⋅⋅ G G
任意子空间方法 子空间的选择 传统方法 求()=xM-xb的最小值,其中假设M=M(对称 矩阵)并且xM>0 Vf(x)=Mx-b=x=Mb推导出x最小化f 取向量空间间可=/()f(x 这便是f的最快下降方向,但f并不是残余值。 这种方法不能用于非对成矩阵,和不满足xMx>0 的情况 SMA-HPC C2003 MIT
求 的最小值，其中假设 （对称 矩阵）并且 推导出 x最小化f. 取向量空间 这便是 f的最快下降方向，但 f并不是残余值。 这种方法不能用于非对成矩阵，和不满足 的情况 ( ) 1 2 T T f x x Mx x b = − 任意子空间方法 SMA-HPC ©2003 MIT 子空间的选择 传统方法 T M = M 0 T x Mx > ( ) 1 x f x Mx b x M b− ∇ = −⇒ = { } { ( ) ( ) } 0 1 0 1 ,, ,, k w w fx fx kx x − − ⋅⋅⋅ = ∇ ⋅⋅⋅ ∇ G G 0 T x Mx >